Mô hình thuật giải phân chia: Bài giảng Tính toán song song và phân toán

11/16/12

7. Mô hình thuật giải phân chia

1.  Mô hình cây nhị phân (Binary Tree Paradigm) 2.  Chia để trị (Devide and Conquer)

Tính toán song song và phân tán PGS.TS. Trần Văn Lăng tvlang@vast-‐hcm.ac.vn lang@lhu.edu.vn

7.1 Binary Tree Paradigm

Khảo sát việc jnh tổng

•  Xét cây nhị phân đầy đủ với n lá có độ cao là log2n

(hoặc ký hiệu logn) •  Dữ liệu đặt ở n nút lá. •  Quá trình đi từ ngọn đến gốc mất logn thời gian.

•  Thuật giải tuần tự mất O(n) •  Xét với n = 2k để có được cây nhị phân đầy đủ •  Tứ đây chia dữ liệu thành 2 nhóm •  Số process cần thiết là n/2

1 11/16/12

Minh họa

–  Nhóm 1: A(1), A(3), A(5), A(7) –  Nhóm 2: A(2), A(4), A(6), A(8)

•  Với n= 8 = 23,mỗi nhóm có 4 phần tử

•  Cần 4 task •  Với dãy gồm 8 phần tử, mô hình như hình vẽ bên dưới

•  Bốn process đồng thời jnh các giá trị tổng của nó •  Giai đoạn (cid:135)ếp theo chỉ còn lại 4 phần tử. Các phần theo yêu cầu

–  A(1) <— A(1) + A(2) –  A(2) <— A(3) + A(4) –  A(3) <— A(5) + A(6) –  A(4) <— A(7) + A(8)

•  Rồi lưu vào các biến tương ứng tử lưu trong 2 nhóm –  Nhóm 1: A(1), A(3) –  Nhóm 2: A(2), A(4)

2 11/16/12

Thuật giải

–  A(1) <— A(1) + A(2) –  A(2) <— A(3) + A(4)

•  Khi đó 2 process đồng thời cộng

Nhập: Mảng A(1:n)

•  Các kết quả được lưu vào A(1), A(2)

p = n/2 while p > 0 do for i = 1 to p do parallel A(i) = A(2i-1) + A(2i) endParallel p = p/2 endWhile

Xuất: Phần tử A(1)

Độ phức tạp

p = n/2 while p > 0 do

•  Trong câu lệnh 4, chi phí thời gian là O(1) cho 1 task, nên với log2n bước, chi phí thời gian O(logn).

for i = 1 to p do par A(i) = A(2i-1) + A(2i) endPar p = p/2

•  Số process ban đầu là p = n/2 •  Trong mỗi lần thực hiện số task chỉ còn 1/2. •  Nên số task cần thiết là P = n/2 = O(n)

endWhile

3 11/16/12

7.2 Chia để trị

–  Thuật giải tuần tự cần O(n) –  Song song cần O(logn) thời gian với O(n) task

•  Chia bài toán thành các bài toán con để dễ (cid:141)m ra lời giải cho tứng bài toán con riêng lẽ. •  Theo cách thực hiện của mô hình cây nhị phân •  Thuật giải song song chưa tối ưu, bởi: •  Hợp nhất các lời giải này lại để được lời giải của bài toán.

nE p )(

nO )( (log

)

Op ×

(log

)

1 log

nO )( OnO )( ×

•  Với thuật giải jnh tổng như trên, •  Nên hiệu suất Ep(n) (Eﬃciency) quá nhỏ khi n khá lớn:

n log

•  Chúng ta phải khảo sát bài toán sao cho Ep(n) có •  Suy ra giá trị là 1

4 11/16/12

Minh họa

•  Chia mảng A(1:n) thành r = n/logn nhóm, để huy động r task •  A(1), A(2), A(3), ..., A(k) •  A(k+1), A(k+2), ..., A(2k)

.............. •  Mỗi nhóm có logn phần tử. •  Ở đây vẫn giả thiết n = 2k và n/logn là số nguyên (k •  A((i-‐1)k+1), A((i-‐1)k+2), ..., A(ik) = logn) .............. •  Các nhóm được phân bố như sau: •  A((r-‐1)k+1), A((r-‐1)k+2), ..., A(rk)

b) Thuật giải

for i=1 to n/logn do parallel

B(i) = 0

for j=1 to logn do

•  Mỗi process cộng logn phần tử. •  Lưu kết quả lại trong mảng B(1:r) •  Sử dụng thuật giải song song (như phần 1) để jnh

B(i) = B(i)+ A(ik+j-logn)

tổng r phần tử của B.

endFor

•  Thuật giải song song trên B này cần O(logr) thời

endParallel

gian và O(r) process. Nhập: Mảng A(1:n) Xuất: Phần tử B(i)

5 11/16/12

Độ phức tạp

p = r/2

•  Các câu lệnh 2, 3, 4 cần O(logn) bước thời gian. •  Khi đó, các bước tứ 1 đến 5 dùng song song mất

while p > 0 do

O(logn) thời gian O(n/logn) process.

for i=1 to p do parallel

B(i) = B(2i-1) + B(2i)

endParallel

p = p/2

endWhile

6.3 Mô hình phân hoạch

•  Các bước còn lại dùng thuật giải song song dạng cây nhị phân, chi phí O(log(n/logn)) = O(logn-‐ log(logn)) = O(logn) thời gian. •  Theo cách (cid:135)ếp cận chia để trị, thuật giải phải bao gồm 2 bước, trong đó có bước quan trọng là việc hợp nhất các bài toán con đã chia ra để được lời giải của bài toán xuất phát.

•  Đôi khi việc thực hiện này làm ảnh hưởng đến kết •  Dùng O(n/logn) process. •  Như vậy, thuật giải cần O(logn) thời gian với O(n/ quả của ban đầu. logn) process

6 11/16/12

•  Trong mô hình phân hoạch, người ta không quan tâm đến quá trình hợp nhất. •  Giả sử có 2 mảng A(1:n), B(1;n) đã được sắp xếp tăng, cần phải hợp nhất thành 1 mảng C(1:2n) cũng tăng.

•  Ở đây giả thiết n = 2k, và r = n/logn là số nguyên (k •  Tiến trình phân hoạch bảo đảm sao cho khi phân chia xong, việc giải các bài toán con cho kết quả là lời giải của bài toán đặt ra. = logn)

Thuật giải tuần tự

Minh họa thuật giải

•  Phân hoạch A thành r = n/logn nhóm gồm k phần

C(k) = A(i) i = i + 1

tử như sau: –  A(1), A(2), ..., A(k) –  A(k+1), A(k+2), ..., A(2k) .......................................

C(k) = B(j) j = j + 1 endIf k = k + 1

1. A(n+1) = B(n+1) = X 2. i = 1; j = 1; k = 1 3. while k <= 2n do if A(i) < B(j) then 4. 5. 6. else 7. 8. 9. 10. 11. 12. endWhile

–  A((i-‐1)k+1), A((i-‐1)k+2), ..., A(ik) ................................................... –  A((r-‐1)k+1), A((r-‐1)k+2), ..., A(rk)

7 11/16/12

–  B(1), B(2), ..., B(j(1)) –  B(j(1)+1), B(j(1)+2), ..., B(j(2)) ............................................... –  B(j(i-‐1)+1), B(j(i-‐1)+2), ..., B(j(i)) ............................................... –  B(j(r-‐1)+1), B(j(r-‐1)+2), ..., B(j(r))

•  Tiếp theo cần (cid:141)m r số nguyên j(1), j(2), ..., j(r) sao •  Từ đây, phân B thành r nhóm như sau:

cho –  j(1) là chỉ số lớn nhất mà A(k) > B(j(1)) –  j(2) là chỉ số lớn nhất mà A(2k) > B(j(2)) ................................................... –  j(i) là chỉ số lớn nhất mà A(ik) > B(j(i)) ................................................... –  j(r) là chỉ số lớn nhất mà A(rk) > B(j(r))