LỜI CẢM ƠN
Chúng em xin bày tỏ lòng biết ơn chân thành nhất đến Thầy Trần Đan Thư
và th
ầy
Nguyễn Thanh Sơn, hai Thầy đã tận tâm hướng dẫn, giúp đỡ chúng em
trong suốt thời gian thực hiện luận văn này.
Chúng con xin gửi tất cả lòng biết ơn sâu sắc và sự kính trọng đến ông bà,
cha mẹ, cùng toàn thể gia đình, những người đã nuôi dạy chúng con trưởng thành
đến ngày hôm nay.
Chúng em cũng xin chân thành cám ơn quý Thầy cô trong Khoa Công nghệ
thông tin, trường Đại học Khoa học Tự nhiên Tp.Hồ Chí Minh đã tận tình giảng
dạy, hướng d
ẫn, giúp đỡ và tạo điều kiện cho chúng em thực hiện tốt luận văn này.
Xin chân thành cám ơn sự giúp đỡ, động viên và chỉ bảo rất nhiệt tình của
các anh chị và tất cả các bạn, những người đã giúp chúng tôi có đủ nghị lực và ý
chí để hoàn thành luận văn này.
Mặc dù đã cố gắng hết sức, song chắc chắn luận văn không khỏi những
thiếu sót. Chúng em rất mong nhận được sự thông cảm và chỉ bảo tận tình của quý
Thầy Cô và các bạn.
TP.HCM, 7/2005
Nhóm sinh viên thực hiện
Huỳnh Bá Thanh Tùng - Trần Việt Cường
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 nghà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 nghà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 là rất lớ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ể 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ư meta-computing,
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.
Hình ảnh minh họa cho các tài nguyên phân phối
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 tìm hiểu được về tính toán lưới 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 trê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. Kết luận – Hướng phát triển : 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
Chương 1. Giới thiệu 14
1.1. Các khái niệm 14
1.2. Những thách thức đối với tính toán lưới 17
Chương 2. Tính toán song song và phân bố 18
2.1. Khái niệm 18
2.2. Nền tảng tính toán song song và phân bố 19
2.2.1. Kiến trúc xử lý song song và phân bố 19
2.2.2. Tổ chức vật lý của các nền tảng song song và phân bố 26
2.3. Một số mô hình lập trình song song thông dụng 27
2.3.1. Mô hình chia sẽ không gian bộ nhớ 27
2.3.2. Mô hình truyền thông điệp 28
2.4. Cách thức xây dựng một chương trình song song và phân bố 30
2.4.1. Các thuật ngữ căn bản 31
2.4.2. Thiết kế thuật toán song song 33
2.4.3. Một số phương pháp tối ưu 46
2.4.4. Các mô hình thuật toán song song 50
Chương 3. Các môi trường hỗ trợ tính toán lưới 55
3.1. Giới thiệu 55
3.2. Các vấn đề khi lập trình luới 56
3.2.1. Tính mang chuyển, tính khả thi và khả năng thích ứng 56
3.2.2. Khả năng phát hiện tài nguyên 57
3.2.3. Hiệu năng 57
3.2.4. Dung lỗi 58
3.2.5. Bảo mật 58
3.2.6. Các siêu mô hình 59
3.3. Tồng quát về các môi trường hỗ trợ 59
3.3.1. 59 Một số môi trường Grid
3.3.2. Những mô hình lập trình và công cụ hỗ trợ 63
3.3.3. Môi trường cài đặt 69
3.4. Những kỹ thuật nâng cao hỗ trợ lập trình 81
3.4.1. Các kỹ thuật truyền thống 81
3.4.2. Các kỹ thuật hướng dữ liệu 82
3.4.3. Các kỹ thuật suy đoán và tối ưu 83
3.4.4. Các kỹ thuật phân tán 83
3.4.5. Nhập xuất hướng Grid 84
3.4.6. Các dịch vụ giao tiếp cấp cao 84
3.4.7. Bảo mật 86
3.4.8. Dung lỗi 86
3.4.9. Các siêu mô hình và hệ thống thời gian thực hướng Grid 88
3.5. Kết luận 89
Chương 4. Mô hình lập trình truyền thông điệp - MPI 91
4.1. Các khái niệm cơ bản 92
4.2. Cấu trúc chương trình MPI 95
4.3. Trao đổi thông tin điểm-điểm 96
4.3.1. Các thông tin của thông điệp 97
4.3.2. Các hình thức truyền thông 97
4.3.3. Giao tiếp blocking 99
4.3.4. Giao tiếp non-blocking 103
4.4. Trao đổi thông tin tập hợp 109
4.4.1. Đồng bộ hóa 109
4.4.2. Di dời dữ liệu trong nhóm 109
4.4.3. Tính toán gộp 113
4.5. Các kiểu dữ liệu 118
4.5.1. Những kiểu dữ liệu đã được định nghĩa 118
4.5.2. Các kiểu dữ liệu bổ sung 119
4.5.3. 123 Pack và UnPack
4.6. Quản lý nhóm và communicator 124
4.6.1. Tổng quan 124
4.6.2. Nguyên tắc sử dụng 126
Chương 5. Thử nghiệm các thuật toán lý thuyết đồ thị 129
5.1. Các khái niệm cơ bản 129
5.2. Dijkstra 130
5.2.1. Tuần tự 130
5.2.2. Song song 134
5.2.3. Thực nghiệm chương trình 136
5.3. Prim 138
5.3.1. Tuần tự 138
5.3.2. Song song 141
5.3.3. Thực nghiệm chương trình 143
5.4. Bellman – Ford 143
5.4.1. Tuần tự 143
5.4.2. Song song 147
Chương 6. Kết luận – Hướng phát triển 151
6.1. Kết luận 151
6.2. Hướng phát triển 151
Tài liệu tham khảo 153
Danh sách hình
Hình 1-1 : 3 tầng của Grid 16
Hình 2-1 : Phân lọai hệ thống máy tính theo Flynn-Johnson 20
Hình 2-2 : Kiến trúc SISD 20
Hình 2-3 : Kiến trúc SIMD 21
Hình 2-4 : Kiến trúc MISD 23
Hình 2-5 : Kiến trúc MIMD 24
Hình 2-6 : Mô hình chía sẽ không gian bộ nhớ 28
Hình 2-7 : Mô hình truyền thông điệp 29
Hình 3-1 : mô hình NetSolve 60
Hình 3-2 : Các thành phần của Globus 63
Hình 4-1 : Các tiến trình tạo lập trên mô hình lập trình MPI 92
Hình 4-2 : Cách thức truyền thông của các process 94
Hình 4-3 : Blocking và non-blocking 94
Hình 4-4 : Group, communicator và rank 95
Hình 4-5 : Cấu trúc của chương trình MPI 96
Hình 4-6 : Giao tiếp blocking 99
Hình 4-7 : Thứ tự các xử lý 102
Hình 4-8 : Cách thức xử lý tiến trình 103
Hình 4-9 : Giao tiếp non-blocking 103
Hình 4-10 : Broadcast dữ liệu 110
Hình 4-11 : Ví dụ hàm Scatter 111
Hình 4-12 : Hàm MPI_Gather 112
Hình 4-13 : Hàm MPI_Allgather 112
Hình 4-14 : Hàm MPI_Alltoall 113
Hình 4-15 : Hàm MPI_Reduce 114
Hình 4-16 : Sử dụng 8 xử lý để tính giá trị tuyệt đối 116
Hình 4-17 Hàm Mpi-Allreduce 117
Hình 4-18 : Hàm MPI_Reduce_scatter 117
Hình 4-19 : Hàm MPI_Scan 118
Hình 4-20 : MPI_Type_contiguous 120
Hình 4-21 : MPI_Type_vetor 121
Hình 4-22 : MPI_Type_indexed 122
Hình 4-23 : MPI_Type_struct 122
Hình 5-1. Thuật toán Dijkstra tuần tự 134
Hình 5-1.1. 131
Hình 5-1.3. 132
Hình 5-1.4. 133
Hình 5-1.5 133
Hình 5-1.6 134
Hình 5-2 : Thuật toán Dijkstra song song 135
Hình 5-3. Thuật toán Prim tuần tự 141
Hình 5-3 : Thuật toán Prim song song 142
Hình 5-4: Thuật toán Bellman-Ford tuần tự 145
Hình 5-5 : Thuật toán Bellman-Ford song song 149
Trang 14
Chương 1. Giới thiệu
1.1. Các khái niệm
Trong những năm đầu thập niên 90, nhiều nhóm nghiên cứu đã bắt đầu khai
thác các nguồn tài nguyên tính toán phân tán trên Internet. Các nhà khoa học đã
tập trung và sử dụng hàng trăm các máy trạm để thực hiện các chương trình song
song như thiết kế phân tử và hiển thị đồ họa máy tính. Trong khi đó các nhóm
nghiên cứu khác đã kết hợp các siêu máy tính lớn lại với nhau thành một siêu máy
tính ảo duy nhất, rồi phân phối các phần của một ứng dụng r
ất lớn cho các máy
tính trên một mạng diện rộng, ví dụ như máy tính giả lập các ứng dụng như tương
tác giữa chất lõng và cánh quạt của chân vịt tàu…Thêm vào đó phạm vi của các
dự án nghiên cứu này đã nêu ra tiềm năng thực sự của mạng máy tính, cùng với cơ
sở phần mềm và tin học để phát triển nó xa hơn.
Hệ thống đa bộ xử lý (Multiprocessor Systems - MPs), Cluster, Grids là các
ví dụ của ki
ến trúc tính toán phân tán. Trong MPs, các bộ xử lý được kết hơp chặt
chẽ với nhau, thông qua bộ nhớ chia sẽ chung và đường truyền kết nối rất cao. Ví
dụ như là PVPs (Parallel Vector Processors), chúng hầu như rất thích hợp cho tính
Không có nhận xét nào:
Đăng nhận xét