tailieunhanh - Bài giảng Tính toán song song và phân toán - Chương 7: 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 - Chương 7: Mô hình thuật giải phân chia trình bày về mô hình cây nhị phân (binary tree paradigm), chia để trị (devide and conquer). Với các bạn chuyên ngành Công nghệ thông tin thì đây là tài liệu hữu ích. | 11/16/12 7. Mô hình thuật giải phân chia Tính toán song song và phân tán . Trần Văn Lăng 1.  Mô hình cây nhị phân (Binary Tree Paradigm) 2.  Chia để trị (Devide and Conquer) tvlang@vast-­‐ lang@ 1 2 Binary Tree Paradigm •  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. Khảo sát việc jnh tổng •  •  •  •  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 A1 •  Với n= 8 = 23,mỗi nhóm có 4 phần tử –  Nhóm 1: A(1), A(3), A(5), A(7) –  Nhóm 2: A(2), A(4), A(6), A(8) A1 •  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 A1 A1 •  Bốn process đồng thời jnh các giá trị tổng của nó theo yêu cầu •  Rồi lưu vào các biến tương ứng –  A(1) 0 do for i = 1 to p do parallel A(i) = A(2i-1) + A(2i) endParallel p = p/2 Nhập: Mảng A(1:n) endWhile Xuất: Phần tử A(1) Độ phức tạp •  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) •  Trong câu lệnh 4, chi phí thời gian là O(1) cho 1 .