Khóa luận Nghiên cứu tính toán lưới và thử nghiệm một số thuật toán lý thuyết đồ thị

Mục lục

Danh sách hình . 11

Chương 1. Giới thiệu . 13

1.1. Các khái niệm. 13

1.2. Những thách thức đối với tính toán lưới . 16

Chương 2. Tính toán song song và phân bố. 17

2.1. Khái niệm . 17

2.2. Nền tảng tính toán song song và phân bố. 18

2.2.1. Kiến trúc xửlý song song và phân bố.18

2.2.2. Tổchức vật lý của các nền tảng song song và phân bố.25

2.3. Một sốmô hình lập trình song song thông dụng. 26

2.3.1. Mô hình chia sẽkhông gian bộnhớ.26

2.3.2. Mô hình truyền thông điệp .27

2.4. Cách thức xây dựng một chương trình song song và phân bố. 29

2.4.1. Các thuật ngữcăn bản.29

2.4.2. Thiết kếthuật toán song song .31

2.4.3. Một sốphương pháp tối ưu.43

2.4.4. Các mô hình thuật toán song song .48

Chương 3. Các môi trường hỗtrợtính toán lưới . 52

3.1. Giới thiệu. 52

3.2. Các vấn đềkhi lập trình luới . 53

3.2.1. Tính mang chuyển, tính khảthi và khảnăng thích ứng.53

3.2.2. Khảnăng phát hiện tài nguyên .54

3.2.3. Hiệu năng .54

3.2.4. Dung lỗi .55

3.2.5. Bảo mật .55

3.2.6. Các siêu mô hình.55

3.3. Tổng quát vềcác môi trường hỗtrợ. 56

3.3.1. Một sốmôi trường Grid .56

3.3.2. Những mô hình lập trình và công cụhỗtrợ.59

3.3.3. Môi trường cài đặt .64

3.4. Những kỹthuật nâng cao hỗtrợlập trình . 75

3.4.1. Các kỹthuật truyền thống.76

3.4.2. Các kỹthuật hướng dữliệu.76

3.4.3. Các kỹthuật suy đoán và tối ưu.77

3.4.4. Các kỹthuật phân tán.77

3.4.5. Nhập xuất hướng Grid .78

3.4.6. Các dịch vụgiao tiếp cấp cao .78

3.4.7. Bảo mật .80

3.4.8. Dung lỗi .80

3.4.9. Các siêu mô hình và hệthống thời gian thực hướng Grid.82

3.5. Tóm tắt . 83

Chương 4. Mô hình lập trình truyền thông điệp - MPI . 85

4.1. Các khái niệm cơbản . 86

4.2. Cấu trúc chương trình MPI . 89

4.3. Trao đổi thông tin điểm-điểm . 90

4.3.1. Các thông tin của thông điệp .90

4.3.2. Các hình thức truyền thông.91

4.3.3. Giao tiếp blocking.92

4.3.4. Giao tiếp non-blocking .96

4.4. Trao đổi thông tin tập hợp. 101

4.4.1. Đồng bộhóa.101

4.4.2. Di dời dữliệu trong nhóm .101

4.4.3. Tính toán gộp .105

4.5. Các kiểu dữliệu. 109

4.5.1. Những kiểu dữliệu đã được định nghĩa .109

4.5.2. Các kiểu dữliệu bổsung.110

4.5.3. Pack và UnPack .113

Chương 5. Thửnghiệm các thuật toán lý thuyết đồthị. 114

5.1. Các khái niệm cơbản . 114

5.2. Dijkstra . 115

5.2.1. Tuần tự.115

5.2.2. Song song.119

5.2.3. Thực nghiệm chương trình .120

5.3. Prim . 122

5.3.1. Tuần tự.122

5.3.2. Song song.124

5.3.3. Thực nghiệm chương trình .126

5.4. Bellman – Ford. 128

5.4.1. Tuần tự.128

5.4.2. Song song.130

5.4.3. Thực nghiệm chương trình .132

5.5. Đánh giá chung. 134

Chương 6. Tổng kết . 136

6.1. Kết luận . 136

6.2. Hướng phát triển . 136

Tài liệu tham khảo . 138