TS. Ngô Văn Thanh, Viện Vật lý.
Chuyên ngành : Công nghệ thông tin. http://iop.vast.ac.vn/~nvthanh/cours/parcomp/
Chương 4: Các thuật toán song song
4.1 Mô hình PRAM 4.2 Các thuật toán song song nhân hai ma trận 4.3 Các thuật toán sắp xếp song song 4.4 Tìm kiếm trên danh bạ 4.5 Các thuật toán song song trên đồ thị
4.5.1 Tìm đường đi ngắn nhất.
4.5.2 Tìm cây khung bé nhất.
4.6 Các thuật toán song song tìm kiếm tổ hợp.
@2009, Ngô Văn Thanh -Viện Vật Lý
4.1 Mô hình PRAM
PRAM: "Parallel random access machine" được đưa ra bởi Fortune và Wyllie
Mô hình PRAM là một mô hình thuộc hệ bộ nhớ chia sẻ (shared memory). Mục đích: xây dựng mô hình lý thuyết để diễn tả và phân tích các thuật toán. Dựa trên mô hình này, chúng ta có thể đánh giá mức độ phức tạp một bài
vào năm 1978.
Mô hình PRAM bao gồm:
Bộ điều khiển trung tâm.
toán.
Bộ nhớ dùng chung (global memory) p processors P1, P2,… Pp. Mỗi một processor có thể có
(control unit)
@2009, Ngô Văn Thanh -Viện Vật Lý
một bộ nhớ riêng. (private memory)
Các processor sẽ thực hiện một vòng đồng bộ: đọc – tính toán - ghi. (read-
Trong mỗi bước tính một processor hoạt động (active processor) có thể đọc dữ
compute-write).
liệu từ bộ nhớ riêng, xử lý dữ liệu và ghi kết quả trở lại lên bộ nhớ riêng. Tất cả các active processor cần phải thực hiện cùng một câu lệnh trên các
Mô hình PRAM còn được gọi là máy tính có bộ nhớ dùng chung và xử lý một
dòng lệnh trên nhiều phần dữ liệu: SM SIMD (shared memory, single instruction, multiple data).
Các thuật toán hoạt động độc lập với nhau và nó chỉ thực hiện trên một vùng
phần dữ liệu khác nhau.
Atomic: một công việc được gọi là atomic nếu như nó thực hiện xong hoàn
bộ nhớ mà nó được phép truy nhập tại mỗi thời điểm.
Các kiểu điều khiển quá trình đọc và viết trong PRAM
Exclusive read (ER) – chỉ đọc: chỉ có một processor được phép đọc tất cả các
vùng trên bộ nhớ dùng chung tại mỗi thời điểm.
Exclusive write (EW) – chỉ ghi: chỉ có một processor được phép ghi lên tất cả
toàn, hoặc là không thực hiện gì cả.
@2009, Ngô Văn Thanh -Viện Vật Lý
các vùng trên bộ nhớ dùng chung tại mỗi thời điểm.
Concurrent read (CR) – đọc đồng thời: nhiều processor được phép đọc cùng
Concurrent write (CW) – ghi đồng thời: nhiều processor được phép ghi đồng
một vùng trên bộ nhớ dùng chung tại mỗi thời điểm.
Common (thông thường): tất cả các quá trình concurrent write ghi cùng một giá trị dữ liệu. Arbitrary (bất kỳ): chỉ một giá trị nào đó được ghi lại, bỏ qua các giá trị khác. Minimum (tối thiểu) : Chỉ một processor nào đó có chỉ số bé nhất được phép ghi, các giá trị khác bị loại bỏ. Reduction (rút gọn): Tất cả các giá trị được rút gọn lại thành một giá trị duy nhất và được ghi lên bộ nhớ. Phép rút gọn các giá trị phải được thực hiện một trong những hàm như tổng (sum), tích (product), cực đại (maximum)…
Các lớp con của mô hình PRAM:
EREW PRAM: một processor đọc, một processor ghi. ERCW PRAM: một processor đọc, nhiều processor ghi. CREW PRAM: nhiều processor đọc, một processor ghi. CRCW PRAM: nhiều processor đọc, nhiều processor ghi.
@2009, Ngô Văn Thanh -Viện Vật Lý
thời lên cùng một vùng trên bộ nhớ dùng chung tại mỗi thời điểm. Sự xung đột giữa các quá trình ghi dữ liệu được giải quyết theo các quy ước (policy):
Truy cập đa luồng trên mô hình EREW PRAM.
Tại mỗi thời điểm chỉ có một processor được phép ghi hoặc đọc dữ liệu trên
Thuật toán Broadcast_EREW: nhằm thực hiện quá trình truy cập đồng thời
một vùng nhớ đã chọn.
Giả thiết: địa chỉ của một vùng nhớ là x, và quá trình đọc song song được
của nhiều processor trên một vùng nhớ.
Xét ví dụ p = 8 processor
L[p] : mảng vùng nhớ dùng chung P1 đọc giá trị x từ vùng nhớ riêng, sau đó ghi lên mảng L[1]. P1 đọc giá trị x từ L[1], ghi vào bộ nhớ riêng đồng thời ghi lên L[2]…
@2009, Ngô Văn Thanh -Viện Vật Lý
thực hiện trên các processors. P1 đọc giá trị x, sau đó chuyển cho P2. P1 và P2 chuyển tiếp một cách đồng thời cho P3 và P4 P1, P2, P3, P4 lại chuyển tiếp đồng thời đến P5, P6, P7, P8.
Thuật toán Broadcast_EREW: Algorithm Broadcast_EREW Processor P1
y (in P1’s private memory) x L[1] y
for i=0 to log (p – 1) do
y (in Pj’s private memory) L[j-2i] L[j] y
forall Pj, where 2i + 1 j 2i+1 do in parallel
endfor
@2009, Ngô Văn Thanh -Viện Vật Lý
endfor
Thuật toán tính tổng (sum).
Tính tổng của các phần tử trong mảng A[1..n].
Tính tổng n phần tử của một mảng trong mô hình EREW.
Giả thiết n là một số lũy thừa của 2, ví dụ: 4, 8, 16, 32,…
Số processor cần sử dụng :
Số vòng lặp : log n
Algorithm Sum_EREW
for i=1 to log n do
forall Pj, where 1 j n/2 do in parallel
if (2j modulo 2i)=0 then
endif
A[2j] A[2j] + A[2j-2i-1]
endfor
@2009, Ngô Văn Thanh -Viện Vật Lý
endfor
Bước 1: cả 4 processor cùng tính tổng hai phần tử trong mảng
Các kết quả được ghi vào vị trí trong mảng: 2, 4, 6, 8
Bước 2: processor P2 và P4 thực hiện phép tổng và ghi lại kết quả vào A[4] và A[8]
Bước 3: processor P4
thực hiện phép tổng và ghi lại kết quả vào A[8]
@2009, Ngô Văn Thanh -Viện Vật Lý
Hạn chế: có nhiều processor không làm việc sau khi đã thực hiện xong một phần công việc của mình.
Tính tổng các phần của mảng n phần tử trong mô hình EREW.
Số processor cần sử dụng : p = n - 1 Tất cả các processor đều hoạt động.
Algorithm AllSums_EREW for i=1 to log n do
forall Pj, where 2i-1 + 1 j n do in parallel
A[j] A [j] + A[j – 2i-1]
endfor
@2009, Ngô Văn Thanh -Viện Vật Lý
endfor
4.2 Các thuật toán song song nhân hai ma trận
@2009, Ngô Văn Thanh -Viện Vật Lý
Mô hình sử dụng n3 processors.
Xét bài toán nhân hai ma trận có kích thước n × n Giả thiết hai ma trận: A[1..n, 1..n] và B[1..n, 1..n] đã được nạp vào bộ nhớ
Giả sử các processor được sắp xếp vào một mảng 3 chiều Pi,j,k với 1 i, j, k n Mảng C[i, j, k] với 1 i, j, k n Kết quả của phép nhân ma trận chỉ là C[i, j, n] với 1 i, j n Thuật toán để giải bài toán tích hai ma trận được chia thành 2 bước:
Mỗi một processor Pi,j,k thực hiện phép nhân A[i, k]*B[k, j] và được lưu lại trong mảng C[i, j, k]. Tất cả các processor thực hiện một cách đồng thời.
Áp dụng n2 lần thuật toán tính tổng Sum_EREW theo chiều k (chiều thứ 3)
dùng chung.
@2009, Ngô Văn Thanh -Viện Vật Lý
của mảng C[i, j, k] sau đó lưu kết quả vào C[i, j, n] với 1 i, j n.
Xét bài toán nhân hai ma trận có kích thước n × n
Algorithm MatMult_CREW /* Step 1 */ forall Pi,j,k, where 1 i, j, k n do in parallel
C[i,j,k] A[i,k]*B[k,j]
endfor /* Step 2 */ for m = 1 to log n do
forall Pi,j,k, where 1 i, j n & 1 k n/2
do in parallel if (2k modulo 2m)=0 then
C[i,j,2k] C[i,j,2k] + C[i,j, 2k – 2m-1]
endif
/* Kết quả C[i,j,n], where 1 i,j n */ endfor
@2009, Ngô Văn Thanh -Viện Vật Lý
endfor
@2009, Ngô Văn Thanh -Viện Vật Lý
@2009, Ngô Văn Thanh -Viện Vật Lý
Chia ma trận thành các ma trận con.
Chia mỗi ma trận a[n, n] và b[n, n] thành s2 ma trận con. Các ma trận con : A[n/s, n/s] và B[n/s, n/s]
for (p=0; p < s; p++)
for (q=0; q < s; q++){
C[p,q] = 0;
for (r=0; r C[p,q] = C[p,q] + A[p,r]*B[r,q] }
Trong đó tích hai ma trận A[p,r]*B[r,q] và phép tính tổng được áp dụng @2009, Ngô Văn Thanh -Viện Vật Lý thuật toán tính song song trên các ma trận con. @2009, Ngô Văn Thanh -Viện Vật Lý Thuật toán tính trực tiếp với n2 processors. Mỗi một processor Pi,j được dùng để tính cho một phần tử Ci,j.
Processor Pi,j cần phải có dữ liệu của hàng thứ i của ma trận A và cột thứ j Dữ liệu được gửi từng phần riêng biệt cho các processor. @2009, Ngô Văn Thanh -Viện Vật Lý của ma trận B. Thuật toán tính cấu trúc cây với n processors. @2009, Ngô Văn Thanh -Viện Vật Lý Thuật toán đệ quy. matMult(A, B, s){
if ( s == 1)
C = A * B else{ s =s/2
P0 = matMult (A[p,p], B[p,p], s);
P1 = matMult (A[p,q], B[q,p], s);
P2 = matMult (A[p,p], B[p,q], s);
P3 = matMult (A[p,q], B[q,q], s);
P4 = matMult (A[q,p], B[p,p], s);
P5 = matMult (A[q,q], B[q,p], s);
P6 = matMult (A[q,p], B[p,q], s);
P7 = matMult (A[q,q], B[q,q], s);
C[p,p] = P0 + P1;
C[p,q] = P2 + P3;
C[q,p] = P4 + P5;
C[q,q] = P6 + P7;
} @2009, Ngô Văn Thanh -Viện Vật Lý } @2009, Ngô Văn Thanh -Viện Vật Lý 4.3 Các thuật toán sắp xếp song song
Sắp xếp theo vị trí (rank sort) Xét một dãy hỗn độn gồm n phần tử a1, a2, …, an.
Vị trí của một phần tử ai trong dãy các phần tử đã sắp xếp được xác định bởi Nếu có hai hay nhiều phần tử bằng nhau thì thứ tự sắp xếp dựa trên chỉ số số các phần từ bé hơn nó.
Ví dụ: có ci phần tử bé hơn ai thì phần tử ai có số thứ tự là ci + 1. Đoạn mã chương trình tuần tự của các phần tử đó. Phần tử có chỉ số lớn hơn được xem là có giá trị lớn hơn.
Ví dụ: giả sử ta có hai số ai = aj, nếu i > j thì ta xem như ai > aj. for (i=0; i if (a[i] > a[j]) x++; x=0;
for (j=0; j b[x] = a[i]; @2009, Ngô Văn Thanh -Viện Vật Lý } Đoạn mã chương trình song song sử dụng n processor. forall (i=0; i x=0;
for (j=0; j if (a[i] > a[j]) x++; b[x] = a[i]; Thuật toán sắp xếp đơn giản, sử dụng mô hình PRAM kiểu CRCW. Sử dụng n2 processors được phân bố dạng mảng hai chiều Pi, j với i là chỉ số hàng và j là chỉ số cột. Sử dụng hai mảng một chiều A[1 . . n] và C[1 . . n].
Mảng A[1 . . n] dùng để lưu kết quả trên bộ nhớ dùng chung của dãy các } Mảng C[1 . . n] dùng để lưu số các phần tử bé hơn cho mỗi một phần tử phần tử sẽ được sắp xếp. @2009, Ngô Văn Thanh -Viện Vật Lý trong mảng A[1 . . n]. Thuật toán chia thành hai bước: Mỗi hàng processors thứ i tính giá trị C[i] là số các phần tử bé hơn A[i]. Mỗi Processor đầu tiên trong mỗi hàng Pi, 1, đưa A[i] vào vị trí của nó trong dãy processor Pi, j so sánh A[i] and A[j], rồi cập nhật giá trị của C[i]. được sắp xếp, (vị trí C[i] + 1). Algorithm Sort_CRCW
/* Step 1 */
forall Pi,j, where 1 i, j n do in parallel if A[i] > A[j] or (A[i] = A[j] and i > j) then C[i] 1 else C[i] 0 endif endfor
/* Step 2 */
forall Pi,1, where 1 i n do in parallel A[C[i] + 1] A[i] @2009, Ngô Văn Thanh -Viện Vật Lý endfor @2009, Ngô Văn Thanh -Viện Vật Lý Đoạn mã chương trình tuần tự if (a > b){
tmp = A;
A = B;
B = tmp; }
Sử dụng kiểu message passing để tính toán song song. Kiểu tính toán song song không đối xứng.
Chu trình P1 gửi số A cho P2.
Chu trình P2 so sánh giá trị của A với B. Nếu B > A thì gửi giá trị B đến P1, ngược lại
nếu B < A thì gửi số A trở lại cho P1. Mã chương trình:
Trên P1: Trên P2: send(&A, P2);
recv(&A, P2);
recv(&A, P1);
if (A > B){ send(&B, P1);
B = A; }
else send(&A, P1); @2009, Ngô Văn Thanh -Viện Vật Lý Sắp xếp kiểu so sánh và tráo đổi. Kiểu tính toán song song đối xứng. Mỗi một chu trình gửi số của nó đến một chu trình khác.
Tất cả các process đều so sánh giá trị của A với B. Trên P1 nếu A > B thì đặt Mã chương trình:
Trên P1: send(&A, P2);
recv(&B, P2); giá trị A = B , ngược lại trên P2 nếu A > B thì đặt B = A. Trên P2: if (A > B) A = B recv(&A, P1); Hạn chế: Dễ bị hiện tượng deadlock @2009, Ngô Văn Thanh -Viện Vật Lý send(&B, P1);
if (A > B) B = A; @2009, Ngô Văn Thanh -Viện Vật Lý Sắp xếp kiểu chia nhỏ dữ liệu Thông thường số các phần tử trong dãy cần sắp xếp lớn hơn rất nhiều so với @2009, Ngô Văn Thanh -Viện Vật Lý số processors. Lúc đó mỗi một processor sẽ làm việc trên một dãy con.
Mỗi một processor nối dãy con của nó với một dãy con khác nhận từ một
processor khác. Sau đó sắp xếp dãy đó, cuối cùng là giữ lại một nửa trên
hoặc nửa dưới của dãy chung. Sắp xếp kiểu bubble. Đơn giản nhung có hiệu quả cao.
Đoạn chương trình tuần tự: for (i = n-1; i>0; i--) for (j = 0; j } k = j+1;
if (a[j] > a[k]){
tmp = a[j];
a[j] = a[k];
a[k] = tmp; Sau mỗi vòng lặp j này sẽ tìm số lớn nhất trong các phần tử có chỉ số từ 0 đến i và chuyển về cuối dãy tại vị trí thứ i. Mỗi vòng lặp i sẽ lặp lại quá trình trên để thu được một dãy được sắp xếp } @2009, Ngô Văn Thanh -Viện Vật Lý hoàn chỉnh Chương trình tính song song kiểu chẵn-lẻ:
Đối với giai đoạn chẵn (0, 2, 4, 6,...) Pi (i=1,3,..; odd):
send(&A, P(i-1));
recv(&newA, P(i-1)); Pi (i=0,2,..; even):
recv(&newA, P(i+1));
send(&A, P(i+1));
if(newA < A) A = newA; if(newA > A) A = newA; Đối với giai đoạn lẻ (1, 3, 5, 7,...) Pi (i=1,3,..; odd):
send(&A, P(i+1));
recv(&newA, P(i+1)); Pi (i=2,4,..; even):
recv(&newA, P(i-1));
send(&A, P(i-1));
if(newA > A) A = newA; if(newA < A) A = newA; @2009, Ngô Văn Thanh -Viện Vật Lý Sắp xếp kiểu Sheresort : Ứng dụng cho mảng 2 chiều Sắp xếp theo từng hàng.
Sau đó sắp xếp theo từng cột.
Có thể dùng phương pháp chuyển vị ma trận để chuyển hàng thành cột @2009, Ngô Văn Thanh -Viện Vật Lý Phương pháp chuyển vị ma trận @2009, Ngô Văn Thanh -Viện Vật Lý Sắp xếp kiểu Mergesort. Chia dãy số thành Sắp xếp các dãy con. Trộn các dãy con. @2009, Ngô Văn Thanh -Viện Vật Lý các dãy con. @2009, Ngô Văn Thanh -Viện Vật Lý Trộn hai dãy đã được sắp xếp theo kiểu chẵn lẻ. @2009, Ngô Văn Thanh -Viện Vật Lý 4.4 Tìm kiếm trên danh bạ @2009, Ngô Văn Thanh -Viện Vật Lý Các định nghĩa: Đồ thị vô hướng G(V, E): V : là tập hợp các điểm hay các đỉnh.
E : là tập hợp các cạnh vô hướng.
Cạnh (u, v): có nghĩa là đỉnh u và v được nối với nhau. Đồ thị có hướng : Các cạnh trong tập E là cạnh có hướng hay các mũi tên.
Cạnh (u, v): có nghĩa là có một kết nối từ đỉnh u sang v.
Các đỉnh nằm hai đầu của một cạnh được gọi là kề nhau.
Đường đi (path): đường đi từ đỉnh v sang u là một chuỗi Độ dài của đường đi được định nghĩa bởi số các cạnh @2009, Ngô Văn Thanh -Viện Vật Lý trong đường đi. Nếu như có một đường đi từ u sang v thì u được xem như có thể tới được v.
Một đường đi đơn nếu như tất cả các đỉnh của nó không trùng nhau.
Một đường đi có kiểu vòng tròn (đường đi kín) nếu như đỉnh đầu và đỉnh Một đồ thị không có đường đi kín thì gọi là đồ thị không kín (đồ thị hở).
Vòng kín đơn nếu như các đỉnh trung gian của nó không trùng nhau. Đồ thị con: Đồ thị cây (tree): là một đồ thị kết nối từ các cuối của nó trùng nhau. Trọng số: là một số thực thể hiện cho chi phí đi lại trên đồ thị hở. Trọng số của đồ thị bằng tổng các trọng số của các cạnh.
Trọng số của đường đi bằng tổng các trọng số của các cạnh trên đường đi đó. @2009, Ngô Văn Thanh -Viện Vật Lý mỗi cạnh của đồ thị. Đồ thị có dạng G(V, E, w). Biểu diễn đồ thị qua ma trận kề: Xét một đồ thị G(V, E ) có n đỉnh được đánh số từ 1 đến n.
Ma trận kề của đồ thị được định nghĩa dưới dạng mảng A(ai,j) hai chiều n n: nếu Đối với đồ thị trọng số, ma trận kề có dạng: cho các trường hợp khác. nếu nếu i = j Kích thước không gian để lưu ma trận kề là @2009, Ngô Văn Thanh -Viện Vật Lý cho các trường hợp khác. Biểu diễn đồ thị qua chuỗi kề: Xét một đồ thị G(V, E ) có n đỉnh được đánh số từ 1 đến n.
Chuỗi kề của đồ thị là một mảng n phần tử A[v], Kích thước không gian để lưu chuỗi kề là @2009, Ngô Văn Thanh -Viện Vật Lý mỗi phần tử v V là một chuỗi gồm các đỉnh kề của v. 4.5.2 Tìm cây khung bé nhất (Prim's Algorithm)
Cây khung : đó là một đồ thị con của một đồ thị cây G mà nó chứa tất cả các Đối với đồ thị trọng số thì trọng số của cây khung bằng tổng trọng số của các đỉnh của G. Cây khung bé nhất (MST minimum spanning tree) của một đồ thị vô hướng là đường đi trong đồ thị con đó. @2009, Ngô Văn Thanh -Viện Vật Lý một cây khung có trọng số bé nhất. Thuật toán Prim: Chọn một đỉnh bất kỳ trong G làm đỉnh ban đầu.
Chọn một đỉnh tiếp theo với chi phí đường đi thấp nhất so với đỉnh ban đầu
Nối đỉnh vừa tìm được vào cây khung. Cụ thể: Đỉnh r được chọn lúc đầu gọi là gốc của cây khung: d [r] = 0.
Tất cả các đỉnh v (V – VT), Lặp lại việc tìm kiếm đó cho đến khi tất cả các đỉnh được chọn.
Xét một đồ thị trọng số G(V, E, w) với ma trận kề trọng số A(ai,j).
Sử dụng một mảng VT là các đỉnh của cây khung bé nhất.
Một mảng d [1..n] .Tương ứng với mỗi đỉnh v (V – VT), d [v] là trọng số
của một cạnh nào đó có giá trị bé nhất trong các trọng số giữa đỉnh v và
các đỉnh còn lại trong VT. Trong quá trình tính lặp, đỉnh u được thêm vào mảng VT nếu như chi phí d [v] = w(r, v) nếu như đường đi từ r đến v tồn tại.
d [v] = nếu như đường đi từ r đến v không tồn tại. @2009, Ngô Văn Thanh -Viện Vật Lý đường đi d[u] = min{d[v]|v (V - VT)}. Chọn đỉnh b: VT = {b}
Dựa vào ma trận trọng số, đưa ra mảng vì (d, b) = 1, và (c, b) = 5 (a, b) =1, d[1, 0, 5, 1, , ] Có hai giá trị trọng số bé nhất tương ứng với đỉnh a và d
Chọn đỉnh d, VT = {b,d}, đưa ra mảng trọng số d[1, 0, 2, 1, 4, ] (e, b) = , và (f, b) = . d[a] = 1 vì trọng số (b, a) = 1, (a, d) = .
d[b] = 0 : gốc của cây. // không cần tính
d[c] = 2 : vì trọng số (c, b) = 5, (c, d) = 2.
d[d] = 1 : không đổi.
d[e] = 4 : vì trọng số (e, b) = ,
(e, d) = 4.
d[f] = : vì trọng số (f, b) = Chọn đỉnh tiếp theo là a và (f, d)= . @2009, Ngô Văn Thanh -Viện Vật Lý vì d[a] = 1 có chi phí thấp nhất. Chọn đỉnh a; VT = {b,d,a}, đưa ra mảng trọng số d [1, 0, 2, 1, 4, 3] Cuối cùng chọn đỉnh c đưa vào cây khung. @2009, Ngô Văn Thanh -Viện Vật Lý d[a] = 1 : không đổi.
d[b] = 0 : gốc của cây. // không cần tính
d[c] = 2 : vì trọng số (c, b) = 5, (c, d) = 2 và (c, a) = 3.
d[d] = 1 : không đổi.
d[e] = 4 : vì trọng số (e, b) = , (e, a) = và (e, d) = 4.
d[f] = 3 : vì trọng số (f, b) = , (f, a) = 3 và (f, d)= . Chọn đỉnh c; VT = {b,d,a,c}, đưa ra mảng trọng số d [1, 0, 2, 1, 1, 3] d[a] = 1 : không đổi.
d[b] = 0 : gốc của cây. // không cần tính
d[c] = 2 : không đổi.
d[d] = 1 : không đổi.
d[e] = 4 : vì trọng số (e, b) = , (e, a) = , (e, d) = 4, và (e, c) = 1. d[f] = 3 : vì trọng số (f, b) = , (f, a) = 3 và (f, d)= , Cuối cùng chọn đỉnh e đưa vào cây khung, tất nhiên là phần tử cuối là f @2009, Ngô Văn Thanh -Viện Vật Lý và (f, c) = . Thuật giải Prim:
procedure PRIM_MST(V, E, w, r)
{ VT = {r};
d[r] = 0;
for all v (V - VT) if (cạnh (r, v) tồn_tại) d[v] = w(r, v);
else d[v] = ; Tìm đỉnh u sao cho d[u] = min{d[v]|v (V - VT)};
VT = VT {u};
for all v (V - VT) do while VT V do
{ } d[v] = min{d[v], w(u, v)}; @2009, Ngô Văn Thanh -Viện Vật Lý } Tính song song cho thuật toán Prim: Giả thiết hệ có n đỉnh, chương trình song song được thực hiện trên p Tập hợp các đỉnh của V được chia thành các tập con gồm n/p phần tử.
Mỗi một tập con được gán để tính trên một processor.
Mỗi một processor Pi giữ một tập con di,
di[u] = min{d[v]|v (V - VT) Vi};
Sử dụng hàm reduction để tìm giá trị
bé nhất trong các di[u], và kết
quả này được lưu trên P0. Processor P0 nhận đỉnh u mới tìm được
và chèn vào mảng VT. Sau đó sử dụng
broadcast để gửi đỉnh u cho tất cả các
processor khác. Mỗi một processor phải lưu các cột
tương ứng của ma trận trọng số. @2009, Ngô Văn Thanh -Viện Vật Lý processors. 4.5.1 Tìm đường đi ngắn (Dijkstra's Algorithm). Đường đi ngắn nhất từ một đỉnh đơn: Xét một đồ thị trọng số G(V, E, w).
Đường đi ngắn nhất từ một đỉnh v V đến tất cả các đỉnh khác trong V chính Thuật toán Dijkstra: là đường đi có chi phí trọng số thấp nhất. procedure DIJKSTRA_SP(V, E, w, s){ VT = {s}; // tập hợp các đỉnh của đường đi ngắn nhất
for all v (V - VT) if (cạnh(s, v) tồn tại) l[v] = w(s, v);
else l[v] = ; // chi phi đi từ v đến s while VT V do { tìm đỉnh u sao cho l[u]= min{l[v]|v (V - VT)};
VT = VT {u};
for all v (V - VT) l[v] = min{l[v], l[u] + w(u, v)}; } @2009, Ngô Văn Thanh -Viện Vật Lý } 4.6 Các thuật toán song song tìm kiếm tổ hợp @2009, Ngô Văn Thanh -Viện Vật Lý4.5 Các thuật toán song song trên đồ thị
