Luận án Song song hóa các thuật toán trên mạng đồ thị - Nguyễn Đình Lầu
DANH MỤC CÁC HÌNH
DANH MỤC CÁC CHỮ VIẾT TẮT
MỞ ĐẦU . 1
1. Tính cấp thiết của việc nghiên cứu .1
2. Tổng quan tình hình nghiên cứu .2
3. Mục tiêu của luận án .5
4. Đối tượng và phạm vi nghiên cứu.5
5. Phương pháp nghiên cứu.6
6. Điểm mới của luận án .6
7. Kết quả nghiên cứu .7
8. Bố cục của luận án .7
CHƢƠNG 1. XỬ LÝ SONG SONG . 8
1.1. Giới thiệu về xử lý song song .8
1.2. Kiến trúc máy tính song song .9
1.2.1. Kiến trúc song song SIMD.10
1.2.2. Kiến trúc song song MIMD.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.1999
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 .51100
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 .78101
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 Á
Bạn đang xem trước 20 trang tài liệu Luận án Song song hóa các thuật toán trên mạng đồ thị - Nguyễn Đình Lầu, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
-1) i(6, -1)
z(5, 6)
3, 0
2, 0 2, 2 2, 2
5, 0
2, 0
3, 0
2, 2
2, 1
2, 2
3, 3
3, 3
Hình 2.17. Mạng đồ thị cân bằng f, g
45
Cân bằng i Q. Hàng đợi Q: h|i|f|g|i|c|e|g (Hình 2.18).
Cân bằng c Q. Hàng đợi Q: h|i|f|g|i|c|e|g|b (Hình 2.18).
Cân bằng e Q. Hàng đợi Q: h|i|f|g|i|c|e|g|b|d (Hình 2.19).
Cân bằng g Q. Hàng đợi Q: h|i|f|g|i|c|e|g|b|d|h (Hình 2.19).
Cân bằng b Q. Hàng đợi Q: h|i|f|g|i|c|e|g|b|d|h (Hình 2.20).
Cân bằng d Q. Hàng đợi Q: h|i|f|g|i|c|e|g|b|d|h (Hình 2.20).
Cân bằng hQ. d(h)=d(z)+1=5+1=6.
Hàng đợi Q: h|i|f|g|i|c|e|g|b|d|h|h (Hình 2.21).
b(1, -2)
a(0, 0)
d(1, 0)
c(2, 0)
e(2, -2)
f(3, 0) h(4, 0)
g(5, -1) i(6, 0)
z(5, 5)
3, 0
2, 2 2, 2 2, 2
5, 0
2, 0
3, 0
2, 2
2, 1
2, 2
3, 3
3, 2
Hình 2.18. Mạng đồ thị cân bằng i, c
b(1, -2)
a(0, 0)
d(1, -2)
c(2, 0)
e(2, 0)
f(3, 0) h(4, -1)
g(5, 0) i(6, 0)
z(5, 5)
3, 0
2, 2 2, 2 2, 2
5, 0
2, 0
3, 2
2, 2
2, 0
2, 2
3, 3
3, 2
Hình 2.19. Mạng đồ thị cân bằng e, g
b(1, 0)
a(0, 4)
d(1, 0)
c(2, 0)
e(2, 0)
f(3, 0) h(4, -1)
g(5, 0) i(6, 0)
z(5, 5)
3, 2
2, 2 2, 2 2, 2
5, 2
2, 0
3, 2 2, 2
2, 0
2, 2
3, 3
3, 2
Hình 2.20. Mạng đồ thị cân bằng b, d
46
Cân bằng h Q. Hàng đợi Q: h|i|f|g|i|c|e|g|b|d|h|h (Hình 2.22)
Bây giờ hàng đợi Q =∅, kết thúc và luồng cực đại có giá trị là 4.
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
2.4.2.1. Phương pháp hỗn hợp đẩy kéo luồng tổng quát
Đây là phương pháp mới tìm luồng cực đại. Kết hợp phương pháp đẩy luồng
trước và phương pháp kéo luồng sau ở trên, chúng tôi đề xuất phương pháp hỗn hợp
đẩy kéo luồng tổng quát như sau:
Bước 1. Khởi taọ:
- Xây dưṇg luồng trước xuất phát f với các cung đi từ đỉnh nguồn có luồng
bằng khả năng thông qua , còn các cung khác có luồng bằng 0. Chọn hàm độ
cao h nào đó trong maṇg G.
- Bổ sung vào f luồng sau xuất phát với các cung đi đ ến đỉnh đích (trừ cung
đã có luồng trước dương) có luồng bằng khả năng thông qua . Chọn hàm độ
sâu d nào đó trong mạng G.
Bước 2. Tiêu chuẩn dừng:
Nếu không có đỉnh lêc̣h thì dừng, luồng f trên mạng trở thành luồng cưc̣ đaị.
Bước 3. Xử lý đỉnh lêc̣h:
b(1, 0)
a(0, 4)
d(1, 0)
c(2, 0)
e(2, 0)
f(3, 0) h(6, -1)
g(5, 0) i(6, 0)
z(5, 5)
3, 2
2, 2 2, 2 2, 2
5, 2
2, 0
3, 2 2, 2
2, 0
2, 2
3, 3
3, 2
Hình 2.21. Mạng đồ thị cân bằng h
b(1, 0)
a(0, 4)
d(1, 0)
c(2, 0)
e(2, 0)
f(3, 0) h(6, 0)
g(5, 0) i(6, 0)
z(5, 4)
3, 2
2, 2 2, 2 2, 2
5, 2
2, 0
3, 2
2, 2
2, 0
2, 2
3, 2
3, 2
Hình 2.22. Mạng đồ thị cân bằng h
47
- Chọn đỉnh lệch u có độ lệch dương.
Nếu tồn taị cung ưu tiên (u, v)Ef thì đẩy trên cung (u, v) môṭ luồng có giá tri ̣
min{delta, cf(u, v)}, trong đó delta là đô ̣lêc̣h luồng của đỉnh u.
Nếu không tồn taị cung ưu tiên đi từ u, thì tăng độ cao của đỉnh u như sau:
h(u)= 1 + min{h(v) | (u, v)Ef}.
- Chọn đỉnh lệch v có độ lệch âm.
Nếu tồn taị cung ưu tiên (u, v)Ef thì kéo trên cung (u, v) môṭ luồng có giá tri ̣
min{delta, cf(u, v)}, trong đó delta (< 0) là độ lệch luồng của đỉnh v. Nếu
không tồn taị cung ưu tiên đi đến v, thì tăng độ sâu của đỉnh v như sau:
d(v)= 1 + min{d(u) | (u, v)Ef}. Quay laị bước 2.
Từ các tính chất của thuật toán đẩy luồng trước và thuật toán kéo luồng sau
ta suy ra các mệnh đề và định lý sau:
Mêṇh đề 2.7. Phương pháp hỗn hợp đẩy kéo luồng luôn bảo toàn tính chất của
hàm độ cao h và hàm độ sâu d.
2.4.2.2. Thuâṭ toán hỗn hợp đẩy kéo luồng
Đây là thuâṭ toán cu ̣thể thuôc̣ phương pháp h ỗn hợp đẩy kéo luồng. Ở đây
các đỉnh lệch dương được đẩy vào hàng đợi Q+ và các đỉnh lêc̣h âm đươc̣ đẩy vào
hàng đợi Q.
Với mỗi đỉnh lêc̣h dương lấy từ hàng đơị Q+, ta se ̃đẩy luồng vào các cung ưu
tiên môṭ cách tối đa cho tới khi đỉnh trở thành không lêc̣h hoăc̣ không còn cung ưu
tiên nữa. Nếu không còn cung ưu tiên nữa và đỉnh còn lêc̣h thì ta tăng đô ̣ cao và đẩy
nó vào hàng đợi Q+.
Với mỗi đỉnh lêc̣h âm lấy từ hàng đơị Q, ta se ̃kéo luồng vào các cung ưu
tiên môṭ cách tối đa cho tới khi đỉnh trở thành không lêc̣h hoăc̣ không còn cung ưu
tiên nữa. Nếu không còn cung ưu tiên nữa và đỉnh còn lêc̣h thì ta tăng đô ̣sâu và đẩy
nó vào hàng đợi Q. Bây giờ ta mô tả thuâṭ toán hỗn hợp đẩy kéo luồng như sau:
Bước 1. Khởi taọ:
- Xây dưṇg luồng trước xuất phát f với các cung đi từ đỉnh nguồn có luồng
bằng khả năng thông qua, còn các cung khác có luồng bằng 0.
48
- Chọn hàm độ cao h(v) là độ dài đường đi ngắn nhất từ v đến đỉnh đích z.
- Đẩy các đỉnh lệch dương vào hàng đợi Q+.
- Bổ sung vào f luồng sau xuất phát với các cung đi đ ến đỉnh đích (trừ cung
đã có luồng trước dương) có luồng bằng khả năng thông qua.
- Chọn hàm độ sâu d(v) là độ dài đường đi ngắn nhất từ đỉnh a đến đỉnh v.
- Đẩy các đỉnh lệch âm vào hàng đợi Q.
Bước 2. Tiêu chuẩn dừng:
- Nếu Q+ = ∅ và Q =∅, luồng f trở thành luồng cưc̣ đaị, kết thúc.
- Ngược lại sang bước 3.
Bước 3. Xử lý đỉnh lêc̣h:
- Lấy đỉnh lêc̣h u từ hàng đơị Q+.
Duyêṭ các cung ưu tiên (u, v) Ef . Đẩy trên cung (u, v) môṭ luồng có giá tri ̣
min{delta, cf(u, v)}, trong đó delta là độ lệch luồng của đỉnh u.
Nếu đỉnh v là đỉnh lệch mới, thì đẩy đỉnh v vào hàng đợi Q+.
Nếu đỉnh u vâñ còn lêc̣h, thì tăng độ cao của đỉnh u như sau:
h(u)= 1 + min{h(v) | (u, v)Ef}. Đẩy u vào hàng đợi Q+.
- Lấy đỉnh lêc̣h v từ hàng đơị Q.
Duyêṭ các cung ưu tiên (u, v)Ef. Kéo trên cung (u, v) môṭ luồng có giá tri ̣
min{delta, cf(u, v)}, trong đó delta (< 0) là độ lệch luồng của đỉnh v. Nếu
đỉnh u là đỉnh lệch mới, thì đẩy đỉnh u vào hàng đợi Q. Nếu đỉnh v vâñ còn
lêc̣h, thì tăng độ sâu của đỉnh v như sau: d(v)= 1 + min{d(u) | (u, v)Ef} sau
đó đẩy v vào hàng đợi Q. Quay laị bước 2.
Mêṇh đề 2.8. Trong quá trình thưc̣ hiêṇ thuật toán hỗn hợp đẩy kéo luồng, luôn
tồn taị đường đi điṇh hướng từ mỗi đỉnh lêc̣h dương đến đỉnh nguồn và luôn tồn taị
đường đi điṇh hướng t ừ đỉnh đích đ ến mỗi đỉnh lêc̣h âm trong maṇg thăṇg dư , và
không tồn taị đường đi điṇh hướng từ đỉnh nguồn đến đích trong maṇg thăṇg dư.
Hê ̣quả 2.5. Trong quá trình thưc̣ hiêṇ thuật toán hỗn hợp đẩy kéo luồng, đô ̣cao
và độ sâu mỗi đỉnh luôn nhỏ hơn 2.|V|.
49
Điṇh lý 2.4. Thuật toán hỗn hợp đẩy kéo luồng tìm luồng cực đại là đúng.
Tương tự như thuật toán đẩy luồng trước và thuật toán kéo luồng sau, ta có
độ phức tạp của phương pháp hỗn hợp đẩy kéo luồng là O(|V|2|E|).
2.4.2.3. Ví dụ minh họa
Tìm luồng cực đại f bằng thuật toán hỗn hợp đẩy kéo luồng của mạng đồ thị
như trong Hình 2.23. Thứ tự các đỉnh là a, b, c, d, e, f, g, h, i, z. Kết quả cân bằng
các đỉnh được biểu diễn trên các Hình 2.24 đến Hình 2.32.
o Cân bằng bQ+. Cân bằng đỉnh h Q-
o Cân bằng dQ+. Cân bằng đỉnh i Q-.
Hình 2.23. Mạng đồ thị G
b
a
d
c
e
f h
g i
z
3
2 2 2
5
2
3
2
2
2
3
3
b(4, 3, 1)
a(5, -8, 0)
d(4, 5, 1)
c(3, 0, 2)
e(3, 0, 2)
f(2, 0, 3) h(1, -3, 4)
g(2, 0, 3) i(1, -3, 4)
z(0, 6, 5)
3, 3
2, 0 2, 0 2, 0
5, 5
2, 0
3, 0
2, 0
2, 0
2, 0
3, 3
3, 3
Hàng đợi Q+ :b|d Hàng đợi Q-:h|i
Hình 2.24. Mạng đồ thị khởi tạo
b(6, 1, 1)
a(5, -8, 0)
d(4, 5, 1)
c(3, 2, 2)
e(3, 0, 2)
f(2, -2, 3) h(1, 0, 4)
g(2, -1, 3) i(1, -3, 4)
z(0, 6, 5)
3, 3
2, 2 2, 0 2, 2
5, 5
2, 0
3, 0
2, 0
2, 1
2, 0
3, 3
3, 3
Hàng đợi Q+ : b|d|c|b Hàng đợi Q-:h|i|f|g
Hình 2.25. Mạng đồ thị cân bằng b, h
50
o
o Cân bằng cQ+. Cân bằng đỉnh f Q-
o Cân bằng bQ+. Cân bằng đỉnh gQ-
o Cân bằng eQ+, tăng h(e). Cân bằng đỉnh iQ-
Hình 2.27. Mạng đồ thị cân bằng c, f
d(4, 0, 1) e(3, 3, 2) g(2, -3, 3) i(1, -1, 6)
5, 5
2, 2
Hàng đợi Q+ : b|d|c|b|e|c Hàng đợi Q-:h|i|f|g|i|
b(6, 1, 1)
a(5, -8, 0)
c(5, 2, 2) f(2, 0, 3) h(1, 0, 4)
z(0, 6, 5)
3, 3
2, 2 2, 2 2, 2
2, 2
3, 3
2, 1
2, 0
3, 3
3, 3
b(6, 0, 1)
a(5, -7, 0)
d(4, 0, 1)
c(5, 2, 2)
e(5, 1, 2)
f(2, 0, 4) h(1, 0, 4)
g(2, -1, 5) i(1, 0, 6)
z(0, 5, 5)
3, 2
2, 2 2, 2 2, 2
5, 5
2, 2
3, 3
2, 2
2, 1
2, 2
3, 3
3, 2
Hàng đợi Q+ : b|d|c|b|e|c|e Hàng đợi Q-:h|i|f|g|i|g
Hình 2.29. Mạng đồ thị cân bằng e, i
Hình 2.28. Mạng đồ thị cân bằng b, g
z(0, 6, 5)
b(6, 1, 1)
a(5, -8, 0)
d(4, 0, 1)
c(3, 4, 2)
e(3, 3, 2)
f(2, -2, 3) h(1, 0, 4)
g(2, -3, 3) i(1, -1, 6)
3, 3
2, 2 2, 0 2, 2
5, 5
2, 2
3, 3
2, 2
2, 1
2, 0
3, 3
3, 3
Hàng đợi Q+ : b|d|c|b|e Hàng đợi Q-:h|i|f|g|i
Hình 2.26. Mạng đồ thị cân bằng d, i
z(0, 6, 5)
h(1, 0, 4)
i(1, -1, 6)
3, 3
3, 3
b(6, 0, 1)
a(5, -7, 0)
d(4, 0, 1)
c(5, 2, 2)
e(3, 1, 2)
f(2, 0, 3)
g(2, -1, 5)
3, 2
2, 2 2, 2 2, 2
5, 5
2, 2
3, 3
2, 2
2, 1
2, 2
Hàng đợi Q+ : b|d|c|b|e|c
Hàng đợi Q-:h|i|f|g|i|g
51
o Cân bằng cQ+. Cân bằng gQ-
o Cân bằng eQ+. Cân bằng hQ-. Tăng d(h)=1+5=6
o Cân bằng dQ+. tăng h(d)=1+5=6 và cân bằng tiếp dQ+ và hQ-.
Q+ ,Q- đều rỗng. Kết luận luồng cực đại cần tìm là 4.
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
2.4.3.1. Giới thiệu
b(6, 0, 1)
a(5, -7, 0)
d(4, 2, 1)
c(5, 0, 2)
e(5, 1, 2)
f(2, 0, 4) h(1, -1, 4)
g(2, 0, 5) i(1, 0, 6)
z(0, 5, 5)
3, 2
2, 2 2, 2 2, 2
5, 5
2, 0
3, 3
2, 2
2, 0
2, 2
3, 3
3, 2
Hàng đợi Q+ : b|d|c|b|e|c|e|d Hàng đợi Q-:h|i|f|g|i|f|g|h
Hình 2.30. Mạng đồ thị cân bằng c, g
b(6, 0, 1)
a(5, -4, 0)
d(4, 3, 1)
c(5, 0, 2)
e(5, 0, 2)
f(2, 0, 4) h(1, -1, 6)
g(2, 0, 5) i(1, 0, 6)
z(0, 5, 5)
3, 2
2, 2 2, 2 2, 2
5, 5
2, 0
3, 2 2, 2
2,0
2, 2
3, 3
3, 2
Hàng đợi Q+ : b|d|c|b|e|c|e|d Hàng đợi Q-:h|i|f|g|i|f|g|h|h
Hình 2.31. Mạng đồ thị cân bằng e, h
b(6, 0, 1)
a(5, -4, 0)
d(6, 0, 1)
c(5, 0, 2)
e(5, 0, 2)
f(2, 0, 4) h(1, 0, 6)
g(2, 0, 5) i(1, 0, 6)
z(0, 4, 5)
3, 2
2, 2 2, 2 2, 2
5, 2
2, 0
3, 2 2, 2
2, 0
2, 2
3, 2
3, 2
Hàng đợi Q+ : b|d|c|b|e|c|e|d|d Hàng đợi Q-:h|i|f|g|i|f|g|h|h
Hình 2.32. Mạng đồ thị cân bằng d, h
52
Thuật toán đẩy luồng trước và thuật toán kéo luồng sau bắt đầu thực hiện ở
đỉnh nguồn và đỉnh đích. Vì vậy, nếu ta thực hiện song song thì việc thiết kế thuật
toán rất dễ dàng, độ phức tạp giảm so với thuật toán đẩy luồng trước là đáng kể.
Thuật toán đẩy luồng trước, kéo luồng sau và thuật toán hỗn hợp đẩy kéo
luồng đều có độ phức tạp là O(|V|2|E|). Để giảm độ phức tạp thời gian tính toán,
chúng tôi đề xuất thuật toán song song hỗn hợp đẩy kéo luồng tìm luồng cực đại.
2.4.3.2. Ý tưởng của thuật toán song song
Thuật toán song song sẽ dùng ba bộ xử lý, một bộ xử lý P0 quản lý dữ liệu,
gửi và nhận dữ liệu từ hai bộ xử lý phụ P1, P2. Trong hai bộ xử lý phụ, một bộ xử lý
P1 sẽ đẩy luồng từ Q+ và bộ xử lý P2 sẽ kéo luồng từ Q-. Các bộ xử lý phụ kết thúc
khi các Q+ và Q- là rỗng.
2.4.3.3. Xây dựng thuật toán song song
Đầu vào: Đồ thị G(V, E, c) với nguồn a, đích z, khả năng thông qua:
c= {ci, j | (i, j)E} (28)
Ba bộ xử lý P0, P1 và P2. Trong đó, P0 là bộ xử lý chính, P1 và P2 là hai bộ
xử lý phụ.
Đầu ra: Luồng cực đại:
f = {fi, j | (i, j)E} (29)
Các bước:
Bước 1: Bộ xử lý chính thực hiện.
- Bộ xử lý chính khởi tạo: h, d, e, f, c, Q+, Q-.
Bước 2: Bộ xử lý chính kiểm tra kết thúc.
- Nhận dữ liệu từ các bộ xử lý phụ (nếu các bộ xử lý phụ có gửi dữ liệu đến)
- Bộ xử lý chính kiểm tra nếu Q+, Q- là rỗng và các bộ xử lý P1 và P2 kết
thúc, thì luồng f trở thành luồng cưc̣ đaị, kết thúc.
Ngược lại sang bước 3.
Bước 3: Bộ xử lý chính thực hiện kiểm tra.
- Bộ xử lý chính lấy đỉnh u từ Q+ và y từ Q-.
- Gửi h, e, f, u, Q+ đến bộ xử lý P1. Gửi d, e, f, đỉnh y, Q- đến bộ xử lý P2
53
- Bộ xử lý chính kiểm tra: Nếu với mọi cung ưu tiên (u, v)Ef và với mọi
cung ưu tiên (x, y)Ef mà u trùng với x hoặc y trùng với v thì sang bước 5.
Ngược lại sang bước 4.
Bước 4: Bộ xử lý phụ P1 và P2 thực hiện song song các công việc sau đây:
- Hai bộ xử lý phụ nhận dữ liệu mà bộ xử lý chính P0 gửi đến.
- Bộ xử lý P1 thực hiện.
Đẩy luồng trước: lấy đỉnh lệch u từ hàng đơị Q+. Duyêṭ các cung ưu tiên
(u, v)Ef . Đẩy trên cung (u, v) môṭ luồng có giá tri ̣ min{delta, cf(u, v)}, trong
đó delta là độ lệch luồng của đỉnh u. Nếu đỉnh v là đỉnh lệch mới, thì đẩy
đỉnh v vào hàng đợi Q+.
Nếu đỉnh u vâñ còn lêc̣h, thì tăng độ cao của đỉnh u như sau:
h(u)= 1 + min{h(v) | (u, v)Ef}. Sau đó, đẩy u vào hàng đợi Q+.
Chuyển Q+, h, e, f, cf về bộ xử lý chính.
- Bộ xử lý P2 thực hiện.
Kéo luồng sau: lấy đỉnh lệch y từ Q-. Duyêṭ các cung ưu tiên (x, y) Ef . Kéo
trên cung (x, y) môṭ luồng có giá tri ̣ min{delta, cf(x, y)}, trong đó delta (< 0)
là độ lệch luồng của đỉnh y. Nếu đỉnh x là đỉnh lệch mới, thì đẩy đỉnh x vào
hàng đợi Q-.
Nếu đỉnh y vâñ còn lêc̣h, thì tăng độ sâu của đỉnh y như sau:
d(y)= 1 + min{d(x) | (x, y) Ef}. Sau đó, đẩy y vào hàng đợi Q.
Chuyển Q-, d, e, f về bộ xử lý chính.
Quay lại bước 2.
Bước 5: Hai bộ xử lý P1 và P2 thực hiện tuần tự.
- Bộ xử lý phụ P1 thực hiện
Nhận dữ liệu từ P0 gửi đến ở bước 3.
Đẩy luồng trước: lấy đỉnh lệch u từ Q+. Duyêṭ các cung ưu tiên (u, v)Ef.
Đẩy trên cung (u, v) môṭ luồng có giá tri ̣ min{delta, cf(u, v)}, (delta là độ lệch
luồng của đỉnh u). Nếu đỉnh v là đỉnh lệch mới, thì đẩy v vào Q+.
Nếu đỉnh u vâñ còn lêc̣h, thì tăng độ cao của đỉnh u như sau:
54
h(u)= 1 + min{h(v) | (u, v) Ef}. Sau đó, đẩy u vào hàng đợi Q+.
Chuyển Q+, h, e, f, về bộ xử lý chính. Chuyển e, f đến bộ xử lý P2.
- Bộ xử lý phụ P2 thực hiện.
Nhận dữ liệu từ P0 gửi đến ở bước 3 và nhận dữ liệu P1 gửi đến ở bước 5.
Kéo luồng sau:
Lấy đỉnh lệch y từ hàng đơị Q-. Duyêṭ các cung ưu tiên (x, y)Ef . Kéo trên
cung (x, y) môṭ luồng có giá tri ̣ min{delta, cf(x, y)}, trong đó delta (< 0) là
đô ̣lêc̣h luồng của đỉnh y.
Nếu đỉnh x là đỉnh lệch mới, thì đẩy đỉnh x vào hàng đợi Q-.
Nếu đỉnh y vâñ còn lêc̣h, thì tăng độ sâu của đỉnh y như sau:
d(y)= 1 + min{d(x) | (x, y)Ef}. Sau đó, đẩy y vào hàng đợi Q.
Chuyển Q-, d, e, f, về bộ xử lý chính.
Quay lại bước 2
Điṇh lý 2.5. Thuật toán song song hỗn hợp đẩy kéo luồng tìm luồng cực đại là
đúng.
Chứng minh: Ta xét hai trường hợp sau:
- Trường hợp 1: P1 và P2 thực hiện đồng thời, nghĩa là việc cân bằng các
đỉnh ở Q+ và các đỉnh ở Q- là độc lập nhau. Trong trường hợp này sẽ lấy u từ Q+ và
y từ Q- thỏa với mọi cung ưu tiên (u, v)Ef và với mọi cung ưu tiên (x, y)Ef mà u
không trùng với x và y không trùng với v để P1 và P2 cân bằng. Sau mỗi lần cân
bằng thì bộ xử lý P0 sẽ đồng bộ hóa dữ liệu của các đỉnh. Vậy từ thuật toán tuần tự
suy ra việc thực hiện song song trong trường hợp này là đúng.
- Trường hợp 2: P1 và P2 thực hiện tuần tự, nghĩa là việc cân bằng các đỉnh ở
Q+ và các đỉnh ở Q- là tuần tự, trong đó P1 thực hiện xong rồi gửi kết quả đến P2 và
P2 tiếp tục thực hiện. Trong trường hợp này sẽ lấy u từ Q+ và y từ Q- thỏa với mọi
cung ưu tiên (u, v)Ef và với mọi cung ưu tiên (x, y)Ef mà u trùng với x hoặc y
trùng với v để P1 và P2 cân bằng. Suy ra, việc kéo đẩy luồng trong trường hợp này
là đúng vì phù hợp với thuật toán tuần tự.
2.4.3.4. Ví dụ minh họa
55
Tìm luồng cực đại f trên ba bộ xử lý P0, P1, P2 của đồ thị được trình bày như
trong Hình 2.23.
Pha 1:
Bước 1: Khởi tạo h, d, e, f, c, Q+, Q- như trong thuật toán tuần tự.
Bước 2: Bộ xử lý chính kiểm tra Q+={b, d}, Q-={h, i} khác rỗng nên sang bước 3.
Bước 3: Bộ xử lý chính lấy b từ Q+ và h từ Q-. Sau đó, kiểm tra không có cung ưu
tiên (b, v)Ef và cung ưu tiên (x, h)Ef mà b trùng với x hoặc h trùng với v
nên sang bước 4.
Bước 4: P1 và P2 thực hiện song song, tức là ở P1 cân bằng đỉnh b thuộc Q+ và P2 sẽ
cân bằng đỉnh h tại Q- và có kết quả ở Hình 2.33. Các bộ xử lý phụ chuyển kết
quả về bộ xử lý chính.
Quay lại bước 2
Pha 2:
Bước 2: Bộ xử lý chính kiểm tra Q+={d, c, b}, Q-={i, f, g} khác rỗng sang bước 3.
Bước 3: Bộ xử lý chính lấy d từ Q+ và i từ Q-. Sau đó, kiểm tra không có cung ưu
tiên (d, v)Ef và cung ưu tiên (x, i)Ef mà d trùng với x hoặc i trùng với v
nên sang bước 4.
Bước 4: P1 và P2 thực hiện song song, tức là ở P1 cân bằng đỉnh d thuộc Q+ và P2
cân bằng đỉnh i tại Q- và có kết quả ở Hình 2.34. Các bộ xử lý phụ chuyển
kết quả về bộ xử lý chính.
Quay lại bước 2.
b(6, 1, 1)
a(5, -8, 0)
d(4, 5, 1)
c(3, 2, 2)
e(3, 0, 2)
f(2, -2, 3) h(1, 0, 4)
g(2, -1, 3) i(1, -3, 4)
z(0, 6, 5)
3, 3
2, 2 2, 0 2, 2
5, 5
2, 0
3, 0 2, 0
2, 1
2, 0
3, 3
3, 3
Hàng đợi Q+ : b|d|c|b Hàng đợi Q-:h|i|f|g
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
56
Pha 3:
Bước 2: Bộ xử lý chính kiểm tra Q+={c, b, e}, Q-={f, g, i} khác rỗng sang bước 3.
Bước 3: Bộ xử lý chính lấy c từ Q+ và f từ Q-. Sau đó kiểm tra có đẩy cung ưu tiên
(c, f)Ef và kéo cung ưu tiên (c, f)Ef, 2 cung này trùng nhau qua bước 5.
Bước 5: P1, P2 thực hiện tuần tự, tức là P1 cân bằng đỉnh c thuộc Q+ trước rồi gửi
kết quả đến P2 và P2 sẽ cân bằng đỉnh f tại Q- và có kết quả ở Hình 2.35. Các
bộ xử lý phụ P2 chuyển kết quả về bộ xử lý chính, sau đó quay lại bước 2.
Tương tự như vậy thuật toán kết thúc sau khi thực hiện xong pha 9.
Pha 4: P1, P2 thực hiện đồng thời. P1 cần bằng đỉnh b thuộc Q+, P2 sẽ cân bằng đỉnh
g tại Q-
Pha 5: P1, P2 thực hiện đồng thời. P1 cần bằng đỉnh e thuộc Q+, P2 sẽ cân bằng đỉnh
i tại Q-.
Pha 6: P1, P2 thực hiện đồng thời. P1 cần bằng đỉnh c thuộc Q+, P2 sẽ cân bằng đỉnh
g tại Q-.
Pha 7: P1, P2 thực hiện đồng thời. P1 cần bằng đỉnh e thuộc Q+, P2 sẽ cân bằng đỉnh
b(6, 1, 1)
a(5, -8, 0)
d(4, 0, 1)
c(3, 4, 2)
e(3, 3, 2)
f(2, -2, 3) h(1, 0, 4)
g(2, -3, 3) i(1, -1, 6)
z(0, 6, 5)
3, 3
2, 2 2, 0 2, 2
5, 5
2, 2
3, 3 2, 2
2, 1
2, 0
3, 3
3, 3
Hàng đợi Q+ : b|d|c|b|e Hàng đợi Q-:h|i|f|g|i
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
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
d(4, 0, 1) e(3, 3, 2) g(2, -3, 3) i(1, -1, 6)
5, 5
2, 2
Hàng đợi Q+ : b|d|c|b|e|c Hàng đợi Q-:h|i|f|g|i
b(6, 1, 1)
a(5, -8, 0)
c(5, 2, 2) f(2, 0, 3) h(1, 0, 4)
z(0, 6, 5)
3, 3
2, 2 2, 2 2, 2
2, 2
3, 3
2, 1
2, 0
3, 3
3, 3
57
h tại Q-.
Pha 8: P1, P2 thực hiện đồng thời. P1 cần bằng đỉnh d thuộc Q+, P2 sẽ cân bằng đỉnh
h tại Q-. Q- =∅.
Pha 9: P1 cần bằng đỉnh d thuộc Q+. Q+ =∅. Kết thúc.Suy ra luồng cực đại f=4.
2.4.3.5. Kết quả thực nghiệm
a. Dữ liệu thực nghiệm
Dữ liệu thực nghiệm được tạo ngẫu nhiên có cấu trúc giống như trong thuật
toán song song đẩy luồng trước được trình bày mục 2.3.2.6.
b. Môi trường thực nghiệm.
Chúng tôi thực nghiệm trên hệ thống đa bộ xử lý với cấu trúc gồm một bộ xử
lý chính được gọi Server và các bộ xử lý phụ được gọi là Client. Các bộ xử lý có
cấu hình gần tương đương nhau là cấu hình Intel Core Dual T2450, bộ nhớ 1G.
Thuật toán được cài đặt bằng ngôn ngữ Java hệ điều hành Win 7 với hệ quản trị cơ
sơ MySQL.
Hình 2.36. Giao diện Client
58
c. Kết quả thực nghiệm
Kết quả thực nghiệm để kiểm tra tính đúng đắn của mạng đồ thị như trong
Hình 2.23 được biểu diễn bằng giao diện như trong Hình 2.36 và Hình 2.37. Chúng
tôi tạo ngẫu nhiên mạng đồ thị gồm 5500 và 7500 với độ giãn nở khác nhau và cho
thử nghiệm thực toán tuần tự và song song trên 2 bộ xử lý thì kết quả thực hiện song
song có thời gian giảm so với thuật toán tuần tự, cụ thể là 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ự đối với mạng đồ thị
5500 đỉnh và 7500 đỉnh tương ứng là 1.62 và 1.79.
Hình 2.37. Giao diện Server
59
d. Nhận xét
Thuật toán song song làm giảm thời gian đáng kể so với thuật toán tuần tự
được thể hiện qua mức độ tăng tốc của 2 mạng đồ thị nêu trên. Việc tính toán của
thuật toán đẩy luồng trước và kéo luồng sau là độc lập nhau nên việc xử lý song
song chỉ làm chậm thời gian khi các bộ xử lý thực hiện đồng thời. Vì vậy, mức độ
tăng tốc càng lớn (thời gian càng giảm) khi dữ liệu đầu vào là lớn. Tuy nhiên, mức
độ tăng tốc cũng phụ thuộc vào độ giãn nở của đồ thị.
2.4.3.6. Kết luận
Từ thuật toán đẩy luồng trước và thuật toán kéo luồng sau, chúng tôi đã đề
xuất thuật toán mới: thuật toán hỗn hợp đẩy kéo luồng tìm luồng cực đại. Hơn nữa,
để giảm thời gian tính toán thì thuật toán song song tìm luồng cực đại dựa trên thuật
toán hỗn hợp được đề xuất. Chúng tôi chứng minh chi tiết các định lý, mệnh đề liên
quan đến thuật toán và phần thực nghiệm cho kết quả chính xác và thuật toán song
song giảm thời gian so với thuật toán tuần tự.
2.5. Kết luận chƣơng
Trong chương hai, chúng tôi đã trình bày chi tiết thuật toán tuần tự đẩy luồng
trước được kế thừa từ các nghiên cứu đã có và đề xuất thuật toán hỗn hợp đẩy kéo
luồng tìm luồng cực đại. Từ đó, chúng tôi tối ưu thuật toán song song đẩy luồng
trước và đề xuất thuật toán song song hỗn hợp đẩy kéo luồng tìm luồng cực đại. Các
thuật toán song song được đề xuất cụ thể, rõ ràng. Các định lý, mệnh đề và hệ quả
liên quan đến các thuật toán đều được chứng minh rõ ràng. Các thuật toán song
song đều phân tích thời gian tính toán. Đặc biệt, nội dung chính của chương này
được chúng tôi công bố trong 3 bài báo chuyên ngành Công nghệ Thông tin và
được liệt kê ở tài liệu [1], [3], [4] trong danh mục các công trình của tác giả.
60
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
Các thuật toán tuần tự tìm đường đi ngắn nhất trên đồ thị mở rộng đã được
nghiên cứu trong [9], [22], [27] và thuật toán tuần tự tìm luồng cực đại chi phí giới
hạn trên mạng giao thông mở rộng được nghiên cứu trong [14], [27]. Trong thực tế,
khi dữ liệu đầu vào lớn thì thời gian thực hiện rất lớn. Vì vậy, để giảm thời gian tính
toán cho các thuật toán trên chúng tôi đề xuất hai thuật toán song song tương ứng
cho hai thuật toán tuần tự trên. Nội dung chính trong chương này, chúng tôi đề xuất
chi tiết hai thuật toán song song: tìm đường đi ngắn nhất trên đồ thị mở rộng và tìm
luồng cực đại chi phí giới hạn trên mạng giao thông mở rộng.
3.1. Đồ thị mở rộng
Cho đồ thị hỗn hợp G(V, E) với tập đỉnh V và tập cạnh E, trong đó các cạnh
có thể có hướng hoặc vô hướng. Mỗi cạnh eE được gán trọng số wE(e). Với mỗi
đỉnh vV, ký hiệu Ev là tập các cạnh liên thuộc đỉnh v. Mỗi đỉnh v V và mỗi cạnh
(e, e
‟
)EvEv, e≠e‟ được gán trọng số wV(v, e, e‟).
Bộ (V, E, wE, wV) gọi là đồ thị mở rộng. Cho p là đường đi từ u đến v qua các
cạnh ei, i=1,,h+1, và các đỉnh ui, i=1,,h như sau:
p=[ u, e1, u1, e2, u2, , eh, uh, eh+1, v]
Định nghĩa độ dài đường đi p, ký hiệu l(p), theo công thức sau:
(30)
Bài toán tìm đường đi ngắn nhất:
Cho đồ thị mở rộng G=(V, E, wE, wV) và các đỉnh s, tV. Tìm đường đi ngắn
nhất từ s đến t.
3.2. Thuật toán tìm đƣờng đi ngắn nhất trên đồ thị mở rộng
3.2.1. Thuật toán tuần tự
h
i
iiiV
h
iE eeuwewpl
i 1
1
1
1
),()()( ,
61
3.2.1.1. Giới thiệu
Thuật toán tìm đường đi ngắn nhất trên đồ thị là thuật toán cơ sở được rất
nhiều nhà khoa học trong và ngoài nước nghiên cứu cả về tuần tự và song song
[23], [29], [38], [43], [44], [46]. Hơn nữa, thuật toán này cũng được sử dụng để giải
các bài toán luồng cực đại trên mạng đồ thị [10], [11], [12], [13], [16], [24], [25].
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 đó. Do đó, cần xây dựng một mô hình đồ thị mở rộng để có thể áp dụng
mô hình hóa các bài toán thực tế chính xác và hiệu quả hơn. Đồng thời, sử dụng
thuật toán này để xây dựng nhiều bài toán tối ưu trên mạng đồ thị mở rộng như: ứng
dụng để tìm luồng cực đại trên mạng mở rộng [17], [30], [31], [32], [33], ứng dụng
để xây dựng bài toán phân luồng tối ưu [15], [18], [20] và ứng dụng để xây dựng
thuật toán tìm luồng cực đại chi phí giới hạn [14], [19], [21]. Trên thế giới cũng có
nhiều nhà khoa học nghiên cứu đến trọng số của đỉnh [74], [75], [76], [77], nhưng
cách tiếp cận này không ứng dụng để xây dựng được các thuật toán tối ưu trên
mạng mở rộng. Trong phần tiếp theo, chúng tôi sẽ kế thừa các nghiên cứu trong [9],
[22], [27] để trình bày lại thuật toán tuần tự.
3.2.1.2. Xây dựng thuật toán
- Đầu vào: Đồ thị mở rộng G(V, E, wE, wV), và các đỉnh s, tV.
- Đầu ra: l(t) là chiều dài đường đi ngắn nhất từ s đến t và đường đi ngắn nhất (nếu
l(t) <+∞).
- Các bước:
Thuậ
Các file đính kèm theo tài liệu này:
luan_an_song_song_hoa_cac_thuat_toan_tren_mang_do_thi_nguyen.pdf
