Báo Cáo Trình bày và viết chương trình minh họa cho phương pháp Parallel Bucket Sorting

Trình bày và viết chương trình minh họa cho phương pháp Parallel Bucket Sorting

MỤC LỤC

TỔNG QUAN VỀ ĐỀ TÀI 4
CHƯƠNG I. CƠ SỞ LÝ THUYẾT VỀ TÍNH TOÁN SONG SONG 5
I.1. Tính toán song song. 5
I.1.1. Tính toán song song là gì 5
I.1.2. Tại sao phải tính toán song song. 5
I.2. Phân loại máy tính song song. 6
I.2.1. Phân loại dựa trên sự tương tác giữa các BXL 6
I.2.1.1. Chia sẻ bộ nhớ chung. 6
I.2.1.2. Bộ nhớ phân tán. 8
I.2.1.3. Máy tính với bộ nhớ lai 9
I.2.2. Phân loại dựa trên cơ chế điều khiển chung. 9
I.2.2.1. Hệ thống đơn lệnh đa dữ liệu (SIMD). 9
I.2.2.2. Hệ thống đa lệnh đa dữ liệu (MIMD). 10
I.3. Các mô hình lập trình song song. 11
I.3.1. Tổng quan về mô hình lập trình song song. 11
I.3.2. Mô hình chia sẻ bộ nhớ chung. 11
I.3.3. Mô hình luồng. 12
I.3.4. Mô hình truyền thông điệp. 12
I.3.5. Mô hình song song dữ liệu. 13
I.3.6. Mô hình lai 14
I.4. Hiệu năng của tính toán song song. 14
I.4.1. Định luật Amdahl’s. 14
I.4.2. Cân bằng tải 15
I.4.2.1. Các thuật toán cân bằng tải tập trung. 15
I.4.2.2. Các thuật toán cân bằng tải phân tán hoàn toàn. 16
I.4.2.3. Các thuật toán cân bằng tải phân tán một nửa. 16
I.4.2.4. Sự bế tắc(Deadlock). 16
CHƯƠNG II. Giới thiệu về lập trình song song với MPI 18
II.1. Giới thiệu về MPI: 18
II.2. Các hàm thông dụng trong MPI: 18
II.2.1. Các hàm MPI phổ biến. 18
II.2.2. Các kiểu dữ liệu được dùng với MPI. 19
II.2.3. Các hàm tính gộp trong MPI. 20
CHƯƠNG III. TRIỂN KHAI ĐỀ TÀI 21
III.1. Thuật toán sắp xếp. 21
III.1.1. Sắp xếp theo giỏ (Bucket sort). 21
III.1.2. Thuật toán tuần tự. 21
III.1.3. Thuật toán song song. 22
III.1.3.1. Phân tích:. 23
III.1.3.2. Mã nguồn. 24
III.1.3.3. Kết quả thu được. 26
III.2. Demo. 27
KẾT LUẬN 29
TÀI LIỆU THAM KHẢO 30