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

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









Danh sách hình
Hình 1-1 : 3 tầng của Grid 15
Hình 2-1 : Phân lọai hệ thống máy tính theo Flynn-Johnson 19
Hình 2-2 : Kiến trúc SISD 19
Hình 2-3 : Kiến trúc SIMD 20
Hình 2-4 : Kiến trúc MISD 22
Hình 2-5 : Kiến trúc MIMD 23
Hình 2-6 : Mô hình chía sẽ không gian bộ nhớ 27
Hình 2-7 : Mô hình truyền thông điệp 28
Hình 3-1 : Mô hình NetSolve 56
Hình 3-2 : Các thành phần của Globus 59
Hình 4-1 : Các tiến trình tạo lập trên mô hình lập trình MPI 86
Hình 4-2 : Cách thức truyền thông của các process 87
Hình 4-3 : Blocking và non-blocking 88
Hình 4-4 : Group, communicator và rank 88
Hình 4-5 : Cấu trúc của chương trình MPI 89
Hình 4-6 : Giao tiếp blocking 92
Hình 4-7 : Thứ tự các xử lý 95
Hình 4-8 : Cách thức xử lý tiến trình 95
Hình 4-9 : Giao tiếp non-blocking 96
Hình 4-10 : Broadcast dữ liệu 102
Hình 4-11 : Ví dụ hàm Scatter 103
Hình 4-12 : Hàm MPI_Gather 103
Hình 4-13 : Hàm MPI_Allgather 104
Hình 4-14 : Hàm MPI_Alltoall 104
Hình 4-15 : Hàm MPI_Reduce 105
Hình 4-16 : Sử dụng 8 xử lý để tính giá trị tuyệt đối 107
Hình 4-17 Hàm Mpi-Allreduce 108
Hình 4-18 : Hàm MPI_Reduce_scatter 108
Hình 4-19 : Hàm MPI_Scan 109
Hình 4-20 : MPI_Type_contiguous 110









Trang 12
Hình 4-21 : MPI_Type_vetor 111
Hình 4-22 : MPI_Type_indexed 112
Hình 4-23 : MPI_Type_struct 112
Hình 5-1. Thuật toán Dijkstra tuần tự 118
Hình 5-2 : Thuật toán Dijkstra song song 119
Hình 5-3. Thuật toán Prim tuần tự 124
Hình 5-3 : Thuật toán Prim song song 125
Hình 5-4: Thuật toán Bellman-Ford tuần tự 130
Hình 5-5 : Thuật toán Bellman-Ford song song 132









Trang 13
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 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 toán hiệu năng cao, như là các ứng dụng song song dựa vào
trao đổi thông điệp tốc độ cao giữa các tiến trình song song.









Trang 14
Trong khi đó Cluster lại là các máy tính đơn hay đa bộ xử lý được kết
hợp tương đối với nhau thông qua đường mạng, vì thế nó chậm hơn từ 1 đến 2
lần so với kết nối MP. Ví dụ như cluster Beowulf chạy Linux, hay TCF
(Technical Compute Farm) của Sun chạy hệ điều hành Solaris/TM, chúng được
sử dụng cho các tính toán số lượng lớn, phân phối các tác vụ tính toán (thường
là không song song) cho các bộ xử lý, rồi thu thập lại các kết quả tính toán vào
k
ết quả toàn cục. Các tính toán này có thể là việc hiển thị hàng ngàn khung
hình để làm phim hay là giả lập việc kiểm tra và thiết kế để xây dựng thế hệ
tiếp theo của chip VLSI, hay như trong công nghệ sinh học, đó là việc cắt lớp
hàng trăm ngàn chuỗi gen.
Trong khi MPs và Cluster chỉ là các hệ thống đơn, thường là trong một
domain đơn. Grid điện toán bao gồm các cluster của mạng các MPs hay/và
cluster, nằm trên nhiều domain khác nhau, phân bố ở nhiều phòng ban, xí
nghiệp hay th
ậm chí là trên mạng Internet. Về bản chất, những grid có một độ
phức tạp cao hơn, đặc biệt là ở tầng trung gian, trong việc thực thi, quản lý, và
sử dụng các tài nguyên tính toán phân tán, và ở tầng ứng dụng là việc thiết kế,
phát triển, chạy các phần mềm để triển khai grid một cách hiệu quả.
Tóm lại Grid là một kiến trúc tính toán phân tán cho phép chuyển giao
các tài nguyên lưu trữ và tính toán như thể là một dịch vụ trên Internet. Đây là
bước phát triển tiếp theo về cơ sở hạ tầng kỹ thuật, cho phép kết nối các máy
tính phân tán, các thiết bị lưu trữ, các thiết bị di động, các công cụ, cơ sở dữ
liệu, và các ứng dụng phần mềm, và cung cấp cách thức truy cập duy nhất đến
cộng đồng người dùng để cho phép tính toán, trao đổi thông tin và cộng tác.
Một số hệ thống grid hiện tại như là NASA Information Power Grid (IPG);
DoD Distance Computing và NetSolve cho chia sẽ
và khai thác phần mềm toán
học; Nimrod cho chia sẽ tài nguyên trên phạm vi trường học; SETI@Home cho
tìm kiếm trí thông minh ngòai trái đất; hay là APGrid để kết nối các trung tâm
máy tính ở vành đai Châu Á Thái Bình Dương trong tương lai gần.

Xem chi tiết: 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ị