Luận án tiến sĩ: Song song hóa các thuật toán trên mạng đồ thị

Chia sẻ: Tỉ Thành | Ngày: | Loại File: PDF | Số trang:105

Thêm vào BST

Báo xấu

48
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án tiến sĩ: Song song hóa các thuật toán trên mạng đồ thị

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ù 1
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 2
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 phá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 3
mới ở đây là luồ ng trước. Luồng trước là tập hợp các luồng trên cung , trong đó có thể chấ p nhâ ̣n tồ n ta ̣i đỉnh có luồ ng vào lớn hơn luồ ng ra . Trong phương pháp này , các tác giả duy trì các luồ ng trước cực đa ̣i và hiê ̣u chin ̉ h chúng thà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 4
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. 5
- Đề 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ự. 6
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. 7
CHƢƠNG 1. XỬ LÝ SONG SONG Trong chương này, chúng tôi sẽ 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. Trên cơ sở đó, chúng tôi đề xuất các thuật toán song song trong các chương tiếp theo. Nội dung của chương này chủ yếu được kế thừa từ các tài liệu [1], [37], [39], [41]. 1.1. Giới thiệu về xử lý song song Các ứng dụng của lý thuyết đồ thị là rất lớn và rất phong phú trong nhiều lĩnh vực khác nhau như: kinh tế, giao thông, truyền thông, điện tử, y khoa… Vì vậy, các bài toán trên đồ thị cần phải xử lý với dữ liệu đầu vào là rất lớn để đáp ứng nhu cầu thực tế. Do vậy, cần xây dựng các bài toán này theo hướng song song để giảm thời gian tính toán. Những vấn đề về xử lý ngôn ngữ tự nhiên, nhận dạng, xử lý ảnh ba chiều, dự báo thời tiết, mô hình và mô phỏng những hệ thống lớn trong thực tế đều đòi hỏi phải xử lý dữ liệu với tốc độ rất cao và khối lượng dữ liệu rất lớn. Do đó, cần phải có những hệ thống máy tính thật mạnh mới thực hiện được những yêu cầu trong thực tế một cách nhanh chóng và hiệu quả. Điều này còn gặp nhiều khó khăn do khả năng giới hạn về vật lý. Vì vậy, hướng xử lý song song là dùng các hệ thống máy tính đa bộ xử lý hoặc bộ xử lý đa nhân được lựa chọn để giải quyết các bài toán đặt ra. Xử lý song song là quá trình xử lý gồm nhiều tiến trình được kích hoạt đồng thời và cùng tham gia giải quyết một vấn đề, nói chung là thực hiện tính toán trên những hệ thống đa bộ xử lý [1]. Tính toán song song là một hình thức tính toán trong đó nhiều phép tính được thực hiện đồng thời, hoạt động trên nguyên tắc là những vấn đề lớn đều có thể chia thành nhiều phần nhỏ hơn để giải quyết đồng thời trên các bộ xử lý. Các bộ xử lý cùng kết hợp với nhau để giải quyết cùng một vấn đề cho nên giảm được thời gian xử lý, vì mỗi thời điểm có thể có nhiều phép toán được thực hiện đồng thời. 8
Phần lớn các hệ điều hành ngày nay đều đã hỗ trợ đa xử lý, đa nhiệm và cho phép nghiên cứu, khai thác các phương pháp lập trình song song. Bằng cách tăng số lượng bộ xử lý, ta hy vọng sẽ thực hiện nhiều công việc hơn với thời gian ít hơn so với hệ điều hành đơn bộ xử lý. Hệ đa xử lý cho phép chia các công việc thành các phần nhỏ giao cho các bộ xử lý đảm nhận, cho phép tích hợp các hệ thống máy tính đã có để tạo ra các hệ thống mới với sức mạnh tăng rất nhiều lần. Một trong các mục đích chính của xử lý song song là thực hiện tính toán nhanh trên cơ sở sử dụng nhiều bộ xử lý đồng thời. Cùng với tốc độ xử lý nhanh hơn, việc xử lý song song cũng sẽ giải được những bài toán phức tạp và yêu cầu khối lượng tính toán lớn. 1.2. Kiến trúc máy tính song song Theo Michael Flynn [79] và Seyed H. Roosta [37], kiến trúc máy tính được phân thành 4 loại: - SISD (Single Instructions Stream, Single Data Stream): Máy tính một luồng lệnh, một luồng dữ liệu. Các máy tính SISD tương ứng với các máy một bộ xử lý mà chúng ta đã nghiên cứu. SISD chỉ có một CPU, ở mỗi thời điểm thực hiện một chỉ lệnh và chỉ đọc, ghi một mục dữ liệu. - SIMD (Single Instructions Stream, Multiple Data Stream): Máy tính một luồng lệnh, nhiều luồng dữ liệu. Các máy SIMD có một số lớn các bộ xử lý giống nhau, cùng thực hiện một lệnh giống nhau để xử lý nhiều luồng dữ liệu khác nhau. Mỗi bộ xử lý có bộ nhớ dữ liệu riêng, nhưng chỉ có một bộ nhớ lệnh và một đơn vị điều khiển. - MISD (Multiple Instructions Stream, Single Data Stream): Máy tính nhiều luồng lệnh, một luồng dữ liệu. Máy tính loại MISD là ngược lại với SIMD. Máy tính MISD có thể thực hiện nhiều lệnh trên cùng một mục dữ liệu. Đây là lớp các máy tính yêu cầu những đơn vị xử lý khác nhau có thể nhận được những chỉ lệnh khác nhau để thực hiện trên cùng một mục dữ liệu. - MIMD (Multiple Instruction Stream, Multiple Data Stream): Máy tính nhiều luồng lệnh, nhiều luồng dữ liệu. Các máy MIMD nổi lên và được xem như 9
một kiến trúc đương nhiên phải chọn cho các máy nhiều bộ xử lý dùng trong các ứng dụng thông thường, một tập hợp các bộ xử lý thực hiện một chuỗi các lệnh khác nhau trên các tập hợp dữ liệu khác nhau. Máy tính loại MIMD còn gọi là đa bộ xử lý. Trong đó, mỗi bộ xử lý có thể thực hiện những luồng lệnh khác nhau trên các luồng dữ liệu riêng. Hầu hết các hệ thống MIMD đều có bộ nhớ riêng. 1.2.1. Kiến trúc song song SIMD Luồng Phần tử dữ liệu 1 Tín hiệu xử lý 1 điều khiển Luồng Phần tử dữ liệu 2 xử lý 2 . Luồng lệnh . . Luồng Phần tử dữ liệu n Kết quả xử lý n Bộ nhớ Hình 1.1. Mô hình kiến trúc song song SIMD Trong một máy SIMD, nhiều thành phần xử lý được giám sát bởi một đơn vị điều khiển. Tất cả những thành phần xử lý đều nhận cùng mệnh lệnh từ đơn vị điều khiển nhưng lại thực hiện trên những tập dữ liệu khác nhau và đến từ những luồng dữ liệu khác nhau. Một máy SIMD có những đặc điểm sau: xử lý phân tán trên một số lượng lớn phần cứng, thực hiện đồng thời trên nhiều thành phần dữ liệu khác nhau và thực hiện cùng một câu lệnh trên các thành phần dữ liệu. Mô hình kiến trúc song song SIMD được Seyed H. Roosta trình bày ở [37, tr. 6] như trong Hình 1.1. 1.2.2. Kiến trúc song song MIMD Một máy tính MIMD là một hệ thống nhiều bộ xử lý và nhiều bộ nhớ, trong đó mỗi bộ xử lý có một đơn vị xử lý riêng và thực hiện chương trình riêng. Các bộ xử lý thực hiện nhiều câu lệnh khác nhau trên các tập dữ liệu khác nhau, chia sẻ tài nguyên chứa trong hệ thống bộ nhớ chính. Các hệ thống MIMD thực hiện các phép toán theo dạng song song không đồng bộ [34], [37]. 10
Mô hình MIMD gồm hai loại: loại các bộ kết nối chặt và loại các bộ kết nối rời tùy thuộc vào cách thức mà các bộ xử lý truy cập vào bộ nhớ. Những bộ xử lý kết nối chặt được chia sẻ từ một hệ thống bộ nhớ chung được hiểu là hệ thống chia sẻ bộ nhớ. Mô hình này được Seyed H. Roosta trình bày ở [37, tr. 24] như trong Hình 1.2. Bộ xử lý1 Bộ xử lý2 ... Bộ xử lýn Mạng kết nối .... Bộ nhớ1 Bộ nhớ2 ... Bộ nhớm Bộ nhớ chung Hình 1.2. Mô hình MIMD chia sẻ bộ nhớ Đối với hệ thống MIMD kết nối rời chia sẻ từ bộ nhớ hệ thống nhưng mỗi bộ xử lý có một bộ nhớ riêng được hiểu như hệ thống truyền thông điệp. Những máy tính truyền thông điệp gửi đến nhiều máy tính trong đó mỗi bộ xử lý có bộ nhớ riêng và chỉ truy cập đến bộ xử lý đó. Mô hình này được Seyed H. Roosta trình bày ở [37, tr. 25] như trong Hình 1.3. Mạng kết nối Bộ nhớ1 Bộ nhớ2 Bộ nhớm ... Bộ xử lý1 Bộ xử lý 2 ... Bộ xử .... lým Hình 1.3. Mô hình MIMD truyền thông điệp 11
1.2.3. Mô hình máy tính PRAM PRAM (Parallel Random Access Machine) là mô hình máy truy cập ngẫu nhiên song song được đưa ra bởi Fortune và Wyllie [80] vào năm 1978 và được đề cập, phát triển nhiều trong [37], [39], [41]. Thông thường khi xây dựng các thuật toán song song, chúng ta quy ước là phát triển thuật toán cho mô hình trừu tượng này. PRAM không phải là một môi trường thực thi cụ thể (mang tính vật lý), mà là một mô hình máy tính song song trừu tượng với cấu trúc bao gồm: k bộ xử lý có bộ nhớ cục bộ riêng, một bộ nhớ dùng chung với một mô hình truy xuất bộ nhớ phải được quy định (ví dụ, CREW – Concurrent Read, Exclusive Write - Cho phép xung đột đọc và không cho phép xung đột ghi [37, tr. 62]) và thời gian liên lạc là không có. Xử lý được bắt đầu với đầu vào lưu trong bộ nhớ toàn cục và một bộ xử lý được kích hoạt. Tại mỗi bước, một bộ xử lý đang hoạt động có thể thực hiện một trong các thao tác: đọc dữ liệu từ bộ nhớ riêng cục bộ hay bộ nhớ toàn cục, ghi dữ liệu vào bộ nhớ riêng cục bộ hay toàn cục hoặc kích hoạt bộ xử lý khác. Các mô hình PRAM khác nhau ở chỗ làm thế nào để giải quyết được các xung đột từ thao tác ghi và đọc vào bộ nhớ toàn cục. Theo Seyed H. Roosta [37], Behrooz Parhami [39] và Michael J. Quinn [41], mô hình PRAM chia thành 3 loại: - EREW (Exclusive Read, Exclusive Write): Không cho phép xung đột đọc và ghi [37, tr. 62-63]. - CREW (Concurrent Read, Exclusive Write): Cho phép xung đột đọc và không cho phép xung đột ghi. Tại cùng một thời điểm, nhiều bộ xử lý có thể đọc đến cùng một địa chỉ trong bộ nhớ toàn cục nhưng không có quá một bộ nhớ được phép ghi [37]. - CRCW (Concurrent Read, Concurrent Write):Cho phép xung đột đọc và cho phép xung đột ghi. Tại cùng một thời điểm, nhiều bộ xử lý có thể đọc hoặc ghi cùng một địa chỉ trong bộ nhớ toàn cục [37]. Mô hình PRAM được Michael J. Quinn biểu diễn trong [41] như trong Hình 1.4. 12
CU ... ... ... ... P1. Bộ nhớ riêng 1 P2. Bộ nhớ riêng 2 Pk. Bộ nhớ riêng k Mạng kết nối Bộ nhớ chung ... Hình 1.4. Mô hình PRAM Với mô hình trừu tượng này thì độ phức tạp của một thuật toán song song mới định nghĩa được. Chú ý, như đã nói ở trên, mô hình PRAM không có thời gian liên lạc, nhưng độ phức tạp sẽ được quy ra số bước để gửi và nhận kết quả. Độ phức tạp được quy ra số bước để gửi và nhận kết quả được đánh giá theo hàm log. Ví dụ, trong [37, tr. 273-274] Seyed H. Roosta đã phân tích, chứng minh được thời gian tính của thuật toán song song ký hiệu Tk trên k bộ xử lý tìm cây khung (spanning tree) trên đồ thị n đỉnh là: Tk= O(n2/k)+O(n log k). Với O(n log k) là độ phức tạp bởi số bước gửi và nhận kết quả, O(n2/k) là thời gian tính toán. Tương tự như vậy, Hua Wang [51] đã đề xuất thuật toán song song tìm đường đi ngắn nhất của mọi cặp đỉnh trên đồ thị. Ông cũng đã chỉ ra độ phức tạp bởi số bước gửi và nhận kết quả là O(n2log k) và thời gian tính toán là O(n3/k). Tuy nhiên, cần lưu ý rằng thời gian tính toán và thời gian truyền thông được quy định bởi số bước gửi và nhận kết quả là để phân tích đánh giá thời gian thực hiện song song, còn về mặt lý thuyết thì độ phức tạp của thuật toán tuần tự và song song là như nhau. Hơn nữa, thời gian thực hiện thuật toán song song trong môi trường thực tế còn phụ thuộc vào rất nhiều tham số khác như: kích cỡ thông điệp, cấu hình kết nối 13
mạng đường truyền và cách thức truyền thông điệp. Khi thực nghiệm thì không thể lặp lại mô hình PRAM trừu tượng, và do đó phát sinh rất nhiều loại phí tổn khác nhau như đã đề cập ở trên. Do có nhiều loại phí tổn nên rõ ràng là mức độ tăng tốc (speedup) không thể lên cao được khi tăng số lượng bộ xử lý lên nhiều lần. Như vậy, mục đích của mô hình PRAM là để xây dựng mô hình lý thuyết. Dựa trên mô hình này, chúng ta có thể đánh giá độ phức tạp về mặt thời gian của thuật toán. Đây là mô hình tổng quát cho máy tính song song kiểu MIMD. 1.3. Thuật toán song song 1.3.1. Quy trình thiết kế thuật toán song song Song song hóa thuật toán là chuyển một thuật toán tuần tự đã có thành một thuật toán song song. Quy trình thiết kế thuật toán song song thực hiện qua bốn công đoạn: phân rã (Partition), truyền thông (Communication), tích tụ (Agglomeration) và ánh xạ (Mapping) [37]. - Phân rã: Khi bài toán được xác định, công việc tính toán và dữ liệu của bài toán được phân rã thành nhiều tác vụ. Ta cố gắng chú trọng vào việc xác định được nhiều tác vụ càng nhiều càng tốt nếu có thể. Số lượng tác vụ có thể lớn hơn nhiều so với số lượng bộ xử lý để linh hoạt hơn khi áp dụng vào mô hình thực tế. Trong giai đoạn này ta chưa đề cập đến vấn đề truyền thông, cấu trúc máy tính song song mà chỉ đề cập đến việc xác định được các khả năng thực hiện song song của bài toán. Mục đích của công đoạn này là ta tìm ra tập các tác vụ độc lập với nhau của bài toán và chú ý việc kết hợp dữ liệu, xác định kết hợp tính toán với dữ liệu như thế nào. - Truyền thông: Công đoạn truyền thông được thể hiện thông qua luồng thông tin sao cho các tác vụ được tạo ra trong công đoạn trên sẽ được thực hiện đồng thời. Tính toán thực hiện trong một tác vụ thường sẽ yêu cầu dữ liệu kết hợp với các dữ liệu khác. Sau đó, dữ liệu phải được truyền giữa các tác vụ để cho phép thực hiện tính toán. - Tích tụ: Công đoạn này sẽ gộp các tác vụ nhỏ đã tạo ra ở công đoạn phân rã thành các tác vụ có kích thước lớn hơn. Khi tích tụ các tác vụ nhỏ thành các tác vụ lớn thì 14
chi phí truyền thông sẽ giảm đi nhưng sẽ làm giảm tiềm năng thực hiện đồng thời. - Ánh xạ: Đây là công đoạn cuối cùng, mỗi tác vụ sẽ được ấn định vào một bộ xử lý nào đó. Bốn công đoạn trên được Seyed H. Roosta [ 37, tr. 223] biểu diễn như trong Hình 1.5. Bài toán Phân rã Truyền thông Tích tụ Ánh xạ BXL1 BXL3 BXL2 Hình 1.5. Quy trình thiết kế thuật toán song song 15
1.3.2. Nguyên lý thiết kế thuật toán song song Những thuật toán, trong đó có một số thao tác có thể thực hiện đồng thời được gọi là thuật toán song song. Tổng quát hơn, thuật toán song song là một tập các tiến trình hoặc các tác vụ có thể thực hiện đồng thời và có thể trao đổi dữ liệu với nhau để kết hợp cùng giải một bài toán đặt ra. Có năm nguyên lý chính trong thiết kế thuật toán song song [1]: 1. Các nguyên lý lập lịch: Tạo lịch trình để giảm tối thiểu các bộ xử lý sử dụng trong thuật toán sao cho thời gian tính toán là không tăng (xét theo khía cạnh độ phức tạp). 2. Nguyên lý hình ống: Nguyên lý này được áp dụng khi bài toán xuất hiện một dãy các thao tác {T1, T2, . . ., Tn}, trong đó Ti+1 thực hiện sau khi Ti kết thúc. 3. Nguyên lý chia để trị: Chia bài toán thành những phần nhỏ hơn tương đối độc lập với nhau và giải quyết chúng một cách song song. 4. Nguyên lý đồ thị phụ thuộc dữ liệu: Phân tích mối quan hệ dữ liệu trong tính toán để xây dựng đồ thị phụ thuộc dữ liệu và dựa vào đó để xây dựng thuật toán song song. 5. Nguyên lý điều kiện tương tranh : Nếu hai tiến trình cùng muốn truy cập vào cùng một mục dữ liệu chia sẻ thì chúng phải tương tranh với nhau, nghĩa là chúng có thể cản trở lẫn nhau. Ngoài những nguyên lý nêu trên, khi thiết kế thuật toán song song còn một số điểm cần quan tâm: 1. Hiệu quả thực hiện của thuật toán song song có thể rất khác nhau, mà yếu tố quan trọng nhất ảnh hưởng tới độ phức tạp tính toán là cấu hình tô pô liên kết mạng. 2. Thuật toán song song phải được thiết kế dựa trên những kiến thức về kiến trúc máy tính, ngôn ngữ lập trình song song và các phương pháp tính toán. 1.3.3. Các cách tiếp cận trong thiết kế Có ba cách tiếp cận để thiết kế thuật toán song song: 1. Thực hiện song song hoá những thuật toán tuần tự, biến đổi những cấu trúc 16
tuần tự để tận dụng được những khả năng song song tự nhiên của tất cả các thành phần trong hệ thống xử lý. 2. Thiết kế những thuật toán song song mới phù hợp với kiến trúc song song. 3. Xây dựng những thuật toán song song từ những thuật toán song song đã được xây dựng cho phù hợp với cấu hình tô pô mạng và môi trường song song thực tế. 1.3.4. Phân tích, đánh giá thuật toán song song Độ phức tạp tính toán về thời gian của thuật toán song song không chỉ phụ thuộc vào kích cỡ của dữ liệu đầu vào mà còn phụ thuộc vào kiến trúc máy tính song song và số lượng các bộ xử lý được phép sử dụng trong hệ thống. Độ phức tạp thời gian là thước đo quan trọng nhất đánh giá mức độ hiệu quả của thuật toán song song. Độ phức tạp thời gian của thuật toán song song được xác định bởi số các phép toán cơ sở và số các bước truyền tải dữ liệu giữa các bộ xử lý với nhau. Từ đó suy ra, độ phức tạp thời gian của thuật toán song song không chỉ phụ thuộc vào mô hình tính toán song song mà còn phụ thuộc vào số bộ xử lý được sử dụng. Mức độ tăng tốc (Speedup) [37, tr. 228-231] của thuật toán song song sử dụng p bộ xử lý được xác định như sau: Sp = TS/Tp (1) Trong đó, TS là thời gian thực hiện tính toán trên một bộ xử lý Tp là thời gian thực hiện tính toán trên p bộ xử lý. Để sử dụng hiệu quả các thuật toán song song, chúng ta cần phải biết cách đánh giá nó. Để đánh giá được độ phức tạp tính toán của các thuật toán song song, ngoài số bước tính toán chúng ta còn cần đánh giá thời gian truyền thông của các tiến trình. Thời gian thực hiện song song, ký hiệu là tp gồm hai phần tcomp và tcomm tp = tcomp + tcomm (2) Trong đó, tcomp là thời gian tính toán và tcomm thời gian truyền thông dữ liệu. 17
1.4. Kết luận chƣơng Để giải những bài toán đặt ra một cách hiệu quả trên những máy tính mà chúng ta có, vấn đề chính là làm thế nào để xây dựng được những thuật toán song song. Cách làm khá thông dụng là biến đổi các thuật toán tuần tự về song song, hay chuyển từ một dạng song song về dạng song song phù hợp hơn nhưng vẫn bảo toàn được tính tương đương trong tính toán. Dựa vào bốn công đoạn và những nguyên lý thiết kế chính: nguyên lý lập lịch, nguyên lý hình ống, nguyên lý chia để trị, nguyên lý đồ thị phụ thuộc dữ liệu, nguyên lý điều kiện tranh đua để xây dựng một số thuật toán song song. Để đánh giá được tính hiệu quả của thuật toán song song thường phải dựa vào độ phức tạp thời gian của thuật toán. Độ phức tạp thời gian của thuật toán song song không chỉ phụ thuộc vào kích cỡ của dữ liệu đầu vào mà còn phụ thuộc vào kiến trúc máy tính song song và số lượng các bộ xử lý được phép sử dụng trong hệ thống. 18
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 chính trong chương này gồm hai phần: Phần thứ nhất là kế thừa thuật toán tuần tự và song song đẩy luồng trước tìm luồng cực đại đã được nghiên cứu trong [55], [56]. [61]. Từ đó, chúng tôi tối ưu thuật toán song song đẩy luồng trước này. Phần thứ hai, đề xuất thuật toán tuần tự hỗn hợp đẩy kéo luồng. Dựa vào đó, đề xuất thuật toán song song cho thuật toán hỗn hợp đẩy kéo luồng để tìm luồng cực đại. 2.1. Mạng và luồng  Mạng (network) là đồ thị có hướng, có thêm trọng số ở các cạnh G=(V, E, c) thoả mãn: (i) Có duy nhất một đỉnh mà nửa bậc vào của đỉnh đó bằng 0, được gọi là đỉnh nguồn. (ii) Có duy nhất một đỉnh mà nửa bậc ra của đỉnh đó bằng 0, được gọi là đỉnh đích. (iii) Trọng số ci, j của cung (i, j) là các số không âm và gọi là khả năng thông qua của cung. Đồ thị ở Hình 2.1 là mạng với nguồn là đỉnh a và đích là đỉnh z, ta có khả năng thông qua ca, b=3, cb, c=2, ca, d=5, cd, c=2, cd, e=2, cc, z=4, ce, z=4. b 2 c 3 4 a 2 z 5 4 d 2 e Hình 2.1. Mạng đồ thị với nguồn a đích z  Luồng: Cho mạng G=(V, E, c). Tập các giá trị f = {fi, j  (i, j)E} (3) gọi là luồng trên mạng G nếu thoả mãn: 19
(i) 0  fi, j  ci, j (i, j)E (4) (ii) Với mọi đỉnh k không phải nguồn hoặc đích  fi, k   f k , j (5) (i , k )E ( k , j )E Với mọi đỉnh kV, tổng  f i, k gọi là luồng vào của đỉnh k và tổng (i , k )E  fk, j gọi là luồng ra của đỉnh k. Với đồ thị ở Hình 2.1, tập {fi, j} sau là luồng ( k , j)E fa, b = 2, fb, c = 2, fc, z = 3, fa, d = 3, fd, c = 1, fd, e = 2, fe, z = 2. Tập các luồng này được biểu diễn bằng các số trong ngoặc đơn trên các cung trong mạng như trong Hình 2.2. b 2(2) c 3(2) 4(3) a 2(1) z 5(3) 4(2) d 2(2) e Hình 2.2. Mạng đồ thị biểu diễn luồng  Định lý 2.1. [3] Cho f = {fi, j , (i, j)E}, là luồng trên mạng G với nguồn a và đích z. Khi đó  f a, i   f i, a   f i, z   f z , i (6) ( a , i )E (i , a )E (i , z)E ( z , i)E  Giá trị của luồng. Cho luồng f trên mạng G. Giá trị của luồng f, ký hiệu v(f) là đại lượng. v( f )   f a, i   f i, a   f i, z   f z , i (7) ( a , i )E (i , a )E (i , z )E ( z , i )E 2.2. Bài toán luồng cực đại Trong thực tế ta thường gặp bài toán gọi là bài toán tìm luồng cực đại như sau: Cho mạng G với nguồn a, đích z và khả năng thông qua ci, j, (i, j)E. Trong số 20