TAÛp chê khoa hoüC, Âaûi hoüc Huãú, Säú 27, 2005

}

Từ khóa Par chỉ ra rằng những câu lệnh trong phần thân được thực hiện một cách đồng thời. Đây là song song mức dòng lệnh.

+ Phân chia khối: Ma trận được phân chia thành từng nhóm gồm một số dòng hoặc cột và gán cho các bộ xử lí riêng. Mỗi nhóm chứa một số dòng (cột) bằng nhau, hoặc có thể phân chia những dòng (cột) cho các bộ xử lí theo một chu trình.

+ Phân chia bảng ô vuông: Ma trận được phân thành những ma trận con nhỏ hơn phân bố giữa các bộ xử lí và tất cả những ma trận con có cùng kích thước và được phân chia cho cả hai dòng và cột và không có bộ xử lí nào được gán cho dòng hoặc cột đầy đủ. Tóm lại, sự phân chia bảng ô vuông ánh xạ ma trận thành một ma trận vuông những bộ xử lí 2 chiều.

Xét phép nhân ma trận A cấp n x n, A = [a_ij]_nxn và ma trận B = [b_ij]_nxn là một ma trận C cấp n x n, C = [c_ij]_nxn, và được định nghĩa là: c_ij = A_ikB_kj. Ta có thể áp dụng mô hình mảng SIMD 2 chiều hoặc 3 chiều trên những kiến trúc thích hợp.

Pha 1, bộ xử lí Pij lưu trữ A[i,j] và B[i,j]. Sau đó gửi các thành phần để tạo ra tích C = A*B bằng cách quay lên thành phần của B và quay trái với thành phần A. Pha 2, tính tích vô hướng trong mỗi bộ xử lí. Pha 3, kết quả của 2 pha được gửi đến các bộ xử lí kề nhau hướng trái và lên trên của ma trận A và B. Sau 3 pha, c[i,j] của tích được thể hiện trong bộ xử lí P_ij.

Procedure Paralel_Matrix_Matrix(A,B,C)

For k = 0 to n-1 do \*Phase1*\

For P_ij where 0 i,j n-1 do in parallel

If i > k then A[i,j-1]  A[i,j] Endif

If j > k then B[i-1,j]  B[i,j] Endif

Endfor P_ij

Endfor

For P_ij where 0 i,j n-1 do in parallel \*Phase 2*\

Endfor P_ij

For k = 0 to n-1 do \*Phase3*\

For Pij where 0 i,j n-1 do in parallel

A: P_ij  (move-left) A: P_ij

B:P_ij  (move-up) B: P_ij

C[i,j] = C[i,j] + A[i,j]* B[i,j]

Endfor P_ij

Endfor

End Parallel_Matrix_Matrix

Những thành phần của ma trận cũng như tích ma trận là nhị phân, nghĩa là mỗi thành phần của chúng là 0 hoặc 1.

Thuật toán: parallel matrix_matrix(A,B,C)

For j =0 to n-1 do in parallel ( 0  i n-1)

A(0,i,j) = 1

Endfor

For k= 0 to n-1 do in parallel B(0,j,k) =A(0,j,k)

Endfor

Endfor

begin Parallel_Matrix_matrix(A,B,C);

For j =0 to n-1 do in parallel

For k = 0 to n-1 do in paralllel

Begin A(0,j,k) :=C(0,j,k);

B(0,j,k) :=C(0,j,k)

End;

End

Endfor;

Để tính quan hệ suy dẫn (gọi IDB) từ những quan hệ CSDL và qui tắc đã cho, ta có:

BEGIN Weimatrix; Parallel_Matrix-boolean(W[n,n]);

For i:= 1 to n do

For j:=1 to n do

begin v[i] := Name(i); v[j]:= Name(j);

writeln("tên quan hệ IDB(",v[i],v[j], D[i,j],")");

end;

(2) ancestor(X,Y):- parrent(X,Z) & ancestor(Z,Y);

và tập sự kiện: parrent(1,2), parrent(2,3), parrent(3,4), parrent(4,5), parrent(5,6):

1 1 0 0 0 0

2 4 6 0 1 1 0 0 0

0 0 1 1 0 0 0 0 0 1 1 0

1 3 5 0 0 0 0 1 1

Hình 2.3.Đồ thị G với ma trận kề: 0 0 0 0 0 1

0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0

0 0 1 1 0 0 x 0 0 1 1 0 0 = 0 0 1 1 1 0

0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0

0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1

0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1

1 1 1 1 1 1

và tương tự cho: B² x B² = B⁴ và B⁴ x B⁴ = B⁸ = 0 1 1 1 1 1

0 0 1 1 1 1

0 0 0 1 1 1

0 0 0 0 1 1

0 0 0 0 0 1
Ma trận B⁸ cho biết rằng đường đi trên đồ thị có độ dài 8-1 = 7, và có log (8-1) = 2³ tức là có 3 phép nhân liên tiếp để tạo thành ma trận C = B⁸ và ta thu được những cặp cạnh kết nối sau: (1,2),(1,3), (1,4), (1,5), (1,6), (2,3), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6), (4,5), (4,6), (5,6).

b. Thuật toán đồ thị song song:

* Thuật toán Floyd: Thuật toán bao gồm n bước. Bước đầu tiên, cạnh i, j (1 i,j n) được thay với đường dẫn có giá trị nhỏ nhất từ i đến j cho phép thông qua đỉnh 1. Ma trận kết quả sau bước đầu tiên là W⁽¹⁾_ij. Đến bước thứ 2, đường dẫn từ i đến j được tính toán từ bước đầu tiên được thay bằng đường dẫn có giá trị nhỏ nhất từ i đến j thông qua đỉnh 1 và 2. Đường dẫn được kí hiệu là W⁽²⁾_ij = Min {w⁽¹⁾_ij, w⁽¹⁾_i2+w⁽¹⁾_2j}, trong đó ma trận kết quả là W⁽²⁾_ij. Để tính toán W^(k)_ij, là giá trị nhỏ nhất của một đường dẫn từ i đến j:

Wij k= 0

W^(k)_ij = Min(W^(k-1)_ij, (W^(k-1)_ik+ W^(k-1)_kj) 0  k  n-1

Procedure sequential_shortest_path(W[n,n])

Array D[n,n], W[n,n]

For i,j = (1,2...n) D[i,j]  W[i,j]

For k = (1,2...n)

For i= (1,2...n)

For j = (1,2...n) D[i,j]  min {D[i,j], (D[i,k] + D[k,j])}

Return D

Thuật toán tuần tự đòi hỏi n phép lặp, và mỗi phép lặp yêu cầu O(n²) thời gian. Do đó, toàn bộ thời gian thực hiện của thuật toán tất cả cặp đường dẫn ngắn nhất tuần tự là O(n³), D khởi đầu có trọng số giữa các đỉnh như sau:

W(i,j)  0 nếu i  j

W(i,j) =  nếu cạnh (k,j) không tồn tại.

Thuật toán sử dụng n² bộ xử lí và được tổ chức thành một mảng 2 chiều. Bộ xử lí Pij tính toán giá trị W^(k)_ij trong đó k = 1,2,..n. Thuật toán thể hiện logn phép lặp và đường dẫn ngắn nhất giữa các cặp đỉnh, mỗi phép lặp k, bộ xử lí Pij cần những giá trị W^(k-1)_ij, W^(k-1)_ik và W^(k-1)_kj.

Procedure parallel_shortest_path(W[n,n]).

Array D[n,n], W[n,n], T[n,n]

For all i,j = (1,2...n) in parallel do D[i,j]  W[i,j]

Repeat logn lần

For all i,j,x = (1,2...n) in parallel do

T[i,x,j]  D[i,x] + D[x,j]

For all i,j= (1,2...n) in parallel do

D[i,j]  min (D[i,x], T[i,1,j],T[i,1,j],...T[i,n,j]).

Return D

For i:= 1 to n do

For j := 1 to n do

if (d[i,j] > 0 and d[i,j]  +) then E = E  E(v[i], v[j], d[i,j] );

End parallel_shortest_path.

Ví dụ: Tìm tất cả các cặp thành phố đã cho có chi phí thấp nhất.

(1) Tour(A,B,N): -distance(A,B,N) (2) Tour(A,B,N):-tour(A,C,M) & tour(C,B,L).

Với các khoảng cách: Distance(1,1,1), Distance(1,2,10), Distance(1,3,5), Distance(2,3,2), Distance(2,5,1), Distance(3,2,3), Distance(3,4,2), Distance(4,5,4), Distance(5,4,6).

1 10 5   1 10 5   1 10 5    0 2  1  0 2  1  0 2  1

W =  3 0 2  D₁ =  3 0 2  D₂ =  3 0 2 4

   0 4    0 4    0 4

   6 0    6 0    6 0



1 8 5 7 9 1 8 5 7 9 1 8 5 7 9

 0 2 4 1  0 2 4 1  0 2 4 1

D₃ =  3 0 2 4 D₄ =  3 0 2 4 D₅ =  3 0 2 4

   0 4    0 4    0 4

   6 0    6 0    6 0

Ta được: tour(1,1,1); tour(1,2,8), tour(1,3,5), tour(1,4,7), tour(1,5,9), tour(2,3,2); tour(2,4,4), tour(2,5,1), tour(3,2,3); tour(3,4,2), tour(4,5,4), tour(5,4,6). Khác với thuật toán tất cả cặp đường dẫn ngắn nhất của Dijkstra, thuật toán Floyd thậm chí nếu tồn tại một số cạnh nào đó có trọng số âm nghĩa là những trọng số nào đó của các cạnh trong đường dẫn âm.

1. 
   Jeffrey D. Ullman. Nguyên lý các hệ cơ sở dữ liệu và cơ sở tri thức (3 tập), Nhà xuất bản thống kê (1996)
   
2. 
   Barry Wilkinson, Michael Allen. Parallel Programming, techniques and applications using networked workstations and parallel computers, Prentice Hall, Upper Saddle River, New Jersey 07458.
   
3. 
   Seyed H.Roosta. Parallel Processing and Parallel Algorithms theory and computation, Springer, Oswego, New York (1999)
   
4. 
   Clement T.Yu, Weiyi Meng. Principles of Database Query Processing for Advanced Applications, Morgan Kaufman Inc (1998)
   
5. 
   Hong. Parallel Query Processing Using Shared Memory Multiproseccors and Disk Arrays, Univesity of California, Berkeley, August (1992)