Tiến Sĩ 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.