LỜI NÓI ĐẦU

Nhân lọai ngày nay đang chứng kiến sự phát triển mạnh mẽ của ngành

Công nghệ Thông tin, một trong những ngành mũi nhọn của nhiều quốc gia

trên thế giới. Sự phát triển vượt bậc của nó là kết quả tất yếu của sự phát triển

kèm theo các thiết bị phần cứng cũng như phần mềm tiện ích.

Sự phát triển đó đã kéo theo rất nhiều các ngành khác phát triền theo,

trong đó có lĩnh vực nghiên cứu khoa học. Tuy công nghệ ngày càng phát triển,

tốc độ xử lý của các thiết bị cũng không ngừng tăng cao, nhưng nhu cầu tính

toán của con người vẫn còn rất lớn. Cho đến hiện nay vẫn còn rất nhiều vấn đề

mà các nhà khoa học cùng với khả năng tính toán của các máy tính hiện nay

vẫn chưa giải quyết được hay giải quyết được nhưng với thời gian rất lớn.

Các vấn đề đó có thể là :

ã Mô hình hóa và giả lập

ã Xử lý thao tác trên các dữ liệu rất lớn

ã Các vấn đề “grand challenge” (là các vấn đề không thể giải quyết

trong thời gian hợp lý)

Lời giải cho những vấn đề này đã dẫn đến sự ra đời của các thế hệ siêu

máy tính. Tuy nhiên việc đầu tư phát triển cho các thiết bị này gần như là điều

quá khó khăn đối với nhiều người, tổ chức, trường học . Chính vì lẽ đó mà

ngày nay người ta đang tập trung nghiên cứu cách cách sử dụng các tài nguyên

phân bố một cách hợp lý để tận dụng được khả năng tính toán của các máy tính

đơn. Những giải pháp này được biết đến với nhiều tên gọi khác nhau như metacomputing,

salable-computing, global- computing, internet computing và gần

nhất hiện nay là peer to peer computing hay Grid computing.

Đây là phương pháp nhằm tận dụng khả năng của các máy tính trên toàn

mạng thành một máy tính “ảo” duy nhất, nhằm hợp nhất tài nguyên tính toán ở

nhiều nơi trên thế giới để tạo ra một khả năng tính toán khổng lồ, góp phần giải

quyết các vấn đề khó khăn trong khoa học và công nghệ. Ngày nay nó đang

càng được sự hỗ trợ mạnh hơn của các thiết bị phần cứng, băng thông

Grid Computing có khả năng chia sẻ, chọn lựa, và thu gom một số lượng

lớn những tài nguyên khác nhau bao gồm những siêu máy tính, các hệ thống

lưu trữ, cùng với những nguồn dữ liệu, các thiết bị đặt biệt Những tài nguyên

này được phân bố ở các vùng địa lý khác nhau và thuộc về các tổ chức khác

nhau.

Nhận thấy được nhu cầu phát triển ấy, nhóm chúng em đã quyết định

chọn thực hiện đề tài “Nghiên cứu tính toán lưới và thực nghiệm trên một

số thuật toán lý thuyết đồ thị”

Mục tiêu của đề tài đề ra là tìm hiểu về tính toán lưới, và qua đó tận

dụng các kiến thức có được để có thể cài đặt một số thuật toán lý thuyết đồ thị,

nhằm có thể giải quyết các vấn đề tìm đường đi khi số đỉnh tương đối lớn

Các nội dung chính:

ã Nghiên cứu tính toán lưới

ã Tìm hiểu các môi trường hỗ trợ

ã Tìm hiểu lập trinh song song và phân tán

ã Cài đặt một số thuật toán với kiến thức có được

Nội dung của luận văn được chia làm 6 chương :

Chương 1. Giới thiệu : Giới thiệu tổng quan về tính toán lưới, khái

niệm lịch sử phát triển.

Chương 2. Tính toán song song và phân bố : Trình bày về các kiến

trúc, mô hình xử lý song song và phân bố, cách thức xây dựng chương trình,

thiết kế thuật toán

Chương 3. Các môi trường hỗ trợ tính toán lưới : Tìm hiểu về các

môi trường đang được sử dụng và nghiên cứu hiện nay trên thế giới.

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

thể được dùng để phát triển ứng dụng MPI.

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

xây dựng chương trình , các khái niệm lý thuyết, thực nghiệm thực tế

Chương 6. Tổng kết : Nêu các kết quả đã đạt được, một số vấn đề còn

tồn tại, định hướng mục tiêu mở rộng phát triển đề tài trong tương lai.

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