Tìm kiếm
Đang tải khung tìm kiếm
Kết quả 1 đến 1 của 1

    TIẾN SĨ Song song hóa các thuật toán trên mạng đồ thị

    D
    dream dream bây giờ đang trực tuyến (18495 tài liệu)
    .:: Cộng Tác Viên ::.
  1. Gửi tài liệu
  2. Bình luận
  3. Chia sẻ
  4. Thông tin
  5. Công cụ
  6. Song song hóa các thuật toán trên mạng đồ thị

    1

    MỞ ĐẦU
    1. Tính cấp thiết của việc nghiên cứu
    Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu và có nhiều ứng
    dụng hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất vào những
    năm đầu của thế kỷ 18 bởi nhà toán học lỗi lạc người Thụy Sỹ Leonhard Euler.
    Chính ông là người đã sử dụng đồ thị để giải bài toán nổi tiếng bảy cây cầu ở thành
    phố Konigsberg [35].
    Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh hoặc cung nối các
    đỉnh đó [35]. Đây là công cụ hữu hiệu để mô hình hoá và giải quyết các bài toán
    trong nhiều lĩnh vực khoa học, kỹ thuật, kinh tế, xã hội, .
    Mạng là một dạng đồ thị định hướng có trọng số dùng để mô tả các mạng
    lưới giao thông vận tải, liên lạc, truyền tin, . Trọng số các cung trong mạng được
    hiểu là khả năng thông qua (thông lượng) của cung [56].
    Các bài toán chính trên đồ thị và mạng là các bài toán tìm đường đi, bài toán
    luồng cực đại (maxflow problem) và có rất nhiều ứng dụng trong thực tế. Việc tìm
    các phương pháp giải các bài toán trên để nâng cao hiệu năng tính toán và giảm thời
    gian tính toán là một vấn đề được nhiều người quan tâm.
    Hơn nữa, để đáp ứng được nhu cầu thực tế trên các mạng lưới giao thông thì
    đồ thị và mạng đồ thị phải được cải tiến, mở rộng cho phù hợp (ví dụ như mạng đồ
    thị truyền thống chỉ xét đến trọng số của các cạnh, các đỉnh một cách độc lập, trong
    đó độ dài đường đi chỉ đơn thuần là tổng trọng số các cạnh và các đỉnh trên đường
    đi đó. Tuy nhiên, trong nhiều bài toán thực tế, trọng số tại một đỉnh không giống
    nhau với mọi đường đi qua đỉnh đó mà còn phụ thuộc vào cạnh đi đến và cạnh đi
    khỏi đỉnh đó). Vì vậy, việc xây dựng các mô hình về đồ thị và mạng đồ thị mở rộng
    là rất cần thiết để đáp ứng được nhu cầu thực tế hiện nay.
    Hiện nay, ở trong nước cũng như thế giới việc xử lý song song đang được
    ứng dụng ở nhiều trung tâm tính toán lớn cũng như ở các trường đại học. Nhiều nhà
    khoa học đã nghiên cứu lý thuyết về xử lý song song, các mô hình, các phương
    pháp để xử lý song song và đưa ra một số thuật toán song song điển hình. Mặc dù 2

    tốc độ xử lý của các bộ xử lý tăng nhiều trong những năm qua, nhưng do giới hạn
    về vật lý nên khả năng tính toán của chúng không thể tăng mãi được. Điều này, dẫn
    tới là muốn tăng được khả năng tính toán của các hệ thống tính toán thì đích cuối
    cùng là phải khai thác được khả năng xử lý song song của chúng.
    Khi xây dựng thuật toán tuần tự cho các bài toán trên mạng đồ thị, nếu dữ
    liệu đầu vào là lớn thì thuật toán tuần tự xử lý rất lâu hoặc có những trường hợp
    thuật toán tuần tự không thực hiện được. Điều này, đòi hỏi phải phân tích dữ liệu,
    tìm sự phụ thuộc dữ liệu giữa các bước của thuật toán, phân tích câu lệnh, tìm hiểu
    các mô hình xử lý song song, hệ thống máy tính và ngôn ngữ lập trình để song song
    hóa các thuật toán tuần tự tương ứng.
    Vì thế, việc nghiên cứu các thuật toán tìm đường đi và các thuật toán tìm
    luồng cực đại trên mạng đồ thị truyền thống và đồ thị mở rộng là rất cần thiết. Các
    ứng dụng thực tế cho các thuật toán này đòi hỏi phải xử lý với khối dữ liệu lớn, thời
    gian giảm đi so với thuật toán tuần tự. Đặc biệt, với các mô hình thực tế thì dữ liệu
    càng ngày càng lớn. Do đó, xây dựng các thuật toán này theo hướng song song hóa
    từ các thuật toán tuần tự là đòi hỏi hết sức cần thiết. Xuất phát từ đó chúng tôi chọn
    vấn đề “Song song hóa các thuật toán trên mạng đồ thị” làm đề tài nghiên cứu
    của luận án với hy vọng rằng những nghiên cứu của luận án không chỉ đóng góp về
    mặt lý luận và thực tiễn của các thuật toán song song đã được đề xuất mà còn góp
    phần làm nền tảng để tiếp tục xây dựng các thuật toán song song khác trên mạng đồ
    thị.
    2. Tổng quan tình hình nghiên cứu
    Trên thế giới, vấn đề xử lý song song cũng được quan tâm từ rất lâu. John
    Weley và Sons [40] đã giới thiệu cách xử lý song song và đánh giá độ phức tạp trong
    tính toán song song. Michael J. Quinn [41] đã nghiên cứu về lý thuyết tính toán
    song song và thực nghiệm, ông đã xây dựng các mô hình tính toán song song và đưa
    ra các thuật toán song song cơ bản. Tiếp theo đó, Seyed H. Roosta [37] đã xây dựng
    các mô hình cấu trúc máy tính. Từ đó, ông đưa ra kiến trúc để xử lý song song, cách
    thực hiện chương trình song song, cách thiết kế thuật toán song song và xây dựng 3

    các thuật toán song song trên đồ thị như: thuật toán tô màu đồ thị, bài toán người du
    lịch, thuật toán tìm chu trình và thuật toán tìm cây khung nhỏ nhất trên đồ thị.
    Năm 2002, Behrooz Parhami [39] đã nghiên cứu rất kỹ tại sao phải xử lý
    song song và đưa ra mô hình xử lý song song: PRAM, bộ nhớ phân tán, kiến trúc
    song song SIMD, MIMD Đồng thời khẳng định tính khả thi của việc sử lý song
    song. Ông cũng đã nêu ra động cơ để thúc đẩy việc xử lý song song là rất cần thiết.
    Năm 2000, các tác giả M. Sasikumar, Dinesh Shikhare, P. Ravi Prakash [42] đã giới
    thiệu về xử lý song song, phân tích các kiến trúc xử lý song song và xây dựng các
    hệ thống tính toán song song trên đa bộ xử lý. Từ những cơ sở lý thuyết trên, luận
    án sẽ xác định được những vấn đề liên quan đến xử lý song song: cách xây dựng
    thuật toán song song, song song hóa thuật toán đã có, chọn ngôn ngữ lập trình song
    song, mô hình xử lý song song, hệ thống thực nghiệm thuật toán và đánh giá độ
    phức tạp về mặt thời gian.
    Các tác giả trong các công trình [45], [47], [48], [49], [50], [51], [52], [58],
    [59], [60], [61], [62] đã xây dựng các thuật toán song song trên đồ thị và mạng đồ
    thị. Đặc biệt, các thuật toán tìm đường đi ngắn nhất, tìm cây phủ nhỏ nhất và tìm
    luồng cực đại. Đây là các thuật toán cơ bản trên đồ thị. Các tác giả đã phân tích
    thuật toán tuần tự, chọn hệ thống máy tính để thực hiện song song, xây dựng thuật
    toán song song, chứng minh tính đúng đắn và chỉ ra độ phức tạp của thuật toán song
    song. Các tác giả hầu hết đều phân tích và so sánh mức độ tăng tốc (speedup) của
    thuật toán song song so với thuật toán tuần tự thông qua biểu đồ hoặc bảng biểu.
    Bài toán tìm luồng cực đại trên mạng đồ thị là một trong số những bài toán
    tối ưu trên đồ thị được ứng dụng rộng rãi trong thực tế cũng như những ứng dụng
    thú vị trong lý thuyết tổ hợp. Bài toán được đề xuất và giải quyết bởi hai nhà toán
    học Mỹ Ford and Fulkerson [53], các tác giả đã dùng phương pháp đường đi tăng
    luồng để tìm luồng cực đại. Bài toán này sau đó được các nhà khoa học quan tâm
    nghiên cứu. Edmonds và Karp [54] đưa ra phương pháp khác. Tuy nhiên, A.
    Goldberg và R.E. Tarjan [55] đã đề xuất phương pháp đẩy luồng trước . Phương
    pháp này đề xuất cách tiếp cận khác để giải bài toán tìm luồng cực đại. Khái niệm 4

    mới ở đây là luồng trước. Luồng trước là tập hợp các luồng trên cung , trong đó có
    thể chấp nhâ ̣n tồn ta ̣i đỉnh có luồng vào lớn hơn luồng ra . Trong phương pháp này ,
    các tác giả duy trì các luồng trước cực đa ̣i và hiê ̣u chỉnh chúng thành luồng . Mới
    đây nhất, các phương pháp mới tìm luồng cực đại cũng đã được nghiên cứu [2] [3],
    [4], [5], [6], [7], [8].
    Các thuật toán song song tìm luồng cực đại cũng đã được nghiên cứu. Năm
    1988, A. Goldberg và R.E. Tarjan [57] đưa ra ý tưởng để xây dựng thuật toán song
    song. Năm 1992, Anderson R. J. and Jo A. C. S [58] đã xây dựng thuật toán song
    song tìm luồng cực đại bằng phương pháp đẩy luồng trước. Tiếp theo đó, Bader D.
    and Sachdeva V [59] đã phát triển thuật toán song song bằng phương pháp đẩy
    luồng trước theo các hướng khác nhau nhằm làm giảm thời gian tính toán của thuật
    toán cũng như tận dụng được cấu trúc đa bộ xử lý. Năm 2008, Hong B đã công bố
    công trình [60], đây cũng là thuật toán song song cho bài toán tìm luồng cực đại
    bằng phương pháp đẩy luồng trước. Năm 2010, Zhengyu He, Bo Hong đã xây dựng
    thuật toán song song trong môi trường GPU dùng ngôn ngữ CUDA [61]. Từ các
    công trình đã phân tích ở trên, luận án sẽ tối ưu thuật toán song song đẩy luồng
    trước tìm luồng cực đại được kế thừa từ [61], đề xuất thuật toán song song hỗn hợp
    đẩy kéo luồng tìm luồng cực đại sao cho giảm được thời gian tính toán so với các
    thuật toán khác.
    Hơn nữa, trong thực tế cần xây dựng mạng đồ thị mở rộng, từ đó xây dựng
    thuật toán tìm luồng cực đại đồng thời chi phí giới hạn trên mạng giao thông mở
    rộng để giải quyết bài toán phân luồng giao thông. Tuy nhiên, trên thực tế mạng
    lưới giao thông rất phức tạp nên việc thực hiện tuần tự sẽ tốn rất nhiều thời gian với
    dữ liệu đầu vào lớn. Do đó, chúng tôi sẽ đề xuất thuật toán song song tìm đường đi
    ngắn nhất trên đồ thị mở rộng và thuật toán song song tìm luồng cực đại đồng thời
    chi phí giới hạn trên mạng giao thông mở rộng.
    Tóm lại, xuất phát từ nhu cầu thực tế và kế thừa nghiên cứu trước đó. Luận
    án xác định rõ các nội dung cụ thể về lý thuyết như: Kiến trúc xử lý song song, mô
    hình xử lý song song và phân tích sự phụ thuộc dữ liệu. Từ đó, đề xuất thuật toán 5

    song song, tìm môi trường lập trình song song, hệ thống thực nghiệm, lập trình song
    song và cách đánh giá độ phức tạp thời gian tính toán song song. Bên cạnh đó, luận
    án sẽ đề xuất các thuật toán song song mới từ các thuật toán tuần tự tương ứng để
    làm giảm thời gian tính toán khi dữ liệu đầu vào lớn. Đồng thời, luận án tối ưu thuật
    toán song song đẩy luồng trước tìm luồng cực đại dựa vào sự tồn tại của các nghiên
    cứu đã công bố như: vấn đề chia dữ liệu, môi trường thực nghiệm và đưa ra ví dụ
    minh họa. Các thuật toán trong luận án là song song về dữ liệu, phân chia dữ liệu
    cho các bộ xử lý để các bộ xử lý cùng đồng thời thực hiện các công việc được giao.
    Hay nói cách khác, song song dữ liệu là song song mà trong đó tập trung vào phân
    phối dữ liệu qua các bộ xử lý tính toán khác nhau để được xử lý song song.
    3. Mục tiêu của luận án
    - Phân tích đánh giá về mặt lý thuyết và thuật toán để tìm ra các hạn chế của
    thuật toán song song trên mạng đồ thị. Từ đó, cải tiến những hạn chế của thuật toán
    song song đã có.
    - Đề xuất, phân tích các thuật toán tuần tự về mặt câu lệnh và dữ liệu để đề
    xuất các thuật toán song song tương ứng.
    4. Đối tượng và phạm vi nghiên cứu
     Đối tượng nghiên cứu
    - Luận án nghiên cứu lý thuyết xử lý song song, các mô hình tính toán song
    song.
    - Luận án nghiên cứu lý thuyết đồ thị, chủ yếu là bài toán tìm đường đi ngắn
    nhất trên đồ thị mở rộng, các thuật toán tìm luồng cực đại trên trên mạng đồ thị
    truyền thống và mạng đồ thị mở rộng.
     Phạm vi nghiên cứu
    - Đề xuất thuật toán song song tìm đường đi ngắn nhất trên đồ thị mở rộng.
    - Tối ưu thuật toán song song tìm luồng cực đại bằng phương pháp đẩy luồng
    trước từ thuật toán song song đã có.
    - Đề xuất thuật toán song song tìm luồng cực đại bằng phương pháp hỗn hợp
    đẩy kéo luồng. 6

    - Đề xuất thuật toán song song tìm luồng cực đại đồng thời chi phí giới hạn
    trên mạng giao thông mở rộng.
    5. Phương pháp nghiên cứu
    - Tổng hợp, phân tích các kết quả nghiên cứu trước đây từ đó rút ra, tìm ra
    các vấn đề cần phải giải quyết và đút rút các phương pháp giải quyết vấn đề.
    - Tìm các phương pháp mở rộng bài toán, cải tiến, xây dựng các thuật toán
    mới để giải quyết các vấn đề đặt ra.
    - Từ thực nghiệm đến chứng minh bằng phương pháp toán học để chỉ ra tính
    vượt trội của cấu trúc mới, thuật toán mới.
    6. Điểm mới của luận án
    - Đề xuất thuật toán song song tìm đường đi ngắn nhất trên đồ thị mở rộng.
    Chúng tôi đề xuất thuật toán này để ứng dụng cho mạng giao thông phù hợp với
    thực tế. Từ đó, phân tích độ phức tạp thời gian và đưa ra ví dụ minh họa rõ ràng.
    - Tối ưu thuật toán song song tìm luồng cực đại bằng phương pháp đẩy luồng
    trước từ thuật toán song song đã có. Điểm mới ở đây là phân tích dữ liệu, chia dữ
    liệu cụ thể cho các bộ xử lý. Phần thực nghiệm được thực hiện rõ ràng, chương trình
    được xây dựng trên hệ thống cụm máy tính. Các kết quả được bình luận và so sánh
    cụ thể.
    - Đề xuất thuật toán song song tìm luồng cực đại bằng phương pháp hỗn hợp
    đẩy kéo luồng. Chúng tôi kết hợp thuật toán đẩy luồng trước và thuật toán kéo
    luồng sau để xây dựng thuật toán song song. Các định lý liên quan đến thuật toán
    được chứng minh và các ví dụ minh họa được xây dựng cụ thể. Do tính độc lập của
    thuật toán đẩy và kéo luồng nên thời gian thực hiện thuật toán song song giảm so
    với thời gian thực hiện của các thuật toán song song khác.
    - Đề xuất thuật toán song song tìm luồng cực đại đồng thời chi phí giới hạn
    trên mạng giao thông mở rộng. Để giảm thời gian tính toán của thuật toán, chúng tôi
    đã xây dựng thuật toán song song tìm luồng cực đại chi phí giới hạn. Các định lý
    liên quan đến thuật toán được chứng minh. Thuật toán song song làm giảm nhiều
    thời gian so với thuật toán tuần tự. 7

    7. Kết quả nghiên cứu
    - Luận án đã đề xuất được các thuật toán song song mới trên cơ sở các yêu
    cầu thực tế đặt ra, chứng minh tính đúng đắn, phân tích độ phức tạp thời gian của
    thuật toán. Đồng thời luận án cũng song song hóa thuật toán đã có, từ đó chỉ ra các
    ưu điểm so với thuật toán đã có trước.
    - Luận án cũng đã xây dựng được chương trình thực nghiệm trên các hệ
    thống song song khác nhau. Từ đó, đưa ra các số liệu cụ thể để: đánh giá, so sánh
    kết quả đạt được của thuật toán song song so với thuật toán tuần tự và so sánh với
    các thuật toán song song đã có trước đó.
    8. Bố cục của luận án
    Ngoài phần mở đầu, kết luận, tài liệu tham khảo, luận án được trình bày
    thành ba chương cơ bản như sau:
    Chương 1: Xử lý song song.
    Nội dung trong chương này chủ yếu trình bày lý thuyết về xử lý song song:
    kiến trúc song song, các mô hình về xử lý song song, cách xây dựng thuật toán song
    song và cách đánh giá độ phức tạp thời gian của thuật toán song song.
    Chương 2: Các thuật toán tuần tự và song song trên mạng đồ thị truyền
    thống.
    Nội dung thứ nhất trong chương này chủ yếu tối ưu thuật toán song song đẩy
    luồng trước tìm luồng cực đại được kế thừa từ các công trình đã được nghiên cứu.
    Nội dung thứ hai, đề xuất thuật toán tuần tự hỗn hợp đẩy kéo luồng. Từ đó, đề xuất
    thuật toán song song mới cho thuật toán hỗn hợp này.
    Chương 3: Một số thuật toán song song tìm đường đi ngắn nhất và tìm luồng
    cực đại trên mạng đồ thị mở rộng.
    Nội dung trong chương này chủ yếu kế thừa các thuật toán tuần tự để đề xuất
    các thuật toán song song tìm đường đi ngắn nhất trên đồ thị mở rộng và thuật toán
    song song tìm luồng cực đại chi phí giới hạn trên mạng giao thông mở rộng.

    Xem Thêm: Song song hóa các thuật toán trên mạng đồ thị
    Nội dung trên chỉ thể hiện một phần hoặc nhiều phần trích dẫn. Để có thể xem đầy đủ, chi tiết và đúng định dạng tài liệu, bạn vui lòng tải tài liệu. Hy vọng tài liệu Song song hóa các thuật toán trên mạng đồ thị sẽ giúp ích cho bạn.
    #1
  7. Đang tải dữ liệu...

    Chia sẻ link hay nhận ngay tiền thưởng
    Vui lòng Tải xuống để xem tài liệu đầy đủ.

    Gửi bình luận

    ♥ Tải tài liệu

social Thư Viện Tài Liệu

Từ khóa được tìm kiếm

Nobody landed on this page from a search engine, yet!

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
DMCA.com Protection Status