Khóa luận 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ị

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 TRẦN VIỆT CƯỜNG - 0112339 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Ị 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 NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... .......................................................................................................................................... NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆ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 toàn thể gia đình, những người đã nuôi dạy chúng con trưởng thành đến ngày hôm nay. Chúng em cũng xin chân thành cám ơn quý Thầy cô trong Khoa Công nghệ thông tin, trường Đại học Khoa học Tự nhiên Tp.Hồ Chí Minh đã tận tình giảng dạy, hướng dẫn, giúp đỡ và tạo điều kiện cho chúng em thực hiện tốt luận văn này. Xin chân thành cám ơn sự giúp đỡ, động viên và chỉ bảo rất nhiệt tình của các anh chị và tất cả các bạn, những người đã giúp chúng tôi có đủ nghị lực và ý chí để hoàn thành luận văn này. Mặc dù đã cố gắng hết sức, song chắc chắn luận văn không khỏi những thiếu sót. Chúng em rất mong nhận được sự thông cảm và chỉ bảo tận tình của quý Thầy Cô và các bạn. TP.HCM, 7/2005 Nhóm sinh viên thực hiện Huỳnh Bá Thanh Tùng - Trần Việt Cường LỜI NÓI ĐẦU Nhân lọai ngày nay đang chứng kiến sự phát triển mạnh mẽ của ngành Công nghệ Thông tin, một trong những ngành mũi nhọn của nhiều quốc gia trên thế giới. Sự phát triển vượt bậc của nó là kết quả tất yếu của sự phát triển kèm theo các thiết bị phần cứng cũng như phần mềm tiện ích. Sự phát triển đó đã kéo theo rất nhiều các ngành khác phát triền theo, trong đó có lĩnh vực nghiên cứu khoa học. Tuy công nghệ ngày càng phát triển, tốc độ xử lý của các thiết bị cũng không ngừng tăng cao, nhưng nhu cầu tính toán của con người vẫn còn rất lớn. Cho đến hiện nay vẫn còn rất nhiều vấn đề mà các nhà khoa học cùng với khả năng tính toán của các máy tính hiện nay vẫn chưa giải quyết được hay giải quyết được nhưng với thời gian rất lớn. Các vấn đề đó có thể là : • Mô hình hóa và giả lập • Xử lý thao tác trên các dữ liệu rất lớn • Các vấn đề “grand challenge” (là các vấn đề không thể giải quyết trong thời gian hợp lý) Lời giải cho những vấn đề này đã dẫn đến sự ra đời của các thế hệ siêu máy tính. Tuy nhiên việc đầu tư phát triển cho các thiết bị này gần như là điều quá khó khăn đối với nhiều người, tổ chức, trường học…. Chính vì lẽ đó mà ngày nay người ta đang tập trung nghiên cứu cách cách sử dụng các tài nguyên phân bố một cách hợp lý để tận dụng được khả năng tính toán của các máy tính đơn. Những giải pháp này được biết đến với nhiều tên gọi khác nhau như meta- computing, salable-computing, global- computing, internet computing và gần nhất hiện nay là peer to peer computing hay Grid computing. Đây là phương pháp nhằm tận dụng khả năng của các máy tính trên toàn mạng thành một máy tính “ảo” duy nhất, nhằm hợp nhất tài nguyên tính toán ở nhiều nơi trên thế giới để tạo ra một khả năng tính toán khổng lồ, góp phần giải quyết các vấn đề khó khăn trong khoa học và công nghệ. Ngày nay nó đang càng được sự hỗ trợ mạnh hơn của các thiết bị phần cứng, băng thông… Grid Computing có khả năng chia sẻ, chọn lựa, và thu gom một số lượng lớn những tài nguyên khác nhau bao gồm những siêu máy tính, các hệ thống lưu trữ, cùng với những nguồn dữ liệu, các thiết bị đặt biệt… Những tài nguyên này được phân bố ở các vùng địa lý khác nhau và thuộc về các tổ chức khác nhau. Nhận thấy được nhu cầu phát triển ấy, nhóm chúng em đã quyết định chọn thực hiện đề tài “Nghiên cứu tính toán lưới và thực nghiệm trên một số thuật toán lý thuyết đồ thị” Mục tiêu của đề tài đề ra là tìm hiểu về tính toán lưới, và qua đó tận dụng các kiến thức có được để có thể cài đặt một số thuật toán lý thuyết đồ thị, nhằm có thể giải quyết các vấn đề tìm đường đi khi số đỉnh tương đối lớn… Các nội dung chính: • Nghiên cứu tính toán lưới • Tìm hiểu các môi trường hỗ trợ • Tìm hiểu lập trinh song song và phân tán • Cài đặt một số thuật toán với kiến thức có được Nội dung của luận văn được chia làm 6 chương : Chương 1. Giới thiệu : Giới thiệu tổng quan về tính toán lưới, khái niệm lịch sử phát triển. Chương 2. Tính toán song song và phân bố : Trình bày về các kiến trúc, mô hình xử lý song song và phân bố, cách thức xây dựng chương trình, thiết kế thuật toán… Chương 3. Các môi trường hỗ trợ tính toán lưới : Tìm hiểu về các môi trường đang được sử dụng và nghiên cứu hiện nay trên thế giới. Chương 4. Mô hình lập trình truyền thông điệp - MPI : Mô hình cụ thể được dùng để phát triển ứng dụng MPI. Chương 5. Thử nghiệm các thuật toán lý thuyết đồ thị : Cách thức xây dựng chương trình , các khái niệm lý thuyết, thực nghiệm thực tế … Chương 6. Tổng kết : Nêu các kết quả đã đạt được, một số vấn đề còn tồn tại, định hướng mục tiêu mở rộng phát triển đề tài trong tương lai. Mục lục Danh sách hình..................................................................................................... 11 Chương 1. Giới thiệu ........................................................................................... 13 1.1. Các khái niệm.......................................................................................... 13 1.2. Những thách thức đối với tính toán lưới ................................................. 16 Chương 2. Tính toán song song và phân bố ...................................................... 17 2.1. Khái niệm ................................................................................................ 17 2.2. Nền tảng tính toán song song và phân bố ............................................... 18 2.2.1. Kiến trúc xử lý song song và phân bố ..............................................18 2.2.2. Tổ chức vật lý của các nền tảng song song và phân bố ....................25 2.3. Một số mô hình lập trình song song thông dụng..................................... 26 2.3.1. Mô hình chia sẽ không gian bộ nhớ..................................................26 2.3.2. Mô hình truyền thông điệp ...............................................................27 2.4. Cách thức xây dựng một chương trình song song và phân bố ................ 29 2.4.1. Các thuật ngữ căn bản.......................................................................29 2.4.2. Thiết kế thuật toán song song ...........................................................31 2.4.3. Một số phương pháp tối ưu...............................................................43 2.4.4. Các mô hình thuật toán song song....................................................48 Chương 3. Các môi trường hỗ trợ tính toán lưới ............................................. 52 3.1. Giới thiệu................................................................................................. 52 3.2. Các vấn đề khi lập trình luới ................................................................... 53 3.2.1. Tính mang chuyển, tính khả thi và khả năng thích ứng....................53 3.2.2. Khả năng phát hiện tài nguyên .........................................................54 3.2.3. Hiệu năng..........................................................................................54 3.2.4. Dung lỗi ............................................................................................55 3.2.5. Bảo mật .............................................................................................55 3.2.6. Các siêu mô hình...............................................................................55 3.3. Tổng quát về các môi trường hỗ trợ........................................................ 56 3.3.1. Một số môi trường Grid....................................................................56 3.3.2. Những mô hình lập trình và công cụ hỗ trợ......................................59 3.3.3. Môi trường cài đặt ............................................................................64 3.4. Những kỹ thuật nâng cao hỗ trợ lập trình ............................................... 75 3.4.1. Các kỹ thuật truyền thống.................................................................76 3.4.2. Các kỹ thuật hướng dữ liệu...............................................................76 3.4.3. Các kỹ thuật suy đoán và tối ưu........................................................77 3.4.4. Các kỹ thuật phân tán........................................................................77 3.4.5. Nhập xuất hướng Grid ......................................................................78 3.4.6. Các dịch vụ giao tiếp cấp cao ...........................................................78 3.4.7. Bảo mật .............................................................................................80 3.4.8. Dung lỗi ............................................................................................80 3.4.9. Các siêu mô hình và hệ thống thời gian thực hướng Grid................82 3.5. Tóm tắt .................................................................................................... 83 Chương 4. Mô hình lập trình truyền thông điệp - MPI................................... 85 4.1. Các khái niệm cơ bản .............................................................................. 86 4.2. Cấu trúc chương trình MPI ..................................................................... 89 4.3. Trao đổi thông tin điểm-điểm ................................................................. 90 4.3.1. Các thông tin của thông điệp ............................................................90 4.3.2. Các hình thức truyền thông...............................................................91 4.3.3. Giao tiếp blocking.............................................................................92 4.3.4. Giao tiếp non-blocking .....................................................................96 4.4. Trao đổi thông tin tập hợp..................................................................... 101 4.4.1. Đồng bộ hóa....................................................................................101 4.4.2. Di dời dữ liệu trong nhóm ..............................................................101 4.4.3. Tính toán gộp ..................................................................................105 4.5. Các kiểu dữ liệu..................................................................................... 109 4.5.1. Những kiểu dữ liệu đã được định nghĩa .........................................109 4.5.2. Các kiểu dữ liệu bổ sung.................................................................110 4.5.3. Pack và UnPack ..............................................................................113 Chương 5. Thử nghiệm các thuật toán lý thuyết đồ thị ................................. 114 5.1. Các khái niệm cơ bản ............................................................................ 114 5.2. Dijkstra .................................................................................................. 115 5.2.1. Tuần tự ............................................................................................115 5.2.2. Song song........................................................................................119 5.2.3. Thực nghiệm chương trình .............................................................120 5.3. Prim ....................................................................................................... 122 5.3.1. Tuần tự ............................................................................................122 5.3.2. Song song........................................................................................124 5.3.3. Thực nghiệm chương trình .............................................................126 5.4. Bellman – Ford...................................................................................... 128 5.4.1. Tuần tự ............................................................................................128 5.4.2. Song song........................................................................................130 5.4.3. Thực nghiệm chương trình .............................................................132 5.5. Đánh giá chung...................................................................................... 134 Chương 6. Tổng kết ........................................................................................... 136 6.1. Kết luận ................................................................................................. 136 6.2. Hướng phát triển ................................................................................... 136 Tài liệu tham khảo ............................................................................................. 138 Danh sách hình Hình 1-1 : 3 tầng của Grid ................................................................................ 15 Hình 2-1 : Phân lọai hệ thống máy tính theo Flynn-Johnson ........................... 19 Hình 2-2 : Kiến trúc SISD ................................................................................ 19 Hình 2-3 : Kiến trúc SIMD ............................................................................... 20 Hình 2-4 : Kiến trúc MISD ............................................................................... 22 Hình 2-5 : Kiến trúc MIMD.............................................................................. 23 Hình 2-6 : Mô hình chía sẽ không gian bộ nhớ ................................................ 27 Hình 2-7 : Mô hình truyền thông điệp .............................................................. 28 Hình 3-1 : Mô hình NetSolve............................................................................ 56 Hình 3-2 : Các thành phần của Globus ............................................................. 59 Hình 4-1 : Các tiến trình tạo lập trên mô hình lập trình MPI ........................... 86 Hình 4-2 : Cách thức truyền thông của các process.......................................... 87 Hình 4-3 : Blocking và non-blocking ............................................................... 88 Hình 4-4 : Group, communicator và rank......................................................... 88 Hình 4-5 : Cấu trúc của chương trình MPI ....................................................... 89 Hình 4-6 : Giao tiếp blocking ........................................................................... 92 Hình 4-7 : Thứ tự các xử lý............................................................................... 95 Hình 4-8 : Cách thức xử lý tiến trình ................................................................ 95 Hình 4-9 : Giao tiếp non-blocking .................................................................... 96 Hình 4-10 : Broadcast dữ liệu ......................................................................... 102 Hình 4-11 : Ví dụ hàm Scatter ........................................................................ 103 Hình 4-12 : Hàm MPI_Gather ........................................................................ 103 Hình 4-13 : Hàm MPI_Allgather .................................................................... 104 Hình 4-14 : Hàm MPI_Alltoall ....................................................................... 104 Hình 4-15 : Hàm MPI_Reduce ....................................................................... 105 Hình 4-16 : Sử dụng 8 xử lý để tính giá trị tuyệt đối...................................... 107 Hình 4-17 Hàm Mpi-Allreduce....................................................................... 108 Hình 4-18 : Hàm MPI_Reduce_scatter........................................................... 108 Hình 4-19 : Hàm MPI_Scan ........................................................................... 109 Hình 4-20 : MPI_Type_contiguous ................................................................ 110 Trang 12 Hình 4-21 : MPI_Type_vetor.......................................................................... 111 Hình 4-22 : MPI_Type_indexed ..................................................................... 112 Hình 4-23 : MPI_Type_struct ......................................................................... 112 Hình 5-1. Thuật toán Dijkstra tuần tự ............................................................. 118 Hình 5-2 : Thuật toán Dijkstra song song....................................................... 119 Hình 5-3. Thuật toán Prim tuần tự .................................................................. 124 Hình 5-3 : Thuật toán Prim song song ............................................................ 125 Hình 5-4: Thuật toán Bellman-Ford tuần tự ................................................... 130 Hình 5-5 : Thuật toán Bellman-Ford song song ............................................. 132 Trang 13 Chương 1. Giới thiệu 1.1. Các khái niệm Trong những năm đầu thập niên 90, nhiều nhóm nghiên cứu đã bắt đầu khai thác các nguồn tài nguyên tính toán phân tán trên Internet. Các nhà khoa học đã tập trung và sử dụng hàng trăm các máy trạm để thực hiện các chương trình song song như thiết kế phân tử và hiển thị đồ họa máy tính. Trong khi đó các nhóm nghiên cứu khác đã kết hợp các siêu máy tính lớn lại với nhau thành một siêu máy tính ảo duy nhất, rồi phân phối các phần của một ứng dụng rất lớn cho các máy tính trên một mạng diện rộng, ví dụ như máy tính giả lập các ứng dụng tương tác giữa chất lỏng và cánh quạt của chân vịt tàu…Thêm vào đó phạm vi của các dự án nghiên cứu này đã nêu ra tiềm năng thực sự của mạng máy tính, cùng với cơ sở phần mềm và tin học để phát triển nó xa hơn. Hệ thống đa bộ xử lý (Multiprocessor Systems - MPs), Cluster, Grids là các ví dụ của kiến trúc tính toán phân tán. Trong MPs, các bộ xử lý được kết hơp chặt chẽ với nhau, thông qua bộ nhớ chia sẽ chung và đường truyền kết nối rất cao. Ví dụ như là PVPs (Parallel Vector Processors), chúng hầu như rất thích hợp cho tính toán hiệu năng cao, như là các ứng dụng song song dựa vào trao đổi thông điệp tốc độ cao giữa các tiến trình song song. Trang 14 Trong khi đó Cluster lại là các máy tính đơn hay đa bộ xử lý được kết hợp tương đối với nhau thông qua đường mạng, vì thế nó chậm hơn từ 1 đến 2 lần so với kết nối MP. Ví dụ như cluster Beowulf chạy Linux, hay TCF (Technical Compute Farm) của Sun chạy hệ điều hành Solaris/TM, chúng được sử dụng cho các tính toán số lượng lớn, phân phối các tác vụ tính toán (thường là không song song) cho các bộ xử lý, rồi thu thập lại các kết quả tính toán vào kết quả toàn cục. Các tính toán này có thể là việc hiển thị hàng ngàn khung hình để làm phim hay là giả lập việc kiểm tra và thiết kế để xây dựng thế hệ tiếp theo của chip VLSI, hay như trong công nghệ sinh học, đó là việc cắt lớp hàng trăm ngàn chuỗi gen. Trong khi MPs và Cluster chỉ là các hệ thống đơn, thường là trong một domain đơn. Grid điện toán bao gồm các cluster của mạng các MPs hay/và cluster, nằm trên nhiều domain khác nhau, phân bố ở nhiều phòng ban, xí nghiệp hay thậm chí là trên mạng Internet. Về bản chất, những grid có một độ phức tạp cao hơn, đặc biệt là ở tầng trung gian, trong việc thực thi, quản lý, và sử dụng các tài nguyên tính toán phân tán, và ở tầng ứng dụng là việc thiết kế, phát triển, chạy các phần mềm để triển khai grid một cách hiệu quả. Tóm lại Grid là một kiến trúc tính toán phân tán cho phép chuyển giao các tài nguyên lưu trữ và tính toán như thể là một dịch vụ trên Internet. Đây là bước phát triển tiếp theo về cơ sở hạ tầng kỹ thuật, cho phép kết nối các máy tính phân tán, các thiết bị lưu trữ, các thiết bị di động, các công cụ, cơ sở dữ liệu, và các ứng dụng phần mềm, và cung cấp cách thức truy cập duy nhất đến cộng đồng người dùng để cho phép tính toán, trao đổi thông tin và cộng tác. Một số hệ thống grid hiện tại như là NASA Information Power Grid (IPG); DoD Distance Computing và NetSolve cho chia sẽ và khai thác phần mềm toán học; Nimrod cho chia sẽ tài nguyên trên phạm vi trường học; SETI@Home cho tìm kiếm trí thông minh ngòai trái đất; hay là APGrid để kết nối các trung tâm máy tính ở vành đai Châu Á Thái Bình Dương trong tương lai gần. Trang 15 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 toá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ẽ được dành riêng cho tính toán theo yêu cầu, tính toán trên thông tin nhạy cảm, tính toán cộng tác, và siêu tính toá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 toá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 toán giống như cách mà người ta sử dụng điện hiện nay. Trang 16 1.2. Những thách thức đối với tính toán lưới Hầu hết các kỹ thuật phức tạp bê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 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 17 Chương 2. Tính toá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 toá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ệ. Ngoà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. Trang 18 2.2. Nền tảng tính toá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 toá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ì 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 In st ru ct io n S tre am (s ) SISD (Uniprocessors) SIMD (Array Processors) MISD GMSV GMMP DMSV Data Stream(s) Single Multiple M ul tip le S in gl e Shared Variables Message Passing G lo ba l D is tri bu te d M em or y Communication DMMP MIMD Hình 2-1 : Phân lọai hệ thống máy tính theo Flynn-Johnson 2.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.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 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 Trang 20 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 đ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 Trang 21 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). 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à hoàn toàn có thể. 2.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 đó. Trang 22 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.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 bao gồm khả năng uyển Trang 23 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 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ý Trang 24 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 toá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 toá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 toá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ộ. 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 Trang 25 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 toán tuần tự (Random Access Machine hay là RAM) bao gồm p bộ xử lý và một vùng nhớ toà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ô hì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. Toàn quyền đọc - Toàn quyền ghi (exclusive-read, exclusive write) EREW. Trong loại này, truy cập vào vùng nhớ là toàn quyền. Không có 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 – Toà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. Toà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ự. Trang 26 4. Đồng thời đọc – Đồng thời ghi (concurrent read, concurrent 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 đượ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 Trang 27 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ử toàn bộ bộ nhớ là toà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ề 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). Trang 28 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 toá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à đoá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 đồ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 hoàn toà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 toá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 Trang 29 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à hoàn toà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 toá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 toá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 toá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 toá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 toá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 toán sau khi phân họach. Xử lý đồng thời nhiều tác vụ là điều Trang 30 kiện tiên quyết để rút ngắn thời gian giải quyết toà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. 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 Trang 31 Hình 2-9 :Đồ thi tương tác trong bài toán nhân ma trận với vector 2.4.2. Thiết kế thuật toán song song Phân chia một công việc tính toá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 toá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 toá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 nhiề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 Trang 32 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à 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 toá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 toá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 toá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 toá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ụ. Trang 33 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 toá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 toá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 toá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 toán một cách tự nhiên theo chức năng nhập. Trong nhiều thuật toá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 trước. Trong các thuật toá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 Trang 34 như vậy, việc phân chia theo dữ liệu nhập là hoàn toàn có thể, và sau đó dùng kết quả này để thực hiện đồng thời việc tính toá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 toá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 toá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 toá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 khả năng xử lý đồng thời cao hơn so với khi thực hiện trên dữ liệu nhập hay xuất. Thông thường trong giải quyết một vấn đề nào đó thì dữ liệu trung gian không được phát sinh một cách tường minh và trong khi cấu trúc lại các thuật tóan ban đầu người ta có thể cần đến dữ liệu trung gian để tạo ra sự phân họach. vd: như trong ví dụ nhân ma trận bên trên, ta có thể gia tăng khả năng tính tóan song song bằng cách đưa ra một bước trung gian mà trong đó có 8 tác vụ thực hiện tính toán các ma trận con tương ứng của chúng rồi lưu kết quả trong một ma trận 3 chiều D. Ma trận con Dk,i,j là kết quả của việc nhân Ai,k và Bk,j. Trang 35 Hình 2-11 : Nhân hai ma trận A và B với phần trung gian là ma trận D Việc phân chia thành ma trận trung gian D dẫn đến phân hoạch thành 8 tác vụ. Sau bước nhân, ta thực hiện cộng các ma trận kết quả con (chi phí không cao) thành ma trận C. Tất cả các ma trận con D*,i,j được cộng lại với nhau để tạo thành Ci,j. 8 tác vụ (đánh số từ 1-8) thực hiện việc nhân các ma trận con của A và B có kích thước n/2 x n/2 với chi phí là O(n3/8). Sau đó 4 tác vụ (đánh số từ 9-12) thực hiện cộng các ma trận con trung gian D thành ma trận kết quả C với chi phí là (n2/8). Trang 36 Hình 2-12 : Phân họach bài toán nhân ma trận theo ma trận trung gian 3-chiều Phân hoạch thăm dò Phân họach thăm dò được dùng để phân họach những vấn đề mà có nội dung tính toán tương ứng với một không gian tìm kiếm của những giải pháp. Trong phân họach thăm dò, chúng ta phân chia không gian tìm kiếm thành nhiều phần nhỏ hơn, và thực hiện tìm kiếm trên từng phần đồng thời với nhau, cho đến khi tìm ra giải pháp cần tìm. Trang 37 Lưu ý là mặc dù phân hoạch thăm dò trông có vẻ tương tự như phân hoạch dữ liệu (không gian tìm kiếm có thể được xem như là dữ liệu được phân chia), về cơ bản chúng khác nhau ở những điểm sau đây. Những tác vụ có được sau khi phân hoạch dữ liệu được thực hiện hoàn toàn và từng tác vụ đều thực hiện các phép tính hữu dụng để tìm ra giải pháp cho vấn đề. Mặt khác, trong phân hoạch thăm dò, những tác vụ mặc dù chưa thực hiện xong nhưng vẫn bị kết thúc nếu đã có một giải pháp được tìm ra từ một tác vụ khác. Vì thế từng phần của không gian tìm kiếm khi được thực hiện bởi công thức song song có thể khác rất nhiều so với khi được tìm kiếm bởi thuật toán tuần tự. Cho nên số lượng công việc mà công thức song song thực hiện có thể nhiều hơn hay ít hơn so với khi thực hiện bằng thuật toán tuần tự. Trang 38 Hình 2-13 : Các bước phát sinh theo phân hoạch thăm dò Phân hoạch suy đoán Trang 39 Phân hoạch suy đoán được dùng khi một chương trình có thể lấy một trong các nhánh tính toán có thể, tùy thuộc vào kết quả xuất của những phép tính toán trước đó. Trong trường hợp này, trong khi một tác vụ đang thực hiện các phép tính mà kết quả xuất sẽ quyết định bước tính toán tiếp theo, trong khi các tác vụ khác có thể bắt đầu đồng thời các công việc tính toán của giai đoạn tiếp theo. Ngữ cảnh này trông giống với ước lượng song song một hay nhiều nhánh của câu lệnh switch trong ngôn ngữ C trước khi tồn tại giá trị vào của câu lệnh. Trong khi một tác vụ thực hiện tính toán để giải quyết switch, các tác vụ khác thực hiện song song trên các nhánh khác của switch. Khi giá trị đầu vào cuối cùng của switch được tính ra, thì nhánh có các phép tính tương ứng sẽ được thực hiện trong khi bỏ qua các nhánh còn lại. Thời gian cho việc chạy song song sẽ nhỏ hơn khi chạy tuần tự vì thời gian được sử dụng tối ưu để thực hiện song song các phép tính toán hợp lý cho giai đoạn tiếp theo. Tuy nhiên dạng song song của switch cũng bảo đảm sẽ có ít nhất một vài phép tính toán lãng phí. Nhằm làm giảm các phép tính toán này, một dạng khác nhỏ của phân họach suy đoán có thể đuợc sử dụng, đặc biệt trong những trường hợp mà một trong các kết quả xuất của switch có khả năng xảy ra hơn so với các trường hợp còn lại. Trong trường hợp này, chỉ có nhánh ‘khả thi” nhất được một tác vụ thực thi song song cùng với các phép tính toán trước đó. Nhưng nếu kết quả xuất của switch khác với những gì được mong đợi thì ta sẽ “roll back” lại việc tính toán và thực thi chính xác nhánh switch cần thực hiện. Phân hoạch suy đoán và phân hoạch thăm dò khác nhau ở một vài điểm sau. Trong phân hoạch suy đoán đầu vào là không biết, còn trong phân hoạch thăm dò kết quả đầu ra là không biết. Trong phân hoạch suy đoán, thuật toán tuần tự sẽ chỉ thực hiện nghiêm ngặt một trong các tác vụ ở giai đọan suy đoán, bởi vì khi mà nó bắt đầu thực hiện một giai đoạn nào đó, nó đã biết chính xác phải thực hiện theo nhánh nào. Một chương trình song song khi thực hiện theo phân hoạch suy đoán sẽ phải làm nhiều công việc hơn so với chương trình đó khi viết theo tuần tự. Mặt khác trong phân hoạch thăm dò, thuật toán tuần tự tìm ra nhiều hướng đi, do mỗi nhánh đều dẫn tới một giải pháp mà chưa được biết trước. Vì thế, một chương trình song song có thể thực hiện ít hơn, nhiều Trang 40 hơn hay bằng với số lượng công việc của thuật toán tuần tự tùy thuộc vào vị trí của giải pháp trong không gian tìm kiếm. Kết hợp các phép phân hoạch Cho đến bây giờ chúng ta đã xem xét một số phương pháp phân hoạch có thể được dùng để tạo ra một số mô hình song song cho các thuật toán. Những kỹ thuật này không phải là hoàn toàn tuyệt đối mà nguợc lại chúng có thể được sử dụng kết hợp với nhau. Thông thường một phép tính được phân thành nhiều bước và đội khi ta phải áp dụng nhiều cách phân hoạch cho các buớc khác nhau. Ví dụ như khi tìm giá trị nhỏ nhất của một tập hợp số n rất lớn, phương pháp phân hoạch đệ quy thuần túy có thể làm phát sinh ra nhiều tác vụ hơn là số bộ xử lý đang có. Một cách phân hoạch hiệu quả là chia dữ liệu ban đầu thành P phần bằng nhau và gán vào cho P bộ xử lý. Kết quả cuối cùng có được bằng cách tìm giá trị nhỏ nhất của các kết quả trung gian bằng cách áp dụng phân hoạch đệ quy. Hình 2-14 : Phân hoạch lai để tìm giá trị nhỏ nhất của mảng 2.4.2.2. Ánh xạ Một khi bài toán đã được phân rã thành các tác vụ, thì các tác vụ này sẽ được ánh xạ vào trong các tiến trình xử lý với mục tiêu là hoàn thành tất cả trong thời gian ngắn nhất. Để đạt được thời gian xử lý nhỏ thì chi phí cho thực thi song song các tác vụ phải được giảm đến mức tối thiểu. Với một phân họach đã cho thì có hai yếu tố chính dẫn đến chi phí là : thời gian cho giao tiếp giữa các tiến trình và thời gian khi chúng nhàn rỗi. Một tiến trình có thể nhàn rỗi vì nhiều lý do trước khi toàn bộ các phép tính được hoàn tất. Sự phân bố không đều có thể làm cho một vài tiến trình hoàn thành công việc trước những tiến trình khác. Hoặc cũng có thể do các tác vụ chưa thực hiện được ánh xạ vào Trang 41 các tiến trình đang bận thực hiện một tác vụ khác gây ra thời gian chờ. Vì thế một cách ánh xạ các tác vụ được đánh giá là tốt khi nó đạt được hai mục tiêu sau : • Giảm thiểu thời gian các tiến trình trao đổi với nhau. • Giảm thiểu tổng thời gian khi các tiến trình này nhàn rỗi trong khi các tiến trình khác phải thực thi nhiều tác vụ. Hai mục tiêu đó thường mâu thuẫn với nhau. Ví dụ, khi bạn muốn giảm đến mức tối thiểu tương tác giữa các tiến trình bằng cách kết gán một tập hợp các tác vụ vào cùng một tiến trình. Trong nhiều trường hợp như vậy, phép kết gán như vậy sẽ đem lại sự mất cân bằng tải giữa các tiến trình, gây ra thời gian nhàn rỗi cho các tiến trình khác. Trong phần này chúng ta sẽ xem xét nhiều cách thức để ánh xạ các tác vụ vào trong các tiến trình với mục tiêu chính là cân bằng tải và giới hạn đến nhỏ nhất thời gian tương tác giữa chúng. vd: trong ví dụ sau cho ta thấy cách ánh xạ 12 tác vụ vào trong 4 tiến trình, mà trong đó 4 tác vụ cuối cùng chỉ có thể được thực hiện khi 8 tác vụ trước đó đã được hoàn tất. Trong hình bên dưới thể hiện hai cách ánh xạ khác nhau, mỗi các sẽ đem lại thời gian hoàn tất khác nhau Hình 2-15 : Hai cách phân hoạch với đồng bộ hóa Các kỹ thuật ánh xạ đại khái có thể phân thành hai loại chính là ánh xạ tĩnh và ánh xạ động. Mô hình lập trình song song, tính chất của các tác vụ và sự tương tác giữa chúng sẽ quyết định nên chọn cách ánh xạ nào cho thích hợp. Trang 42 • Ánh xạ tĩnh (static): kỹ thuật ánh xạ tĩnh phân phối tác vụ giữa các tiến trình tùy thuộc tính ưu tiên trong việc thực thi các thuật toán. Đối với những tác vụ được phát sinh tĩnh thì áp dụng một trong hai kỹ thuật đều khả thi. Việc chọn ra được một cách ánh xạ tốt thì còn phụ thuộc vào nhiều yếu tố, bao gồm kích thước của tác vụ, kích thước của dữ liệu đi kèm với chúng, tính chất tương tác giữa các tác vụ, và thậm chí là mô hình lập trình song song được sử dụng. Tuy nhiên trong nhiều trường hợp thực tế phương pháp heuristic cũng đem lại giải pháp gần đúng chấp nhận được cho việc tối ưu vấn đề ánh xạ tĩnh. Các thuật toán mà sử dụng ánh xạ tĩnh thì nhìn chung dễ dàng hơn cho việc hiết kế và lập trình. • Ánh xạ động (dynamic): kỹ thuật ánh xạ động phân phối công việc giữa các tiến trình trong suốt quá trình thực thi thuật toán. Nếu các tác vụ được phát sinh động thì nó cũng sẽ được ánh xạ động. Nếu kích thước của tác vụ là chưa biết thì nếu sử dụng ánh xạ tĩnh sẽ dẫn đến sự mất cân bằng tải nghiêm trọng và trong trường này sử dụng ánh xạ động sẽ hiệu quả hơn. Nếu số lượng dữ liệu đi kèm các tác vụ là khá lớn cho việc tính toán thì khi dùng phương pháp này sẽ đưa đến việc chia sẽ dữ liệu giữa các tiến trình. Chi phí cho việc di chuyển này có thể ảnh hưởng hơn so với những ưu điểm của ánh xạ động và dẫn đến việc sử dụng ánh xạ tĩnh sẽ hiệu quả hơn. Tuy nhiên, trong mô hình chia sẽ không gian địa chỉ thì phương pháp này cũng hữu hiệu hơn thậm chí đối với các dữ liệu lớn. Các thuật toán đòi hỏi ánh xạ động thì thường là phức tạp hơn, đặc biệt là trong mô hình truyền thông điệp. Vd cách ánh xạ trong bài toán nhân ma trận Trang 43 Hình 2-16 : phân chia theo (a) 1 chiều và (b) hai chiều của ma trận xuất. Những phần màu xám là dữ liệu mà tiến trình cần để tính toán. 2.4.3. Một số phương pháp tối ưu Như đã lưu ý ở trên, làm giảm tương tác quá mức giữa các tiến trình là một điều quan trọng cho một chương trình song song hiệu quả. Nguyên nhân xảy ra điều này có thể do nhiều yếu tố, như kích thước của dữ liệu dùng trong quá trình tương tác, tần số tương tác… Trong phần này chúng ta sẽ xem xét một vài phương pháp tổng quát để làm hạn chế quá tải do tương tác xảy ra trong các chương trình song song. Tất cả các kỹ thuật này có thể không thích hợp cho mô hình lập trình song song và một vài trong số đó cần sự hỗ trợ của phần cứng bên dưới. 2.4.3.1. Tối đa hóa dữ liệu cục bộ Trong hầu hết các chương trình song song, các tác vụ được thực thi bởi các tiến trình khác nhau đòi hỏi phải được truy cập đến dữ liệu chung. Ví dụ như trong bài toán nhân ma trận và vector y=Ab , trong đó Trang 44 từng tác vụ thực hiện tính toán từng phần tử của vector y và cần phải truy cập đến các phần tử của vector nhập b. Các kỹ thuật nhằm gia tăng sử dụng dữ liệu cục bộ bao gồm một pham vi rộng lớn các cách thức nhằm giảm thiểu tối đa kích thước của các dữ liệu truyền tải, tối đa hóa việc sử dụng lại các dữ liệu vừa được truy cập, và cực tiểu số lần truy cập. • Cực tiểu dữ liệu trao đổi Một phương pháp cơ bản nhằm làm giảm sự tương tác quá mức là làm giảm đến mức tối đa dữ liệu chia sẽ cần để truy cập bởi nhiều tiến trình cùng một lúc. Điều này tương tự với việc tối đa hóa sử dụng dữ liệu cục bộ một cách tạm thời, nghĩa là thực hiện tham chiếu liên tục đến càng nhiều dữ liệu càng tốt. Rõ ràng càng nhiều bước tính toán trên dữ liệu cục bộ có sẵn sẽ góp phần xóa đi yêu cầu chuyển dữ liệu vào vùng đệm cho các tiến trình xử lý. Như đã nói ở trên để đạt được điều này cần áp dụng các phương pháp phân hoạch và ánh xạ thích hợp. Ví dụ như trong bài toán nhân ma trận nếu ta áp dụng ánh xạ 2 chiều thì kích thước dữ liệu chia sẽ cần được truy cập chỉ là p n22 , còn nếu áp dụng ánh xạ 1 chiều thì kích thước sẽ lên tới 2 2 n p n + . Nói tóm lại, phân bố với số chiều càng cao thì càng làm giảm khối lượng của dữ liệu cần chia sẽ. Một cách khác để làm giảm sự truy cập của các tiến trình đến dữ liệu chia sẽ là sử dụng dữ liệu cục bộ để lưu kết quả trung gian, và chỉ thực hiện truy cập đến dữ liệu chia sẽ tại nơi sẽ tính toán kết quả cuối cùng. • Cực tiểu tần số tương tác Đây là một phương pháp quan trọng trong việc làm giảm sự quá tải tương tác trong các chương trình song song bởi vì trong nhiều kiến trúc thì chi phí kích hoạt cho từng tương tác là khá lớn. Ta có thể làm giảm tần số tương tác bằng cách tái cấu trúc lại các thuật toán sao cho các dữ liệu chia sẽ được truy cập và sử dụng thành các phần lớn. 2.4.3.2. Giảm thiểu tối đa các điểm xung đột, tranh chấp Trang 45 Phần bàn luận của chúng ta cho đến bây giờ chỉ là tập trung làm giảm tương tác quá mức chủ yếu bằng cách trực tiếp hay gián tiếp làm giảm tần số và dụng lượng dữ liệu trao đổi. Tuy nhiên mô hình tương tác giữa các tác vụ thường dẫn đến tranh chấp làm gia tăng sự tương tác. Nói chung, tranh chấp xảy ra khi nhiều tác vụ cùng truy cập đồng thời vào tài nguyên. Nhiều luồng trao đổi dữ liệu trên cùng một đường liên kết, nhiều sự truy cập cùng lúc vào cùng một khối nhớ, hay nhiều tiến trình thực hiện gửi những thông điệp đến cùng một tiến trình vào cùng một thời điểm, tất cả có thể dẫn đến sự xung đột. Điều này bởi vì chỉ một trong nhiều thao tác có thể được thực thi tại một thời điểm còn những thao tác còn lại phải được sắp xếp và thực hiện tuần tự. Xem lại bài toán nhân hai ma trận C = AB, sử dung phương pháp phân hoạch theo 2 chiều như hình bên trên (Hình 2.16). Gọi p là số lượng các tác vụ được ánh xạ 1-1 vào trong các tiến trình. Mỗi tác vụ sẽ chịu trách nhiệm tính toán một phần tử Ci,j của ma trận kết quả C, với pji <≤ ,0 . Phần tử Ci,j được tính theo công thức (viết theo ký hiệu ma trận khối): ∑− = = 1 0 ,,, * p k jkkiji BAC Xem cách truy cập vào bộ nhớ của công thức trên, chúng ta thấy rằng bất cứ tại bước p nào, thì p các tác vụ cũng sẽ truy cập vào cùng một khối của ma trận A và B. Trong trường hợp đặc biệt, tất cả các tác vụ làm việc trên cùng một dòng của C cũng sẽ truy cập lên cùng một khối của A. Ví dụ như tất cả p tiến trình tính C0,0, C0,1, …, C0, 1−p cũng sẽ cùng đọc A0,0 cùng một lúc. Tương tự như vậy tất cả các tác vụ làm việc trên cùng một cột của C cũng sẽ truy cập lên cùng một khối của B. Nhu cầu truy cập đồng thời lên cùng các khối nhớ này của ma trận A và B sẽ tạo ra xung đột trên cả kiến trúc chia sẽ không gian bộ nhớ NUMA và kiến trúc truyền thông điệp. Trang 46 Một cách để làm giảm tranh chấp này là thiết kế lại thuật toán song song để nó truy cập vào dữ liệu theo các mẩu không xung đột. Ví dụ như thuật toán nhân ma trận, chúng ta có thể hiệu chỉnh thứ tự các khối ma trận được nhân với nhau bằng cách sử dụng công thức: ∑− = ++++ = 1 0 ,)%()%(,, * p k jpkjipkjiiji BAC Bằng cách sử dụng công thức này tất cả các tác vụ P*,j làm việc trên cùng một dòng của C sẽ truy cập vào khối nhớ A*, (*+j+k)% p , khác nhau cho từng tác vụ. Vì vậy chỉ bằng cách sắp xếp lại thứ tự nhân các khối với nhau, ta có thể loại bỏ tranh chấp. Ví dụ như trong các tiến trình tính toán khối dòng của C, thì tiến trình tính toán C0,j sẽ truy cập A0,j từ khối dòng đầu tiên của ma trận A thay vì A0,0. Việc sử dụng ánh xạ động thường là nguồn gốc của những tranh chấp trên cấu trúc dữ liệu chia sẽ hay là từ các kênh giao tiếp dẫn đến tiến trình chính. 2.4.3.3. Đan xen các phép tính và tương tác Thời gian mà các tiến trình chờ các dữ liệu chia sẽ đến hay nhận thêm một công việc sau khi tương tác có thể được làm giảm xuống, thông thường là theo từng phần, bằng cách thực hiện một số phép tính tiện ích trong suốt thời gian chờ đợi. Một cách đơn giản để đan xen là khởi gán tương tác đủ sớm để nó hoàn tất trước khi cần cho tính toán. Đề đạt được điều này, chúng ta phải có thể nhận ra các phép tính có thể trước khi thực hiện tương tác. Sau đó trong chương trình song song phải được cấu trúc sao cho thực hiện khởi gán tương tác trước thời điểm mà nó thực hiện trong thuật toán gốc. Về cơ bản, điều này là có thể nếu có nhiều tác vụ sẵn sàng thực thi có sẵn trên cùng một tiến trình sao cho nếu có một khối chờ cho việc tương tác hoàn tất thì tiến trình vẫn có thể thực thi các tác vụ khác. Trong nhiều trường hợp, đan xen các phép tính và sự tương tác đòi hỏi phải có sự hỗ trợ từ mô hình lập trình , hệ điều hành, và thiết bị Trang 47 phần cứng. Mô hình lập trình phải cung cấp một cách thức cho phép tương tác và tính toán được tiến hành đồng thời. Cách thức này phải được hỗ trợ bởi phần cứng bên dưới. Mô hình và kiến trúc không gian địa chỉ không liên kết thường cung cấp sự hỗ trợ này thông qua truyền thông điệp ưu tiên dạng non-blocking. Mô hình lập trình cung cấp các hàm cho việc gửi và nhận thông điệp cho phép trả quyền điều khiển cho chương trình người dùng trước khi nó thực sự hoàn tất. Vì thế chương trình có thể sử dụng các hàm ưu tiên này để khởi tạo những tương tác và sau đó thực hiện các phép tính toán. Nếu phần cứng cho phép tính toán được thực hiện song song với trao đổi thông điệp, thì sự tương tác có thể giảm đáng kể. 2.4.3.4. Tạo bản sao dữ liệu hay các phép tính toán Trong một vài thuật toán song song, nhiều tiến trình có thể đòi hỏi truy cập chỉ đọc thường xuyên vào một cấu trúc dữ liệu chia sẽ, như là bảng băm. Ví thế trừ khi không được phép yêu cầu thêm bộ nhớ, còn không thì nên tạo một bản sao cấu trúc dữ liệu chia sẽ cho mỗi tiến trình để sau khi khởi gán tương tác, tất cả các những truy cập tiếp theo vào cấu trúc dữ liệu này sẽ không gây quá tải do tương tác. Trong mô hình chia sẽ không gian bộ nhớ, việc tạo bản sao của các dữ liệu chỉ đọc, được truy cập thường xuyên thì thường bị chịu tác động bởi những cache mà không phải do sự can thiệp tường minh của lập trình viên. Nhân bản dữ liệu một cách tường minh thường thích hợp cho các kiến trúc và mô hình lập trình mà gặp phải những chi phí đáng kể khi truy cập vào dữ liệu chia sẽ. Vì thế mô hình truyền thông điệp là được lợi nhất khi ta thực hiện tạo bản sao dữ liệu ở các tiến trình, điều này có thể làm giảm đáng kể sự quá tải do tương tác và cũng làm đơn giản hơn khi viết các chương trình song song. Tuy nhiên tạo bản sao dữ liệu không phải là không tốn chi phí. Nó làm gia tăng bộ nhớ của chương trình song song. Dung lượng bộ nhớ yêu cầu gia tăng lũy tiến cùng với số lượng tiến trình chạy đồng thời. Điều này có thể làm giới hạn lại kích thước vấn đề có thể được giải quyết trên Trang 48 một máy tính song song đã cho. Vì lý do này mà sao lưu dữ liệu phải được sử dụng một cách lựa chọn cho số lượng dữ liệu tương đối nhỏ. Bên cạnh dữ liệu nhập, các tiến trình trong một chương trình song song cũng thường chia sẽ kết quả trung gian. Trong những trường hợp như vậy, để cho các tiến trình tự tính toán kết quả trung gian sẽ hiệu quả hơn so với lấy chúng từ những tiến trình khác. 2.4.4. Các mô hình thuật toán song song Sau khi tìm hiểu về các kỹ thuật phân hoạch, ánh xạ và giảm thiểu tối đa tần số tương tác, bây giờ chúng ta sẽ giới thiệu một vài mô hình thuật toán song song hay được sử dụng. Một mô hình thuật toán là một cách thức tiêu biểu nhằm cấu trúc hóa lại một thuật toán song song bằng cách lựa chọn ra một kỹ thuật phân hoạch và ánh xạ và áp dụng kế hoạch thích hợp để tối ưu việc tương tác. 2.4.4.1. Mô hình dữ liệu song song Đây là một trong những mô hình thuật toán đơn giản nhất, các tác vụ được ánh xạ tĩnh hay bán tĩnh vào trong các tiến trình và từng tác vụ sẽ thực hiện cùng một thao tác trên các dữ liệu khác nhau. Loại song song mà có các chỉ thị tương tự nhau được áp dụng đồng thời lên các dữ liệu khác loại nhau được gọi là loại song song dữ liệu (data parallelism). Công việc có thể được thực hiện từng bước và dữ liệu thao tác trên các bước khác nhau có thể khác nhau. Bởi vì tất cả các tác vụ đều cùng thực thi các chỉ thị giống nhau, nên phương pháp phân hoạch được sử dụng ở đây là phân hoạch theo dữ liệu do một phương pháp phân hoạch thống nhất theo sau là cách thức ánh xạ tĩnh là đủ khả năng để đảm bảo cân bằng tải. Những thuật toán song song về dữ liệu có thể được áp dụng cho cả mô hình chia sẽ không gian bộ nhớ và truyền thông điệp. Tương tác trong mô hình này có thể làm giảm thiểu tối đa bằng cách áp dụng các cách thức phân họach riêng biệt cục bộ, và nếu có thể thì bằng cách chồng lấp các phép tính và các tương tác hoặc cũng có thể bằng cách sử dụng các thủ tục tối ưu các tương tác tập thể. Tính chất cốt lõi của Trang 49 các vấn đề song song dữ liệu là trong hầu hết các vấn đề, mức độ song song của dữ liệu sẽ gia tăng cùng với kích thước của vấn đề, điều này làm tăng khả năng giải quyết các vấn đề lớn hơn bằng cách gia tăng số lượng bộ xử lý được sử dụng. 2.4.4.2. Mô hình đồ thị tác vụ Như đã nói ở trên, các phép tính toán trong bất kỳ thuật toán song song nào cũng có thể được biểu diễn theo đồ thị phụ thuộc tác vụ. Nó có thể đơn giản như trong bài toán nhân ma trận hay có thể rất phức tạp. Tuy nhiên, trong những thuật toán song song cụ thể nào đó, đồ thị phụ thuộc tác vụ cũng thể hiện cách ánh xạ vào trong các tiến trình. Trong mô hình đồ thị tác vụ, mối tương giao giữa các tác vụ được sử dụng để gia tăng tính cục bộ hay làm giảm đi chi phí tương tác. Mô hình này về cơ bản được sử dụng để giải quyết những vấn đề mà trong đó dữ liệu đi theo các tác vụ là khá lớn so với nội dung tính toán. Thông thường thì các tác vụ được ánh xạ tĩnh nhằm giúp tối ưu chi phí cho việc di chuyển giữa chúng. Các kỹ thuật làm giảm tương tác có thể áp dụng cho mô hình này là giảm kích thước dữ liệu và tần số tương tác bằng cách gia tăng sử dụng dữ liệu cục bộ, và sử dụng các phương pháp tương tác bất đồng bộ để thay tương tác bằng các phép tính có lợi. 2.4.4.3. Mô hình Work Pool Cách thức ánh xạ tĩnh các tác vụ vào trong các tiến trình nhằm cân bằng tải là một tính chất tiêu biểu của mô hình work pool hay task pool, mà trong đó nó có thể được thực hiện bởi bất kỳ tiến trình nào. Trong mô hình truyền thông điệp, mô hình work pool về cơ bản thường được sử dụng khi khối lượng dữ liệu đi theo các tác vụ là khá nhỏ so với nội dung tính toán của chúng. 2.4.4.4. Mô hình Master-Slave Trong mô hình master-slave hay manager-worker, một hay nhiều tiến trình master sẽ phát sinh công việc và phân phối nó cho các tiến trình con. Các tác vụ có thể đuợc xác định một thứ tự ưu tiên nếu tiến trình chính Trang 50 có thể ước tính được kích thước của các tác vụ đó hay nếu phương pháp ánh xạ ngẫu nhiên có thể thực hiện công việc cân bằng tải. Trong ngữ cảnh khác các tác vụ có thể được gán những phần nhỏ hơn của công việc tại các thời điểm khác nhau. Thông thường người ta sử dụng cách thứ hai nếu tiến trình chính không mất quá nhiều thời gian để phát sinh công việc khiến các tiến trình con phải chờ đợi. Trong nhiều trường hợp các công việc có thể theo nhiều bước, và công việc trong mỗi bước phải được thực hiện xong trước khi công việc của bước tiếp theo được phát sinh. Đối với những trường hợp như vậy, thì tiến trình chính yêu cầu các tiến trình con phải thực hiện đồng bộ sau mỗi bước. Mô hình manager-worker có thể được thể hiện theo cấu trúc phân nhánh hay mô hình manager-worker nhiều tầng mà trong đó manager ở cấp cao hơn sẽ truyền xuống các công việc cho manager ở cấp dưới, cứ thế tiếp tục phân chia cho các worker thực hiện công việc của mình. Mô hình này nhìn chung thích hợp cho mô hình lập trình chia sẽ không gian bộ nhớ và truyền thông điệp vì thường các tương tác là theo 2 chiều, nghĩa là tiến trình chính biết mình phải phân phối công việc còn tiến trình con thì biết mình phải lấy gì từ tiến trình chủ. Trong khi sử dụng mô hình master-slave, cần phải cẩn thận để bảo đảm sao cho tại tiến trình chủ không xảy ra hiện tượng “cổ chai“, điều này có thể xảy ra nếu các tác vụ được thực thi là quá nhỏ (hay các tiến trình con làm việc quá nhanh). 2.4.4.5. Mô hình dây chuyền (pipeline) hay Producer- Consumer Trong mô hình dây chuyền, một dòng tin được truyền qua một dãy liên tiếp các tiến trình, từng tiến trình sẽ thực hiện một vài tác vụ trên đó. Quá trình thực thi đồng thời các chương trình khác nhau trên một dòng tin được gọi là song song theo dòng (stream parallelism). Ngoại trừ tiến trình khởi tạo đường ống, các dữ liệu mới tới sẽ kích hoạt một tiến trình thực thi một tác vụ trên đường ống. Các tiến trình có thể tạo những đường Trang 51 ống như vậy theo dạng tuyến tính hay mảng nhiều hướng, cây, hay các đồ thị thông thường có hay không có vòng. Một đường ống (pipeline) là một chuỗi của các producer và consumer. Từng tiến trình trong đường ống có thể được xem như là người tiêu thụ cho một dãy các phần tử dữ liệu của tiến trình trước đó và cũng là người sản xuất dữ liệu cho tiến trình tiếp theo trong đường ống. Đường ống không nhất thiết là một chuỗi tuyến tính, mà nó có thể là một đồ thị có hướng. Mô hình đường ống thường sử dụng ánh xạ tĩnh các tác vụ vào trong các tiến trình. 2.4.4.6. Mô hình lai Trong một vài trường hơp, có thể áp dụng nhiều hơn một mô hình cho một vấn đề, dẫn đến tạo ra mô hình thuật toán lai. Một mô hình lai có thể được kết hợp từ nhiều mô hình áp dụng theo dạng phân nhánh hay từ nhiều mô hình áp dụng tuần tự cho các bước khác nhau của một thuật toán song song. Trong nhiều trường hợp, một dạng biểu diễn của thuật toán có thể có nhiều tính chất của nhiều hơn một mô hình thuật toán. Ví dụ như là một phép tính chính có thể được thể hiện thành một đồ thị tác vụ, nhưng mỗi nút của đổ thị có thể là một tác vụ cha được kết hợp từ nhiều tác vụ con thích hợp cho mô hình song song dữ liệu hay dây chuyền. Thuật toán Quicksort song song là một trong những áp dụng của mô hình lai. Trang 52 Chương 3. Các môi trường hỗ trợ tính toán lưới 3.1. Giới thiệu Mục tiêu chính của lập trình Grid là nghiên cứu về các mô hình lập trình, các công cụ và các phương pháp nhằm hỗ trợ cho việc phát triển hiệu quả các thuật toán và các chương trình hiệu năng cao trên môi trường lưới. Lập trình lưới yêu cầu các kỹ năng và tính chất cao hơn so với lập trình tuần tự, và thậm chí là lập trình song song và phân tán. Bên cạnh việc sắp xếp các thao tác đơn giản trên những cấu trúc dữ liệu riêng, hay sắp xếp các thao tác phức tạp trên những cấu trúc dữ liệu chia sẽ hay phân tán, một lập trình viên tính toán lưới cần phải đảm nhiệm luôn việc quản lý tính toán trên môi trường. Bên cạnh việc chỉ thực hiện các thao tác đơn giản, người lập trình lưới cũng phải thiết kế tương tác giữa những dịch vụ từ xa, nguồn dữ liệu và tài nguyên phần cứng. Mặc dù người ta có thể xây dựng các ứng dụng Grid với các công cụ lập trình hiện tại, nhưng người ta vẫn đang đồng lòng nhất trí với nhau rằng hiện nay chúng vẫn không đáp ứng hiệu quả để hỗ trợ cho việc xây dựng mã nguồn Grid. Các ứng dụng lưới thường có xu hướng động và không đồng nhất, bởi vì chúng sẽ chạy trên các loại nguồn tài nguyên khác nhau với cấu hình thay đổi khi thực thi. Những cấu hình động này có thể được thúc đẩy bởi sự thay đổi của môi trường, ví dụ như thay đổi hiệu năng hay lỗi của phần cứng, v.v…Bất kể nguyên nhân gì thì liệu một mô hình hay một công cụ lập trình nào đó có thể làm cho các nguồn tài nguyên “hỗn tạp” ấy trở nên “gần gũi” với những người lập trình hay không? che dấu các khác biệt đó trong khi vẫn cho phép người lập trình quyền điều khiển trên các loại tài nguyên nếu có thể? Nhưng nếu có một sự trừu tượng thích hợp được sử dụng thì liệu nó có được hỗ trợ, cung cấp bởi các hệ thống thời gian thực? Grid thường được sử dụng cho tính toán hiệu năng cao với quy mô lớn. Để đạt được hiệu năng cao thì yêu cầu cần phải có một sự cân bằng giữa tính toán và thông tin giữa các nguồn tài nguyên liên quan. Hiện tại thì chúng ta có Trang 53 thể thực hiện điều này bằng cách quản lý tính toán, thông tin, và dữ liệu cục bộ sử dụng truyền thông điệp (message passing) hay gọi yêu cầu các phương thức từ xa (remote method invocation - RMI). Để giải quyết các vấn đề này, chúng ta phải biết được rằng các mô hình lập trình hiện nay đang thiếu những gì, cần thêm những khả năng mới gì, và nó sẽ được thực thi ở mức ngôn ngữ, mức công cụ hay ở hệ thống thời gian thực nào. Thuật ngữ mô hình lập trình ở đây được sử dụng không chỉ liên quan đến ngôn ngữ lập trình. Một mô hình lập trình có thể được thể hiện theo nhiều dạng khác nhau, ví dụ như một ngôn ngữ, một thư viện API, hay đơn thuần chỉ là một công cụ có các chức năng mở rộng. Một mô hình lập trình thành công nhất là mô hình có hiệu năng cao, sự kết hợp và quản lý linh hoạt các nguồn tài nguyên. Các mô hình lập trình cũng phải ảnh hưởng đến toàn bộ chu trình phát triển phần mềm : thiết kế, cài đặt, kiểm lỗi, vận hành, duy trì, v.v…Vì thế những mô hình thành công cũng phải đáp ứng việc sử dụng hiệu quả tất cả các loại công cụ phát triển, ví dụ như là trình biên dịch, trình sửa lỗi, trình theo dõi hiệu năng… Trước tiên ta sẽ tìm hiểu các vấn đề chính khi lập trình lưới, sau đó chúng ta sẽ tìm hiểu một vài mô hình lập trình phổ biến đang được sử dụng và đề xuất trên môi trường Grid. Tiếp theo chúng ta sẽ thảo luận các phương pháp và kỹ thuật lập trình nhằm giải quyết các vấn đề phức tạp bằng cách sử dụng các công cụ đang có hiện nay. 3.2. Các vấn đề khi lập trình luới 3.2.1. Tính mang chuyển, tính khả thi và khả năng thích ứng Các ngôn ngữ lập trình cấp cao hiện nay cho phép người dùng viết mã nguồn hoàn toàn độc lập với bộ xử lý. Các mô hình lập trình lưới cũng nên có khả năng như vậy. Điều này đối với các máy ảo thông dịch nghĩa là độc lập về kiến trúc, nhưng nó cũng có nghĩa là khả năng sử dụng các đoạn mã nguồn hay dịch vụ ở nhiều nơi khác nhau để cung cấp thành một chức năng tương tự. Tính Trang 54 khả chuyển như vậy là một điều kiện tiên quyết cho việc sao chép các cấu hình động và không đồng nhất. Việc sử dụng những đoạn mã nguồn và dịch vụ khác nhau nhưng có chức năng tương tự nhau thể hiện tính cộng tác trong việc thi hành các mô hình lập trình. Khái niệm về một kiến trúc Grid mở và có tính mở rộng ngụ ý là một môi trường phân tán có thể hỗ trợ cho các giao thức, dịch vụ, giao diện lập trình ứng dụng và các công cụ phát triển phần mềm. Cuối cùng tính mang chuyển và tính cộng tác sẽ dẫn đến khả năng thích ứng. Một chương trình Grid phải có khả năng thích ứng với các cấu hình khác nhau dựa trên nguồn tài nguyên sẵn có. Điều này có thể xảy ra vào thời điểm bắt đầu, hay tại thời điểm thực thi nguyên do sự thay đổi các yêu cầu của ứng dụng hay do khả năng phục hồi lỗi. Khả năng thích ứng như vậy có thể liên quan đến một bước khởi động lại đơn giản ở đâu đó hay là một sự tích hợp thật sự giữa tiến trình và dữ liệu. 3.2.2. Khả năng phát hiện tài nguyên Tìm ra các tài nguyên hiện có trên mạng là một phần quan trọng của tính toán lưới. Mã nguồn của chương trình lưới sẽ chỉ ra rõ ràng những máy (host) thích hợp nào để chạy chương trình. Tuy nhiên bởi vì Grid chứa đựng nhiều dịch vụ cố định, nên chúng cũng vẫn phải có khả năng tìm ra các dịch vụ này và các giao diện mà chúng hỗ trợ. Cách sử dụng các dịch vụ này phải có khả năng tái lập trình và kết hợp lại theo một cách thống nhất. Vì thế môi trường và công cụ lập trình phải chú ý tìm ra các dịch vụ hiện có và cung cấp cho người dùng các cách thức tường minh hay ngầm ẩn để khai thác chúng trong quá trình xây dựng và triển khai các ứng dụng Grid. 3.2.3. Hiệu năng Rõ ràng đối với nhiều ứng dụng Grid, vấn đề hiệu năng là điều rất đáng quan tâm. Bởi vì Grid sử dụng băng thông hỗn tạp và các hệ thống phân cấp ẩn cho nên điều này gây khó khăn cho việc đạt được hiệu năng tốt nhất và cách sử dụng hiệu quả các nguồn tài nguyên. Trang 55 Tuy nhiên đối với nhiều ứng dụng, để đạt hiệu năng đáng tin cậy cũng là một vấn đề khá quan trọng. Một môi trường động và không đồng nhất có thể tạo ra nhiều khả năng thực thi khác nhau mà có thể sẽ không được chấp nhận trong nhiều tình huống. Vì thế trong môi trường chia sẽ, chất lượng dịch vụ sẽ trở nên càng cần thiết nhằm đạt được hiệu năng đáng tin cậy trên một cấu hình tài nguyên đã cho. Trong khi người dùng có thể yêu cầu mô hình theo một hiệu năng nào đó, tuy nhiên sẽ hợp lý hơn nếu hiệu năng cung cấp nằm bên trong một khoảng giới hạn nào đó. 3.2.4. Dung lỗi Việc cần có nhiều cấp độ dung lỗi trong môi trường Grid là hoàn toàn cần thiết. Điều này đặc biệt đúng khi các ứng dụng khởi tạo hàng ngàn các công việc độc lập tương tự với nhau trên hàng ngàn máy trạm (host). Rõ ràng khi số lượng các tài nguyên tham gia tính toán ngày càng tăng thì cũng làm gia tăng xác suất bị hỏng. Các chương trình Grid phải có khả năng kiểm tra các lỗi khi đang thực thi, và bên cạnh đó cũng phải cung cấp khả năng phục hồi và phản ứng khi có lỗi xảy ra ở cấp độ chương trình. Tại thời điểm đó các công cụ cũng phải bảo đảm cho các phép tính cũng được thực thi ở cấp độ tối thiểu khi có lỗi xảy ra. 3.2.5. Bảo mật Chúng ta sẽ còn tiếp tục chứng kiến sự phát triển của tính toán lưới trên nhiều domain chia sẽ, như là các mạng. Trong khi việc cung cấp một chức năng chứng thực mạnh giữa hai site là cực kỳ quan trọng, thì bên cạnh đó việc quản lý chương trình trên nhiều site cũng là điều không đơn giản. Vì thế, một phương pháp bảo mật có cấp khả năng xác thực người dùng phải được tích hợp vào trong các mô hình lập trình lưới. 3.2.6. Các siêu mô hình Phương pháp lập trình truyền thống với các ngôn ngữ lập trình cổ điển dựa vào trình biên dịch để thực hiện việc chuyển đổi giữa 2 mô hình lập trình, như là giữa ngôn ngữ cấp cao C hay Fortran, với tập các chỉ thị phần cứng thể Trang 56 hiện bởi việc thực thi tuần tự các hàm trên dữ liệu trong bộ nhớ. Quá trình chuyển đổi này có thể là sự xây dựng của một số các mô hình liên quan đến ngữ nghĩa của mã nguồn và sự áp dụng một số tính năng cải tiến như tối ưu, dọn dẹp bộ nhớ, và kiểm tra phạm vi. Sự kết hợp các siêu mô hình tương tự sẽ góp phần xây dựng chương trình Grid. 3.3. Tổng quát về các môi trường hỗ trợ 3.3.1. Một số môi trường Grid 3.3.1.1. NetSolve NetSole là một ứng dụng client/server đuợc thiết kế để giải quyết những vấn đề tính toán khoa học trong môi trường phân phối. Agent Agent Network of servers Client Client MPP servers Scalar serverrequest choice reply Hình 3-1 : Mô hình NetSolve Hệ thống Netsolve dựa trên những hệ thống phân phối, được kết nối thông qua mạng LAN hay WAN. Những chương trình từ máy khách Netsolve có thể được viết bằng C hay FORTRAN, và sử dụng Web để giao tiếp với Server. Một server Netsolve có thể sử dụng một số gói phần mềm liên quan đến khoa học để cung cấp cho những phần mềm tính toán. Những giao tiếp truyền thông bên trong Netsolve thông qua những socket. Netsolve đáp ứng những khả năng cho việc tìm kiếm những tài nguyên máy tính trên một mạng máy Trang 57 tính, chọn những tài nguyên sẵn dùng tốt nhất, giải quyết một vấn đề, và trả kết quả cho người sử dụng. 3.3.1.2. Legion Là một hệ thống trên cơ sở đối tượng được phát triển ở đại học Virginia (Hoa Kỳ). Legion cung cấp kiến trúc phần mềm để hệ thống những máy tính phân phối khắp nơi, với số lượng khổng lồ có thể giao tiếp với nhau một cách dễ dàng. Trong hệ thống Legion, có những đặc điểm sau sau: - Mọi thứ là một đối tượng. Những đối tượng đặc trưng cho tất cả các phần cứng và phần mềm. Mỗi đối tượng là một xử lý hoạt động, đáp ứng những yêu cầu giải pháp cho những đối tượng khác bên trong hệ thống. Legion định nghĩa một tập API cho việc giao tiếp đối tượng. Nhưng không phải là ngôn ngữ lập trình hay giao thức truyền thông. - Những lớp quản lý những trường hợp. Mọi đối tượng Legion được định nghĩa và quản lý bởi chính đối tượng hoạt động .Những lớp đối tượng có những khả năng như sau: tự tạo một trường hợp thể hiện (instance), lập biểu cho việc thực thi, làm cho một đối tượng khác hoạt động, hay không hoạt động, và cung cấp thông tin về trạng thái cho những đối tượng thuộc về các máy tính khác. Những người dùng có thể định nghĩa thêm các lớp mới. Giống ngôn ngữ lập trình hướng đối tượng, người dùng có thể định nghĩa lại hay viết lại những chức năng của một lớp. Đặc điểm này cho phép những chức năng này có thể thêm, hay xoá tùy theo nhu cầu của người dùng. Hệ thống Legion hỗ trợ một tập các dạng đối tượng cốt lõi : • Những lớp và lớp tự định nghĩa • Những đối tượng chủ : Những đối tượng chủ là sự trừu tượng hóa của việc xử lý những tài nguyên, chúng có thể thể hiện một bộ xử lý đơn hay nhiều máy tính hay mhiều bộ xử lý. 3.3.1.3. Globus Trang 58 Globus cung cấp một cơ sở hạ tầng phần mềm, làm cho những ứng dụng có thể quản lý phân phối những tài nguyên tính toán khổng lồ như một máy tính đơn ảo. Một Grid, là một cở sở hạ tầng phần cứng và phần mềm, cung cấp truy xuất các tài nguyên khắp nơi dùng cho tính toán cấp cao, dù cho sự phân phối thuộc về địa lý của tài nguyên và người sử dụng có sự cản trở. Globus cung cấp những dịch vụ cơ bản và những khả năng được yêu cầu để cấu trúc một mạng tính toán lưới. Bộ công cụ bao gồm một tập hợp các thành phần bổ sung cho những dịch vụ cơ bản, chẳng hạn như bảo mật, định vị tài nguyên, quản lý tài nguyên, và dịch vụ truyền thông. Mạng tính toán lưới được hỗ trợ một số lượng lớn những ứng dụng và mô hình lập trình, đó là một điều thiết yếu.Vì thế, việc cung cấp hơn một mô hình lập trình chuẩn, chẳng hạn như mô hình lập trình hướng đối tượng là điều thiết yếu. Globus cung cấp một số dịch vụ cho phép những nhà phát triển công cụ đặc biệt hay những ứng dụng có thể sử dụng để tạo ra những yêu cầu cụ thể cho chính họ. Phương pháp này chỉ khả thi khi những dịch vụ có sự khác biệt và được định nghĩa tốt thông qua những tập API của nó, Globus được kiến tạo như một tầng kiến trúc với những dịch vụ cấp cao được xây dựng trên những dịch vụ cốt lõi ở tầng thấp hơn. Bộ công cụ Globus được phân thành những mô đun, và một ứng dụng có thể khai thác những đặc điểm này của từng mô đun của Globus, chẳng hạn như sự quản lý tài nguyên hay hạ tầng thông tin, mà không sử dụng những thư viện truyền thông của Globus. Bộ công cụ Globus hỗ trợ những dịch vụ sau : • GSI (Grid Security Infrastructure): kiến trúc bảo mật • GridFTP: giao thức truyền tập tin • GRAM (Globus Resource Allocation Manager): quản lý các tài nguyên trên môi trường Grid. • Metacomputing Directory Service • Globus Access to Secondary Storage • Data catalogue và replica management Trang 59 • Advanced Resource Reservation và Allocatoin(GARA) Hình 3-2 : Các thành phần của Globus Globus có thể được nhìn nhận như một hệ thống cơ bản cho tính toán lưới, ngoài việc cung cấp cho nhà phát triển ứng dụng một tập thư viện API đặc trưng cho các dịch vụ Globus mà cung cấp. Globus còn cung cấp cho những nhà phát triển ứng dụng một phương tiện hiện thực cho việc bổ sung các dịch vụ để cung ứng cho môi trường thực thi ứng dụng trên một vùng rộng lớn. 3.3.2. Những mô hình lập trình và công cụ hỗ trợ Cho đến lúc này, gần 20 năm nghiên cứu và phát triển trong ngành lập trình song song và phân bố. Việc thiết kế hệ thống phân bố đã hướng nền phát tiển kỹ thuật phần cứng lên một tầm cao mới và ước hẹn có thể xây dựng được hệ thống tốt, cải thiện được trạng thái hiện thời và sử dụng lại hệ thống. Sự phát triển Grid computing cũng lấy gốc từ việc tính toán song song và phân bố này, bởi vì chúng đã xác lập được những phương pháp lập trình nền tảng cho sự phân bố và song song hoá .Chúng em sẽ đưa ra một số mô hình lập trình và công cụ mà ngày nay đã được thực nghiệm trên thế giới 3.3.2.1. Mô hình chia sẽ trạng thái Trang 60 Mô hình lập trình Shared-state đặc trưng cho sự liên kết chặt chẽ ,những ngôn ngữ đồng bộ và những mô hình thực thi cho những máy tính chia sẻ bộ nhớ và hệ thống mạng chia sẻ vùng nhớ giữa các máy tình, với băng tầng truyền thông cao và độ trễ trong việc truyền thông thấp. Việc này quyết định môi trường Grid và sẽ làm tác động đến các công cụ lập trình khác trở nên không hiệu quả, vì thế cần có một số mô hình lập trình thiết yếu dựa trên hình thức chia sẻ trạng thái, và như thế trình sản xuất và tiêu thụ dữ liệu giữa các tiến trình được phân chia rõ ràng hơn trên môi trường Grid. • JavaSpaces Javaspaces là một sự bổ sung dựa trên Java với khái niệm không gian biến (tuplespace) Linda, điều này được minh hoạ bằng một tập biến được thể hiện bởi một tập các đối tượng. Sử dụng Java có đặc điểm là nhiều client và server tương tác với nhau mà không liên quan đến những kiến trúc của bộ xử lý và hệ điều hành. Sử dụng JavaSpaces nhìn nhận một ứng dụng như một tập những xử lý giao tiếp với nhau bằng cách nhận và đưa những đối tượng vào một hay nhiều vùng không gian (space). Một không gian (space) là một kho chứa đối tượng cụ thể và được chia sẻ và được truy xuất thông qua mạng máy tí