TAILIEUCHUNG - 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 .

• Kỹ thuật lập trình
• Tính toán song song
• Bài giảng Tính toán song song
• Phân tán dữ liệu
• Mô hình thuật giải phân chia
• Mô hình cây nhị phân
• Chia để trị
• Giới thiệu về tính toán song song
• Thuật ngữ tính toán song song
• Mô hình lập trình song song
• Parallel Computing
• Bộ nhớ máy tính song song
• Kiến trúc bộ nhớ máy tính song song
• Thiết kế chương trình song song
• Chi phí của lập trình song song
• Phân tích hiệu năng
• Bài giảng Xử lý song song
• Xử lý song song
• Tài liệu Xử lý song song
• Máy tính song song
• Xử lý song song cơ sở dữ liệu
• Xu hướng phát triển của CPU
• Các mô hình lập trình song song
• Mô hình truyền thống
• Mô hình dựa trên dữ liệu
• Kiến trúc bộ nhớ của máy tính
• Distributed Memory
• Giới thiệu tính toán song song
• Giao diện MPI
• Tốc độ tính toán
• Khái quát về giải thuật song song
• Giải thuật song song
• Hệ thống tính toán song song
• Chương trình song song
• Hệ thống xử lý song song
• Hệ thống nhiều máy tính
• Đề cương Tính toán song song
• Thiết kế thuật toán
• Thuật toán song song
• Độ phức tạp thuật toán song song
• Mô hình phân loại Flynn
• Mô hình PRAM
• Thuật toán song song nhân hai ma trận
• Mô hình bộ nhớ chia sẻ
• Mô hình Thread
• Đánh giá thuật giải song song
• Độ phức tạp thời gian
• Định luật Amdahl
• PVM trong việc lập trình song song
• Môi trường truyền thông điệp
• Hệ thống truyền thông điệp
• Khái niệm tính toán song song
• Lệnh thực thi
• Nguồn tài nguyên tính toán
• Lập trình song song
• Phương pháp trao đổi thông điệp
• Máy ảo song song
• Quản lý tài nguyên
• Quản lý tài nguyên hệ thống tính toán song
• Quản lý hệ thống máy tính
• Hệ thống tính toán song song Cluster
• Tính toán tuần tự
• luận vưn công nghệ
• kiến trúc máy tính
• hệ thống tính toán
• giáo trình máy vi tính
• hệ thống song song
• Kiến trúc máy tính Von Neumann
• Phân loại kinh điển của Flynn
• Thuật ngữ song song
• Đề tài nghiên cứu
• Chương trình xử lý song song
• Xây dựng chương trình xử lý song song
• Khả năng xử lý song song
• Khả năng tính toán CPU
• Kiến trúc song song đồng bộ
• Tổ chức các bộ vi xử lý
• Các mảng bộ vi xử lý
• Luận văn thạc sĩ khoa học
• Phương pháp thiết kế thuật toán cơ bản
• Thiết kế nhân ma trận thưa với Véctơ
• Véctơ trong tính toán song song
• Véctơ trong ứng dụng
• Giới thiệu lập trình song song với MPI
• Bài tập Toán lớp 8
• Đường thẳng song song
• Đường thẳng song song với một đường thẳng
• Tính chất đường thẳng song song cách đều
• Khoảng cách giữa hai đường thẳng song song