Đề tài 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

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Đức Thịnh 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 KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hƣớng dẫn: Tiến sĩ. Nguyễn Minh Hằng HÀ NỘI - 2010 Lời cảm ơn Trước hết là lời cảm ơn sâu sắc của em đến những người đã giúp đỡ em hoàn thành khóa luận tốt nghiệp này, một dấu mấu quan trọng trong cuộc đời và sự nghiệp của em. Em xin chân thành cảm ơn Khoa công nghệ thông tin trường đại học Công Nghệ - Đại học quốc gia Hà Nội đã tạo điều kiện cho em được thực hiện khóa luận này. Khóa luận sẽ không thể hoàn thành nếu thiếu sự chỉ bảo tận tình của TS.Nguyễn Minh Hằng, người đã định hướng, hỗ trợ em trong suốt thời gian 3 tháng thực hiện khóa luận. Em xin chân thành cảm ơn cô. Một lời cảm ơn từ đáy lòng con xin được gửi đến cha mẹ, những người đã nuôi nấng con thành người để được có ngày hôm nay. Em xin cảm ơn các quý thầy cô đã dạy dỗ em trong suốt 4 năm học ở nhà trường, cung cấp cho em những kiến thức quý báu để bước vào đời. Cảm ơn các bạn của tôi đã là những người động viên tinh thần cũng như ở bên tôi giúp đỡ tôi khi tôi gặp khó khăn. Thời gian 3 tháng vừa qua, mặc dù đã cố gắng để hoàn thành khóa luận một cách tốt nhất nhưng vẫn không thể tránh nổi những sai sót. Em xin kính mong nhận được sự góp ý cũng như chỉ bảo của quý thầy cô. Xin chân thành cảm ơn Sinh viên Nguyễn Đức Thịnh Mục lục Lời mở đầu ................................................................................................. 1 Tóm tắt khóa luận ....................................................................................... 3 Chương 1 : Tổng quan về công nghệ Grid Computing ............................. 4 1.1. Lịch sử phát triển của công nghệ Grid ............................................................ 4 1.2. Khái niệm ......................................................................................................... 5 1.3. Các kiểu tài nguyên của Grid ........................................................................... 6 1.3.1. Tài nguyên tính toán ............................................................................................ 6 1.3.2. Tài nguyên lưu trữ ............................................................................................... 6 1.3.3. Phương tiện liên lạc ............................................................................................. 6 1.3.4. Phần mềm, ứng dụng ........................................................................................... 7 1.3.5. Các thiết bị đặc biệt ............................................................................................. 7 1.4. Phân lọai các hệ thống Grid ............................................................................. 7 1.4.1. Grid Tính toán (Computation Grid) ..................................................................... 7 1.4.2. Grid Dữ liệu (Data Grid) ..................................................................................... 8 1.4.3. Scavenging Grid .................................................................................................. 8 1.5. Kiến trúc Grid .................................................................................................. 8 1.5.1. Bản chất Kiến trúc Grid ....................................................................................... 8 1.5.2. Chi tiết Kiến trúc Grid tổng quát ....................................................................... 10 1.5.2.1. Tầng Fabric .................................................................................................. 10 1.5.2.2. Tầng Connectivity ....................................................................................... 11 1.5.2.3. Tầng Resource ............................................................................................. 12 1.5.2.4. Tầng Collective ........................................................................................... 13 1.5.2.5. Tầng Application ......................................................................................... 13 1.6. Grid computing đem lại những lợi ích gì ? .................................................... 13 1.6.1. Khai thác tối đa tài nguyên xử lý ....................................................................... 13 1.6.2. Khả năng xử lý song song.................................................................................. 14 1.6.3. Chia sẽ tài nguyên ảo và tổ chức ảo .................................................................. 14 1.6.4. Sự truy cập đến các tài nguyên khác.................................................................. 14 1.6.5. Cân bằng tài nguyên .......................................................................................... 15 1.6.6. Độ tin cậy ........................................................................................................... 16 Chương 2: Globus Toolkit 4 .................................................................... 17 2.1. Khái niệm về Globus ...................................................................................... 17 2.2. Nguyên nhân thúc đẩy sự phát triển của Globus ........................................... 18 2.3. Kiến trúc Globus ............................................................................................ 19 2.3.1. Các thành phần thường trực ............................................................................... 19 2.3.1.1. Java WS Core .............................................................................................. 19 2.3.1.2. C WS Core ................................................................................................... 19 2.3.2. Các thành phần bảo mật ................................................................................. 19 2.3.2.1. Cơ bản về bảo mật Grid và GSI .................................................................. 20 2.3.3. Các thành phần quản lý dữ liệu ......................................................................... 25 2.3.3.1. GridFTP ....................................................................................................... 25 2.3.3.2. Information services .................................................................................... 26 2.3.3.3. Index Service ............................................................................................... 27 2.3.4. Các thành phần quản lý tài nguyên .................................................................... 27 2.3.4.1. Kiến trúc quản lý tài nguyên của Globus Toolkit ....................................... 27 2.3.4.2. Chi tiết các thành phần ................................................................................ 29 2.3.4.2.1. GRAM ................................................................................................... 29 2.3.4.2.2. Pre-WS GRAM ..................................................................................... 32 2.3.4.2.3. WS-GRAM ........................................................................................... 34 Chương 3 : MPICH và MPICH-G2 ......................................................... 40 3.1. MPI ................................................................................................................. 40 3.2. MPICH ........................................................................................................... 41 3.3. MPICH-G2 ..................................................................................................... 41 3.3.1. Quá trình thực thi một ứng dụng ....................................................................... 42 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 .................. 44 4.1. Triển khai Globus Toolkit .............................................................................. 44 4.1.1. Chuẩn bị về phần cứng và phần mềm hệ thống ................................................. 44 4.1.2. Cài đặt Globus Toolkit ....................................................................................... 45 4.1.3. Cấu hình các thành phần của globus toolkit ...................................................... 47 4.1.3.1. Cấu hình bảo mật ......................................................................................... 47 4.1.3.2. Cấu hình dich vụ GridFTP .......................................................................... 50 4.1.3.3. Cấu hình gatekeeper .................................................................................... 51 4.1.3.4. Cấu hình WS GRAM .................................................................................. 52 4.2. Triển khai MPICH-G2 ................................................................................... 53 Chương 5 : Chạy và đánh giá hiệu năng của hệ thống Grid .................... 54 5.1. Giới thiệu về 3 bài toán sẽ được thử nghiệm ................................................. 54 5.1.1. Tính toán số PI ................................................................................................... 54 5.1.2. Hệ phương trình tuyến tính ................................................................................ 54 5.1.3. Bài toán quy hoạch tuyến tính ........................................................................... 55 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 .................................................................................... 57 5.3. Kết quả chạy các chương trình và đánh giá kết quả ...................................... 59 5.3.1. Kết quả chạy chương trình tính số PI ................................................................ 59 5.3.2. Kết quả chạy chương trình giải hệ phương trình tuyến tính .............................. 59 5.3.3. Kết quả giải bài toán quy hoạch tuyến tính ....................................................... 60 5.3.4. Nhận xét chung .................................................................................................. 62 Kết luận .................................................................................................... 63 Tài liệu tham khảo .................................................................................... 64 1 Lời mở đầu Trong thập niên qua, nền công nghệ thông tin thế giới phát triển đã đóng góp rất nhiều vào sự phát triển chung của thế giới. Chúng ta có thể bắt gặp những ứng dụng của công nghệ thông tin ở khắp mọi nơi, giờ đây nhiều người sở hữu máy tính cá nhân, sở hữu những chiếc điện thoại, cập nhập thông tin qua những trang web, kết nối với nhau qua những phần mềm chat… Đấy là những thứ hiện hữu hàng ngày mà chúng ta trực tiếp sờ thấy và sử dụng nó, ẩn sau nó là những nghiên cứu, những công nghệ được rất nhiều nhà khoa học cũng như phát triển trên thế giới nghiên cứu để đóng góp vào sự phát triển của nền công nghệ thông tin nói riêng và nền khoa học thế giới nói chung. Khi nói đến máy tính, một khái niệm hay được nhắc đến là những chiếc máy tính để bàn nhỏ gọn hay những chiếc laptop cá nhân. Nhưng đó là những thiết bị cá nhân giúp chúng ta giải trí, làm việc, còn với những chiếc máy tính phải xử lý lượng dữ liệu từ khắp nơi trên thế giới một cách thường xuyên và liên tục thì sao. Khi đó ,chúng ta lại được bắt gặp khái niệm siêu máy tính (Super Computer) . Những siêu máy tính trên thế giới được xây dựng rất đắt tiền với hàng trăm ngàn hay hàng triệu bộ vi xử lý, để đầu tư cho những hệ thống máy như vậy tốn rất nhiều tiền của cho việc triển khai cũng như bảo dưỡng, với mục đích sử dụng kết nối những người dùng hay tổ chức có chung một mục đích xử lý hay tận dụng tài nguyên máy tính của bất kỳ người dùng máy tính nào để tạo thành một hệ thống mạnh mẽ phục vụ cho việc giải các bài toán về khoa học, thương mại, một lĩnh vực nghiên cứu mới được đưa ra, đó là Grid Computing. Nói một cách tống quát nhất Grid là một loại hệ thống phân tán, bố trí song song, cho phép linh hoạt chia sẻ, tuyển lựa và tập hợp các nguồn tài nguyên độc lập và rải rác về địa lý, tùy theo khả năng sẵn có, công suất, hoạt động, chi phí và yêu cầu về chất lượng dịch vụ của người sử dụng. Grid Computing có rất nhiều ưu điểm mà có thể áp dụng cho việc nghiên cứu cũng như những ưu điểm có thể áp dụng cho doanh nghiệp. Trên thế giới, ý tưởng về Grid Computing đã được hình thành và nghiên cứu từ rất lâu nhưng thực sự bùng nổ vào vài năm trở lại đây khi được các tổ chức cũng như tập đoàn lớn trên thế giới nghiên cứu và triển khai. Tại Việt Nam, công việc nghiên cứu Grid Computing đã được triển khai từ khá lâu và gần đây nhất là đề tài cấp nhà nước “Nghiên cứu, phát triển hệ thống tính toán lưới để hỗ trợ giải quyết các bài toán có khối lượng tính 2 toán lớn (VNGrid)” do PGS.TS. Vũ Đức Thi làm chủ nhiệm cũng đã đạt được một số thành tựu nhất định. Nhận thấy Grid computing là một hướng nghiên cứu đang rất được quan tâm tại ở Việt Nam cũng như thế giới và những lợi ích to lớn mà nó mang lại. Em quyết định chọn đề tài “Giải 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” với mục đích là tìm hiểu Công nghệ Grid là gì ,những khái niệm và đặc điểm liên quan, thí nghiệm tạo một hệ thống Grid nhỏ bằng gói phần mềm GLOBUS TOOLKIT cùng MPICH-G2 để kiểm nghiệm hiệu năng của hệ thống grid khi chạy bài toán Giải hệ phương trình tuyến tính kích thước lớn. 3 Tóm tắt khóa luận 1. Thông tin chung về khóa luận Tên đề tài : Giải hệ phương trình tuyến tính trên nền tảng Grid Computing Giảng viên hướng dẫn : TS.Nguyễn Minh Hằng Sinh viên thực hiện : Nguyễn Đức Thịnh 2. Tóm tắt nội dung khóa luận Khóa luận thực hiện nghiên cứu tìm hiểu các vấn đề chung của công nghệ Grid về mặt khái niệm, kiến trúc của một hệ thống Grid và những ích lợi của Grid mang lại. Cung cấp một cái nhìn tổng quan về Grid. Tìm hiểu mô hình hoạt động của gói phần mềm Globus Toolkit, một gói phần mềm giúp xây dựng một hệ thống Grid, các vấn đề khi thực hiện triển khai tạo dựng một hệ thống Grid với Globus Toolkit. Tìm hiểu về MPICH, MPICH-G2, nguyên tắc hoạt động của MPICH kết hợp với Globus Toolkit để tạo dựng hệ thống Grid phục vụ việc tính toán song song sử dụng ngôn ngữ C và MPI. Thử nghiệm bài toán giải hệ phương trình tuyến tính theo thuật toán song song trên một hệ thống Grid để xem cách thức hoạt động và ưu điểm về khả năng kết hợp xử lý giữa các máy tính khác nhau. 3. Các công cụ đƣợc sử dụng triển khai và thử nghiệm  Globus Toolkit 4.2.1  Centos 5.4  MPICH-1.2.7 4 Chương 1 : Tổng quan về công nghệ Grid Computing 1.1. Lịch sử phát triển của công nghệ Grid Trong những năm gần đây, chúng ta được nghe nhiều đến công nghệ Grid và những ưu điểm của nó. Vậy Grid xuất hiện từ khi nào, từ bao giờ ? Trong quá khứ, những ý tưởng tính toán có liên quan đến Grid đã xuất hiện, với những tên gọi khác nhau và cách tiếp cận khác nhau. Ví dụ như ý tưởng “chia sẻ năng lực tính toán” đã xuất hiện từ những năm 60-70 của thế kỷ XX, lúc đó toàn bộ năng lực tính toán được chia sẻ từ các máy mainframe. Năm 1965, những người phát triển hệ điều hành Multics (tiền thân của hệ điều hành Unix) đã đề cập đến việc sử dụng năng lực tính toán như là một tiện ích, một quan điểm rất gần với quan điểm về Grid hiện nay. Đó là một hệ thống cung cấp năng lực tính toán tương tự như hệ thống cung cấp điện, nước hiện đang được sử dụng trong cuộc sống hàng ngày. Người dùng khi muốn sử dụng tài nguyên tính toán để xử lý công việc, chỉ cần cắm thiết bị vào hệ thống cung cấp, sử dụng và trả tiền giống như khi cắm thiết bị điện vào lưới điện. Tuy trước đó đã có nhiều ý tưởng về Grid nhưng nguồn gốc của Grid chính thức được xác định vào năm 1990, khi thuật ngữ “siêu tính toán” (metacomputing) ra đời, dùng để mô tả các dự án kết nối các trung tâm siêu máy tính của Mỹ nhằm kết hợp sức mạnh xử lý của nhiều siêu máy tính lại với nhau. Đến năm 1995, 2 dự án siêu tính toán quan trọng, ảnh hưởng lớn đến các công nghệ nền tảng trong các dự án Grid ngày nay là FAFNER (Factoring via Network- Enabled Recursion) và I-WAY(Information Wide Area Year) ra đời. Khái niệm Grid ra đời ở phòng thí nghiệm Argonne National Laboratory vào tháng 7/1997, sau đó được đưa vào quyển sách "The Grid: Blueprint for a New Computing Infrastructure" viết bởi tiến sỹ Ian Foster (Argonne National Laboratory) và Carl Kesselman (University of Southern California) năm 1998. Ian Foster đã từng tham gia dự án I-WAY, Carl Kesselman là người tham gia dự án Globus Toolkit, một dự án nền tảng của công nghệ Grid và Metacomputing. 5 Từ đó đến nay, việc phát triển công nghệ Grid trở nên rất sôi động với sự tham gia nghiên cứu, đầu tư của nhiều tổ chức, tập đoàn công nghệ thông tin, nhiều quốc gia, và đã thu được những thành tựu bước đầu. Có thể nói, việc phát triển và xây dựng hệ thống Grid là sự kế thừa và phát triển các ý tưởng, các công nghệ hiện hành ở mức cao hơn. Sự phát triển không ngừng của cơ sở hạ tầng, phần cứng máy tính, mạng đã giúp các hệ thống Grid ngày nay thực hiện được nhiều điều hơn những ý tưởng trước đây. 1.2. Khái niệm Một định nghĩa về Grid khá hoàn chỉnh được đưa ra bởi tiến sỹ Ian Foster như sau “Grid là một loại hệ thống song song, phân tán cho phép chia sẻ, lựa chọn, kết hợp các tài nguyên phân tán theo địa lý, thuộc nhiều tổ chức khác nhau dựa trên tính sẵn sàng, khả năng, chi phí của chúng và yêu cầu về chất lượng dịch vụ (QoS) của người dùng để giải quyết các bài toán, ứng dụng có quy mô lớn trong khoa học, kỹ thuật và thương mại. Từ đó hình thành nên các “tổ chức ảo” (Virtual Organization (VO)), các liên minh tạm thời giữa các tổ chức và tập đoàn, liên kết với nhau để chia sẻ tài nguyên và/hoặc kỹ năng nhằm đáp ứng tốt hơn các cơ hội kinh doanh hoặc các dự án có nhu cầu lớn về tính toán và dữ liệu, toàn bộ việc liên minh này dựa trên các mạng máy tính” Một hệ thống Grid có những đặc trưng như sau:  Có sự kết hợp, chia sẻ các tài nguyên không được quản lý tập trung Grid tích hợp và phối hợp tài nguyên, người dùng thuộc nhiều vùng quản lý khác nhau, nhiều đơn vị khác nhau trong một tổ chức, hay nhiều tổ chức khác nhau. Công nghệ Grid tập trung giải quyết các vấn đề về bảo mật, chính sách quản trị, chi phí, thành viên,… nảy sinh trong quá trình chia sẻ và sử dụng tài nguyên.  Sử dụng các giao diện và giao thức chuẩn, mang tính mở, đa dụng. Grid được xây dựng trên các giao thức và giao diện tổng quát, đa dụng để giải quyết các vấn đề cơ bản như chứng thực người dùng, phân quyền, tìm kiếm và truy xuất tài nguyên.  Đáp ứng yêu cầu cao về chất lượng dịch vụ. Grid cho phép sử dụng phối hợp các tài nguyên để cung cấp nhiều loại dịch vụ với các mức chất lượng khác nhau, liên quan đến ví dụ như thời gian đáp ứng, hiệu suất, tính sẵn sàng, bảo mật, cho phép kết hợp nhiều kiểu tài nguyên để đáp ứng nhu cầu phức tạp của người dùng. Mục tiêu là phải phối hợp làm sao để khả năng của hệ thống sau khi kết hợp phải lớn hơn hẳn tổng khả năng của từng đơn vị cấu thành nên Grid. 6 1.3. Các kiểu tài nguyên của Grid 1.3.1. Tài nguyên tính toán Đây là tài nguyên phổ biến nhất, là các chu kỳ tính toán (computing cycles) được cung cấp bởi bộ vi xử lý của các thiết bị trong Grid. Các bộ vi xử lý không cần phải cùng loại mà có thể có tốc độ, kiến trúc, chạy phần mềm khác nhau. Có 3 cách để khai thác tài nguyên tính toán của Grid: 1. Cách đơn giản nhất là chạy các ứng dụng hiện có trên một node của Grid thay vì chạy trên máy tính cục bộ. 2. Thiết kế ứng dụng, tách các công việc thành các phần riêng rẽ để có thể thực thi song song trên nh