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ị

112339 NGHIÊN CỨU TÍNH TỐN LƯỚI VÀ THỬ NGHIỆM MỘT SỐ THUẬT TỐN LÝ THUYẾT ĐỒ THỊ KHĨA LUẬN CỬ NHÂN TIN HỌC GIÁO VIÊN HƯỚNG DẪN TS. TRẦN ĐAN THƯ Th.S NGUYỄN THANH SƠN NIÊN KHĨA 2001-2005 ht t p : / / e t r i t h u c . v n NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... ht t p : / / e t r i t h u c . v n NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... ht t p : / / e t r i t h u c . v n 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 tồ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í để hồ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 ht t p : / / e t r i t h u c . v n 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 tố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 tố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 tố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 tồ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 tốn ở nhiều nơi trên thế giới để tạo ra một khả năng tính tốn khổng lồ, gĩp phần giải ht t p : / / e t r i t h u c . v n 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 tốn lưới và thực nghiệm trên một số thuật tốn lý thuyết đồ thị” Mục tiêu của đề tài đề ra tìm hiểu được về tính tố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 tố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 tốn lưới ht t p : / / e t r i t h u c . v n • 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 tố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 tốn lưới, khái niệm lịch sử phát triển. Chương 2. Tính tố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 tốn… Chương 3. Các mơi trường hỗ trợ tính tố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 tố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. ht t p : / / e t r i t h u c . v n 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 tốn lưới ...................................... 17 Chương 2. Tính tốn song song và phân bố ...................................................... 18 2.1. Khái niệm ..................................................................................... 18 2.2. Nền tảng tính tố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 tố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 tốn song song................................................... 50 Chương 3. Các mơi trường hỗ trợ tính tố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 ht t p : / / e t r i t h u c . v n 3.3.1. Một số mơi trường Grid................................................................... 59 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 đố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 tố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 ht t p : / / e t r i t h u c . v n 4.5.3. Pack và UnPack ............................................................................. 123 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 tố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 ht t p : / / e t r i t h u c . v n 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 ht t p : / / e t r i t h u c . v n 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 tố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 tốn Dijkstra song song....................................................................... 135 Hình 5-3. Thuật tốn Prim tuần tự .................................................................................. 141 Hình 5-3 : Thuật tốn Prim song song ............................................................................ 142 Hình 5-4: Thuật tốn Bellman-Ford tuần tự ................................................................... 145 Hình 5-5 : Thuật tốn Bellman-Ford song song ............................................................. 149 ht t p : / / e t r i t h u c . v n 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 tố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 tố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 ht t p : / / e t r i t h u c . v n Trang 15 tố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. 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 tốn số lượng lớn, phân phối các tác vụ tính tố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 tốn vào kết quả tồn cục. Các tính tố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 tố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 tố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 tốn phân tán cho phép chuyển giao các tài nguyên lưu trữ và tính tố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 tố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 tố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 ht t p : / / e t r i t h u c . v n Trang 16 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. Hình 1-1 : 3 tầng của Grid Grid là một cơ sở hạ tầng về phần cứng lẫn phần mềm cung cấp truy cập phụ thuộc, thích hợp, rộng khắp và chi phí thấp vào các khả năng tính tốn. Trong một tương lai khơng xa, những grid này sẽ được các kỹ sư, nhà khoa học, khoa học thực nghiệm, cơng ty, tổ chức, mơi trường, giáo dục và đào tạo, khách hàng, … sử dụng rộng rãi. Chúng sẽ dành riêng cho tính tốn theo yêu cầu, tính tốn trên thơng tin nhạy cảm, tính tốn cộng tác, và siêu tính tốn, dựa trên cơ sở của khách hàng/nhà cung cấp. Ngày nay chúng ta đang thấy những nỗ lực đầu tiên nhằm khai thác một cách cĩ hệ thống các nguồn tài nguyên tính tốn lưới trên mạng Internet. Những dự án này được gọi là peer-to-peer computing, như SETI@home, Distributed.Net và Folderol, cho phép người dùng Internet tải về các dữ liệu khoa học, chạy trên các máy cá nhân theo chu trình xử lý chia sẽ, và gửi lại kết quả cho cơ sở dữ liệu trung tâm. Gần đây cĩ một dự án ở một trường đại học, được gọi là Compute Power Market, được xây dựng nên nhằm phát triển các kỹ thuật phần mềm cho phép tạo lập những Grid, mà ở đĩ bất cứ ai cũng cĩ thể mua hay bán khả năng khả năng tính tốn giống như cách sử dụng điện hiện nay. ht t p : / / e t r i t h u c . v n Trang 17 1.2. Những thách thức đối với tính tốn lưới Hầu hết các kỹ thuật phức tạpbên dưới dành cho Grid hiện nay đang được tiếp tục phát triển. Các mơi trường Grid mẫu tồn tại giống như các dự án Globus và Legion. Đồ án EcoGrid thì đang nghiên cứu cách thức quản lý tài nguyên, và 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 tố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 tồ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. ht t p : / / e t r i t h u c . v n Trang 18 Chương 2. Tính tốn song song và phân bố 2.1. Khái niệm Ngày nay trong khi cơng nghệ ngày một phát triển thì nhu cầu về tốc độ tính tốn của các hệ thống máy tính cũng ngày một tăng cao. Các lĩnh vực địi hỏi tính tĩan hiệu năng cao như là mơ hình số và giả lập các vấn đề của khoa học và cơng nghệ. Ngồi ra nĩ cịn nhằm giải quyết các lọai vấn đề cần tốc độ xử lý cao như: • Mơ hình hĩa và giả lập Mơ hình các mẫu DNA Mơ hình hĩa chuyển động của các phi hành gia … • Xử lý/Thao tác trên các dữ liệu rất lớn Xử lý ảnh và tín hiệu Khai thác dữ liệu và cơ sở dữ liệu Xác định địa chấn … • Các vấn đề “grand challenge” (là những vấn đề khơng thể giải quyết trong thời gian “hợp lý”, như cần 100, 1000,…năm để cĩ đáp án) Mơ hình khí hậu Sự chuyển động của chất lỏng Bộ gene con người Mơ hình chất bán dẫn … Xuất phát từ nhu cầu đĩ đã dẫn đến sự cần thiết phải cĩ những hệ thống song song và phân bố nhằm tận dụng tối đa khả năng thực thi của các bộ xử lý, và để giải quyết các vấn đề nan giải trên. ht t p : / / e t r i t h u c . v n Trang 19 2.2. Nền tảng tính tốn song song và phân bố Trong phần này chúng ta sẽ xem xét cách tổ chức logic và vật lý của các nền tảng song song và phân tán. Cách tổ chức logic liên quan đến quan điểm của người lập trình (kiến trúc xử lý song song và phân bố) trong khi cách tổ chức vật lý liên quan đến cách cơ cấu thực sự của các phần cứng bên dưới. Trong tính tốn 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ì hồn tồ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 ht t p : / / e t r i t h u c . v n Trang 20 In st ru ct io n St re am (s) SISD(Uniprocessors) SIMD (Array Processors) MISD GMSV GMMP DMSV Data Stream(s) Single Multiple M u lti pl e Si n gl e Shared Variables Message Passing G lo ba l D is tri bu te d M e m o ry Communication DMMP MIMD Hình 2-1 : Phân lọai hệ thống máy tính theo Flynn-Johnson 2.1.1. SISD Hình 2-2 : Kiến trúc SISD Kiến trúc này tương tự với kiến trúc Von Neumann. Một đơn vị điều khiển tiếp nhận một chỉ thị đơn từ bộ nhớ, sau đĩ đưa vào cho bộ xử lý thực thi trên một đơn vị dữ liệu được chỉ ra trong chỉ thị nhận được, và cuối cùng là đưa kết quả nhận được vào bộ nhớ. 2.1.2. SIMD Hầu hết các máy tính song song ban đầu đều được thiết kế theo kiến trúc SIMD. Trong kiến trúc này, một đơn vị xử lý trung tâm sẽ thơng dịch và quảng bá 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 ht t p : / / e t r i t h u c . v n Trang 21 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 ht t p : / / e t r i t h u c . v n Trang 22 điều này cĩ thể dẫn đến xử lý một vài tính tố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 tố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 tốn khác. 2. Chip SIMD tùy chọn hay thống nhất (commodity). Một máy SIMD cĩ thể được thiết kế dựa trên những thành phần thống nhất hay là từ những con chip tùy chọn. Trong cách tiếp cận thứ nhất thì các thành phần cĩ xu hướng rẻ hơn do sản xuất hàng loạt. Tuy nhiên những thành phần mang mục đích chung như vậy cĩ thể chứa các yếu tố khơng cần thiết cho một thiết kế cụ thể nào đĩ. Những thành phần thêm vào cĩ thể làm phức tạp việc thiết kế, sản xuất và kiểm thử các máy SIMD và cũng cĩ thể đem lại khiếm khuyết về tốc độ xử lý. Cịn các thành phần tùy chọn thì nhìn chung hỗ trợ tốt hơn cho thực thi tuy nhiên nĩ cũng dẫn đến chi phí cao hơn cho việc phát triển. Khi việc tích hợp nhiều bộ xử lý cùng với bộ nhớ dư dật trên một con chip VLSI đơn trở nên khả thi, thì việc kết hợp ưu điểm của 2 cách tiếp cận trên là hồn tồn cĩ thể. 2.1.3. MISD Mơ hình này hầu như khơng thấy nhiều trong các ứng dụng. Một trong những lý do là bởi vì hầu hết các ứng dụng khơng thế áp dụng một cách dễ dàng vào kiến trúc MISD, điều này dẫn đến việc thiết kế ra một kiến trúc để thỏa mãn cho một mục đích chung là điều khơng thể. Tuy nhiên cĩ thể áp dụng các bộ xử lý song song kiểu MISD vào trong một ứng dụng cụ thể nào đĩ. ht t p : / / e t r i t h u c . v n Trang 23 Hình 2-4 : Kiến trúc MISD Trong hình trên là ví dụ về một bộ xử lý song song với kiến trúc MISD. Một dịng dữ liệu đơn đi vào một máy tính gồm 5 bộ xử lý. Nhiều phép biến đổi được thực hiện trên từng đơn vị dữ liệu trước khi nĩ được chuyển sang một (hay nhiều) bộ xử lý khác. Các đơn vị dữ liệu kế tiếp cĩ thể đi qua các phép biến đổi khác do điều kiện độc lập dữ liệu của các dịng chỉ thị hay do các thẻ điều khiển đặ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 đố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 ht t p : / / e t r i t h u c . v n Trang 24 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 ht t p : / / e t r i t h u c . v n 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à cách lựa chọn thiết kế hiện vẫn là chủ đề đang được tranh cãi trong cộng đồng các nhà nghiên cứu. 1. MPP – massively or moderately parallel processor. Việc xây dựng một bộ xử lý song song từ một số lượng nhỏ các bộ xử lý mạnh mẽ hay từ một số lượng rất lớn các bộ xử lý bình thường (một “bầy voi” hay là một “đàn kiến”) thì cách nào sẽ hiệu quả hơn ?. Theo luật của Amdahl thì cách đầu tiên thích hợp hơn cho những phần tuần tự của một tính tốn, trong khi cách tiếp cận thứ hai sẽ làm tăng tốc hơn nữa những phần mang tính song song. Khơng thể đưa ra một câu trả lời chung cho câu hỏi này, sự lựa chọn tốt nhất tùy thuộc vào loại cơng nghệ và ứng dụng đang được sử dụng. 2. MIMD “chặt chẽ” hay “lỏng lẻo”. Cách tiếp cận nào tốt hơn cho việc tính tốn hiệu năng cao, bằng cách sử dụng đa bộ xử lý được thiết kế đặc biệt trên nhiều máy tính hay là tập hợp của những máy trạm bình thường được kết nối với nhau bởi các hệ thống mạng “tiện nghi” (như là Ethernet hay ATM) và những tương tác nào sẽ được kết nối với nhau bằng hệ thống phần mềm đặc biệt và các hệ thống tập tin phân tán? Cách tiếp cận thứ hai đơi khi được biết đến là mạng của các máy trạm (network of workstations hay là NOW) hay là tính tốn cluster, đã được sử dụng rộng rãi trong những năm gần đây. Tuy nhiên vẫn cịn nhiều vấn đề mở cịn tồn tại nhằm phát huy tối đa khả năng của những kiến trúc cĩ nền tảng là mạng. Thiết bị phần cứng, hệ thống phần mềm, và những khía cạnh ứng dụng của NOW đang được đầu tư tìm hiểu bởi một số lượng lớn các nhĩm ngiên cứu. Một cách tiếp cận trung gian là kết hợp các cluster những bộ xử lý thơng qua mơi trường mạng. Điều 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ộ. ht t p : / / e t r i t h u c . v n Trang 26 3. Truyền thơng điệp tường minh hay chia sẽ bộ nhớ ảo. Lọai nào sẽ tốt hơn, cho phép người dùng chỉ ra tất cả các loại thơng điệp sẽ được truyền giữa các bộ xử lý hay là cho phép họ lập trình ở một cấp độ trừu tượng cao hơn, cùng với các thơng điệp cần thiết tự động được phát sinh bởi hệ thống phần mềm? Câu hỏi này về cơ bản là tương tự với câu được hỏi trong những ngày đầu của những ngơn ngữ lập trình cấp cao và bộ nhớ ảo. Tại một vài thời điểm trong quá khứ, việc lập trình bằng hợp ngữ và thực hiện trao đổi giữa bộ nhớ chính và bộ nhớ phụ cĩ thể đem lại hiệu quả cao hơn. Tuy nhiên, do ngày nay các phầm mềm đã đạt đến mức quá phức tạp, các trình biên dịch cùng với hệ điều hành cũng đã quá cấp cao đến nỗi việc tối ưu các chương trình bằng tay khơng cịn là điều gì quá khĩ. Tuy nhiên chúng ta vẫn chưa ở thời điểm xử lý song song đáng kể, và việc che giấu cấu trúc giao tiếp tường minh giữa các máy tính song song ra khỏi người lập trình sẽ đem lại hiệu năng thực thi rất đáng kể. 2.2.2. Tổ chức vật lý của các nền tảng song song và phân bố Trong phần này chúng ta sẽ chỉ mơ tả một máy tính song song lý tưởng là PRAM. Đây là một cách mở rộng tự nhiên của mơ hình tính tốn tuần tự (Random Access Machine hay là RAM) bao gồm p bộ xử lý và một vùng nhớ tồn cục cĩ kích thước khơng giới hạn và được truy cập từ tất cá các bộ xử lý. Tất cả chúng đều cĩ sử dụng cùng chung một khơng gian địa chỉ. Các bộ xử lý cĩ thể cùng chia sẽ một đồng hồ chung nhưng cũng cĩ thể thực thi các chỉ thị khác nhau trên cùng một chu kỳ. Mơ ình này được biết đến là parallel random access machine (PRAM). Tùy thuộc vào cách thức truy cập bộ nhớ, PRAM được phân thành 4 loại sau. 1. Tồn quyền đọc - Tồn quyền ghi (exclusive-read, exclusive write) EREW. Trong loại này, truy cập vào vùng nhớ là tồn quyền. Khơng cĩ ht t p : / / e t r i t h u c . v n Trang 27 thao tác đọc ghi nào được cho phép. Đây là mơ hình PRAM khơng chắc chắn nhất, chỉ hỗ trợ truy cập đồng thời vào bộ nhớ một cách tối thiểu. 2. Đồng thời đọc – Tồn quyền ghi (concurrent read, exclusive write) CREW. Cho phép nhiều thao tác đọc cùng lúc trên cùng một vùng nhớ, tuy nhiên nhiều thao tác ghi chỉ thực hiện theo tuần tự. 3. Tồn quyền đọc – Đồng thời ghi (exclusive read, concurrent write) ERCW. Cho phép nhiều thao tác ghi cùng lúc trên cùng một vùng nhớ, tuy nhiên nhiều thao tác đọc chỉ thực hiện theo tuần tự. 4. Đồng thời đọc – Đồng thời ghi (concurrent read, co current write) CRCW. Trong loại này, cho phép nhiều thao tác đọc ghi đồng thời trên cùng vùng nhớ chung. Đây là mơ hình PRAM cĩ nhiều ưu điểm nhất. Việc cĩ nhiều thao tác đọc cùng một lúc khơng làm ảnh hưởng đến tính nhất quán của chương trình. Tuy nhiên khi cĩ nhiều thao tác ghi đồng thời thì lại cĩ ảnh hưởng lớn, vì thế cĩ nhiều cách thức được đặt ra để giải quyết vấn đề đĩ: • Chung (common), thao tác ghi cùng lúc chỉ được thực hiện nếu tất cả các bộ xử lý đều muốn ghi một giá trị như nhau. • Tùy ý (arbitrary), chỉ cho phép một bộ xử lý bất kỳ được ghi. • Ưu tiên (priority), tất cả các bộ xử lý được tổ chức theo một danh sách ưu tiên được xác định trước, và bộ xử lý cĩ quyền cao nhất sẽ cĩ quyền ghi. • Tổng hợp (sum), trong đĩ giá trị tổng của các giá trị cần ghi sẽ được ghi. 2.3. Một số mơ hình lập trình song song thơng dụng 2.3.1. Mơ hình chia sẽ khơng gian bộ nhớ Lập trình song song tường minh thường yêu cầu chỉ ra cụ thể các tác vụ song song cùng với các tương tác giữa chúng. Những tương tác này cĩ thể ở trong dạng đồng bộ giữa các tiến trình đồng thời hay là sự giao tiếp giữa các kết quả trung gian. Trong kiến trúc chia sẽ khơng gian bộ nhớ, giao tiếp giữa các tiến trình ht t p : / / e t r i t h u c . v n Trang 28 được chỉ ra là ngụ ý vì tất cả các bộ xử lý đều cĩ quyền truy cập vào một vài (hay tất cả) các bộ nhớ. Do đĩ, mơ hình lập trình cho các máy tính chia sẽ khơng gian địa chỉ tập trung chủ yếu vào các cách thức để thực thi đồng thời, đồng bộ hĩa và những cách để làm giảm sự quá tải do tương tác. Các mơ hình lập trình chia sẽ khơng gian địa cĩ thể khác nhau về cách thức chia sẽ dữ liệu, mơ hình đồng thời, và hỗ trợ đồng bộ hĩa. Các mơ hình giả sử rằng tất cả các dữ liệu của tiến trình đều mặc định là khơng được truy cập, trừ khi nĩ cho phép làm điều đĩ (sử dụng các hàm gọi của hệ thống UNIX như shmat và shmget). Mặc dù đây là một yếu tố quan trọng nhằm bảo mật trong các hệ thống đa người dùng, tuy nhiên khí chúng cùng nhau hợp tác để giải quyết cùng một vấn đề thì điều này là khơng cịn cần thiết. Các chi phí do bảo vệ dữ liệu gia tăng chỉ làm cho các tiến trình ít thích hợp hơn cho lập trình song song. Ngược lại, các tiến trình và tiểu trình giả sử tồn bộ bộ nhớ là tồn cục, và chúng sẽ thực hiện trao đổi thơng tin với nhau một cách tường minh thơng qua đọc và ghi lên biến chia sẽ. Hình 2-6 : Mơ hình chía sẽ khơng gian bộ nhớ Vì các tiến trình đều cĩ quyền đọc và ghi lên vùng nhớ chung vào cùng một thời điểm nên ta cần phải cĩ một cơ chế đồng bộ hĩa để bảo đảm tính đúng đắn khi thao tác trên dữ liệu. 2.3.2. Mơ hình truyền thơng điệp Cĩ rất nhiều ngơn ngữ lập trình và các thư viện được xây dựng nên để dành cho lập trình song song. Những điều này khác nhau ở cách nhìn của chúng về ht t p : / / e t r i t h u c . v n Trang 29 khơng gian địa chỉ dành cho người lập trình, mức đồng bộ trong các chỉ thị song song và sự đa dạng của các chương trình. Mơ hình lập trình truyền thơng điệp là một trong các mơ hình cổ nhất và được sử dụng rộng rãi nhất trong các mơ hình dùng cho lập trình trên các máy tính song song. Lý do chính cho việc này là vì nĩ yêu cầu tối thiểu về phần cứng bên dưới. Trong phần này chúng ta sẽ đề cập một vài khái niệm căn bản về mơ hình truyền thơng điệp và các kỹ thuật dùng với thư viện MPI (sẽ mơ tả kỹ trong chương sau). Hình 2-7 : Mơ hình truyền thơng điệp Cĩ 2 tính chất quan trọng tạo nên bản chất của mơ hình truyền thơng điệp là: thứ nhất là nĩ giả sử khơng gian địa chỉ được phân chia và thứ hai là nĩ chỉ hỗ trợ song song hĩa tường minh. Cấu trúc của những chương trình truyền thơng điệp Các chương trình truyền thơng điệp thường được viết bằng cách sử dụng mơ hình bất đồng bộ hay ít đồng bộ. Trong mơ hình bất đồng bộ, tất cả các tác vụ song song được thực thi một cách bất đồng bộ. Điều này cho phép ta cĩ thể triển khai bất cứ thuật tốn song song nào. Tuy nhiên những chương trình như vậy thường gặp khĩ khăn hơn để suy ra và bên cạnh đĩ cách thể hiện của nĩ cũng khĩ mà đốn trước do những điều kiện về thực thi. Ngược lại những chương trình ít ht t p : / / e t r i t h u c . v n Trang 30 đồng bộ cĩ thể kết hợp tốt cả hai thái cực này. Trong những chương trình như vậy, các tác vụ và những tập hợp con các tác vụ được đồng bộ hĩa để thực hiện những tương tác. Tuy nhiên giữa những tương tác này, các tác vụ được thực thi hồn tồn bất đồng bộ. Bởi vì những tương tác xảy ra một cách đồng bộ, nên việc suy ra chương trình như vậy cũng khá dễ dàng. Nhiều thuật tốn song song phổ biến cũng được thực hiện một cách tự nhiên bằng cách sử dụng những chương trình ít đồng bộ hơn. Trong dạng phổ biến nhất của mình, mơ hình truyền thơng điệp hỗ trợ thực thi cho các chương trình khác nhau trên từng bộ xử lý. Điều này cung cấp tính mềm dẻo tối đa trong lập trình song song, nhưng điều này cũng làm cho cơng việc viết các chương trình song song khơng thể mở rộng một cách hiệu quả. Vì nguyên nhân này mà hầu hết các chương trình truyền thơng điệp được viết bằng cách sử dụng phương pháp single program multiple data (SPMD). Trong những chương trình SPMD, các tiến trình khác nhau thực thi đoạn code tương tự nhau ngọai trừ một số nhỏ các tiến trình (là những tiến trình “gốc”). Điều này khơng cĩ nghĩa là những tiến trình làm việc theo lock-step. Các chương trình SPMD cĩ thể là ít đồng bộ hay là hồn tồn bất đồng bộ. 2.4. Cách thức xây dựng một chương trình song song và phân bố Phát triển thuật tốn là một phần quan trọng trong việc giải quyết vấn đề khi sử dụng máy tính. Một thuật tốn tuần tự về cơ bản là một phương pháp thực hiện hay là một chuỗi tuần tự những bước cơ bản để giải quyết một vấn đề được đặt ra bằng cách sử dụng máy tính tuần tự. Tương tự, một thuật tĩan song song là một phương pháp giải quyết vấn đề dựa trên việc sử dụng nhiều bộ xử lý. Tuy nhiên, để chỉ ra được một thuật tĩan song song khơng đơn giản như là chỉ ra từng bước cụ thể. Mà là ở một mức độ nào đĩ, một thuật tĩan song song phải được thêm vào tính đồng thời và người thiết kế ra thuật tốn cũng phải chỉ ra tập hơp những bước cĩ thể xử lý đồng thời. Điều này nhằm tận dụng được khả năng tính ht t p : / / e t r i t h u c . v n Trang 31 tốn của các máy tính song song. Trong thực tế việc thiết kế ra một thuật tĩan song song là khá phức tạp, nĩ cĩ thể bao gồm một vài hay tất cả những điều sau: • Chỉ ra những phần của cơng việc cĩ thể được thực thi đồng thời. • Ánh xạ các phần của cơng việc vào nhiều bộ xử lý chạy song song. • Phân tán dữ liệu nhập, xuất và trung gian cùng với chương trình. • Quản lý truy cập vào dữ liệu chung giữa các bộ xử lý. • Đồng bộ hĩa các bộ xử lý khi thực thi các chương trình song song 2.4.1. Các thuật ngữ căn bản
Phân họach : là quá trình phân chia một vấn đề cần tính tốn thành các phần nhỏ hơn, một vài hay tất cả các phần đĩ cĩ thể xử lý song song.
Tác vụ : là đơn vị do người lập trình định nghĩa để chỉ ra các phần tính tốn sau khi phân họach. Xử lý đồng thời nhiều tác vụ là điều kiện tiên quyết để rút ngắn thời gian giải quyết tồn bộ vấn đề. Các tác vụ cĩ thể khơng cùng kích thước.
Đồ thị phụ thuộc : là một thể hiện sự phụ thuộc giữa các tác vụ và trật tự thực hiện giữa chúng. Một đồ thị phụ thuộc là một đồ thị cĩ hướng trong đĩ mỗi nút của cây là một tác vụ và cạnh cĩ hướng thể hiện sự phụ thuộc giữa chúng. Một tác vụ chỉ được thực hiện khi các tác vụ trước nĩ (cĩ cạnh nối) được thực hiện. Trong đồ thị phụ thuộc tập hợp cạnh cĩ thể rỗng. ht t p : / / e t r i t h u c . v n Trang 32 Hình 2-8 : Đồ thị phụ thuộc tác vụ
Granularity : số lượng và kích thước của các tác vụ sau bước phân họach được gọi là granularity của bước phân họach. Bước phân họach một vấn đề lớn thành một số lượng lớn các vấn đề nhỏ được gọi là fine- grained và thành một số lượng nhỏ các vấn đề lớn đựơc gọi là coarse- grained.
Đồ thị tương tác : là mơ hình thể hiện sự tương tác giữa các tác vụ. Các nút trong đồ thị tương tác thế hiện các tác vụ cịn các cạnh nối thể hiện tưong tác giữa chúng. Các cung trong đồ thị tương tác thường là cung vơ hướng. Tập hợp cạnh thuờng là tập hợp cha của tập hợp cạnh của đồ thị phụ thuộc Hình 2-9 :Đồ thi tương tác trong bài tốn nhân ma trận với vector ht t p : / / e t r i t h u c . v n Trang 33 2.4.2. Thiết kế thuật tốn song song Phân chia một cơng việc tính tốn thành các phần nhỏ hơn và ánh xạ chúng vào các bộ xử lý khác nhau để thực hiện song song là 2 bước cơ bản trong vịêc thiết kế một thuật tĩan song song. 2.4.2.1. Một số phương pháp phân hoạch Một trong những bước cơ bản mà chúng ta cần làm để giải quyết một vấn đề theo hướng song song là phân chia những phép tính tốn muốn thực hiện thành mơt tập hợp các tác vụ nhỏ hơn để xử lý đồng thời như trong đồ thị phụ thuộc tác vụ. Trong phần này chúng ta sẽ mơ tả một vài kỹ thuật phân họach phổ biến cho xử lý đồng hành. Các kỹ thuật này khơng phải là tất cả các kỹ thuật phân họach cĩ thể cĩ. Thêm vào đĩ, những phương pháp phân họach ở đây khơng bảo đảm sẽ dẫn tới những thuật tốn song song tốt nhất cho một vấn đề nào đĩ. Mặc dù cịn một vài thiếu sĩt, nhưng các kỹ thuật phân họach được đề cập trong phần này là điểm bắt đầu tốt cho nhiều vấn đề và một hay n iều sự kết hơp của các kỹ thuật này cĩ thể được dùng để đạt được các phân họach hiệu quả cho rất nhiều lọai vấn đề. Các kỹ thuật phân họach phân họach ở đây cĩ thể phân thành các lọai sau phân họach đệ quy, phân họach dữ liệu, phân họach thăm dị và phân họach suy đĩan. Trong đĩ phân họach đệ quy và phân họach dữ liệu được dùng cho nhiều lọai vấn đề cịn các phương pháp phân họach khác chỉ được sử dụng cho một lọai vấn đề cụ thể nào đĩ. • Phân họach đệ quy Phân họach đệ quy là một phương pháp dùng để tạo ra sự đồng hành trong những vấn đề cĩ thể được giải quyết bằng phương pháp chia-và-trị. Trong kỹ thuật này trước tiên một vấn đề được giải quyết bằng cách phân chia nĩ thành tập hợp các vấn đề con độc lập với nhau. Đến phiên các vấn đề con lại tiếp tục áp dụng cách thức phân họach đệ quy thành các vấn đề con khác nhỏ hơn. Cuối cùng là ht t p : / / e t r i t h u c . v n Trang 34 chúng ta sẽ thực thi đồng hành các vấn đề con độc lập này, kết quả của vấn đề lớn là sự kết hợp kết quả của các vấn đề con nhỏ hơn. • Phân hoạch dữ liệu Phân họach theo dữ liệu là một phương pháp phân hoạch hiệu quả và được sử dụng nhiều nhất trong việc xác định tính đồng hành trong các thuật tốn để cĩ thể thao tác trên các cấu trúc dữ liệu lớn. Phương pháp này bao gồm 2 bước. Trong bước 1, dữ liệu trong bước tính tĩan sẽ được phân ra thành từng phần, và trong bước 2, phần dữ liệu này sẽ được chuyển thành các tác vụ. Những thao tác mà các tác vụ thực hiện trên các phần dữ liệu khác nhau thường là tương tự nhau hay được chọn từ tập hợp các thao tác nhỏ hơn. Chúng ta sẽ xem xét cụ thể các cách phân chia dữ liệu cĩ thể ở phần bên dưới. Nhìn chung, thì người thiết kế phải tự tìm ra và đánh giá các cách phân chia dữ liệu để quyết định xem cách nào phân họach “tự nhiên” và hiệu quả nhất.
Phân chia dữ liệu xuất Trong nhiều phần tính tốn, từng phần xuất cĩ thể được xử lý độc lập với các phần khác. Trong nhiều phần tính tốn như vậy, việc phân chia dữ liệu xuất tự động dẫn đến việc phân họach những vấn đề thành các tác vụ, với mỗi tác vụ được kết gán cho cơng việc tính tốn một phần của kết quả xuất. vd: nhân ma trận Hãy xem vấn đề nhân 2 ma trận nxn A và B, kết quả trả về là ma trận C. Trước tiên ta phân từng ma trận thành 4 khối hay ma trận con, bằng cách chia các chiều của ma trận theo 1 nửa. 4 ma trận con của ma trận kết quả C, mỗi phần cĩ kích thước n/2 x n/2, cĩ thể được tính tĩan độc lập với nhau bởi 4 tác vụ. ht t p : / / e t r i t h u c . v n Trang 35 Hình 2-10 : (a) Phân các ma trận nhập và xuất thành các ma trận con (b) Phân hoạch phép nhân ma trận thành 4 tác vụ Hầu hết các thuật tốn ma trận, bao gồm nhận ma trận với vector và nhân ma trận với ma trận, cĩ thể được cơng thức hĩa thành các thao tác trên khối ma trận. Trong các cơng thức này, từng ma trận được xem như bao gồm các khối hay các ma trận con, các phép tính tốn được thực hiện trên từng phần tử và được thay thế tương ứng bởi các phép tĩan trên các khối ma trận con. Kết quả cĩ được trên từng phần tử hay trên các khối là tương tự nhau. Thuật tốn ma trận khối thường được dùng để hỗ trợ cho việc phân họach. Chúng ta phải chú ý là phân họach theo dữ liệu khác với phân họach các phép tính thành các tác vụ. Mặc dù 2 khái niệm này thường cĩ liên hệ với nhau, và cái đầu thường hỗ trợ cho cái sau, một kết quả phân họach dữ liệu đã cho khơng chỉ cĩ một cách để phân chúng thành các tác vụ.
Phân chia dữ liệu nhập Phân chia theo dữ liệu xuất chỉ cĩ thể được thực hiện nếu từng kết quả xuất cĩ thể được tính tốn một cách tự nhiên theo chức năng nhập. Trong nhiều thuật tốn, việc phân chia theo dữ liệu xuất là điều khơng thể. Ví dụ như khi tìm giá trị lớn nhất, nhỏ nhất hay tổng của các số đã cho, kết quả xuất là điều khơng thể biết ht t p : / / e t r i t h u c . v n Trang 36 trước. Trong các thuật tốn sắp xếp, từng phần tử riêng biệt của kết quả khơng thế được xác định một cách hiệu quả. Trong những trường hợp như vậy, việc phân chia theo dữ liệu nhập là hồn tồn cĩ thể, và sau đĩ dùng kết quả này để thực hiện đồng thời việc tính tốn. Từng tác vụ được tạo ra cho từng phần dữ liệu nhập và tác vụ này sẽ sử dụng tối đa các phép tính cĩ thể thực hiện trên các dữ liệu cục bộ này. Lưu ý là những giải pháp cho các tác vụ được đúc kết từ dữ liệu nhập cĩ thể khơng giải quyết được một cách trực tiếp vấn đề gốc. Trong những trường hợp như vậy, thì kết quả tính tốn cĩ thể được thực hiện bằng cách “nổi bọt” lên phía trên.Ví dụ như khi tìm tổng của một chuỗi gồm N số dùng p tiến trình (p < N), chúng ta cĩ thể phân chia phần dữ liệu nhập thành p phần con (cĩ kích thước gần bằng nhau). Từng tác vụ thực hiện cộng các số trong từng phần con. Kết quả cuối cùng là cộng của p phần con vừa được tính.
Phân chia cả dữ liệu xuất và nhập Trong nhiều trường hợp việc phân chia theo cả kết quả xuất và dữ liệu nhập cĩ thể làm tăng khả năng xử lý đồng thời.
Phân chia dữ liệu trung gian Các thuật tốn thường cĩ dạng xử lý gồm nhiều giai đọan khác nhau, trong đĩ kết quả xuất của giai đọan này là kết quả nhập của giai đọan theo sau nĩ. Quá trình phân họach cho những thuật tốn như vậy cĩ thể được thực hiện bằng cách phân chia theo dữ liệu nhập hay theo dữ liệu xuất của một giai đọan trung gian. Phân chia theo dữ liệu trung gian đơi khi dẫn tới._.4.5.3. Pack và UnPack Cung cấp những chức năng cho việc truyền nhận dữ liệu khơng liên tục . Ứng dụng sẽ nén dữ liệu vào một bộ đệm liên tục trước khi gửi di .và giải nén sau khi nhận được . Hai hàm thường sử dụng cho việc nén và giải nén là MPI_Pack(void* inbuf, int incount, MPI_Datatype datatype, void *outbuf, int outsize, int *position, MPI_Comm comm) MPI_Pack nén thơng điệp với nội dung thơng điệp là inbuf, incount,datatype,comm vào khơng gian bộ đệm (với thơng tin outbuf và outsize). Bộ đệm vào (inbuf) cĩ thể là bất kỳ bộ đệm truyền thơng (mà được cho phép trong giao tiếp gửi MPI_SEND) và dữ liệu ra (output buffer) là một vùng lưu trữ liên tục chứa outsize bytes, bắt đầu với địa chỉ outbuf MPI_Unpack(void* inbuf, int insize, int *position, void *outbuf, int outcount, MPI_Datatype datatype, MPI_Comm comm) Ngược lại với chức năng của hàm MPI_Pack ,MPI_Unpack giải nén một thơng điệp được đặc tả thơng tin ( giá trị inbuf,kích thước insize) vào bộ đệm nhận được đặt tả với thơng tin (giá trị outbuf,kích thước outsize, dạng dữ liệu datatype) .Bộ đệm đầu ra thuộc bất kỳ dạng dữ liệu nào được truyền thơng trong hàm nhận MPI_Recv. Bộ đệm đầu vào (input buffer) là dạng dữ liệu liên tục chứa insize bytes, bắt đầu với địa chỉ của ìnbuf ht t p : / / e t r i t h u c . v n Trang 124 Việc phân biệt ngữ nghĩa giữ kiểu dữ liệu bổ sung và kiểu dữ liệu MPI_PACKED rất khĩ .Tuỳ theo ngữ cảnh mà người dùng tự chọn cho mình cách biểu thị tốt nhất cho bài tốn tối ưu về mặt ngữ nghĩa và truyền thơng trong các thuật tốn cụ thể 4.6. Quản lý nhĩm và communicator 4.6.1. Tổng quan Nhắc lại, Group là một tập hợp cĩ thứ tự các xử lý. Mỗi xử lý trong một nhĩm là một sự kết hợp với một rank duy nhất. Gía trị Rank trong phạm vi từ 0 đến N-1, trong đĩ N là số xử lý trong nhĩm. Bên trong MPI, một Nhĩm đại diện bên trong bộ nhớ hệ thống như một đối tượng. Người lập trình truy xuất đĩ như một ‘handle’. Một nhĩm luơn luơn liên kết với một đối tượng communicator. Một Communicator đặt trưng cho một nhĩm các xử lý cái mà sẽ giao tiếp với các nhĩm khác. Tất cả thơng điệp phải đặt tả một communicator. Trong trường hợp đơn giản nhất, một communicator là một ‘tag’ mở rộng cái mà bao gồm với những lời gọi MPI. Giống như những nhĩm, những communicators được thể hiện bên trong hệ thống bộ nhớ như những đối tượng và những lập trình viên chỉ truy xuất bằng các ‘handle’. Ví dụ,handle của một communicator mà quản lý tất cả các tác vụ là MPI_COMM_WORLD Mục tiêu chính của Group và những đối tượng Communicator: • Cho phép tổ chức tác vụ, dựa trên chức năng, vào trong những nhĩm tác vụ. Làm cho những thao tác Collective Communication cĩ thể thực hiện liên kết một tập các tác vụ liên quan. • Cung cấp nền tảng cho mơ hình vật lý ảo do người dùng dịnh mơ phỏng (virtual topology) • Cung cấp sự giao tiếp an tồn dữ liệu khi truyền nhận do sử dụng tối ưu các thuật tốn liên quan trên một communicator Group và ht t p : / / e t r i t h u c . v n Trang 125 Communicator là tự động, chúng cĩ thể được tạo và hủy bỏ trong suốt sự thực thi của chương trình Những xử lý cĩ thể xuất hiện nhiều hơn trên một group /communicator.Chúng sẽ cĩ một rank duy nhất trong mỗi group /communicator MPI cung cấp trên r ất nhiều hàm liên quan đến group, communicator Communicator là một đối tượng khơng rõ ràng, với một số thuộc tính, và một số quy tắc đơn giản. A Communicator đặc tả miền truyền thơng cĩ thể được sử dụng cho sự truyền thơng point-to-point. Intracommunicator được sử dụng cho truyền thơng bên trong một nhĩm của những xử lý trong nhĩm đĩ .Intracommunicator cũng được sử dụng cho những collective operations Một intercommunicator được sử dụng cho truyền thơng điểm điểm (point- to-point) giữa những nhĩm xử lý tách rời nhau.Những thuộc tính của mơt intercommunicator là hai nhĩm .Khơng cĩ virtual topology nào (sẽ đề cập sau) liên kết với một intercommunicator Chức năng Intracommunicator Intercommunicator Số nhĩm 1 2 An tồn giao tiếp Cĩ Cĩ Collecitve Communication Cĩ Khơng Topologies Cĩ Khơng Group Management (Sự quản lý nhĩm) Mơ tả sự vận dụng những nhĩm xử lý bên trong MPI. Những thao tác này là local và sự thực thi của nĩ khơng yêu cầu sự giao tiếp giữa các xử lý. MPI cho phép sự vận dụng những nhĩm bên ngồi những communicator nhưng những nhĩm chỉ cĩ thể được sử dụng cho truyền thơng điệp bên trong một communicator Communicator management(Sự quản lý communicator) ht t p : / / e t r i t h u c . v n Trang 126 Mơ tả sự vận dụng của những communicator bên trong MPI.Những thao tác này truy xuất communicators cái mà local và những sự thực thi của nĩ khơng yêu cầu sự giao tiếp giữa các xử lý .Những thao tác này tạo ra những communicator chung và cĩ thể yêu cầu giao tiếp giữa các xử lý. Chúng ta mơ tả những cư xử của những hàm này, thừa nhận rằng tham số comm là một intracommunicator 4.6.2. Nguyên tắc sử dụng 1. Mở rộng handle của nhĩm cha từ MPI_COMM_WORLD bằng cách sử dụng MPI_Comm_group 2. Tạo ra một nhĩm mới như một tập con của nhĩm cha bằng cách sử dụng MPI_Group_incl 3. Tạo ra một communicator mới cho mỗi nhĩm mới bằng cách sử dụng MPI_Comm_create 4. Xác định rank mới trong communicator mới bằng cách sử dụng MPI_Comm_rank 5. Thực hiện giao tiếp các communicator sử dụng các hàm MPI Messsage pasing 6. Khi kết thúc ,giải phĩng communicator mới và group mới tạo với hàm MPI_Comm_free và MPI_Group_free Group Tạo group MPI_Comm_group (MPI_Comm comm ,*group): Xác định group liên kết với một communicator cho trước MPI_Group_excl(MPI_Group group,int n,int *rank,MPI_Group *newgroup): Phát sinh ra một nhĩm bằng các sắp xếp lại một nhĩm đã cĩ và chỉ lấy những thành viên chưa được lệ kê trong danh sách ht t p : / / e t r i t h u c . v n Trang 127 MPI_Group_incl(MPI_Group group,int n,int *ranks,MPI_Group*newgroup) : Phát sinh một nhĩm bằng các sắp xếp lại một nhĩm sẵn cĩ và chỉ lấy những thành viên được liệt kê trong danh sách MPI_Group_intersection(MPI_Group group1,MPI_Group group2,MPI_Group*newgroup): Phát sinh ra một nhĩm là giao của hai nhĩm cho trước với nhau MPI_Group_union(MPI_Group group1,MPI_Group group2,MPI_Group*newgroup):Giống như MPI_Group_intersection nhưng là hợp của hai nhĩm MPI_Group_difference(MPI_Group group1,MPI_Group group2,MPI_Group *newgroup) :Tạo ra một nhĩm mới từ hiệu của hai nhĩm cho trước Truy xuất group MPI_Group_rank(MPI_Group group,int *rank):Trả về rank của xử lý này bên trong một group cho trước ,hay trả về MPI_UNDEFINED nếu xử lý khơng phải là một thành viên MPI_Group_size (MPI_Group group,int *size) : Trả về số lượng xử lý của một group Lưu ý : Mỗi rank phải là một rank hợp lệ trong group và tất cả các thành phần phải được phân biệt hay chức năng là khơng lỗi MPI_Group_compare(MPI_Group group1,MPI_Group group2,*result): So sánh hai nhĩm và trả về một số integer ,số này là MPI_IDENT nếu trật tự và những thành viên của hai nhĩm là như nhau.MPI_SIMILAR nếu chỉ những thành viên là như nhau ,và mặt khác là MPI_UNEQUAL Huỷ group MPI_Group_free(MPI_Group *group):Xác định group cho trước cần giải phĩng ht t p : / / e t r i t h u c . v n Trang 128 Communicator Tạo communicator MPI_Comm_create(comm,group,*newcomm):Tạo mới một communicator từ communicator cũ và nhĩm mới MPI_Comm_dup(MPI_Comm com,MPI_Comm *newcomm): Nhân đơi một communicator đã cĩ với tất cả thơng tin được liên kết Truy xuất communicator MPI_Comm_size(MPI_Comm comm, int *size): Lấy số lượng (size) các xử lý trong communicator MPI_Comm_rank(MPI_Comm comm,int *rank): Lấy định danh của xử lý bên trong một commmunicator ho trước MPI_Comm_compare(MPI_Comm comm1,MPI_Comm comm2,*result) So sánh hai communicator và trả về kết quả là một số integer. Nếu là MPI_IDENT thì ngữ cảnh và n ững nhĩm là như nhau. MPI_CONGRUENT nếu cĩ sự khác biệt về ngữ cảnh, MPI_SIMILAR nếu sự khác biệt về ngữ cảnh nhưng giống nhau về group,và cịn lại là MPI_UNEQUAL Huỷ communicator MPI_Comm_free(MPI_Comm *comm): Giải phĩng đối tượng communicator ht t p : / / e t r i t h u c . v n Trang 129 Chương 5. Thử nghiệm các thuật tốn lý thuyết đồ thị 5.1. Các khái niệm cơ bản 5.1.1. Đồ thị Một đồ thi G=(V,E) trong đĩ V là tập các đỉnh của đồ thị,E là tập các cạnh của đồ thị ,mỗi cạnh sẽ là sự liên kết của hai đỉnh Chỉ đề cập đến hai loại đồ thị là : Đồ thị vơ hướng :nếu những cạnh khơng cĩ thứ tự hai chiều Hai đỉnh u và v trong một đồ thị vơ hướng G được gọi là liền kề hay( láng giềng ) nếu u ,v là một cạnh của G .Nếu e=(u,v) thì e được gọi là cạnh liên thuộc với các đỉnh u và v . Cạnh e cũng được gọi là ạnh nối các đỉnh u và v. Các đỉnh u và v được gọi là các điểm đầu mút của cạnh (u,v) Đồ thị hữu hướng khi cạnh cĩ hai chiều nối hai đỉnh khác nhau Khi (u,v) là cạnh của đồ thị cĩ hướng G , thì u được gọi là nối tới v ,và v được gọi là được nối từ u . Đỉnh u gọi là đỉnh đầu , đỉnh v gọi là đỉnh cuối của cạnh (u,v). Đỉnh đầu và đỉnh cuối của khuyên là trùng nhau Một đồ thị trọng số là đồ thị cĩ độ dài cho mỗi cạnh Ký hiệu :G(V,E, w) Ma trận liền kề : A=(ai,j) ,là một mảng 2 chiều với thơng tin như sau nếu cạnh (i,j) tồn tại thì ai,j=1(hay độ dài của cạnh ) ngược lại thì ai,j=0 5.1.2. Đường đi Đường đi từ đỉnh u đến đỉnh v là một tập thứ tự các đỉnh ,trong đĩ v0=v và vk=v và (vi,vi+1) thuộc tập cạnh E với mọi i từ 0 đến k Chiều dài của đường đi là tổng giá trị độ dài các cạnh Đường đi (u,v): Nếu đường đi tồn tại , u tiến tới v Đơn giản nếu tất cả các đỉnh trung gian đi qua là phân biệt Là khuyên nếu vo=vk ht t p : / / e t r i t h u c . v n Trang 130 G là đồ thị liên thơng nếu cĩ một đường đi từ một đỉnh đến bất kỳ các đỉnh cịn lại 5.2. Dijkstra 5.2.1. Tuần tự Thuật tồn do E.Dijkstra ,nhà tốn học người Hà Lan , đề xuất vào năm 1959 . Các bước thực hiện thuật tốn Dijkstra: Đầu tiên gán cho đỉnh α nhãn bằng 0 và các đỉnh khác là ∞ .Ta ký hiệu L(α)=0 và L(v)= ∞ cho tất cả các đỉnh khác ( bước lặp thứ 0 ). Các nhãn này là độ dài của đường đi ngắn nhất từ đỉnh α tới các đỉnh này., trong đĩ đường đi này chỉ chứa đỉnh α. (Vì khơng cĩ đường đi từ α tới các đỉnh khác α nên ∞ là độ dài đường đi ngắn nhất giữa α và các đỉnh này). Theo thuật tốn Dijkstra ta sẽ xây dựng tập đặc biệt các đỉnh. Gọi Sk là tập này sau bước lặp thứ k của thủ tục gán nhãn. Chúng ta bắt đầu bằng So=Φ. Tập Sk được tạo thành từ Sk-1 bằng cách thêm vào đỉnh u khơng thuộc Sk-1 cĩ nhãn nhỏ nhất. Khi đỉnh u được gộp vào Sk chúng ta sửa đổi nhãn của các đỉnh khơng thuộc Sk sao cho Lk(v),nhãn của v tại bước k, là độ dài của đường đi ngắn nhất từ α tới v mà đường đi này chỉ chứa các đỉnh thuộc Sk (tức là các đỉnh đã thuộc tập đặc biệt các đỉnh cùng với u) Giả sử v là một đỉnh khơng thuộc Sk. Để sửa nhãn của v ta thấy Lk(v) là độ dài của đường đi ngắn nhất từ α tới v và chỉ chứa các đỉnh thuộc Sk. Để sửa đổi nhãn ta lưu ý rằng đường đi ngắn nhất từ α tới u ở bước k-1 cùng với cạnh (u,v). Nĩi cách khác ta cĩ. L(a,v)=min(Lk-1(a,v),Lk-1(a,u)+ w(u,v)) ht t p : / / e t r i t h u c . v n Trang 131 Thủ tục này được lặp bằng cách liên tiếp thêm các đỉnh vào tập đặc biệt các đỉnh cho tới khi đạt tới đỉnh z. Khi thêm z vào tập đặc biệt các đỉnh thì nhãn của nĩ bằng độ dài của đường đi ngắn nhất từ α tới z. Sau đây là một minh dụ cụ thể thực hiện thuật tốn Dijkstra trên một đồ thị vơ hướng 6 đỉnh Hình 5-1.1. ht t p : / / e t r i t h u c . v n Trang 132 Hình 5-1.2. Hình 5-1.3. ht t p : / / e t r i t h u c . v n Trang 133 Hình 5-1.4. Hình 5-1.5 ht t p : / / e t r i t h u c . v n Trang 134 Hình 5-1.6 Hình 5-1. Thuật tốn Dijkstra tuần tự 5.2.2. Song song Thuật tốn Dijkstra tuần tự cĩ rất nhiều điểm dễ song song hố.Do đĩ thuật tốn này đã được các nhà lập trình song song hĩa rất nhiều. Cụ thể sau đây là cách song song hĩa của thuật tốn Dijkstra tuần tự. Lúc này chúng ta nghĩ rằng khơng phẩi thực thi thuật tốn trên một bộ xử lý nữa mà phân phối các cơng việc khác nhau cho mỗi bộ xử lý khác nhau thực hiện.Mỗi bộ xử lý sẽ đảm nhận một số đỉnh của đồ thị cùng với ma trận mơ tả quan hệ của các đỉnh đĩ với các đỉnh cịn lại • Triển khai thuật tốn p l à số bộ xử lý, n là số đỉnh của đồ thị Mỗi bộ xử lý quản lý n/p số đỉnh Nếu n/p dư lẻ thì P0 đến P n-2 sẽ quản lý n/p số đỉnh Số đỉnh cịn lại sẽ do P n-1 quản lý ht t p : / / e t r i t h u c . v n Trang 135 Mỗi bộ xử lý sẽ lưu một ma trận với số cột là số đỉnh do chính Pi quản lý và số dịng là n (tương ứng với số đỉnh của đồ thị) liên quan đến ma trận liền kề A Tương ứng với các đỉnh đĩ sẽ gồm mảng mơ tả độ dài trọng số của đỉnh Li[] Hình 5-2 : Thuật tốn Dijkstra song song Các bước thực hiện song song hố như sau : Bước 1: Khởi tạo tập đỉnh Vt={r},L[k]=∞ ∀k ,L[r]=0; Lấy dữ liệu từ tập tin Phân chia dữ liệu trong ma trận trọng số A[][]đến các bộ xử lý .Với mỗi bộ xử lý sẽ cĩ một ma trận con tương đương với một ma trận con của A nhận dữ liệu Mỗi Pi ngoại trừ P0 sẽ lưu một mảng đỉnh riêng cho mình Vi Bước 2: Từ bộ xử lý master , P0 broadcast đỉnh được chọn là r đến các bộ xử lý cịn lại ht t p : / / e t r i t h u c . v n Trang 136 Bước 3: Lặp cho đến khi nào đỉnh đích đã được chọn Mỗi Pi sẽ cập nhật mảng L[] với L[k]=Min[L[k],L(Selected)+ W(selectedV,k)] với mọi k thuộc về tập đỉnh Vi Mỗi Pi sẽ tính tốn Min Li=Min(trong số mảng Li) Thực hiện việc tính Min trên tất cả các bộ xử lý và lấy giá trị nhỏ nhất .Sau đĩ chọn được đỉnh cĩ độ dài nhỏ nhất là SelectedV P0 sẽ broadcast giá trị SelectedV đến các bộ xử lý cịn lại P0 sẽ đưa đỉnh được chọn vào tập Vt 5.2.3. Thực nghiệm chương trình Phiên bản 1: Giống như hình vẽ minh họa thuật tốn Dijkstra song song. Chương trình được viết dưới dạng C chuẩn trên Linux.Chương trình khơng bao gồm các cấu trúc đồ thị mà lưu tất cả các thơng tin đều bằng mảng,mục đích cho việc truyền dữ liệu được nhanh và gọn hơn. Chương trình được chia thành các ập tin sau đây: Đọc dữ liệu từ tập tin • ReadFile.h • ReadFile.cpp Định nghĩa dạng dữ liệu được truyền giữa các tiến trình trong ứng dụng MPI • Vector.h • Vector.cpp Chương trình chính • Dijkstra.h • Dijkstra.cpp Phiên bản 2: ht t p : / / e t r i t h u c . v n Trang 137 Chương trình này được phân chia rõ ràng nhiệm vụ của các nút trên mơi trường LAM. Chương trình được viết dưới dạng các đối tượng Lớp Slave quản lý cơng việc của các nút Lớp Smatter quản lý thơng tin của đồ thị cĩ nhiệm vụ , đọc thơng tin từ tập tin và phân phối thơng tin đến các nút cịn lại trên mạng. Chương trình được chia thành các tập tin sau đây: Cấu trúc đồ thị: • Graph.h • Graph.cpp Quản lý cơng việc các nút: • Slave.h • Slave.cpp Định nghĩa dạng dữ liệu được truyền giữa các tiến trình trong ứng dụng MPI • Vector.h • Vector.cpp Chương trình chính • Dijkstra.h • Dijkstra.cpp Biên dịch chương trình: Được đĩng gĩi thành tập tin makefile Tạo tập tin Makefile cĩ nội dung như sau all:Dijkstra CC=mpic++ Dijkstra: Dijkstra.o Slave.o Vector.o Graph.o #(CC) -o myapp Dijkstra.o Slave.o Vector.o Graph.o Dijkstra.o: Dijkstra.cpp Dijkstra.h Slave.o Vector.o Graph.o #(CC) -c Dijkstra.cpp Dijkstra.h Slave.o Vector.o Graph.o ht t p : / / e t r i t h u c . v n Trang 138 Slave.o:Slave.cpp Slave.h Dijkstra.h #(CC) -c Slave.cpp Vector.o:Vector.cpp #(CC) -c Vector.cpp Graph.o:Graph.cpp #(CC) -c Graph.cpp Nếu đăng nhập với quyền sử dụng là root thì tập tin Makefile cĩ nội dung như trên ,nếu đăng nhâp với quyền sử dụng khác thì thay dấu # bằng dấu $. Chuyển thư mục hiện hành sang thư mục chứa tập tin Makefile Từ dịng lệnh của màn hình Console gõ #make Thực thi chương trình Sau khi biên dịch ,tập tin thực thi là Dijkstra Đổi quyền đăng nhập khác root để sử dụng LAM.Ví dụ $user Thực thi như sau : $lamboot $mpirun –np k Dijkstra với k là số bộ xử lý của mơi trường LAM 5.3. Prim 5.3.1. Tuần tự Do Robert Prim đưa ra vào năm 1957, mặc dù ý tưởng cở bản của nĩ đã cĩ từ sớm hơn rất nhiều. Để thực hiện thuật tốn Prim ,ta bắt đầu bằng việc chọn một cạnh bất kỳ cĩ trọng số nhỏ nhất, đặt nĩ vào cây khung. Lần lượt ghép vào cây và khơng tạo ra chu trình trong cây. Thuật tốn sẽ dừng khi n-1 cạnh đã được ghép vào cây. b1: ht t p : / / e t r i t h u c . v n Trang 139 b2: b h c i g d e f a 4 8 7 9 10 14 8 11 7 2 4 6 b3: b4: b5: ht t p : / / e t r i t h u c . v n Trang 140 b6: b7: b h i g e f a 4 8 7 9 10 14 8 11 7 2 4 6 c d b8: b h i g e f a 4 8 7 9 10 14 8 11 7 2 4 6 c d b9: ht t p : / / e t r i t h u c . v n Trang 141 b h i g e f a 4 8 7 9 10 14 8 11 7 2 4 6 c d Hình 5-3. Thuật tốn Prim tuần tự 5.3.2. Song song Do hai thuật tốn Dijkstra và Prim gần giống nhau về mặt bản chất đĩ là cùng tìm giá trị nhỏ nhất. Đối với Prim đĩ là cạnh cĩ trọng số nhỏ nhất, cịn đối với Dijkstra là đỉnh cĩ độ dài từ đỉnh nguồn đến nĩ nhỏ nhất. Nên về mặt song song hĩa thuật tốn Prim cũng tương tự như thuật tốn Dijkstra • Triển khai thuật tốn p bộ xử lý ,n=số đỉnh của đồ thị Mỗi bộ xử lý quản lý n/p số đỉnh Nếu n/p dư lẻ thì P0 đến Pn-2 sẽ quản lý n/p số đỉnh Số đỉnh cịn lại sẽ do Pn-1 quản lý Mỗi bộ xử lý sẽ lưu một ma trận với số cột là số đỉnh do chính Pi quản lý và số dịng là n (tương ứng với số đỉnh của đồ thị) của ma trận liền kề A ht t p : / / e t r i t h u c . v n Trang 142 Hình 5-3 : Thuật tốn Prim song song Các bước xử lý thuật tốn : Bước 1: Khởi tạo tập đỉnh Vt={r},L[k]=∞ ∀k ,L[r]=0; Lấy dữ liệu từ tập tin Phân chia dữ liệu trong ma trận trọng số A[][]đến các bộ xử lý .Với mỗi bộ xử lý sẽ cĩ một ma trận con tương đương với một ma trận con của A nhận dữ liệu Mỗi Pi ngoại trừ P0 sẽ lưu một mảng đỉnh riêng cho mình Vi Bước 2: Từ bộ xử lý master , P0 broadcast đỉnh được chọn là r đến các bộ xử lý cịn lại Bước 3: Lặp cho đến khi nào đ ã c ĩ n đỉnh được chọn (với n là số đỉnh của đồ thị) Mỗi Pi sẽ cập nhật mảng L[] với L[k]=Min[L[k],W(selectedV,k)] với mọi k thuộc về tập đỉnh Vi Mỗi Pi sẽ tính tốn Min Li=Min(trong số mảng Li) Thực hiện việc tính Min trên tất cả các bộ xử lý và lấy giá trị nhỏ nhất .Sau đĩ chọn được đỉnh cĩ độ dài nhỏ nhất là SelectedV ht t p : / / e t r i t h u c . v n Trang 143 P0 sẽ broadcast giá trị SelectedV đến các bộ xử lý cịn lại P0 sẽ đưa đỉnh được chọn vào tập Vt 5.3.3. Thực nghiệm chương trình 5.4. Bellman – Ford 5.4.1. Tuần tự Thuật tốn Bellman – Ford giải quyết bài tốn tìm đường đi ngắn nhất trong trường hợp tổng quát hơn so với thuật tốn Dijkstra , trong đĩ trọng số của các cạnh nối cĩ thể là số âm. Cho một đồ thị G=(V, E) cĩ hướng và trọng số, với đỉnh nguồn s và hàm trọng số w : E →R, thuật tốn trả về giá trị kiểu boolean cho biết từ đỉnh nguồn cĩ thể đến được mạch âm hay khơng. Nếu cĩ thì thuật tốn sẽ kết thúc mà khơng cĩ lời giải, cịn nếu khơng sẽ kết xuất tất cả các con đường ngắn nhất cùng với chiều dài của chúng. Giống như thuật tốn Dijkstra, thuật tốn Bellman – Ford cũng sử dụng kỹ thuật relaxation, bằng cách ngày càng giảm chiều dài của đường đi ngắn nhất từ đỉnh s đến các đỉnh v∈V cho đến khi đạt được giá trị ngắn nhất. Thuật tốn trả về giá trị TRUE khi và chỉ khi từ đỉnh gốc khơng đến được mạch âm. BELLMAN-FORD(G, w, s) INITIALIZE-SINGLE-SOURCE(G, s) for i ←1 to |V[G]|-1 do for each edge (u, v) ∈E[G] do RELAX(u, v, w) for each edge (u, v) ∈E[G] do if d[v] > d[u] + w(u, v) then return FALSE return TRUE b1: ht t p : / / e t r i t h u c . v n Trang 144 Hình a b2 Hình b b3 Hình c b4 ht t p : / / e t r i t h u c . v n Trang 145 Hình d b5 Hình e Hình 5-4: Thuật tốn Bellman-Ford tuần tự Hình bên trên thể hiện thuật tốn Bellman-Ford với 5 đỉnh. Sau khi thực hiện phép khởi tạo thơng thường, thuật tốn thực hiện qua |V|-1 bước qua các cạnh của đồ thị. Hình (b) và (e) cho thấy trạng thái của thuật tốn sau mỗi bước. Sauk hi thực hiện |V|-1 bước , thuật tốn sẽ tiến hành kiểm tra mạch âm và trả về giá trị Boolean thích hợp. Thuật tốn Bellman-Ford cĩ chi phí là O(V,E), bởi chi phí cho việc khởi tạo là O(V), cịn từng bước sẽ tốn O(E), và dịng lặp cuối cùng cũng tốn chi phí là O(E). ht t p : / / e t r i t h u c . v n Trang 146 Để chứng minh tính đúng đắn của thuật tốn, chúng ta sẽ chứng minh là nếu đồ thị khơng chứa mạch âm thì cĩ thể tính được đường đi ngắn nhất từ đỉnh gốc đến mọi đỉnh cịn lại. Bổ đề Cho G = (V, E) là một đồ thị cĩ hướng và trọng số với đỉnh nguồn s và hàm trọng số w : E →R, và giả sử trong G đỉnh s khơng tới được mạch âm. Do đĩ khi kết thúc thuật tốn, chúng ta cĩ d[v] = δ (s, v) với mọi đỉnh v cĩ thể đến từ s. Chứng minh Gọi v là đỉnh cĩ thể đến được từ s, và p = (k<=|V|-1) là đường đi ngắn nhất từ s đến v, trong đĩ v0 = s và vk = v. Chúng ta sẽ chứng minh baằng phương pháp quy nạp vớ i = 0, 1, …, k, chúng ta cĩ d[vi] =δ (s, vi) sau bước thứ i, và kết quả này vẫn được duy trì về sau. Bởi vì cĩ |V|-1 bước, chúng ta sẽ dùng kết quả này để chứng minh bổ đề Sau bước khởi gán, chúng ta cĩ d[v0] = δ (s, v0) = 0. Trong bước quy nạp chúng ta giả sử đúng với trường hợp i-1, d[vv-1] = δ (s, vi-1) theo bổ đề ở trên chúng ta kết luận được d[vi] = δ (s, vi) sau bước thứ i, do đĩ bổ đề được chứng minh. Hệ quả Cho G = (V, E) là một đồ thị cĩ hướng và trọng số với đỉnh nguồn s và hàm trọng số w : E →R. Với mỗi đỉnh v∈V, tồn tại một đường đi từ s đến v khi và chỉ khi thuật tốn Bellman-Ford kết thúc với d[v]<∞ Chứng minh Chứng minh tương tự như bổ đề. Định lý (Tính đúng đắn của thuật tốn Bellman-Ford) Thực hiện thuật tốn Bellman-Ford trên đồ thị G = (V, E) cĩ hướng và trọng số với đỉnh nguồn s và hàm trọng số w : E →R. Nếu từ s khơng đến được ht t p : / / e t r i t h u c . v n Trang 147 mạch âm trong G, thuật tốn trả về giá trị TRUE, và ta cĩ d[v] = δ (s, v) với mọi đỉnh v∈V, ngược lại trả về giá trị FALSE. Chứng minh Giả sử trong đồ thị G, từ đỉnh s khơng đến được mạch âm. Trước tiên chúng ta sẽ chứng minh tại thời điểm kết thúc, d[v] = δ (s, v) với mọi đỉnh v∈V. Nếu từ s đến được đỉnh v, thì định lý đã cho là đúng với bổ đề trên. Bây giờ chúng ta sẽ sử dụng phát biểu trên để chứng minh thuật tốn BELLMAN-FORD trả về giá trị TRUE. Khi kết thúc chúng ta cĩ tất cả các cạnh (u, v) ∈E. d[v] = δ (s, v) ≤ δ (s, u) + ω (u, v) = d[u] + ω (u, v) Do đĩ theo như mơ tả trong thuật tốn, giá trị trả về là TRUE. 5.4.2. Song song Mơ tả chương trình Như đã đề cập ở trên ta cĩ 2 khái niệm cần được phân biệt rõ, là xây dựng chương trình song song từ một thuật tốn song song cụ thể đã được thực nghiệm và kiểm tra tính đúng đắn, cịn một cách khác để cài đặt một chương trình song song là tiến hành song song hĩa các phần trong chương trình tuần tự. Trong thực tế, phần lớn người ta thường sử dụng cách thứ hai do việc thiết kế ra một thuật tốn song song là điều rất khĩ khăn và cần nhiều thời gian làm việc. Chương trình song song cài đặt thuật tốn Bellman-Ford được dùng ở đây là tiến hành theo cách thứ hai như đề cập phần trên. Đặc điểm chương trình: o Số bộ xử lý tham gia là biến động tùy thuộc vào người sử dụng. o Nội dung ma trận kề của đồ thị được nhận vào từ tập tin. o Cĩ thể thay đổi các tham số của chương trình như : đỉnh nguồn, đỉnh đích, tên tập tin nhập liệu. Thực hiện ht t p : / / e t r i t h u c . v n Trang 148 Quy ước : + ta cĩ thể hiểu khái niệm tiến trình ở đây là trên một bộ xử lý, số lượng các tiến trình tham gia cũng là số bộ xử lý cần cĩ (cũng là số máy trạm nếu trên một máy chỉ cĩ một bộ xử lý). + P là ma trận gồm 2 dịng, cĩ số cột bằng với số đỉnh của đồ thị, dùng để lưu đường đi ngắn nhất. + L là ma trận kề lưu nội dung của đồ thị. Các bước thuật tốn b1: khởi tạo ma trận P và L. b2: tiến trình chính gửi cho các tiến trình con một số cột của ma trận L, tùy vào số máy để chạy chương trình. b3: tiến trình chính broadcast 1 dịng của ma trận P, rồi nhận lại P sau khi các tiến trình con thực hiện tính tốn, chương trình kết thúc khi: 2 dịng của ma trận P tương tự nhau, lúc đĩ kết luận từ đỉnh nguồn cĩ thể đến được mạch âm, bài tốn kết thúc mà khơng cĩ lời giải. Khi số lần thực thi bước 3 lớn hơn số đỉnh của đồ thị, chương trình kết xuất đường đi ngắn nhất từ đỉnh nguồn đến các đỉnh cịn lại theo như trong ma trận P. ht t p : / / e t r i t h u c . v n Trang 149 Tiến trình chính Tiến trình 1 Tiến trình 2 Tiến trình chính Broadcast 1 dòng của P Nhận lại P sau khi các tiến trình con tính tính toán Tiến trình chính Tiến trình 1 Tiến trình 2 Tiến trình chính Hình 5-5 : Thuật tốn Bellman-Ford song song Thực hiện + Ma trận P được lưu theo lớp TMatrixRow (tổ chức ma trận theo mảng các phần tử được đánh số theo dịng rồi theo cột) class TMatrixRow { public: void printMatrix(); void init(unsigned int mLen, unsigned int nLen); TMatrixRow(unsigned int mLen, unsigned int nLen); void freeMatrix(); unsigned int m; //number of rows unsigned int n; //number of columns ht t p : / / e t r i t h u c . v n Trang 150 double *data; //data, ordered by row, then by column double **rows; //pointers to rows in data TMatrixRow(); virtual ~TMatrixRow(); }; + Ma trận L được lưu theo lớp TMatrixCol(tổ chức ma trận theo mảng các phần tử được đánh số theo cột rồi theo dịng) class TMatrixCol { public: void init(unsigned int len); void printMatrix(); void freeMatrix(); int read(char* filename); unsigned int n; //number of rows = number of columns double *data; //data, ordered by column, then by row double **cols; //pointers to cols in data TMatrixCol(); TMatrixCol(unsigned int len); virtual ~TMatrixCol(); }; ht t p : / / e t r i t h u c . v n Trang 151 Chương 6. Kết luận – Hướng phát triển 6.1. Kết luận Dựa trên các kiến thức đã tìm hiểu được về tính tốn lưới, cách thức lập trình trên mơi trường song song và phân tán, cũng như các mơi trường hỗ trợ phát triển, đề tài đã đat được mục tiêu đề ra là nghiên cứu về tính tốn lưới và thực nghiệm trên một số thuật tốn lý thuyết đồ thị. Mặc dù thời gian thực hiện cĩ hạn, bên cạnh đĩ gặp phải một số khĩ khăn trong việc triển khai ứng dụng, do đây là một đề tài khá mới ít được quan tâm phát triển trước đây, nhưng chúng em cũng cố gắng thực hiện để đạt được các yêu cầu đề ra. Các chương trình viết ra đều cĩ khả năng thực hiện trên nhiều máy với số máy xử lý tùy biến và thực hiện đúng kết quả cần thiết. Chúng em hy vọng sẽ tiếp tục cải tiến chương trình, tối ưu các thuật tốn để đạt được kết quả tốt nhất, tận dụng được sức mạnh của các máy con để giải quyết vấn đề. Bên cạnh đĩ, chúng em cũng hy vọng cĩ thể triển khai trên các hệ thống lớn hơn. 6.2. Hướng phát triển Tương lai của tính tốn song song và phân bố, và xa hơn nữa là tính tốn lưới vẫn cịn rất lớn. Trên thế giới hiện nay người ta vẫn đang tiếp tục nghiên cứu mạnh mẽ nhằm cĩ thể tận dụng được khả năng của các hệ thống máy tính lớn trên thế giới, gĩp phần trong cơng tác nghiên cứu khoa học cũng như thương mại. Do trong thời hạn cho phép cũng như khả năng và kiến thức hiện nay vẫn chưa thực sự phát huy được hết khả năng của tính tốn lưới, vì thế đề tài hiện cịn khả năng phát triển rất lớn. • Cải tiến chương trình ht t p : / / e t r i t h u c . v n Trang 152 Tìm hiểu sâu hơn về thư viện MPI để phát huy tiềm năng rất lớn của nĩ, bên cạnh đĩ cũng cần thực hiện một số phương pháp tối ưu như giảm chi phí do tính tốn, truyền tải thơng tin…Bên cạnh đĩ nếu cĩ điều kịện sẽ sử dụng trên mơi trường hỗ trợ tính tốn lưới phổ biến nhất hiện nay là Globus. • Triển khai thực tế Do hạn chế về cơ sở vật chất nên các chương trình chưa được triển khai trên các hệ thống lớn, thực tế để qua đĩ cĩ thể đánh giá đúng được khả năng của chương trình. Do đĩ chúng em hy vọng cĩ thể tiếp tục phát triển được đề tài để tận dụng được sức mạnh của tính tốn lưới, đem lại hiệu quả cao trong cơng tác nghiên cứu khoa học và áp dụng vào thực tế. ht t p : / / e t r i t h u c . v n Trang 153 Tài liệu tham khảo Tài liệu viết: [1] Wolfgang Gentzsch, Grid Computing : A New Technology for the Advanced Web, Sun Microsystem Inc, 2001 [2] Ananth Gramma, Anshul Gupta, George Karypis, Vipin Kumar : Introduction to Parallel Computing 2nd, Addison Wesley, USA, 2003 [3] Behrooz Parhami, Introduction to Parallel Processing Algorithms and Architectures, Kluwer Academic, 2002 [4] Fran Berman, Anthony J.G.Hey, Geoffrey C.Fox, Grid Computing Making the Global Infrastructure a Reality, Wiley, 2003 [5] IBM RedBooks, Introduction to Grid Computing with Globus, 2003 [6] Graeme S.McHale, Parallel Programming on Linux Networks Using MPI & PVM [7] Mark Baker, Rajkumar Buyya, Domenico Laforenza, Grids and Grid technologies for wide-area distributed computing, Software – Practice and Experience, 2002 [8] 7.1.1 Lam Install ,LAM/MPI Team Open Systems LAb [9] 7.1.1 Lam User Guide,LAM/MPI Team Open Systems LAb Website: [10] Global Grid Forum, [11] Ian Foster, Designing and Building Parallel Programs, 1995, [12] [13] [14] [15] [16] Application of Parallel Computers [17] ._.