Bài giảng Tính toán song song (Parallel computing): Chương 4 - TS. Ngô Văn Thanh

Chia sẻ: Little Little | Ngày: | Loại File: PDF | Số trang:50

Thêm vào BST

Báo xấu

123
lượt xem 15
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 4 - Các thuật toán song song. Nội dung trình bày trong chương này gồm: Mô hình PRAM, các thuật toán song song nhân hai ma trận, các thuật toán sắp xếp song song, tìm kiếm trên danh bạ, các thuật toán song song trên đồ thị, các thuật toán song song tìm kiếm tổ hợp.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Tính toán song song (Parallel computing): Chương 4 - TS. Ngô Văn Thanh

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 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 2i + 1  j  2i+1 do in parallel y (in Pj’s private memory)  L[j-2i] 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 2i-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
@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ý