Luận văn Giải hệ phƣơng trình tuyến tính kích thước lớn trên nền tảng grid computing

on services Grid Information Service (GIS) chịu trách nhiệm cung cấp các thông tin động và 27 tĩnh về tính sẵn sàng và khả năng hiện hành của các tài nguyên cũng như các thông tin khác về toàn bộ hệ thống Grid. Các thông tin này sẽ được dùng để xác định vị trí các tài nguyên theo những tiêu chí cụ thể, để xác định các trình quản lý liên kết với tài nguyên, để xác định các tính chất của tài nguyên, xác định chiến lược sử dụng hiệu quả tài nguyên, và phục vụ nhiều mục đích khác trong quá trình chuyển các đặc tả về tài nguyên cấp cao của ứng dụng thành các yêu cầu cụ thể đến từng trình quản lý tài nguyên. 2.3.3.3. Index Service Hệ thống quản lý thông tin tài nguyên Grid trong GT4 đã có nhiều đổi khác so với GT2. Index Service cũng có các chức năng tương tự như MDS, nhưng nó cung cấp thông tin về các Grid Service dưới các định dạng XML. Không giống như GT2, thành phần GRIS bị loại bỏ vì mỗi Grid Service đều có một tập các thông tin liên quan của riêng nó. Các thông tin này đã được lưu trữ theo một cách thức đã được chuẩn hoá, đã có các cách thức dễ dàng để truy vấn và hiểu các các dữ liệu của service thông qua các interface chuẩn của một Grid service. Các service được yêu cầu phải thông báo các thông tin cơ bản của mình, cho phép người dùng lấy thông tin từ bất cứ Grid service nào.  Index Service đóng vai trò của một GIIS trong mô hình quản lý thông tin Grid, là một trong những GT4 Base Services. Nó thực hiện thu thập, tổng hợp và truy vấn các Service Data, theo dõi quá trình điền dữ liệu; tạo Service Data theo yêu cầu. Nó có thể được sử dụng cho để xây dựng các Service Data chỉ mục mang các thông tin trạng thái từ nhiều service instance phục vụ việc khám phá, lựa chọn và tối ưu hoá việc sử dụng tài nguyên. 2.3.4. Các thành phần quản lý tài nguyên 2.3.4.1. Kiến trúc quản lý tài nguyên của Globus Toolkit Như đã biết, vấn đề quản lý tài nguyên là một thách thức lớn cho công nghệ Grid Computing. Nhóm phát triển Globus Toolkit đã đưa ra một giải pháp khá hoàn chỉnh để giải quyết vấn đề quản lý và chia sẻ tài nguyên trong Grid 28 Hình 2.3. Kiến trúc quản lý tài nguyên của Globus Toolkit Trong kiến trúc này, ngôn ngữ Resource Specification Language (RSL),được sử dụng để trao đổi các yêu cầu về tài nguyên giữa các thành phần: từ ứngdụng (application) đến resource broker, resource co-allocator và resource manager.Tại mỗi bước của quá trình này, các thông tin về yêu cầu tài nguyên được đặc tảtrong chuỗi RSL của ứng dụng hay được xây dựng lại bởi một hay nhiều resourcebroker và co-allocator. Thông tin về khả năng, tính sẵn sàng, tính chất của các tàinguyên có thể lấy từ một Information service Resource broker chịu trách nhiệm chuyển đổi từ một đặc tả RSL cấp caothành các đặc tả RSL chi tiết hơn qua quá trình chi tiết hoá. Nhiều broker có thể phối hợp với nhau để cùng giải quyết một yêu cầu về tài nguyên, một số broker chuyển các yêu cầu của ứng dụng thành các yêu cầu chi tiết hơn về tài nguyên, rồi một số broker khác định vị các tài nguyên thoả yêu cầu. Bản đặc tả chi tiết về vị trí các tài nguyên, có thể được chuyển cho một resource co-allocator, đây là module chịu trách nhiệm phối hợp và quản lý tài nguyên trên nhiều site. Resource co-allocator thực hiện chia nhỏ các yêu cầu tài nguyên trên nhiều site thành từng thành phần nhỏ và chuyển chúng đến resource manager thích hợp. Mỗi 29 Resource manager trong hệ thống chịu trách nhiệm lấy yêu cầu trong RSL và chuyển nó thành các thao tác thực hiện trên hệ thống quản lý tài nguyên cục bộ của site. Information service chịu trách nhiệm cung cấp khả năng truy cập hiệu quả và rộng khắp đến các thông tin về khả năng và tính sẵn sàng hiện tại của các tài nguyên. Thông tin này dùng để định vị các tài nguyên với các đặc tính cụ thể, để xác định Resource Manager liên kết với tài nguyên, xác định tính chất của tài nguyên, và phục vụ cho rất nhiều mục đích trong quá trình biên dịch từ đặc tả yêu cầu tài nguyên cấp cao thành các yêu cầu đến các resource manager cụ thể. Mô hình trên đã giải quyết đƣợc các vấn đề: 1. Quản lý được các tài nguyên không đồng nhất, đa dạng trong nhiều vùng quản trị khác nhau, thông qua module Resource Manager. Resource Manager một mặt cung cấp một giao diện chung thống nhất để sử dụng tài nguyên, che đi sự phức tạp của tài nguyên; một mặt tương thích với từng công cụ quản lý tài nguyên, các chính sách, các cơ chế bảo mật cục bộ. 2. Để điều khiển trực tuyến và mở rộng các chính sách, RSL được định nghĩa để hỗ trợ trao đổi, tìm kiếm giữa các thành phần khác nhau trong kiến trúc. 3. Sử dụng các resource broker để thực hiện chuyển đổi, ánh xạ các yêu cầu cấp cao của ứng dụng thành các yêu cầu cụ thể đến các resource manager. Điều này giảm bớt độ phức tạp cho người dùng khi đặc tả các tài nguyên cần dùng. 4. Giải quyết vấn đề phối hợp cấp phát (co-allocation) bằng cách xác định nhiều chiến lược khác nhau, gói gọn, tích hợp trong các resource coallocator. 2.3.4.2. Chi tiết các thành phần 2.3.4.2.1. GRAM Grid Resource Allocation and Management (GRAM) là thành phần ở tầng thấp nhất trong mô hình trên, thành phần quản lý tài nguyên cục bộ (resource management). GRAM giúp đơn giản hoá việc sử dụng các hệ thống, tài nguyên ở xa bằng cách cung cấp một giao diện chuẩn, đơn giản để yêu cầu và sử dụng các tài nguyên để thực thi các công việc. GRAM xử lý các yêu cầu về tài nguyên để thực thi các ứng dụng từ xa, cấp phát các 30 tài nguyên cần thiết, thực thi và quản lý trạng thái và tiến độ của các công việc đang thực hiện. Nó cũng thực hiện cập nhật các thông tin về khả năng và tính sẵn sàng của các tài nguyên đang quản lý cho module Information Service. GT4.2 chứa 2 bản cài đặt GRAM, một bản xây dựng trên các protocol riêng của Globus (trong GT2) được gọi là Pre-WS GRAM, và một bản mở rộng của Pre-WS GRAM, xây dựng theo chuẩn OGSI, được gọi là WS-GRAM. GRAM cung cấp các hàm API, các dịch vụ để yêu cầu hoặc huỷ bỏ việc thực thi các công việc cũng như kiểm tra trạng thái của các công việc đang thực thi. Các yêu cầu được đặc tả bởi ngôn ngữ đặc tả tài nguyên (Resource Specification Language (RSL)). Resource Specification Language (RSL) là một ngôn ngữ có cấu trúc được sử dụng để đặc tả các yêu cầu tài nguyên và các thông số cần thiết để thực thi một công việc. Trong WS-GRAM, RSL được viết lại dưới dạng XML. GRAM giảm thiểu các cơ chế cần thiết để sử dụng tài nguyên ở xa. Các hệ thống cục bộ ở xa có thể sử dụng nhiều cơ chế quản lý tài nguyên khác nhau (như sử dụng hệ thống lập lịch, hệ thống hàng đợi, hệ thống giữ chỗ, các giao diện điều khiển khác nhau), nhưng người dùng và các nhà phát triển ứng dụng chỉ cần sử dụng một cơ chế, một giao diện duy nhất (của GRAM) để yêu cầu và sử dụng các tài nguyên này. Hiện nay GRAM không có khả năng lập lịch và tìm kiếm để tìm các tài nguyên và để tự động gửi các công việc đến các hệ thống thích hợp, không có các chức năng kế toán và tính toán chi phí. Thay vào đó, nó cung cấp các công cụ và giao diện để xây dựng các chức năng trên. Các chức năng này được bổ sung bằng các dự án khác được xây dựng trên nền tảng GRAM như Condor-G, Gridbus,... GRAM đã được thiết kế để tương thích và sử dụng được với 6 bộ lập lịch cục bộ : Condor, Load Sharing Facility (LSF), Network Queuing Environment (NQE), Fork, EASY, và LoadLeveler. Khi một người dùng hoặc một resource broker gửi một yêu cầu thực thi công việc, nó sẽ đi qua các trạng thái khác nhau theo sơ đồ trạng thái sau: 31 Hình 2.4. Các trạng thái của 1 công việc 1. UnSubmitted Công việc chưa được gửi cho bộ lập lịch cục bộ. Các lời gọi callback về trạng thái công việc sẽ không bao giờ được thực hiện. 2. StageIn Trạng thái khởi tạo, chuẩn bị thực thi, đọc, nhập các file dữ liệu cho job. Một số công việc có thể không có trạng thái này. 3. Pending Công việc đã được gửi đến bộ lập lịch cục bộ, nhưng chưa cấp phát tài nguyên cho nó. 4. Active Công việc đã nhận đủ các tài nguyên cần thiết và đang được thực thi. 5. Suspended Công việc đã bị ngừng tạm thời bởi bộ lập lịch. Chỉ có một số bộ lập lịch cho phép công việc vào trạng thái Suspended. 6. StageOut Trình quản lý công việc gửi các file dữ liệu kết quả đến các kho lưu trữ ở xa. Một số công việc có thể không có trạng thái này. 7. Done Công việc đã thực hiện xong và thành công. 8. Failed 32 Công việc kết thúc trước khi hoàn thành, do một lỗi hay do yêu cầu hủy của người dùng hoặc hệ thống. 2.3.4.2.2. Pre-WS GRAM 1. Các đặc điểm chính - Cung cấp các dịch vụ không theo chuẩn OGSI phục vụ thực thi các công việc trên các site ở xa. - Sử dụng ngôn ngữ RSL để trao đổi các yêu cầu về thực thi công việc. - Các công việc ở xa thực thi dưới quyền của user cục bộ. - Việc uỷ quyền, chứng thực giữa client và dịch vụ phải thông qua thành phần thứ ba (gatekeeper). 2. Mô hình hoạt động tổng quan của pre-WS GRAM Kiến trúc các thành phần và cơ chế hoạt động của Pre-WS GRAM như sau: Hình 2.5. Các thành phần và cơ chế của Pre-WS GRAM 33 Như trên hình vẽ, các thành phần chủ yếu của pre-WS GRAM là : GRAM client library, gatekeeper, RSL parsing library, Job manager và GRAM Reporter. GSI được sử dụng để chứng thực và phân quyền cho người dùng. * GRAM client library được sử dụng bởi các ứng dụng hay một coallocator đại diện cho ứng dụng. Nó giao tiếp với GRAM gatekeeper trên site ở xa để thực hiện mutual authentication và gửi một yêu cầu gồm có bản đặc tả tài nguyên, các yêu cầu về callback, và một số thành phần khác. * Gatekeeper là một thành phần khá đơn giản, chịu trách nhiệm đáp ứng lại yêu cầu từ GRAM client bằng cách thực hiện 3 việc sau: thực hiện mutual authentication với user và tài nguyên, ánh xạ user name cục bộ cho user ở xa, khởi động một Job manager. Job manager này sẽ chạy trên hệ thống như là một user cục bộ, và thực sự xử lý các yêu cầu. * Một Job manager chịu trách nhiệm tạo lập các tiến trình (process) được yêu cầu bởi người dùng. Thông thường nhiệm vụ này được thực hiện bằng cách gửi các yêu cầu cấp phát tài nguyên đến hệ thống quản lý tài nguyên cục bộ của site. Khi các tiến trình được tạo ra, Job manager còn chịu trách nhiệm theo dõi trạng thái của chúng, thông báo callback các thay đổi trạng thái, triển khai các thao tác điều khiển tiến trình như tạm dừng, kích hoạt, kết thúc tiến trình. Hoạt động của Job manager kết thúc khi công việc nó quản lý kết thúc. Một Job manager có 2 thành phần : - Common Component : chuyển thông điệp nhận được từ gatekeeper và client thành các lời gọi đến các API của Machine-Specific Component (MSC). Nó cũng biên dịch các yêu cầu thông báo thông tin callback của MSC thành các thông điệp gửi về client. - Machine-Specific Component : chứa các mã cài đặt cụ thể của các hàm API trên các môi trường cục bộ khác nhau. Đây là phần thay đổi duy nhất trong GRAM để tương thích với các môi trường cục bộ. Mã cài đặt bao gồm các lời gọi hàm đến hệ thống cục bộ, các thông báo đến trình theo dõi tài nguyên (MDS). * GRAM reporter chịu trách nhiệm gửi các thông tin về cấu trúc (như khả năng giữ chỗ, số lượng hàng đợi,… ) và trạng thái (như số lượng các node, số node đang đang sẵn sàng, các công việc đang thực hiện, ….) của bộ lập lịch cục bộ cho hệ thống Information Service (ở đây là MDS). Pre-WS GRAM có thể sử dụng module Global Access to 34 Secondary Storage (GASS) để truyền các file dữ liệu và kết quả về client. Cơ chế này được sử dụng trong lệnh globusrun, gatekeeper và job manager. Người dùng có thể sử dụng cơ chế co-allocator Dynamically-Updated Request Online Coallocator (DUROC) để yêu cầu thực hiện công việc trên nhiều job manager ở cùng một host hay ở nhiều host khác nhau.Các script RSL chứa cú pháp DUROC sẽ được phân tích (parse) ở GRAM client và phân phối đến nhiều job manager. Hình 2.6. Cơ chế hoạt động của duroc trong Pre-WS GRAM 2.3.4.2.3. WS-GRAM 1. Các đặc điểm chính - Cung cấp các service theo chuẩn OGSI phục vụ thực thi các công việc trên các site ở xa. - Sử dụng ngôn ngữ RSL-2 (các đặc tả RSL theo định dạng XML) để trao đổi các yêu cầu về thực thi công việc. - Các công việc ở xa thực thi dưới quyền của user cục bộ. - Việc uỷ quyền, chứng thực giữa client và service không cần thông qua thành phần thứ ba. 2. Mô hình thành phần và hoạt động 35 Với GT4, người dùng đã có thể gọi thực thi các công việc thông qua các Grid service. Kiến trúc GRAM được thiết kế lại theo OGSA thông qua 5 service và một số module: - Master Managed Job Factory Service (MMJFS) Chịu trách nhiệm phát hành các service GRAM ảo cho thế giới bên ngoài. MMJFS sử dụng Service Data Aggregator để thu thập và phát sinh các Service Data Element cục bộ, chứa thông tin về trạng thái các scheduler cục bộ (như tổng các node, các node hiện đang sẵn sàng) và các thông tin về host (host,kiểu CPU, host OS). MMJFS thực hiện cấu hình Redirector để giải quyết các lời gọi createService đến nó qua Startup UHE. Redirector được hướng dẫn để chuyển các lời gọi createService đến hosting environment của người dùng. - Managed Job Factory Service (MJFS) Chịu trách nhiệm tạo lập một instance MJS mới. Nó chỉ phát hành một Service Data Element đơn nhất, là một mảng các GSH của tất cả các instance MJS đang hoạt động. - Managed Job Service (MJS) Là một OGSA service thực hiện gửi công việc đến các scheduler cục bộ, theo dõi trạng thái của công việc, và gửi các thông báo. MJS sẽ khởi động 2 service File Streaming Factory Services làm stdout và stderr cho công việc. Những GSH của 2 service này được lưu trữ trong MFS Service Data Element. - File Stream Factory Service Chịu trách nhiệm tạo các instance mới của File Stream Service. - File Stream Service Là một OGSA service sử dụng một địa chỉ URL đưa vào để chuyển kết quả từ các file cục bộ tạo ra bởi factory đại diện cho các luồng stdout, stderr đến host có URL đó. - Virtual Host Environment Redirector Nhận tất cả các thông điệp SOAP và chuyển chúng đến User Host Environment (UHE). - Starter UHE 36 Được sử dụng bởi Redirector để giải quyết các lời gọi đến một UHE. File gridmap được sử dụng để lấy tên người dùng cục bộ tương ứng với subject DN của người dùng Grid và để đảm bảo chỉ có một UHE trên một người dùng chạy trên một máy. Việc ánh xạ tên người dùng đến số hiệu cổng (port number) của UHE của người dùng đó được quản lý trong một file cấu hình. Khi có một yêu cầu về URL đến và có một điểm nhập(entry) trong file cấu hình, URL đích sẽ được xây dựng và trả về cho Redirector. Nếu UHE ở cổng đó chưa được khởi động, module setuid/launch được sử dụng để khởi động UHE cho user. Nếu một điểm nhập chưa tồn tại trong file cấu hình, một cổng chưa sử dụng được chọn, module setuid/launch được sử dụng để khởi động UHE trên cổng được chọn và trả về URL cho Redirector, sau khi chắc chắn rằng UHE đã được chạy. File cấu hình cũng được cập nhật thêm điểm nhập này. - Launch UHE Dùng để khởi động một hosting environment mới dưới user account. 37 Hình 2.7. Các thành phần và cơ chế hoạt động của WS-GRAM Hình 2.7 miêu tả nguyên tắc hoạt động của WS-GRAM cùng các thành phần. 1. Trước hết MMJFS được cấu hình để sử dụng Redirector để chuyển hướng các lời gọi đến nó và sử dụng Starter UHE để khởi động một UHE nếu chưa có UHE cho người dùng. Sau này, khi có một lời gọi createService MMJFS sẽ sử dụng Redirector để gọi Starter UHE và khởi động một UHE. 2. MMJFS phát hành GSH của nó đến một Registry ở xa. (Có thể không có bước này) 38 3. Một người dùng (client) khởi tạo một proxy và gửi một yêu cầu createService đến server thông qua proxy của mình. Yêu cầu này sẽ được tiếp nhận bởi Redirector. 4. Redirector gọi Starter UHE để thực hiện phân quyền cho yêu cầu của người dủng thông qua Grid-mapfile để xác định tên người dùng cục bộ và cổng được sử dụng, từ đó xây dựng nên một URL đích. 5. Redirector cố gắng chuyển tiếp lời gọi của người dùng đến URL đích vừa được xây dựng. Nếu nó không thể chuyển tiếp được lời gọi bởi vì UHE chưa chạy, module Launch UHE sẽ được gọi. 6. Launch UHE tạo một tiến trình mới UHE dưới tên người dùng cục bộ đã được chứng thực. 7. Starter UHE sẽ chờ cho đến khi UHE được khởi tạo hoàn toàn thông qua cơ chế “ping loop” và trả về URL đích cho Redirector. 8. Redirector chuyển lời gọi createService đến MJFS và ở đây sẽ thực hiện quá trình chứng thực hai chiều và phân quyền. 9. MJFS tạo một MJS mới 10. MJS gửi công việc được yêu cầu đến hệ thống lập lịch cục bộ. 11. Các lời gọi tiếp theo đến MJS từ client sẽ được chuyển đến MJS thông qua Redirector. 12. RIPS cung cấp các dữ liệu liên quan đến các thực thể MJS và MMJFS. Nó thu thập thông tin từ hệ thống lập lịch cục bộ, hệ thống file, thông tin về host,… 13. Các lời gọi FindServiceData sẽ được giải quyết bằng cách trả về một SDE (phát sinh bởi Service Data Aggregate) hoặc được chuyển đến MJFS liên quan. 14. Để gửi các luồng stdout/stderr về client, MJS sẽ tạo ra 2 FSFS, một cho stdout, một cho stderr. 15. Sau đó, MJS tạo các thực thể FSS như xác định trong yêu cầu về công việc. 16. Một trình quản lý GRIM chạy trong UHE để tạo một host certificate. Chứng chỉ này được sử dụng trong quá trình chứng thực hai chiều giữa MJS và 39 client. Từ phiên bản GT3, Các đặc tả yêu cầu tài nguyên và công việc được viết bằng ngôn ngữ RSL mới. Ngôn ngữ RSL mới cũng vẫn có các chức năng tương tự như trong GT2 nhưng được định nghĩa lại dưới dạng XML. 40 Chương 3 : MPICH và MPICH-G2 Máy tính với một bộ vi xử lý có những giới hạn về hiệu năng. Thời gian trễ trên bộ nhớ và thiết bị lưu trữ là rào cản chính mà các nhà thiết kế máy tính phải đối mặt. Thời gian trễ bắt nguồn từ các ràng buộc vật lý và rất khó giảm thiểu. Với các thiết bị lưu trữ độ trễ có thể vào cỡ 10-3giây, gấp hàng triệu lần thời gian trễ của bộ vi xử lý. Như vậy các mô hình tính toán song song là một trong các giải pháp giúp tăng hiệu năng tính toán. Trên quan điểm phần cứng thì mô hình phân tán là cách tiếp cận song song hóa đơn giản nhất. Các máy tình sẽ được kết nổi trong một mạng máy tính. Mô hình lập trình điển hình bao gồm các tiến trình riêng rẽ trên mỗi máy tính trao đổi thông tin với nhau bằng cách gửi và nhận các thông điệp. Đây là mô hình phổ biến nhất của tính toán song song. Hệ thống sử dụng bộ nhớ phân tán là hệ thống tính song song thông dụng nhất hiện nay. Cách tiếp cận sử dụng mô hình bộ nhớ chung sẽ phức tạp hơn, tập hợp các máy tính một cách chặt chẽ hơn bằng cách đưa vào một không gian địa chỉ duy nhất. Các CPU sẽ truy nhập đến dữ liệu thông qua các lệnh nhập và xuất trong tập lệnh cơ bản. Bởi truy cập thông qua tập lệnh cơ bản nhanh hơn là các lệnh truy cập mạng trong hệ thống phân tán cho nên truy cập sẽ có độ trễ thời gian thấp hơn , băng thông rộng hơn. 3.1. MPI MPI (Message Passing Interface) MPI là một hệ thống truyền thông điệp chuẩn hỗ trợ việc trao đổi tài nguyên, thông tin giữa các bộ xử lý phục vụ cho việc viết các ứng dụng song song. Phiên bản MPI đầu tiên được phát hành năm 1994 trên MPI Forum (MPIF). MPI ra đời do mỗi nhà sản xuất MPP (Massively Parallel Processor) đã tạo ra các API trao đổi thông điệp riêng khiến người dùng gặp khó khăn khi viết những chương trình tính toán song song có tính linh động (portable). Tập MPI thi hành bao gồm một thư viện các thủ tục sao cho có thể gọi được từ các chương trình Fortran, C, C++ hay Ada. Lợi thế của MPI so với các thư viện cũ là nó vừa thuận tiện (vì MPI thực thi cho hầu hết các kiến trúc bộ nhớ phân tán) vừa nhanh (vì mỗi thủ tục được tối ưu hóa cho phần cứng mà nó đang chạy). 41 Hiện nay có nhiều phiên bản MPI được phát triển rộng rãi trên khắp thế giới, như là MPICH, Open MPI, LAM/MPI, MVAPICH, Scali MPI... 3.2. MPICH MPICH là một phiên bản MPI khá thông dụng trong mô hình tính toán song song và tính toán phân tán (distributed computing). MPICH là một sản phẩm giữa sự hợp tác giữa phòng thí nghiệm quốc gia Argonne và trường đại học bang Mississippi . Đây là phiên bản được sử dụng rộng rãi trong mạng các máy trạm và hệ thống Beowulf clusters. MPICH miễn phí và có thể download tại: Hiện nay, MPICH là sự kế thừa và phát huy theo chuẩn của MPI-1, với các phần mở rộng hỗ trợ cho các I/O song song đã được định nghĩa trong chuẩn MPI-2. MPICH là một thư viện được phân bố một cách rộng rãi với trung bình 2000 lượt tải mỗi tháng, chưa tính lượt tải tại các trang liên kết. MPICH được phân phối miễn phí và đóng góp khá nhiều cho cộng đồng tính toán song song. Tầng trên cùng của MPICH là MPI interface được định nghĩa bởi chuẩn MPI. Ngay bên dưới là các tầng của MPICH. Hầu hết các đoạn mã của MPI đều độc lập với các thiết bị mạng hoặc hoặc hệ thống quản lý tiến trình. Những đoạn mã này bao gồm việc kiểm tra lỗi và rất nhiều cách sử dụng khác nhau với các đối tượng không rõ ràng. Tất cả các chức năng được thông qua một tầng thấp hơn là Abtract Device Interface (ADI). ADI là một interface đơn giản và tập trung vào việc di chuyển dữ liệu giữa tầng MPU và hệ thống mạng. MPICH-G2 là một sự phát triển từ ADI và còn có cách gọi khác là globus2 device. 3.3. MPICH-G2 MPICH-G2 là một sự bổ sung của MPI v1.1 standard. Nó sử dụng dịch vụ từ Globus Toolkit ,MPICH-G2 cho phép bạn kết hợp nhiều máy tính với các kiến trúc khác nhau để chạy 1 ứng dụng MPI. MPICH-G2 tự động chuyển đổi dữ liệu trong các tin nhắn giữa các máy với kiến trúc khác nhau và hỗ trợ nhiều giao thức giao tiếp khác bằng cách tự động chọn lựa TCP cho việc giao tiếp giữa các máy và phiên bản MPI hỗ trợ việc đó. MPICH-G2 là một sự thể hiện đầy đủ nhất của chuẩn MPI-1 sử dụng Globus Toolkit để hỗ trợ thực thi trong môi trường Grid không đồng nhất. 42 Hình 3.1. Sơ đồ tương tác giữa MPICH với Globus Toolkit 3.3.1. Quá trình thực thi một ứng dụng Trước khi bắt đầu 1 ứng dụng MPICH-G2, người dùng sử dụng Grid Sercurity Infrastruce (GSI) để yêu cầu một (khóa công khai) chứng thực proxy được sử dụng để chứng thực người dùng. Bước này cung cấp khả năng chỉ cần đăng nhập một lần, luôn giữ kết nối trong quá trình chạy ứng dụng mà không cần gõ passphase để chứng thực lại, kết nối này bị hủy khi sử dụng lệnh hủy. Người dùng sử dụng Monitoring and Discovery Service (MDS) để lựa chọn các máy tính sẽ thực thi tiến trình bao gồm các công việc cơ bản như : cấu hình, kiểm tra tính sự tồn tại, kiểm tra kết nối mạng. Sau khi chứng thực và tạo kết nối proxy, người dùng sử dụng dòng lệnh mpirun để yêu cầu tạo một phiên tính toán MPI. MPICH-G2 sử dụng Resource Specification Language (RSL) để đặc tả công việc tính toán. Người dùng viết các file RSL để nhận diện tài nguyên tính toán (ví dụ: máy tính) và môi trường tính toán cụ thể (số lượng CPU sử dụng, bộ nhớ, thời gian thực thi) và các tham số đi kèm cho mỗi một máy tính. Khi tìm thấy thông tin trong file RSL ,MPICH gọi một thư viện được phân phối kèm với Globus Toolkit đó là Dynamic-Updated Request Online Coallocator (DUROC) để lập lịch và khởi động ứng dụng. Thư viện DUROC sử dụng API Grid Resource Allocation and Managenment (GRAM) và các giao thức để khởi động , sau đó quản lý các tiến trình tính toán phụ trên 43 mỗi máy tính. Với mỗi tiến trình tính toán phụ, DUROC sinh ra một yêu cầu GRAM để điều khiển GRAM server yêu cầu chứng thực người dùng, thực thi việc chứng thực người dùng cục bộ và sau đó tương tác với lập lịch cục bộ để khởi tạo quá trình tính toán. DUROC và các thư viện MPICH-G2 liên kết với nhau gói gọn các tiến trình tính toán phụ vào một tiến trình tính toán MPI. GRAM sẽ sử dụng Global Access to Secondary Storage (GASS) để phân các giai đoạn thực thi từ các địa điểm từ xa. Khi GASS được sử dụng, chỉ một ứng dụng được khởi động, chuyển hướng các dòng thông tin đầu ra và lỗi (stdout ,stderr) tới các terminal người dùng. Khi một ứng dụng được khởi động, MPICH-G2 lựa chọn các phương thức giao tiếp có hiệu quả nhất giữa 2 tiến trình, sử dụng phiên bản MPI đi kèm nếu có hoặc Globus communication (Globus IO) với Globus data conversion (Globus DC) cho các giao thức TCP. DUROC và GRAM cũng theo dõi và quản lý các tiến trình thực thi của ứng dụng. Mỗi một server GRAM theo dõi vòng đời của tiến trình tính toán phụ xem chúng đã hoàn thành hay đang thực thi hay đã kết thúc, và chuyển những thông tin này trở về DUROC. Mỗi một tiến trình phụ bị chặn bởi DUROC và được trả lại sau khi các tiến trình phụ đã thực thi xong. Tất nhiên, yêu cầu hủy tiến trình từ người dùng (Coltrol C) cũng được xử lý bởi GRAM và DUROC. Sau khi một tiến trình được khởi động, MPICH-G2 sử dụng thông tin được lưu trữ cụ thể trong file RSL để tạo cluster giữa các tiến trình. 44 Chương 4 : Thí nghiêm triển khai hệ thống Grid cơ bản cho mục đích tính toán song song sử dụng Globus Toolkit và MPICH-G2 Hệ thống các máy thuộc mạng Grid sẽ được triển khai sau đây bao gồm 5 máy tính. Người dùng sẽ được sử dụng dịch vụ của do hệ thống Grid mang lại sẽ là người dùng “thinh”. Cần triển khai lần lượt 2 gói phần mềm Globus Toolkit và MPICH lên cả 5 máy tính. 4.1. Triển khai Globus Toolkit 4.1.1. Chuẩn bị về phần cứng và phần mềm hệ thống Phiên bản GLOBUS Toolkit được sử dụng ở đây là phiên bản 4.2.1, có thể được được tìm thấy trên trang chủ  Phần cứng Sử dụng 4 máy tính với các hostname và địa chỉ IP như sau : Hostname Địa chỉa IP b.ar.com 192.168.1.13 (CA) b1.ar.com 192.168.1.14 b2.ar.com 192.168.1.15 b4.ar.com 192.168.1.17 Khi đặt hostname cho các máy tính, có một số lưu ý sau : - Các hostname phải được đặt ở dạng đầy đủ - Đặt hostname trước khi cài đặt GLOBUS, vì trong quá trình cài đặt GLOBUS sẽ đưa ra các file cấu hình liên quan đến hostname của máy tính. - Các hostname trong cùng một mạng Grid phải có cùng 1 cấu trúc hostname như sau: example.mydomain.com. Trong đó example khác nhau, nhưng luôn luôn phải có mydomain.com. 45 Như đã đề cập trong chương 1 : một hệ thống grid cần có 1 server làm nhiệm vụ chứng thực. Chọn b.ar.com làm server chứng thực (CA)  Phần mềm hệ thống 4 máy tính được cài đặt hệ điều hành CentOS 5.4 Lưu ý : Có thể chọn các bản phân phối khác của Linux cũng như Unix để triển khai Hệ thống phải đảm bảo có các gói sau :  Thư viện zlib cho GSI-OpenSSH  java-1.6.0-openjdk-devel.i386 và java-1.6.0-openjdk.i386 : 2 gói phát triển Java từ Sun  Apache-ant  xinetd  Gcc : C compiler  G++ : C++ compiler  Tar : công cụ nén và giải nén  Make : công cụ cho phép dịch liên kết nhóm các chương trình  Perl : ngôn ngữ perl  IODBC nếu cần triển khai module RSL  Postgresql nếu cần triển khai module RFT 4.1.2. Cài đặt Globus Toolkit Công việc cài đặt được thực hiện tương tự nhau trên cả 3 máy. Tạo người dùng globus với đầy đủ quyền đăng nhập và có thư mục cá nhân Thêm người dùng globus [root@b ~]# Useradd globus Cấp quyền đăng nhập và thư mục cá nhân /home/globus [root@b ~]# Passwd globus Tương tự tạo người dùng thinh với đầy đủ quyền ,đây sẽ là người dùng cục bộ và cũng là người dùng GLOBUS trực tiếp sử dụng dịch vụ grid do GLOBUS TOOLKIT mang lại, người dùng này cần được tạo ra giống nhau trên các máy tham gia mạng grid. 46 Download mã nguồn globus toolkit 4.2.1 : gt4.2.1-all-source-installer.tar.bz2 Với quyền người dùng Globus Giải nén mã nguồn bằng công cụ tar [globus@b ~]$tar xjvf gt4.2.1-all-source-installer.tar.bz2 Tạo một biến môi trường lưu giữ thông tin thư mục sẽ cài đặt Globus toolkit [root@b ~]#export GLOBUS_LOCATION=/usr/local/globus-4.2.1 Tạo thư mục [root@b ~]#mkdir $GLOBUS_LOCATION Cấp quyền sở hữu thư mục này cho người dùng GLOBUS [root@b ~]#chown globus:globus $GLOBUA_LOCATION Với quyền người dùng Globus Chuyển vào thư mục chứa mã nguồn GT4 đã giải nén Sau đó lần lượt thực hiện quy trình biên dịch 1 gói mã nguồn theo các bước sau [globus@b gt4.2.1-all-source-installer]$ ./configure -- prefix=$GLOBUS_LOCATION --with-iodbc=/usr/lib Bước này thành công sẽ tạo ra 1 makefile trong thư mục chứa mã nguồn GT4 để người dùng có thể biên dịch bằng công cụ make Lưu ý : trong bước này thường có thông báo lỗi chưa thiết lập biến môi trường JAVA_HOME. JAVA_HOME là biến chứa thông tin về thư mục gốc của bộ phát triển phần mềm với ngôn ngữ lập trình Java, nơi liên quan đến lệnh javac. Trong trường hợp gặp lỗi trên, cần xác định đường dẫn chính xác thư mục gốc chứa lệnh javac và tạo biến môi trường JAVA_HOME có giá trị là đường dẫn này bằng lệnh export. Tiến hành dịch gói bằng lệnh [globus@b gt4.2.1-all-source-installer]$make | tee install.log 47 Quá trình biên dịch mã nguồn có thể kéo dài 3-4 tiếng đồng hồ với các máy tính cá nhân phổ thông hiện nay Nếu quá trình dịch gói gặp lỗi phát sinh lỗi, hãy kiểm tra file install.log để khắc phục lỗi và dịch lại Nếu quá trình biên dịch thành công, tiến hành cài đặt [globus@b gt4.2.1-all-source-installer]$ make install Quá trình cài đặt thành công ,GT4 sẽ được cài đặt vào thư mục /usr/local/globus-4.2.1 Lưu ý: nên thêm lệnh tạo biến môi trường GLOBUS_LOCALTION vào file /etc/profile để mỗi lần khởi động lại máy tính, biến trên được khởi tạo đồng thời. 4.1.3. Cấu hình các thành phần của globus toolkit 4.1.3.1. Cấu hình bảo mật  b.ar.com b.ar.com đóng vai trò làm server chứng thực, chúng ta cần cài đặt gói simpleCA đi kèm để quản lý các chứng chỉ điện tử. Đặt đường dẫn đến các lệnh của globus [globus@b~]$source $GLOBUS_LOCATION/etc/globus-user-env.sh Cài đặt simpleCA [globus@b~]$GLOBUS_LOCATION/setup/globus/setup-simple-ca Quá trình cài đặt thành công sẽ sinh ra 1 thư mục /home/.globus/simpleCA Tiếp theo, để b.ar.com tin tưởng tuyệt đối vào simpleCA vừa được tạo cần thực hiện lệnh sau với quyền người dùng root [root@b~]#$GLOBUS_LOCATION/setup/globus_simple_ca_ebb88ce5_s etup/setup-gsi -default Sau khi lệnh trên được thực hiện ,thư mục /etc/grid-sercurity được tạo ra Sau đó cần tạo chứng chỉ điện tử cho host b.ar.com và người dùng thinh 48 Máy b.ar.com gửi yêu cầu được CA ký [root@b~]#grid-cert-request -host `hostname` 1 file hostcert_request.pem được tạo ra nằm tại /etc/grid-sercurity Với quyền người dùng globus, thực hiện ký lên hostcert_request.pem để tạo ra chứng chỉ điện tử cho host b [globus@b~]grid-ca-sign –in /etc/grid- sercurity/hostcert_request.pem –out bcert.pem Copy file bcert.pem đè lên file hostcert.pem trong thư mục /etc/grid-sercurity Chứng chỉ điện tử cho host b đã được tạo Tạo chứng chỉ điện tử cho người dùng thinh Chuyển sang quyền người dùng thinh Gửi yêu cầu cần được CA ký [thinh@b~]$grid-cert-request 1 file usercert_request.pem được tạo ra tại thư mục /home/thinh/.globus/ Với quyền người dùng globus, tạo chứng chỉ điện tử cho người dùng thinh bằng việc ký lên usercert_request.pem [globus@b~]$grid-ca-sign –in /home/thinh/.globus/usercert.pem –out thinhcert.pem Người dùng thinh copy file thinhcert.pem đè lên file usercert.pem trong thư mục /home/thinh/.globus/ Quá trình tạo chứng chỉ điện tử cho người dùng thinh kết thúc. Lấy thông tin về người dùng thinh và đưa vào file grid-mapfile [thinh@b~]$ grid-cert-info –subject Ta được thông tin sau : /O=Grid/OU=GlobusTest/OU=simpleCA-b.ar.com/OU=ar.com/CN=Nguyen Thinh Tạo file /etc/grid-sercurity/grid-mapfile như sau : 49 "/O=Grid/OU=GlobusTest/OU=simpleCA-b.ar.com/OU=ar.com/CN=Nguyen Thinh" thinh  b1.ar.com, b2.ar.com, b4.ar.com Copy file globus_simple_ca_xxxx_setup-0.20.tar.gz (xxxx là một mã hash được sinh ra bất kỳ tùy theo từng máy ) từ máy b.ar.com bằng lệnh scp sang các máy b1, b2 ,b3, b4. [globus@b1~]$scp b.ar.com://home/globus/.globus/simpleCA/globus_simple_ca_xxx x_setup-0.20.tar.gz ./ Cài đặt gói vừa copy [globus@b1~]$$GLOBUS_LOCATION/sbin/gpt-built globus_simple_ca_384920d7_setup-0.20.tar.gz [globus@b1~]$$GLOBUS_LOCATION/sbin/gpt-postinstall Chuyển sang người dùng root, để máy tính b1, b2, b3, b4 tin tưởng CA, cần thực hiện lệnh [root@b1~]#$GLOBUS_LOCATION/setup/globus_simple_ca_ebb88ce5_ setup/setup-gsi -default Tạo chứng chỉ điện tử cho host b1, b2, b4 tương tự như với host b .Với quyền root , sử dụng lệnh [root@b1~]#grid-cert-request –host `hostname` File hostcert_request.pem được tạo ra trong thư mục /etc/grid-sercurity/, chuyển file này sang máy b, trên máy b, dùng tài khoản globus ký lên và tạo chứng chỉ điện tử. [globus@b~]$grid-ca-sign –in hostcert.pem –out hostbb1.pem Chuyển file hostb1.pem về máy b1, với tài khoản root trên b1, copy đè file này vào /etc/grid-sercurity/hostcert.pem. Tạo chứng chỉ điện tử cho người dùng thinh trên b1 tương tự như làm với host bằng cách sử dụng lệnh grid-cert-request với tài khoản thinh trên b1 và grid-ca-sign với tài khoản globus trên b. Sau đó, tạo một grid-mapfile trong thư mục /etc/grid-sercurity tương tự như trên máy b. 50 Các bước làm với máy b2, b4 cũng tương tự như các bước làm với máy b1. 4.1.3.2. Cấu hình dich vụ GridFTP Cho cả 4 máy b, b1, b2, b4 Với quyền người dùng root tạo file /etc/xinetd.d/gridftp có nội dung ------------------------------------------------------------ service gsiftp { instances = 100 socket_type = stream wait = no user = root env += GLOBUS_LOCATION=/usr/local/globus-4.2.1 env += LD_LIBRARY_PATH=/usr/local/globus-4.2.1/lib server = /usr/local/globus- 4.2.1/sbin/globus-gridftp-server server_args = -i log_on_success += DURATION disable = no } ------------------------------------------------------------ Thêm dòng gsiftp 2811/tcp vào file /etc/services [root@b~]#echo “gsiftp 2811/tcp” >> /etc/services 2 dòng lệnh trên cho phép dịch vụ /usr/local/globus-4.2.1/sbin/globus-gridftp-server luôn được chạy với cổng 2188 ,giao thức TCP 51 Khởi động lại dịch vụ xinetd [root@b~]#/etc/init.d/xinetd start [root@b~]#/etc/init.d/xinetd reload Kiểm tra xem dịch vụ đã chạy chưa ? [root@b~]#netstat –an | grep 2118 Kiểm tra gridFTP hoạt động hay chưa Với quyền người dùng thinh [thinh@b~]grid-proxy-init -verify –debug Nếu không gặp báo lỗi , thử kiểm tra bằng việc copy sau : [thinh@b~]globus-url-copy gsiftp://b.ar.com/etc/group /home/thinh/ Copy thành công tức là dịch vụ gridFTP đã hoạt động 4.1.3.3. Cấu hình gatekeeper Cho cả 4 máy b, b1, b2, b4 Tạo file /etc/xinetd.d/globus-gatekeeper với nội dung sau : ------------------------------------------------------------ service gsigatekeeper { socket_type = stream protocol = tcp wait = no user = root env = LD_LIBRARY_PATH=/usr/local/4.2.1/lib server = /usr/local/globus-4.2.1/sbin/globus- gatekeeper 52 server_args = -conf /usr/local/globus- 4.2.1/etc/globus-gatekeeper.conf disable = no env = GLOBUS_TCP_PORT_RANGE=40000,50000 } ------------------------------------------------------------ Thêm dòng gsigatekeeper 2119/tcp vào file /etc/service Khởi động lại dịch vụ xinetd. Kiểm tra xem dịch vụ hoạt động chưa bằng lệnh netstat 4.1.3.4. Cấu hình WS GRAM Cho cả 4 máy b, b1, b2, b4 Với quyền root ,dùng lệnh visudo thay đổi thông tin như sau : Chọn comment tại dòng # Defaults requiretty Thêm thông tin sau vào cuối file globus ALL=(thinh) NOPASSWD: /usr/local/globus- 4.2.1/libexec/globus-gridmap-and-execute -g /etc/grid- security/grid-mapfile /usr/local/globus- 4.2.1/libexec/globus-job-manager-script.pl * globus ALL=(thinh) NOPASSWD: /usr/local/globus- 4.2.1/libexec/globus-gridmap-and-execute -g /etc/grid- security/grid-mapfile /usr/local/globus- 4.2.1/libexec/globus-gram-local-proxy-tool * Dòng lệnh trên thêm vào file /etc/sudoer cho phép người dùng globus có quyền thực thi các file nằm tại thư mục riêng của user thinh, đảm bảo cho người dùng thinh có thể thực thi các các ứng dụng 53 Như vậy chúng ta đã cấu hình các thành phần của Globus toolkit để dảm bảo cho người dùng thinh có quyền thực thi các file thông qua cơ chế hoạt động của globus 4.2. Triển khai MPICH-G2 Thực hiện với cả 4 máy. Với quyền người dùng root, tạo thư mục /opt/mpich Cấp quyền sở hữu thư mục cho người dùng globus: [root@b~]#chown globus:globus /opt/mpich Download mã nguồn chương trình mpich từ trang chủ của mpich , mã nguồn có dạng mpich.tar.gz. Giải nén mã nguồn bằng công cụ tar [globus@b~]$tar xzvf mpich.tar.gz Thực hiện 3 bước cấu hình và kiểm tra môi trường cài đặt, biên dịch và cài đặt Kiểm tra môi trường cài đặt : [globus@b mpich-1.2.7-p1]$./configure –prefix=/opt/mpich – device=globus2:-flavor=gcc32dbg Thư mục chỉ định cài đặt là thư mục /opt/mpich, có cài đặt kết nối tới bộ công cụ globus toolkit. Tham số device=globus2 dùng để tại một công cụ kết nối mpich với globus toolkit Bước này thành công, tạo ra 1 makefile cho phép công cụ make tự động biên dịch chương trình. Biên dịch [globus@b mpich-1.2.7-p1]$make Cài đặt [globus@b mpich-1.2.7-p1]$make instal 54 Chương 5 : Chạy và đánh giá hiệu năng của hệ thống Grid Hệ thống Grid mini gồm 5 máy tính kết nối chúng ta vừa tạo được hoạt động như thế nào, có hiệu năng ra sao ? Trong chương này sẽ là phần thử nghiệm lần lượt 3 chương trình tính toán song song khác nhau với kích thước bài toán khác nhau để dánh giá hiệu năng của hệ thống Grid Các chương trình được sử dụng bao gồm : - Chương trình tính toán số PI - Chương trình giải hệ phương trình tuyến tính (HPTTT) - Chương trình giải bài toán quy hoạch tuyến tính (QHTT) 5.1. Giới thiệu về 3 bài toán sẽ đƣợc thử nghiệm 5.1.1. Tính toán số PI Hằng số Pi, được ký hiệu trong toán học là π, nó được xác định bởi chu vi đường tròn chia cho đường kính của đường tròn đó. Mục tiêu của chương trình là dùng giải thuật để tính toán số Pi với độ chính xác của phần thập phân cho trước. Mã nguồn của chương trình được đi kèm phần mềm MPICH 5.1.2. Hệ phƣơng trình tuyến tính Trong toán học (cụ thể là trong đại số tuyến tính), một hệ phƣơng trình đại số tuyến tính hay đơn giản là hệ phương trình tuyến tính là một tập hợp n phương trình tuyến tính với k biến số: 𝑎1,1𝑥1 + 𝑎1,2𝑥2 +⋯+ 𝑎1,𝑘𝑥𝑘 = 𝑏1 𝑎2,1𝑥1 + 𝑎2,2𝑥2 +⋯+ 𝑎2,𝑘𝑥𝑘 = 𝑏2 𝑎3,1𝑥1 + 𝑎3,2𝑥2 +⋯+ 𝑎3,𝑘𝑥𝑘 = 𝑏3 … 𝑎𝑛 ,1𝑥1 + 𝑎𝑛 ,2𝑥2 +⋯+ 𝑎𝑛 ,𝑘𝑥𝑘 = 𝑏𝑛 Hệ phương trình trên có thể được viết theo dạng phương trình ma trận: Ax=B 55 𝑎1,1 𝑎2,1 ⋮ 𝑎𝑛 ,1 𝑎1,2 𝑎2,2 ⋮ 𝑎𝑛 ,2 𝑎1,3 𝑎2,3 ⋮ 𝑎𝑛 ,3 …𝑎1,𝑘−1 𝑎1,𝑘 …𝑎2,𝑘−1 𝑎2,𝑘 ⋮ … 𝑎𝑛 ,𝑘−1 𝑎𝑛 ,𝑘 𝑥1 𝑥2 ⋮ 𝑥𝑘 = 𝑏1 𝑏2 ⋮ 𝑏𝑘 Mục tiêu của bài toán là tìm nghiệm x của hệ phương trình trên. Các trường hợp xảy ra đối với nghiệm của bài toán là: - Hệ không có nghiệm (vô nghiệm). - Hệ có duy nhất một nghiệm. - Hệ có vô số nghiệm. Kết quả chạy bài toán này sẽ được lấy ra tại thời điểm giải xong HPTTT đầu tiên có kích thước mlog x mlog khi giải bài toán QHTT. Lý do là trong giải thuật áp dụng với bài toán QHTT có 1 bước phải giải HPTTT. Giải thuật áp dụng trong bài toán QHTT sẽ được trình bày sau đây. 5.1.3. Bài toán quy hoạch tuyến tính Có thể tạm định nghĩa quy hoạch tuyến tính là lĩnh vực toán học nghiên cứu các bài toán tối ưu mà hàm mục tiêu (vấn đề được quan tâm) và các ràng buộc (điều kiện của bài toán) đều là hàm và các phương trình hoặc bất phương trình tuyến tính. Thuật toán được áp dụng ở đây là thuật toán Newton tổng quát dùng để giải bài toán quy hoạch tuyến tính dạng chuẩn sau đây :  * min , : , 0T n n x X f c x X x Ax b x       (P) Mục đích của bài toán: với các aij, bi là biết trước, cần tìm xj (j=0,1….,n) sao cho f là nhỏ nhất. Bài toán quy hoạch tuyến tính có tính ứng dụng rất cao trong công việc của các nhà tổ chức , thiết kế ki ̃thuâṭ , quản lí điều hành công việc , ... và ngày càng được ứng dụng rôṇg raĩ trong nhiều liñh vưc̣ khác nhau của cuôc̣ sống . Các lớp bài toán quy hoạch tuyến tính thông dụng hiện nay bao gồm bài toán lập kế hoạch, bài toán vận tải, bài toán túi xách, bài toán đóng gói, bài toán lập lịch biểu... Ngoài ra, có rất nhiều bài toán thực tế được mô hình hóa dưới dạng bài toán quy hoạch tuyến tính, ví dụ như các bài toán tìm 56 cấu trúc tối ưu của chuỗi sinh học, các mô hình môi trường thật, các bài toán cơ học hệ thống lớn, v.v.. Với khối lượng thông tin ngày càng tăng, các kích thước của các bài toán ứng dụng thực tế cũng ngày càng tăng, thế nên việc xử dụng các thuật toán truyền thống không đem lại kết quả mong đợi. Chính vì lý do này một thuật toán mới được đề ra cho phép giải các bài toán quy hoạch tuyến tính kích thước lớn (~ 106 biến, ~103 ràng buộc). Thuật toán này đã được thực hiện trên nền tảng tính toán song song sử dụng MPI. Thuật toán ban đầu sử dụng thuật toán gradient liên hợp, sau đó lấy kết quả và sử dụng tiếp thuật toán Newton tổng quát. Có 6 bước làm như sau : 1. Xác định dự đoán ban đầu 0x và 0 0,p p p . 2. Tính gradient ,( , , ) ( ) T k k s s k S G p x b A x A p c p         ở vòng lặp thứ k của phương pháp Newton để giải bài toán tối đa hóa không ràng buộc . Ở đây s là số thứ tự vòng lặp ngoài. 3. Xác định ma trận Hessian tổng quát cho (18) T k kH I AD A  ở đây A là ma trận m n , ma trận chéo n n kD  được xác định như sau 1 if ( ) 0 ( ) 0 if ( ) 0 T i ii s k k T i k k x A p c D x A p c            Như vậy ma trận m m kH  . 4. Hướng tối đa hóa xấpxỉ p được tìm như là nghiệm của hệ phương trình tuyến tính .k kH p G   Vì kH là ma trận dương, đối xứng và bán xác định nên chúng ta có thể dùng phương pháp gradient liên hợp có tiền điều kiện để giải phương trình tuyến tính (21). Phần chéo của ma trận kH được dùng như tiền điều kiện (preconditioner) cho các bước gradient liên hợp. 57 5. Xác định 1k k kp p p    , với k  là kích thước bước được chọn theo quy tắc Armijo: max ( , , )k k sS p p x    Trên thực tế tham số k được đặt bằng 1 trong tất cả các thí nghiệm tính toán. 6. Sai khi các vòng lặp trong hội tụ thì gán 1kp p  , tính 1 ( ) T s sx x A p c    , đặt 0p p và lặp lại các bước 2-6. 5.2. Cách thức chạy 1 bài toán trên hệ thống Grid đƣợc xây dựng bởi 2 công cụ Globus Toolkit và MPICH  Đăng nhập với người dùng của globus, cụ thể trong trường hợp này là người dùng thinh  Tạo một proxy chứng thực cho người dùng Grid-proxy-init  Biên dịch mã nguồn MPICH cung cấp các công cụ mpicc để biên dịch các bài toán được viết bằng ngôn ngữ C Ví dụ biên dịch một chương trình viết bằng ngôn ngữ C : program1.c mpicc –o program program.c  Tạo file Resource Specification Language (RSL) đặc tả công việc tính toán cho chương trình cần chạy RSL là một file scripts lưu trữ các thông tin chi tiết về môi trường tính toán cụ thể cho một chương trình : máy tính nào chạy chương trình, số lượng CPU được dùng để tính toán, lượng RAM được sử dụng, thời than thực thi chương trình. Cấu trúc cơ bản của 1 file RSL dùng để chạy 1 chương trình là như sau : + // Bắt đầu file là dấu + // Mỗi 1 máy tính chạy chương trình được đặc tả bằng các tham số nằm trong dấu “ ( )” 58 ( &(resourceManagerContact="b.ar.com") // Host được sử dụng để chạy chương trình (count=2) // Số lần chạy (label="subjob 0") // Nhãn của tiến trình phụ (environment=(GLOBUS_DUROC_SUBJOB_INDEX 0) // Môi trường thực thi của subjob (LD_LIBRARY_PATH /usr/local/globus-4.2.1/lib/)) // Đường dẫn đến thư viện GT (directory=/home/thinh/) // Thư mục chứa chương trình (executable=/home/thinh/cpi) // Đường dẫn đến chương trình cần thực thi trên host ) ( &(resourceManagerContact="b1.ar.com") (count=2) (label="subjob 1") (environment=(GLOBUS_DUROC_SUBJOB_INDEX 1) (LD_LIBRARY_PATH /usr/local/globus-4.2.1/lib/)) (directory=/home/thinh/) (executable=/home/thinh/cpi) ) ……  Sử dụng globusrun để chạy chương trình Globusrun –w –f file.rsl Globurun sẽ chịu trách nhiệm đọc nội dung file RSL và thực thi chương trình với những đặc tả đã nêu, kết quả chạy được hiển thị trên màn hình máy tính 59 5.3. Kết quả chạy các chƣơng trình và đánh giá kết quả 5.3.1. Kết quả chạy chƣơng trình tính số PI Số lƣợng máy 1 2 4 Thời gian 0.000083 0.003505 0.009917 Đánh giá : Đây là một bài toán rất nhỏ nên khi chương trình được thực thi, thời gian trao đổi giữa các host với nhau làm cho việc chạy trên nhiều máy mất nhiều hơn rất nhiều so với khi chạy trên 1 máy. 5.3.2. Kết quả chạy chƣơng trình giải hệ phƣơng trình tuyến tính Ma trận trong hệ phương trình có kích thước 2000x2000 Số lƣợng máy 1 2 4 Thời gian 90.6723 48.6365 27.2324 Đánh giá : Khi kích thước bài toán tăng lên rất nhiều lần ,thời gian thực thi chương trình trên 3 máy đã tốt hơn rõ rệt so với thực thi trên 1 máy. Cụ thể thời gian thực thi trên 4 máy đã giảm gần 3.3 lần so với khi thực thi trên trên 1 máy 60 5.3.3. Kết quả giải bài toán quy hoạch tuyến tính Kích thước bài toán được triển khai : 5000 biến và 1000 ràng buộc Số lƣợng máy 1 2 4 Thời gian 232.541 124.578s 69.4445 0 10 20 30 40 50 60 70 80 90 100 1 computer 2 computer 4 computer t (s) 61 Trong bài toán này, nền tảng Grid Computing lại một lần nữa thể hiện được những ưu điểm của mình trong việc giải những bài toán kích thước lớn. Nhưng có một vấn đề đó là độ sai số trong kết quả của bài toán. Có thể quan sát bảng kết quả dưới đây khi thực hiện bài toán quy hoạch tuyến tính để đánh giá. Bảng thể hiện kết quả tính toán khi thực hiện trên số lượng máy khác nhau lần lượt là 1, 2, 4 1 2 4 |Ax-b| 7.59468e+12 4.96612e+12 4.78923e+12 |(A^t u - c)_+| 1.97028e+08 2.76091e+08 2.09592e+08 |c^t x - b^t u| 3.72625e+12 3.6899e+12 6.06735e+12 Lấy kết quả khi thực hiện bài toán trên 1 máy làm chuẩn, từ đó có thể thấy, khi càng có nhiều máy tham gia mạng grid để tính toán, độ chênh lệch càng lớn. Đây cũng là một trong những điểm yếu của tính toán song song, thời gian thực hiện nhanh hơn nhưng 0 50 100 150 200 250 1 computer 2 computer 4 computer t (s) 62 đi kèm đó là độ chính xác giảm đi. Muốn giảm thiểu sai số cần phải tạo ra thuật toán song song giải quyết tốt vấn đề này. 5.3.4. Nhận xét chung Trong quá trình thực thi một chương trình chạy song song, có rất nhiều giao tiếp giữa các máy được xảy ra để có thể đưa đến kết quả cuối cùng, điều đấy có nghĩa là sẽ mất 1 khoảng thời gian nhất định cho những giao tiếp trên. Vì lý do đó, với bài toán có kích thước càng lớn thì hệ thống càng tỏ ra tối ưu hơn vì khi đó thời gian dành cho giao tiếp giữa các máy sẽ nhỏ hơn nhiều so với thời gian thực thi cả bài toán lớn. Qua đây, có thể thấy, với hệ thống đã được triển khai, công nghệ grid đã tỏ ra hiệu quả thực sự khi cần tính toán các bài toán có kích thước lớn. Càng nhiều máy tham gia, thời gian giải bài toán càng nhanh. Nhưng Grid cũng bộc lộ những khuyết điểm về khả năng sai số khi giải quyết các bài toán này, tuy nhiên đây là vấn đề có thể giải quyết được. 63 Kết luận Kết thúc khóa luận “giải hệ phương trình tuyến tính kích thước lớn trên nền tảng Grid computing”, những kết quả thu được bao gồm : 1. Lý thuyết  Khóa luận đã đề cập một cách tổng quan về khái niệm, kiến trúc cũng như lợi ích của một hệ thống Grid trong thực tế.  Chỉ ra những đặc điểm, kiến trúc của gói phần mềm Globus, một trong những gói phần mềm nổi tiếng để triển khai một hệ thống Grid  Chỉ ra những kiến thức chung về gói phần mềm MPICH, MPI, những bộ thư viện và công cụ để tạo ra một chương trình song song cũng như thực thi các chương trình đó.  Cơ chế làm việc kết hợp Globus toolkit và MPICH để chạy một bài toán song song trên một hệ thống Grid 2. Thực hành và kết quả  Cài đặt và cấu hình Globus Toolkit để xây dựng thành công một hệ thống Grid gồm 3 máy tính khác nhau.  Cấu hình và cài đặt thành công MPICH để kếp hợp với Globus Toolkit tạo thành một hệ thống Grid thực thi được những bài toán song song được viết bằng ngôn ngữ C kết hợp với MPI.  Thử nghiệm các bài toán : tính toán số PI, giải hệ phương trình tuyến tính kích cỡ lớn, giải bài toán quy hoạch tuyến tính kích thước lớn và chứng minh được hiệu năng của hệ thống Grid đã xây dựng được khi giải các bài toán lớn. Khóa luận sẽ đóng góp một phần giúp những người đi sau trong việc tìm hiểu Công nghệ Grid trong việc tính toán các bài toán kích thước lớn tiếp cận một cách nhanh chóng hơn và dễ dàng hơn.Hướng phát triển của khóa luận sẽ là tiến tới triên khai xây dựng hệ thống Grid trong môi trường thật, phục vụ trực tiếp cho các nhu cầu thực tế, cụ thể là một phòng, một đơn vị chuyên tính toán hiệu năng cao. 64 Tài liệu tham khảo  Tài liệu tiếng Việt [1] Nguyễn Mạnh Dũng,Nguyễn Đăng Thành – Đại học khoa học tự nhiên TP.Hồ Chí Minh: Tìm hiểu công nghệ Grid Computing và ứng dụng thử nghiệm trong bài toán quản trị mạng  Tài liệu tiếng nước ngoài [2] Ian Foster ,Carl Kesselman, Steven Tuecke : The Anatomy of the Grid Enabling Scalable Virtual Organizations [3] Ian Foster : Globus Toolkit Version 4: Software for Service-Oriented Systems www.globus.org [4] Nicholas T. Karonis, Brian Toonen and Ian Foster : MPICH-G2:A Grid-enabled implementation of the Message Passing Interface [5] William Gropp and Ewing Lusk : Installation and User’s Guide to MPICH, a Portable Implementation of MPI Version 1.2.7 The globus2 device for Grids [6] Ian Foster, Carl Kesselman, Gene Tsudik, Steven Tuecke, : A Security Architecture for Computational Grids, 5th ACM Conference on Computer and Communication Security, www.globus.org [7] Y.G. Evtushenko, V.A. Garanzha, A.I. Golikov, H.M. Nguyen : Parallel Implementation of Generalized Newton Method for Solving Large-Scale LP Problems [8] Website : [9] Website :