TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN CÔNG NGHỆ PHẦN MỀM
HUỲNH BÁ THANH TÙNG
TRẦN VIỆT CƯỜNG 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Ị
KHOÁ LUẬN CỬ NHÂN TIN HỌC
TP. HCM, NĂM 2005
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
KHOA CÔNG NGHỆ THÔNG TIN
BỘ MÔN CÔNG NGHỆ PHẦN MỀM HUỲNH BÁ THANH TÙNG - 0112079
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
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ă
• 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
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
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
độ cao giữa các tiến trình song song.
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 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
các khối xây dựng như vậy đang tồn tại trong trình quản lý tài nguyên mang tính
thương mại của phần mềm Sun Grid Engine.
Diễn đàn Grid (GGF – Global Grid Forum), được thành lập vào năm 1998,
đã tập hợp được hàng tr
ăm các nhà khoa học để cùng nhau nghiên cứu và thảo
luận về một kiến trúc Grid chung. Trong đó vẫn còn tồn tại một số thách thức sau:
• Phát triền phần mềm ứng dụng cho Grid
• Chỉ ra và truy cập các nguồn tài nguyên tính toán thích hợp trên môi
trường phân tán
• Định nghĩa những giao tiếp chuẩn cho phép giao tiếp giữa các khối Grid
với nhau, nhằm đáp ứng nhu cầu phát triển ứng dụng.
• Bảo đả
m các truy cập được xác nhận và truyền dữ liệu an toàn.
• Cung cấp các dịch vụ cho phép theo dõi, quảng cáo và kết xuất báo cáo.
• Thiết kế các nghi thức mạng cho việc trao đổi và định dạng thông điệp.
Trang 18
Chương 2. Tính toán song song và phân bố
2.1. Khái niệm
song song thì từ quan điểm của người lập trình gồm 2 thành phần chính quan trọng
đó là cách thức thể hiện các tác vụ song song (cấu trúc điều khi
ển) và những
phương pháp xác định tương tác giữa các tác vụ này (mô hình giao tiếp).
2.2.1. Kiến trúc xử lý song song và phân bố
Máy tính song song có thể được chia theo 2 lọai chính là : dòng điều khiển
(control flow) và dòng dữ liệu (data flow). Máy tính song song dòng điều khiển
dựa chủ yếu theo các nguyên tắc của máy tính Von Neumann, ngọai trừ nhiều
dòng điều khiển có thể thực hiện vào bất cứ thời gian nào. Máy tính song song
dòng dữ liệu , đôi khi được biết đến là “phi Von Neumann”, thì hoàn toàn khác
biệt ở chỗ nó không có con trỏ trỏ tới các chỉ thị hiện hành hay trung tâm điều
khiển.
Ở đây chúng ta chỉ tập trung vào các máy tính song song dòng điều khiển.
Năm 1966, M.J.Flynn đã phân chia các hệ thống máy tính dựa trên dòng chỉ
thị và dòng điều khiển thành 4 loại sau:
• SISD (Single Instruction stream, a Single Data stream)
• SIMD (Single Instruction stream, Multiple Data streams)
• MISD (Multiple Instruction streams, a Single Data stream)
• MIMD (Multiple Instruction streams, Multiple Data streams)
Phân theo mức độ hay được sử dụng: MIMD > SIMD > MISD Trang 19
Instruction Stream(s)
SISD
(Uniprocessors)
các tín hiệu điều khiển thích hợp cho các bộ xử lý theo chiều kim đồng hồ. Từng
bộ xử lý sẽ thực thi các chỉ thị một cách đồng thời, và chúng cũng có quyền không
tiếp nhận trên các chỉ thị nào đó. Sự phổ biến của kiến trúc SIMD là do tính năng
của các ứng dụng song song ban đầu và từ yêu cầu của nền kinh tế. Theo quan
điểm của người dùng thì các ứng dụng sử dụng kiến trúc SIMD thì dễ dàng được
lập trình hơn và tận dụng hiệu quả hơn các thiết bị phần cứng.
Hình 2-3 : Kiến trúc SIMD
Bên trong SIMD, tồn tại hai lựa chọn thiết kế cơ bản sau:
1. SIMD đồng bộ và bất đồng bộ.
Trong một máy SIMD, từng bộ xử lý
có thể thực thi hay bỏ qua các chỉ thị được quảng bá dựa vào trạng thái
cục bộ của nó hay những điều kiện phụ thuộc vào dữ liệu. Tuy nhiên
Trang 21
Trang 22
điều này có thể dẫn đến xử lý một vài tính toán điều kiện không hiệu
quả. Một cách giải quyết khả thi là sử dụng phiên bản bất đồng bộ của
S1IMD, được biết đến là SPMD (Single Program Multiple Data), trong
đó từng bộ xử lý sẽ chạy một bản sao của chương trình chung. Điểm
thuận lợi của SPMD là trong lúc tính toán biểu thức điều kiện “if-then-
else”, từng bộ
xử lý sẽ chỉ thực hiện ở nhánh thích hợp mà không mất
thời gian cho các chi phí tính toán khác.
2.
Chip SIMD tùy chọn hay thống nhất (commodity)
.
đặc biệt được truyền cùng với dữ liệu. Chính vì vậy mà cách tổ chức theo kiến trúc
MISD có thể được xem như là một hệ thống ống lệnh cấp độ cao và phức tạp với
nhiều đường dẫn và trong đó từng giai đọan có thể được lập trình riêng biệt.
2.1.4. MIMD
Được tiên đoán bởi các doanh nghiệp vào thập niên 90, mô hình MIMD gần
đây đã trở nên khá phổ biến. Lý do cho sự thay đổi này là vì tính uyển chuyển cao
của kiến trúc MIMD và bởi khả năng tận dụng được những ưu điểm của các bộ vi
xử lý được sản xuất hàng lọat (commodity microprocessors), vì thế tránh được
những vòng phát triển dài dòng và qua đó có thể được phát triển cùng với sự cải
thiện của các bộ xử
lý. Các máy tính MIMD được áp dụng rất hiệu quả cho các
ứng dụng song song mà vấn đề của nó được phân rã từ trung bình cho đến tốt
(medium- to coarse-grain parallel applications).Ưu điểm của các máy tính MIMD
Trang 23
bao gồm khả năng uyển chuyển cao trong việc khai thác nhiều dạng thức song
song khác nhau, dễ phân chia nhỏ hơn cho các bộ xử lý độc lập trong môi trường
đa người dùng (tính chất này là ngụ ý quan trọng cho tính dung lỗi), ít khó khăn
trong việc mở rộng (scalability). Nhưng bên cạnh đó kiến trúc này cũng có khuyết
điểm là sự quá tải do giao tiếp giữa các bộ xử lý và việc lập trình gặp nhiều khó
khăn.
Hình 2-5 : Kiến trúc MIMD
Trang 24
Trang 25
Bên trong kiến trúc MIMD, tồn tại 3 loại vấn đề cơ bản hay còn được gọi là
này về cơ bản là một phương pháp phân nhánh, đặc biệt thích hợp khi
có một sự truy cập rất lớn đến dữ liệu cụ
c bộ.
Copyright: Tài liệu đại học ©