Đồ án Thiết kế giải thuật song song

MỞ ĐẦU 3

CHƯƠNG I TỔNG QUAN VỀ TÍNH TOÁN SONG SONG 7

1. 1 Kiến trúc Von Neumann 7

1. 2. Phân loại Flynn 7

1. 3 Các kiến trúc bộ nhớ máy tính song song 9

1. 3. 1 Bộ nhớ dùng chung 9

1. 3. 2 Bộ nhớ phân tán 10

1. 3. 3 Bộ nhớ kết hợp 11

1. 4 Các mô hình lập trình song song 11

1. 4. 1 Lập trình bộ nhớ dùng chung 11

1. 4. 2 Truyền thông điệp 12

1. 4. 3 Mô hình song song dữ liệu 12

1. 4. 4 Mô hình hướng đối tượng 13

1. 4. 5 Mô hình logic 13

1. 5 Truyền thông trong mô hình Multicomputer 13

CHƯƠNG 2 THIẾT KẾ GIẢI THUẬT SONG SONG 16

2. 1 Mô hình thiết kế 16

2. 2 Phương pháp thiết kế 17

2. 3 Phân rã 19

2. 3. 1. Phân rã theo miền 19

2. 3. 2 Phân rã chức năng 20

2. 3. 3 Các vấn đề cần quan tâm 22

2. 4 Truyền thông 23

2. 4. 1 Truyền thông cục bộ 23

2. 4. 2 Truyền thông toàn cục 24

2. 4. 3 Các vấn đề cần quan tâm 26

2. 5 Tích tụ 26

2. 5. 1Gia tăng kích thước tác vụ 28

2. 5. 2 Duy trì khả năng linh động 30

2. 5. 4 Các vấn đề cần quan tâm 30

2. 6 Ánh xạ 31

2. 6. 1 Các giải thuật cân bằng nạp 32

2. 6. 2 Các giải thuật lập lịch trình tác vụ 33

2. 6. 3 Các vấn đề cần quan tâm 34

CHƯƠNG 3 MẠNG KẾT NỐI 35

3. 1 Các mạng kết nối thông dụng 35

3. 1. 1 Mạng Mesh 36

3. 1. 2 Mạng bus/star 36

3. 1. 3 Mạng cây nhị phân 37

3. 1. 4 Mạng Hypertree 37

3. 1. 5 Mạng hình chóp 38

3. 1. 6 Mạng Butterfly 39

3. 1. 7 Mạng Hypercube 39

3. 1. 8 Mạng Cube-Connected Cycles 40

3. 1. 9 Mạng shuffle-exchange 41

3. 1. 10 Mạng de Bruijn 41

3. 2 Ánh xạ dữ liệu 42

3. 2. 1 Ring sang 2-D Mesh 44

3. 2. 2 Mesh 2-D sang Mesh 2-D 44

3. 2. 3 Cây nhị phân hoàn chỉnh sang 2D Mesh 45

3. 2. 4 Cây nhị thức sang Mesh2-D 45

3. 2. 5 Nhúng đồ thị vào trong mạng Hypercube 45

3. 2. 6 Cây nhị thức sang Hypercube 46

3. 2. 7 Rings và Meshes sang Hypercube 46

CHƯƠNG 4 CƠ SỞ ĐÁNH GIÁ GIẢI THUẬT SONG SONG 49

4. 1 Thời gian thực hiện 49

4. 1. 1 Thời gian tính toán 50

4. 1. 2 Thời gian truyền thông 50

4. 1. 3 Thời gian rỗi (Idle) 52

4. 2 Tăng tốc và hiệu quả. 52

4. 3 Tính qui mô 53

CHƯƠNG 5 GIẢI HỆ PHƯƠNG TRÌNH TUYẾN TÍNH 55

5. 1 Tách A = L*U dựa theo giải thuật khử Guassian 55

5. 1. 1 Giải thuật song song theo hàng 59

5. 1. 2 Giải thuật song song theo cột 61

5. 1. 3 Giải thuật song song hai chiều 62

5. 1. 4 Khử Gauss với kỹ thuật lựa chọn phần tử xoay 64

5. 2 Giải hệ phương trình với ma trận hệ số tam giác 64

5. 2. 1 Giải thuật song song tích tụ theo hàng 67

5. 2. 2 Giải thuật song song tích tụ theo cột 70

5. 2. 3 Giải thuật song song hai chiều 72

5. 3 Thực thi giải thuật 74

5. 3. 1 Xây dựng chương trình 74

5. 3. 2 Các kết quả thực hiện Error! Bookmark not defined.

5. 3. 3 Các hạn chế và hướng phát triển chương trình 77

KẾT LUẬN 78

TÀI LIỆU THAM KHẢO 79