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âṇ tồn taị đỉ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ị và hiêụ 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. 
8 
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ú tron ... ......................................................... 10 
1.2.3. Mô hình máy tính PRAM ....................................................................... 12 
1.3. Thuật toán song song ......................................................................................... 14 
1.3.1. Quy trình thiết kế thuật toán song song .................................................. 14 
1.3.2. Nguyên lý thiết kế thuật toán song song ................................................ 16 
1.3.3. Các cách tiếp cận trong thiết kế.............................................................. 16 
1.3.4. Phân tích, đánh giá thuật toán song song ............................................... 17 
1.4. Kết luận chươ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 ........................................................... 19 
2.1. Mạng và luồng .................................................................................................... 19 
99 
2.2. Bài toán luồng cực đại ........................................................................................ 20 
2.3. Thuật toán đẩy luồng trước tìm luồng cực đại ................................................... 21 
2.3.1. Thuật toán tuần tự ................................................................................... 21 
2.3.1.1. Giới thiệu .................................................................................... 21 
2.3.1.2. Các khái niệm cơ bản ................................................................. 21 
2.3.1.3. Phương pháp đẩy luồng trước tổng quát .................................... 23 
2.3.1.4. Thuâṭ toán đẩy luồng trước ......................................................... 24 
2.3.1.5. Ví dụ minh họa ........................................................................... 27 
2.3.2. Thuật toán song song .............................................................................. 30 
2.3.2.1. Giới thiệu .................................................................................... 30 
2.3.2.2. Ý tưởng của thuật toán song song .............................................. 31 
2.3.2.3. Xây dựng thuật toán song song .................................................. 31 
2.3.2.4. Ví dụ minh họa ........................................................................... 33 
2.3.2.5. Phân tích độ phức tạp thời gian .................................................. 36 
2.3.2.6. Kết quả thực nghiệm ................................................................... 37 
2.3.2.7. Kết luận ....................................................................................... 40 
2.4. Thuật toán hỗn hợp đẩy kéo luồng ..................................................................... 40 
2.4.1. Thuật toán tuần tự kéo luồng sau ........................................................... 40 
2.4.1.1. Giới thiệu .................................................................................... 40 
2.4.1.2. Các khái niệm cơ bản ................................................................. 40 
2.4.1.3. Phương pháp kéo luồng sau tổng quát ........................................ 41 
2.4.1.4. Thuâṭ toán kéo luồng sau ............................................................ 42 
2.4.1.5. Ví dụ minh họa ........................................................................... 43 
2.4.2. Thuật toán tuần tự hỗn hợp đẩy kéo luồng tìm luồng cực đại ................ 46 
2.4.2.1. Phương pháp hỗn hợp đẩy kéo luồng tổng quát ......................... 46 
2.4.2.2. Thuâṭ toán hỗn hợp đẩy kéo luồng ............................................. 47 
2.4.2.3. Ví dụ minh họa ........................................................................... 49 
2.4.3. Thuật toán song song hỗn hợp đẩy kéo luồng tìm luồng cực đại ........... 51 
2.4.3.1. Giới thiệu .................................................................................... 51 
100 
2.4.3.2. Ý tưởng của thuật toán song song .............................................. 52 
2.4.3.3. Xây dựng thuật toán song song .................................................. 52 
2.4.3.4. Ví dụ minh họa ........................................................................... 54 
2.4.3.5. Kết quả thực nghiệm ................................................................... 57 
2.4.3.6. Kết luận ....................................................................................... 59 
2.5. Kết luận chương ................................................................................................. 59 
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 ............................................................................................................. 60 
3.1. Đồ thị mở rộng ................................................................................................... 60 
3.2. Thuật toán tìm đường đi ngắn nhất trên đồ thị mở rộng .................................... 60 
3.2.1. Thuật toán tuần tự ................................................................................... 60 
3.2.1.1. Giới thiệu .................................................................................... 61 
3.2.1.2. Xây dựng thuật toán.................................................................... 61 
3.2.2. Thuật toán song song .............................................................................. 62 
3.2.2.1. Giới thiệu .................................................................................... 62 
3.2.2.2.Ý tưởng của thuật toán song song ............................................... 63 
3.2.2.3. Xây dựng thuật toán song song .................................................. 63 
3.2.2.4. Kết quả thực nghiệm ................................................................... 67 
3.2.2.5. Kết luận ....................................................................................... 70 
3.3. Thuật toán tìm luồng cực đại đồng thời chi phí giới hạn ................................... 70 
3.3.1. Thuật toán tuần tự ................................................................................... 70 
3.3.1.1. Giới thiệu .................................................................................... 70 
3.3.1.2. Mạng giao thông mở rộng ......................................................... 70 
3.3.1.3. Phát biểu bài toán luồng cực đại đồng thời chi phí giới hạn ...... 71 
3.3.1.4. Thuật toán tìm luồng cực đại đồng thời chi phí giới hạn ........... 73 
3.3.1.5. Trình bày thuật toán theo giả mã ................................................ 76 
3.3.2. Thuật toán song song tìm luồng cực đại đồng thời chi phí giới hạn ...... 78 
3.3.2.1. Giới thiệu .................................................................................... 78 
101 
3.3.2.2. Ý tưởng thuật toán song song ..................................................... 79 
3.3.2.3. Xây dựng thuật toán song song .................................................. 79 
3.3.2.4. Ví dụ minh họa ........................................................................... 83 
3.3.2.5. Phân tích độ phức tạp thời gian .................................................. 84 
3.3.2.6. Kết quả thực nghiệm ................................................................... 84 
3.3.2.7. Kết luận ....................................................................................... 86 
3.4. Kết luận chương ................................................................................................. 86 
KẾT LUẬN .................................................................................................... 87 
DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ ĐÃ CÔNG BỐ LIÊN 
QUAN ĐẾN LUẬN ÁN ................................................................................ 88 
TÀI LIỆU THAM KHẢO ............................................................................ 89 
102 
DANH MỤC CÁC HÌNH 
Hình 1.1. Mô hình kiến trúc song song SIMD .......................................................... 10 
Hình 1.2. Mô hình MIMD chia sẻ bộ nhớ ................................................................. 11 
Hình 1.3. Mô hình MIMD truyền thông điệp ............................................................ 11 
Hình 1.4. Mô hình PRAM ......................................................................................... 13 
Hình 1.5. Quy trình thiết kế thuật toán song song .................................................... 15 
Hình 2.1. Mạng đồ thị với nguồn a đích z ................................................................ 19 
Hình 2.2. Mạng đồ thị biểu diễn luồng ..................................................................... 20 
Hình 2.3. Mạng đồ thị G ........................................................................................... 27 
Hình 2.4. Mạng đồ thị khởi tạo ................................................................................. 27 
Hình 2.5. Mạng đồ thị cân bằng b, d ......................................................................... 29 
Hình 2.6. Mạng đồ thị cân bằng c, b ......................................................................... 29 
Hình 2.7. Mạng đồ thị cân bằng e, d ......................................................................... 30 
Hình 2.8. Mạng đồ thị biểu diễn kết quả thực hiện của 2 bộ xử lý phụ .................... 34 
Hình 2.9. Mạng đồ thị biểu diễn kết quả thực hiện của bộ xử lý chính .................... 35 
Hình 2.10. Mạng đồ thị biểu diễn kết quả thực hiện của 2 bộ xử lý phụ .................. 36 
Hình 2.11. Giao diện tạo mạng đồ thị ngẫu nhiên .................................................... 38 
Hình 2.12. Biểu diễn kết quả ví dụ............................................................................ 38 
Hình 2.13. Biểu diễn mức độ tăng tốc trên các bộ xử lý của đồ thị 7000 đỉnh (nét 
liền) và 5000 đỉnh (nét đứt) ....................................................................................... 39 
Hình 2.14. Mạng đồ thị G ......................................................................................... 43 
Hình 2.15. Khởi tạo mạng đồ thị ............................................................................... 44 
Hình 2.16. Mạng đồ thị cân bằng h, i ........................................................................ 44 
Hình 2.17. Mạng đồ thị cân bằng f, g ........................................................................ 44 
Hình 2.18. Mạng đồ thị cân bằng i, c ........................................................................ 45 
Hình 2.19. Mạng đồ thị cân bằng e, g ....................................................................... 45 
Hình 2.20. Mạng đồ thị cân bằng b, d ....................................................................... 45 
Hình 2.21. Mạng đồ thị cân bằng h ........................................................................... 46 
Hình 2.22. Mạng đồ thị cân bằng h ........................................................................... 46 
103 
Hình 2.23. Mạng đồ thị G ......................................................................................... 49 
Hình 2.24. Mạng đồ thị khởi tạo ............................................................................... 49 
Hình 2.25. Mạng đồ thị cân bằng b, h ....................................................................... 49 
Hình 2.26. Mạng đồ thị cân bằng d, i ........................................................................ 50 
Hình 2.27. Mạng đồ thị cân bằng c, f ........................................................................ 50 
Hình 2.28. Mạng đồ thị cân bằng b, g ....................................................................... 50 
Hình 2.29. Mạng đồ thị cân bằng e, i ........................................................................ 50 
Hình 2.30. Mạng đồ thị cân bằng c, g ....................................................................... 51 
Hình 2.31. Mạng đồ thị cân bằng e, h ....................................................................... 51 
Hình 2.32. Mạng đồ thị cân bằng d, h ....................................................................... 51 
Hình 2.33. Mạng đồ thị cân bằng b ở bộ xử lý P1, và cân bằng h ở bộ xử lý P2 ...... 55 
Hình 2.34. Mạng đồ thị cân bằng d ở bộ xử lý P1 và cân bằng i ở bộ xử lý P2 ........ 56 
Hình 2.35. Mạng đồ thị cân bằng c ở bộ xử lý P1, và cân bằng f ở bộ xử lý P2 ....... 56 
Hình 2.36. Giao diện Client ...................................................................................... 57 
Hình 2.37. Giao diện Server ...................................................................................... 58 
Hình 3.1. Ma trận trọng số cạnh trên 2 bộ xử lý ....................................................... 66 
Hình 3.2. Đồ thị mở rộng G ...................................................................................... 67 
Hình 3.3. Giao diện tạo đồ thị mở rộng ngẫu nhiên .................................................. 68 
Hình 3.4. Giao diện Server ........................................................................................ 69 
Hình 3.5. Mức độ tăng tốc trên các bộ xử lý đối với đồ thị 7000 nút (nét liền) và 
5000 nút (nét đứt) ...................................................................................................... 69 
Hình 3.5. Mạng giao thông mở rộng ......................................................................... 83 
Hình 3.6. Giao diện đăng nhập để chọn dữ liệu thực nghiệm ................................... 85 
Hình 3.7. Mức độ tăng tốc trên các bộ xử lý với dữ liệu của thành phố Đà Nẵng ... 85 
Hình 3.8. Giao diện Server ........................................................................................ 86 
104 
DANH MỤC CÁC CHỮ VIẾT TẮT 
1. BXL Bộ xử lý. 
2. CPU Central Processing Unit. 
 Đơn vị xử lý trung tâm. 
3. CU Control Unit. 
 Đơn vị điều khiển. 
4. MISD Multiple Instruction Stream, Single Data Stream. 
 Đa luồng lệnh, đơn luồng dữ liệu. 
5. MIMD Multiple Instruction Stream , Multiple Data Stream. 
 Đa luồng lệnh, đa luồng dữ liệu. 
6. MPI Message Passing Interface. 
Trao đổi thông điệp. 
7. PRAM Parallel Random Access Machine. 
Máy truy cập ngẫu nhiên song song. 
8. SIMD Single Instruction Stream, Multiple Data Stream. 
 Đơn luồng lệnh, đa luồng dữ liệu. 
9. SISD Single Instruction Stream, Single Data Stream. 
 Đơn luồng lệnh, đơn luồng dữ liệu. 
105 
LỜI CAM ĐOAN 
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi, và có kế 
thừa các công trình nghiên cứu trước có liên quan đến đề tài. 
Các số liệu, kết quả nghiên cứu trong luận án là trung thực và chưa 
từng được ai công bố trong bất kỳ công trình nào khác. 
 Tác giả luận án 
 Nguyễn Đình Lầu