Bài giảng Tính toán song song - Chương 4: Các thuật toán song song - Ngô Văn Thanh

TS. Ngô Văn Thanh, Viện Vật lý. Chuyên ngành : Công nghệ thông tin. 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 vào năm 1978.  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 toán.  Mô hình PRAM bao gồm:  Bộ điều khiển trung tâm. (control unit)  Bộ nhớ dùng chung (global memory)  p processors P1, P2, Pp.  Mỗi một processor có thể có một bộ nhớ riêng. (private memory) @2009, Ngô Văn Thanh - Viện Vật Lý  Các processor sẽ thực hiện một vòng đồng bộ: đọc – tính toán - ghi. (read- compute-write).  Trong mỗi bước tính một processor hoạt động (active processor) có thể đọc dữ 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 phần dữ liệu khác nhau.  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 bộ nhớ mà nó được phép truy nhập tại mỗi thời điểm.  Atomic: một công việc được gọi là atomic nếu như nó thực hiện xong hoàn toàn, hoặc là không thực hiện gì cả.  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ả các vùng trên bộ nhớ dùng chung tại mỗi thời điểm. @2009, Ngô Văn Thanh - Viện Vật Lý  Concurrent read (CR) – đọc đồng thời: nhiều processor được phép đọc cùng một vùng trên bộ nhớ dùng chung tại mỗi thời điểm.  Concurrent write (CW) – ghi đồng thời: nhiều processor được phép ghi đồng 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): 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ý 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 một vùng nhớ đã chọn.  Thuật toán Broadcast_EREW: nhằm thực hiện quá trình truy cập đồng thời của nhiều processor trên một vùng nhớ.  Giả thiết: địa chỉ của một vùng nhớ là x, và quá trình đọc song song được 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.  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ý  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 forall Pj, where 2 i + 1  j  2i+1 do in parallel y (in Pj’s private memory)  L[j-2 i] L[j]  y endfor endfor @2009, Ngô Văn Thanh - Viện Vật Lý 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 A[2j]  A[2j] + A[2j-2i-1] endif endfor endfor @2009, Ngô Văn Thanh - Viện Vật Lý  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] 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. @2009, Ngô Văn Thanh - Viện Vật Lý  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 2 i-1 + 1  j  n do in parallel A[j]  A [j] + A[j – 2i-1] endfor endfor @2009, Ngô Văn Thanh - Viện Vật Lý 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ớ dùng chung.  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) 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. @2009, Ngô Văn Thanh - Viện Vật Lý  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 endfor /* Kết quả C[i,j,n], where 1  i,j  n */ endfor @2009, Ngô Văn Thanh - Viện Vật Lý @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<s; 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 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ý @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 của ma trận B.  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ý 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 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.  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ố 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.  Đoạn mã chương trình tuần tự for (i=0; i<n; i++){ x=0; for (j=0; j<n; j++) if (a[i] > a[j]) x++; 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<n; i++){ x=0; for (j=0; j<n; 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 phần tử sẽ được sắp xếp.  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ử trong mảng A[1 . . n]. @2009, Ngô Văn Thanh - Viện Vật Lý  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 Pi, j so sánh A[i] and A[j], rồi cập nhật giá trị của C[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 đượ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] endfor @2009, Ngô Văn Thanh - Viện Vật Lý @2009, Ngô Văn Thanh - Viện Vật Lý Sắp xếp kiểu so sánh và tráo đổi.  Đ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: send(&A, P2); recv(&A, P2);  Trên 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ý  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 giá trị A = B , ngược lại trên P2 nếu A > B thì đặt B = A.  Mã chương trình:  Trên P1: send(&A, P2); recv(&B, P2); if (A > B) A = B  Trên P2: recv(&A, P1); send(&B, P1); if (A > B) B = A;  Hạn chế: Dễ bị hiện tượng deadlock @2009, Ngô Văn Thanh - Viện Vật Lý @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 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. @2009, Ngô Văn Thanh - Viện Vật Lý 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<i; 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 hoàn chỉnh @2009, Ngô Văn Thanh - Viện Vật Lý  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=0,2,..; even): Pi (i=1,3,..; odd): recv(&newA, P(i+1)); send(&A, P(i-1)); send(&A, P(i+1)); recv(&newA, P(i-1)); if(newA A) A = newA;  Đối với giai đoạn lẻ (1, 3, 5, 7,...) Pi (i=2,4,..; even): Pi (i=1,3,..; odd): recv(&newA, P(i-1)); send(&A, P(i+1)); send(&A, P(i-1)); recv(&newA, 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 các dãy con.  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ý @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ý 4.5 Các thuật toán song song trên đồ thị 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 trong đường đi. @2009, Ngô Văn Thanh - Viện Vật Lý  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 cuối của nó trùng nhau.  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 đồ thị hở.  Trọng số: là một số thực thể hiện cho chi phí đi lại trên mỗi cạnh của đồ thị. Đồ thị có dạng G(V, E, w).  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ý 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 cho các trường hợp khác.  Đối với đồ thị trọng số, ma trận kề có dạng: nếu nếu i = j cho các trường hợp khác.  Kích thước không gian để lưu ma trận kề là @2009, Ngô Văn Thanh - Viện Vật Lý 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], mỗi phần tử v  V là một chuỗi gồm các đỉnh kề củ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ý 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 đỉnh của G.  Đố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 đường đi trong đồ thị con đó.  Cây khung bé nhất (MST minimum spanning tree) của một đồ thị vô hướng là một cây khung có trọng số bé nhất. @2009, Ngô Văn Thanh - Viện Vật Lý  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.  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.  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), 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.  Trong quá trình tính lặp, đỉnh u được thêm vào mảng VT nếu như chi phí đường đi d[u] = min{d[v]|v (V - VT)}. @2009, Ngô Văn Thanh - Viện Vật Lý  Chọn đỉnh b : VT = {b}  Dựa vào ma trận trọng số, đưa ra mảng d[1, 0, 5, 1, , ] vì (d, b) = 1, và (c, b) = 5 (a, b) =1, (e, b) = , và (f, b) = .  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, ] 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) =  và (f, d)= .  Chọn đỉnh tiếp theo là a vì d[a] = 1 có chi phí thấp nhất. @2009, Ngô Văn Thanh - Viện Vật Lý  Chọn đỉnh a; VT = {b,d,a}, đưa ra mảng trọng số d [1, 0, 2, 1, 4, 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 : 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)= .  Cuối cùng chọn đỉnh c đưa vào cây khung. @2009, Ngô Văn Thanh - Viện Vật Lý  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)= , và (f, c) = .  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ý  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] = ; while VT  V do { Tìm đỉnh u sao cho d[u] = min{d[v]|v (V - VT)}; VT = VT  {u}; for all v (V - VT) 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 processors.  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ý 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 là đường đi có chi phí trọng số thấp nhất.  Thuật toán Dijkstra: 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ý