Đề 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 lục

Chương 1. Giới thiệu . 14

1.1. Các khái niệm . 14

1.2. Những thách thức đối với tính toán lưới . 17

Chương 2. Tính toán song song và phân bố . 18

2.1. Khái niệm . 18

2.2. Nền tảng tính toán song song và phân bố . 19

2.2.1. Kiến trúc xửlý song song và phân bố . 19

2.2.2. Tổchức vật lý của các nền tảng song song và phân bố . 26

2.3. Một sốmô hình lập trình song song thông dụng . 27

2.3.1. Mô hình chia sẽkhông gian bộnhớ. 27

2.3.2. Mô hình truyền thông điệp . 28

2.4. Cách thức xây dựng một chương trình song song và phân bố . 30

2.4.1. Các thuật ngữcăn bản. 31

2.4.2. Thiết kếthuật toán song song . 33

2.4.3. Một sốphương pháp tối ưu. 46

2.4.4. Các mô hình thuật toán song song . 50

Chương 3. Các môi trường hỗtrợtính toán lưới . 55

3.1. Giới thiệu. 55

3.2. Các vấn đềkhi lập trình luới . 56

3.2.1. Tính mang chuyển, tính khảthi và khảnăng thích ứng. 56

3.2.2. Khảnăng phát hiện tài nguyên . 57

3.2.3. Hiệu năng . 57

3.2.4. Dung lỗi . 58

3.2.5. Bảo mật . 58

3.2.6. Các siêu mô hình. 59

3.3. Tồng quát vềcác môi trường hỗtrợ . 59

3.3.1. Một sốmôi trường Grid . 59

3.3.2. Những mô hình lập trình và công cụhỗtrợ. 63

3.3.3. Môi trường cài đặt . 69

3.4. Những kỹthuật nâng cao hỗtrợlập trình . 81

3.4.1. Các kỹthuật truyền thống . 81

3.4.2. Các kỹthuật hướng dữliệu. 82

3.4.3. Các kỹthuật suy đoán và tối ưu. 83

3.4.4. Các kỹthuật phân tán. 83

3.4.5. Nhập xuất hướng Grid . 84

3.4.6. Các dịch vụgiao tiếp cấp cao . 84

3.4.7. Bảo mật . 86

3.4.8. Dung lỗi . 86

3.4.9. Các siêu mô hình và hệthống thời gian thực hướng Grid. 88

3.5. Kết luận . 89

Chương 4. Mô hình lập trình truyền thông điệp - MPI. 91

4.1. Các khái niệm cơbản . 92

4.2. Cấu trúc chương trình MPI . 95

4.3. Trao đổi thông tin điểm-điểm . 96

4.3.1. Các thông tin của thông điệp . 97

4.3.2. Các hình thức truyền thông. 97

4.3.3. Giao tiếp blocking. 99

4.3.4. Giao tiếp non-blocking . 103

4.4. Trao đổi thông tin tập hợp. 109

4.4.1. Đồng bộhóa. 109

4.4.2. Di dời dữliệu trong nhóm . 109

4.4.3. Tính toán gộp . 113

4.5. Các kiểu dữliệu . 118

4.5.1. Những kiểu dữliệu đã được định nghĩa . 118

4.5.2. Các kiểu dữliệu bổsung. 119

4.5.3. Pack và UnPack . 123

4.6. Quản lý nhóm và communicator . 124

4.6.1. Tổng quan . 124

4.6.2. Nguyên tắc sửdụng. 126

Chương 5. Thửnghiệm các thuật toán lý thuyết đồthị . 129

5.1. Các khái niệm cơbản . 129

5.2. Dijkstra . 130

5.2.1. Tuần tự . 130

5.2.2. Song song. 134

5.2.3. Thực nghiệm chương trình . 136

5.3. Prim. 138

5.3.1. Tuần tự . 138

5.3.2. Song song. 141

5.3.3. Thực nghiệm chương trình . 143

5.4. Bellman – Ford. 143

5.4.1. Tuần tự . 143

5.4.2. Song song. 147

Chương 6. Kết luận – Hướng phát triển . 151

6.1. Kết luận . 151

6.2. Hướng phát triển. 151

Tài liệu tham khảo. 153

pdf153 trang | Chia sẻ: lethao | Lượt xem: 2588 | Lượt tải: 2download
Bạn đang xem trước 20 trang tài liệu Đề 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ị, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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. ht t p : / / e t r i t h u c . v n Trang 59 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ể 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 Autonomic IBM Computing Toolkit :Là một tập hợp những kỹ thuật, những công cụ, tài liệu được thiết kế cho người dùng học, thích hợp, và phát triển JXTA Peer to Peer do những nhà nghiên cứu Sun Microsystems dựa trên giao những truyền thông API JXTA Peer to Peer 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. ht t p : / / e t r i t h u c . v n Trang 60 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 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. 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, 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, những áp dụng sau đây. 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 ht t p : / / e t r i t h u c . v n Trang 61 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 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à điều thiết yếu.Vì thế, việc cung cấp hơn một mô hình lập trình ht t p : / / e t r i t h u c . v n Trang 62 chuẩn, chẳng hạn như mô hình lập trình hướng đối tượng là điều cần 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 APIcủ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 and replica management • Advanced Resource Reservation and Allocatoin(GARA) ht t p : / / e t r i t h u c . v n Trang 63 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 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ột môi trường thực thi ứng dụng trên môt vùng rộng lớn. Globus được chúng tôi nghiên cứu kỹ và đã cài đặt phiên bản Globus 3.2 trên máy đơn, nhưng không triển khai được trên môi trường mạng để tạo Grid. Vì thế chúng tôi đã chuyển sang dùng môi trường khác để thực nghiệm chương trình thực thi phân bố sau này. 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 nghành lập trình song song và phân bố. Việc thiết kế hệ thống phân bố đã hướng cho nền phát tiển kỹ thuật phần cứng lên 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 tồn tại tốt và sử dụng lại. 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 ht t p : / / e t r i t h u c . v n Trang 64 đã 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 tôi sẽ đưa ra một số mô hình lập trình và công cụ mà ngày ngay đã được thực nghiệm trên thế giới 3.3.2.1. Mô hình chia sẽ trạng thái 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 trí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 những 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 shared-state, v à như thế trình sản xuất và tiêu thụ dữ liệu đượ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ẻ mà có thể được truy xuất thông qua mạng máy tính. Những xử lý sử dụng kho chứa như một kỹ thuật trao đổi dữ liệu thay vì phải giao tiếp trực tiếp với nhau. Những thao tác chính là một xử lý có thể có một không gian để đặt, nhận, đọc, sao chép những đối tượng .Trên thao tác nhận hay đọc, đối tượng nhận được xác định bởi một thao tác có tính chất kiểm tra sự gần giống liên kết (associative matching ). Sự gần giống này gồm dạng và số lượng thành phần liên kết với đối tượng đặt vào không gian. Một lập trình viên muốn xây dựng một ứng dụng trên nền tảng như thế này nên thiết kết cấu trúc dữ liệu phân phối giống như một tập những đối tượng được lưu trữ trong một hay nhiều không gian. Sự tiếp cận ht t p : / / e t r i t h u c . v n Trang 65 mới mà mô hình lập trình JavaSpace mang lại cho lập trình viên xây dựng những ứng dụng phân phối dễ dàng hơn. Hiện thời thì việc viết ứng dụng đựa trên JavaSpace được hỗ trợ trên Grid sử dụng công cụ Java của Sun cho Globus. 3.3.2.2. Mô hình truyền thông điệp (Message Passing) Trong những mô hình Message-Passing ,những tiến trình được phân chia riêng không gian bộ nhớ,và thông tin trao đổi bằng cách truyền thông điệp từ một tiến trình đến các tiến trình còn lại. Sự song song hoá thể hiện rõ ràng bằng các thông điệp, nó mang lại cho người sử dụng đầy đủ quyền điều khiển mà những mô hình lập trình khác không có. • MPI và những biến thể của nó MPI(Message Passing Interface) là một chuẩn rất phổ biến cho lập trình truyền thông điệp .Chúng tôi sẽ mô tả chi tiết chuẩn này trong phần sau . MPCH-G2 là một sự bổ sung của MPI cho Grid sử dụng những dịch vụ Globus và cho phép lập trình viên kết nối nhiều máy tính với kiến trúc khác nhau để chạy ứng dụng MPI .MPICH-G2 tự động chuyển đổi dữ liệu trong những thông điệp được gửi giữa những máy tính với kiến trúc khác nhau và hỗ trợ truyền thông đa giao thức bằng cách tự chọn TCP cho việc truyền thông điệp giữa các máy tính với nhau. Sư phổ biến của MPI đã làm xuất hiện một số những biến thể của nó ,liên quan đến những vấn đề của Grid như tự động hoá quản lý tiến trình ,và nhiều thao tác hiệu quả liên quan đến nhiều tiến trình . Ví dụ thư viện MagPIe là một sự bổ sung cho những thao tác liên quan đến nhiều tiến trình (collective operation)của MPI chằng hạn như broadcast, đồng bộ các tiến trình,và những toán tử tính toán gộp với những tối ưu hoá cho những hệ thống rộng lớn như Grid. Những thao tác này sẽ được nói đến chi tiết trong phần lập trình MPI tiếp theo. ht t p : / / e t r i t h u c . v n Trang 66 Stampi hỗ trợ trình quản lý tiến trình tự động ,MPI-IO và MPI-2. MPI_Connect làm cho những ứng dụng MPI khác nhau, của các nhà phân phối MPI khác nhau có thể giao tiêp được với nhau 3.3.2.3. Mô hình RPC và RMI Những mô hình truyền thông điệp (Message Passing),chúng cung cấp các hình thức truyền thông như điểm điểm,một điểm đến nhiều điểm,v.v... Những trình gửi thông điệp đều có những thông số thiết yếu cho những trình nhận xác định thông điệp này, và quyết định xử lý thông điệp hay không dựa trên dạng thông điệp. Ngữ nghĩa liên quan đến dạng thông điệp thường được định nghĩa bởi các nhà thiết kế ứng dụng. Những hình thức gọi hàm từ xa RPC(Remote Procedure Call) và cung cấp phương thức từ xa RMI(Remote Method Invocation) cung cấp những khả năng như thế này. Nhưng cấu trúc giao tiếp giữa trình gửi và trình nhận giông như là một ngôn ngữ hơn là những lời gọi hàm thư viện đơn giản di chuyển dữ liệu giữa nhiều điểm A và B của mô hình truyền thông điệp. Những mô hình RPC và RMI cung cấp một kỹ thuật đơn giản và dễ hiểu cho sự quản lý tính toán từ xa.Ngoài chức năng là một kỹ thuật cho quản lý các dòng điều khiển và dữ liệu. RPC và RMI cũng cho phép kiểm tra các dạng tham số và số lượng tham số. RPC và RMI có thể được dùng để xây dựng những mô hình cấp cao hơn cho Grid ,như những thành phần,những dịch vụ mạng v.v... • RPC hướng Grid GridRPC là một mô hình RPC và là thư viện API cho Grid.Bên cạnh cung cấp ngữ nghĩa chuẩn RPC với sự thực thi bất đồng bộ, song song các tác vụ v.v.. Ba khả năng rất quan trong mà GridPRC cung cấp cho người sử dụng cái nhìn trong suốt về cách quản lý như sau: + Tìm kiếm và lập biểu tự động cho tài nguyên (Dynamic resoure discovery and scheduling) Những dịch vụ RPC có thể được đặt bất kỳ ở đâu trên Grid. Tìm kiếm, lựa chọn,và lập biểu cho sự thực thi từ đằng xa nên được thực hiện dựa trên những ràng buộc,những yêu cầu cơ bản của người sử dụng ht t p : / / e t r i t h u c . v n Trang 67 + Bảo mật (security) :Bảo mật Grid thông qua GSI và chứng thực X.509 là điều thiết yếu cho hệ điều hành trong một môi trường mở.Globus là công cụ Grid hỗ trợ bảo mật này . + Khả năng tự sửa chữa ( Fault tolerance) :Thông qua việc kiểm tra các nút, giảm thiểu hay chạy lại các ứng dụng trên các nút nhằm bảo đảm độ tin cậy ngày càng trở nên thiết yếu cùng với số lượng tài nguyên liên quan tăng lên. Trình quản lý giao tiếp là một vấn đề quan trọng cho tất cả các mô hình gọi hàm từ xa( RPC). Điển hình là một ngôn ngữ định nghĩa giao tiếp (Interface Definition Languague IDL). GridRPC cũng được thiết kế với một số những thuộc tính trong trường hợp cải thiện khả năng dùng lại và dễ bổ sung và triển khai: + Hỗ trợ cho một ngôn ngữ đăc tả giao tiếp cụ thể :Bao gồm nhiều tham số dạng ma trận ,những tham số ma trận chia sẻ bộ nhớ, tham số tập tin, và những tham số này đều được gọi tham chiếu qua hàm. + Quản lý ngôn ngữ đặc tả giao tiếp ở máy chủ : Chỉ có những máy chủ GridRPC quản lý và giám sát tiến trình tác vụ. Máy khách chỉ có nhiệm vụ đơn giản hơn là chỉ thực thi tiến trình. • Java RMI Những phương thức Java được cung cấp từ xa làm cho những lập trình viên có thể tạo những ứng dụng phân phối dựa trên ngôn ngữ lập trình Java.RMI thừa kế từ thiết kế RPC cơ bản, nó có những đặc điểm phân biệt với RPC cơ bản. Với RMI,một chương trình chạy trên máy ảo Java có thể yêu cầu những phương thức của những đối tượng khác bên trong các máy ảo khác. Thuận lợi chính của RMI là mô hình hướng đối tượng thực sự, hỗ trợ tất cả các dạng dữ liêu của một chương trình Java, và hỗ trợ thu gom rác của chương trình. Do đó Java RMI cung cấp một giao diện lập trình cấp cao, rất thích hợp cho tính toán lưới. 3.3.2.4. Mô hình hỗn hợp ht t p : / / e t r i t h u c . v n Trang 68 Sự tất nhiên của tính toán lưới là tạo ra tất cả các máy tinh sẵn dùng trong ứng dụng Grid. Vì thế, một số ứng dụng sẽ muốn thực thi cả bên trong và xuyến suốt không gian địa chỉ. Thực thi nhiều tiểu trình trong cùng một không gian địa chỉ được phân phối, và cũng thông qua dữ liệu và điều khiển giữa các máy tính. Ví dụ một tình trạng xảy ra trong một nhóm nhiều bộ xử lý cân bằng và bên trong Grid. Một số mô hình lập trình đã được phát triển để đề cập tời vấn đề này. • OpenMP và MPI OpenMP là một thư viện hỗ trợ lập trình song song trong những máy tính chia sẻ bộ nhớ. Thư viện này được phát triển bỏi một tổ chức nhữ g nhà cung cấp với những mục tiêu của việc sản xuất một giao tiếp lập trình chuẩn cho những máy tính chia sẻ bộ nhớ song song, và sử dụng những ngôn ngữ như Fortran, C và C++. OpenMP cho phép những đoạn mã thực thi song song (vòng lập Do song song ), định nghĩa dữ liệu chia sẻ (SHARED) và đồng bộ hoá các xử lý. Sự liên kết cả hai OpenMP và MPI bên trong một ứng dụng. Nguyên tắc nhìn nhận những ứng dụng thuộc dạng này là khả năng thực hiện ứng dụng của mỗi mô hình. OpenMP thiết yếu như một mô hình đa tiểu trình. Vì vậy, OpenMP yêu cầu ứng dụng quản lý các thư viện MPI. 3.3.2.4. Mô hình Peer-to-Peer Tính toán peer – peer là sự chia sẻ của những tài nguyên máy tính và những dịch vụ bằng cách trao đổi trực tiếp giữa các hệ thống. Tính toán peer – peer nhận những ưu điểm của sự tồn tại tính toán trên những máy tính mạnh và sự liên kết mạng, cho phép những • JXTA Một họ những giao thức thiết kế đặc biệt cho tính toán P2P là JXTA. Tên JXTA được trích dẫn từ “juxtapose” và có nghĩa đơn giản như hình thức tính toán P2P client/server và tính toán dựa trên Web. Như vậy, JXTA là một tập hợp những giao thức tổng quát P2P , được định nghĩa trong những thông điệp XML, cho phép một số thiết bị đã kết nối trên mạng sắp xếp từ những máy điện thoại ht t p : / / e t r i t h u c . v n Trang 69 động (cell phone và những thiết bị máy tính bỏ túi (PDA) đến những máy tính (PC) và máy chủ (server) để giao tiếp và làm việc với nhau ở dạng hình thức P2P. 3.3.3. Môi trường cài đặt 3.3.3.1. Tồng quan Chúng em đã thử cài đặt Globus phiên bản 3.2 nhưng hiệu quả cài đặt không cao. Việc cài đặt và lập trình trên máy đơn hầu như đơn giản ,chỉ cần vài thao tác có thể xong. Nhưng việc cài đặt trên một mạng LAN thì khó khăn trong việc thông nhau giữa các máy sử dụng Globus. Chúng em quyết định sử dụng môi trường lập trình truyền thông điệp LAM. LAM/MPI không phải là một công cụ hỗ trợ tính toán phân bố .Mà LAM là công cụ dùng cho việc viết các chương trình theo chuẩn MPI chạy trên nhiều máy đã cài đặt LAM.Ta xem LAM như là một dịch vụ trên hệ điều hành phục vụ cho việc biên dich,thực thi chương trình MPI. Là phiên bản nguồn mở, cung cấp miễn phí với chuẩn MPI. LAM/MPI được nghiên cứu, phát triển và hỗ trợ bởi Phòng thí nghiệm hệ thống mở (Open Systems Lab) ở trường đại học Indiana. LAM/MPI hỗ trợ tất cả các chuẩn MPI- 1và nhiều chuẩn MPI-2. LAM/MPI không chỉ là thư viện bổ sung các hàm API của MPI ,mà còn là môi trường thực thi LAM : 1 tầng user,môi trường nền tảng trung gian ,nó cung cấp nhiều dịch vụ cho những chương trình MPI .Cả những thành phần chính của LAM/MPI được thiết kế như những thành phần có chức năng riêng biệt, có khả năng mở rộng với những mô đun vào lúc thi hành .Thành phần này được biết như là Hệ thống Giao tiếp Dịch vụ (System Services Interface _SSI). 3.3.3.2. Cài đặt 3.3.3.2.1. Những yêu cầu o Những yêu cầu chung Hệ điều hành: ht t p : / / e t r i t h u c . v n Trang 70 LAM/MPI được sử dụng trên Linux .Mặc dù MPI/MPI được thử nghiệm trên Red Hat và hệ thống Mandrake Linux sử dụng phiên bản kernel hiện tại nhưng nó vẫn chay tốt trên các phiên bản Linux phân phối khác Các phiên bản Linux cũ hơn như kernel phiên bản 2.2.0 đến 2.2.9 có vài lỗi trong vấn đề mạng TCP/IP .Phiên bản 2.2.10 đã sửa được các vấn đề này . Vì thế các bạn có thể nâng cấp phiên bản Linux lên 2.2.10 hay mới hơn để việc cài đặt và thực hiện chương trình LAM/MPI được chắc chắn hơn Phiên bản Linux chúng tôi sử dụng là RedHat 10 core 1 , hay các phiên bản Linux 9 . Trình biên dịch trên hệ điều hành Trình biên dịch ANSI C Trình biên dịch C++ có hỗ trợ namespace Các tiện ích Unix shell như sed, awk,và grep v.v. hay các tiện ích của Linux như emacs,gedit,terminal v.v... o Những yêu cầu của mô đun dịch vụ hệ thống Như đã nói LAM/MPI được xây dựng xung quanh một thành phần kiến trúc cốt lõi được biết như Hệ thống giao tiếp dịch vụ (System Services Interface _SSI) .Một trong những nguyên tắc chủ yếu là khả năng thực hiện “gắn vào _tháo ra” (plug-in) lúc thực thi để mở rông khả năng của các mô đun của LAM. Mỗi mô đun thành phần được chọn từ mỗi loại lúc thực thi và được sử dụng đê thực hiện hiệu quả môi trường LAM và thư viện MPI (Xem chi tiết trong chuẩn lập trình song song MPI) Hiện thời LAM/MPI sử dụng 4 dạng thành phần mô đun  boot :Bắt đầu môi trường thực thi LAM, được sử dụng với dòng lệnh lamboot  coll :quản lý những hàm MPI truyền thông đa xử lý, sử dụng bên trong xử lý MPI. ht t p : / / e t r i t h u c . v n Trang 71  cr :Khởi động lại những chức năng , được sử dụng bên trong xử lý MPI và dòng lệnh LAM  rpi : quản lý những hàm MPI truyền thông điểm điểm, chỉ sử dụng bên trong xử lý MPI Mỗi mô đun hệ thống giao tiếp dịch vụ có cấu hình chính của nó và xây dựng hệ thống phụ. Một số mô đun cấu hình bị lỗi sẽ có thể bỏ qua và nó không gây ra việc cài đặt bị lỗi, giống như cài đặt chương trình nào đó mà ta bấm qua nút Skip Mỗi SSI mô đun có thể có những yêu cầu cho việc cài đặt thêm, ngoại trừ nhứng yêu cầu chung của LAM. Chi tiết các mô đun ở trên :  Bproc Boot:chỉ được kiểm thử với tập hợp 3.2.x với phiên bản v3.2.5.Những phiên bản trước đó của 3.2.x bị lỗi và có thể gây cho LAM/MPI hỏng khi đang chaỵ.  SLURM Boot:Hỗ trợ việc thực thi trong những môi trường SLURM .Không cấu hình bổ sung hay xây dựng những tham số là cần thiết cho việc hỗ trợ SLURM.Dòng lệnh laminfo có thể được sử dụng để xác nhận lại rằng mô đun boot slurm sẵn có trong gói việc cài đặt LAM  Các mô đun còn lại có thể tham khảo thêm  TM Boot :  BLCR Checkpoint /Restart  Myrinet (gm) RPI  Infiniband(ib) RPI  Shared Memory RPI 3.3.3.2.2. Cấu hình LAM/MPI ht t p : / / e t r i t h u c . v n Trang 72 Bước đầu tiên và cũng phức tạp nhất trong việc cài đặt LAM/MPI là cấu hình xử lý .Nhiều lựa chọn có thể được thiết lập lúc cài đặt hay khi thực thi chương trình , việc cấu hình đơn giản chỉ để trạng thái mặc định Các bước trong việc cài đặt : Giải nén Phiên bản phân phối LAM được đóng gói như một tập tin được nén có định dạng gzip hay bzip2 . shell$ gunzip –c lam-7.1.tar.gz|tar xf shell$ tar zxf lam-7.1.tar.gz Những cấu hình cơ bản : LAM sử dụng một đoạn script cấu hình GNU để hiển thị các trang cài đặt và đặt tả các cấu hình: Chuyển đường dẫn tới thư mục chứa tập tin Lam đã được giải nén .Thiết lập các biến môit trường cần thiết và thực thi tập tin script configure shell$cd lam-7.1 shell$ ./configure Mặc định thì tập tin script configure thiết lập thư mục cài đặt LAM ở thư mục cha nơi mà dòng lệnh lamclean được tìm thấy ,hay đường đẫn /usr/local nếu dòng lệnh lamclean không tìm thấy .Cách cài đặt như thế này có thể được chồng lắp với tuỳ chọn –prefix Tuỳ chọn trình biên dịch : Đoạn mã trong tập tin configure tìm kiếm các trình biên dịch đúng cho việc xây dựng LAM/MPI Tuỳ chọn trình biên dịch Đặc tả trình biên dịch và những tuỳ chọn trình biên dịch Những biến môi trường được sử dụng để chồng lắp lên những thông số đã cài đặt mặc định ht t p : / / e t r i t h u c . v n Trang 73 Trình biên dịch :Những biến môi trường CC,CXX,và FC đặc tả trình biên dịch C, C++ và Fortran được sử dụng để xây dựng LAM .Dòng lệnh tương ứng sẽ là mpicc,mpic++ và mpiff7 Những cờ biên dịch :Những biến môi trường CFLAGS,CXXFLAGS,và FFFLAGS đặc tả những cờ biên dịch để thông qua các trình biên dịch thích hợp .Những cờ này chỉ được sử dụng khi xây dựng LAM và không được thêm vào những danh sách tham số của trình biên dịch có tính chất như vỏ bọc bên ngoài chẳng hạn như mpicc,mpic++. Các trình biên dịch này được gọi như vậy bởi vì nó bao bọc một trình biên dịch bên trong, chẳng hạn như trình mpicc bao bọc trình biên dịch gcc,trình mpic++ bao bọc trình gc++ v.v... Những cờ liên kết : Những biến môi trường như LDFLAGS,CXXLDFLAGS được sử dụng để thêm những tham số vào trình liên kết (hay trình biên dịch C++ khi sử dụng một trình liên kết ). Chúng cũng không được thêm vào danh sách tham số của trình biên dịch có tính chất như vỏ bọc bên ngoài các trình biên dịch khác Tuỳ chọn cấu hình : Đoạn mã cấu hình trong tập tin configure sẽ tạo một số tập tin cấu hình sử dụng trong suốt pha xây dựng LAM .Bao gồm những tập tin dùng để định nghĩa như /share/include/lam_config.h. Những tuỳ chọn tổng quát : Những tuỳ chọn sau đây liên quan đến những kiến trúc cơ bản LAM/MPI: o --disable-static : Không xây dựng các thư viện tĩnh .Cờ trạng thái này chỉ có nghĩa khi –enalble-shared được thiết lập,nếu cờ này được đặc tả mà –enable- shared không thiết lập thì nó coi như được bỏ qua và thư viện tĩnh được tạo ra ht t p : / / e t r i t h u c . v n Trang

Các file đính kèm theo tài liệu này:

  • pdfNghiê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ị.pdf