Thạc Sĩ 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ị

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