Tài liệu Mô hình tính toán lưới và ứng dụng giải một số bài toán trên đồ thị

ĐẠI HỌC THÁI NGUYÊN ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Hà Thị Thúy MÔ HÌNH TÍNH TOÁN LƢỚI VÀ ỨNG DỤNG GIẢI MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2013 ĐẠI HỌC THÁI NGUYÊN ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG HÀ THỊ THUÝ MÔ HÌNH TÍNH TOÁN LƢỚI VÀ ỨNG DỤNG GIẢI MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ Chuyên ngành : Khoa học máy tính Mã số : 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS ĐOÀN VĂN BAN Soá hoùa bôûi Trung taâm Hoïc lieäu Thái Nguyên - 2013 http://lrc.tnu.edu.vn/ LỜI CAM ĐOAN Tôi xin cam đoan những kiến thức trình bày trong luận văn này là do tôi tìm hiểu, nghiên cứu và trình bày lại theo cách hiểu của tôi. Trong quá trình làm luận văn tôi có tham khảo các tài liệu có liên quan và đã ghi rõ nguồn tài liệu tham khảo đó. Phần lớn những kiến thức tôi trình bày trong luận văn này chưa được trình bày hoàn chỉnh trong bất cứ tài liệu nào. Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ LỜI CẢM ƠN Lời đầu tiên, tôi xin gửi lời cảm ơn chân thành và biết ơn sâu sắc nhất tới PGS.TS. Đoàn Văn Ban, người thầy đã chỉ bảo và hướng dẫn tận tình cho tôi trong suốt quá trình nghiên cứu khoa học và thực hiện luận văn này. Tôi xin chân thành cảm ơn các thầy cô giáo, cán bộ thuộc phòng Khoa học và Đào tạo, Trường Đại học Công nghệ thông tin & Truyền thông Thái Nguyên, đã tạo điều kiện thuận lợi giúp đỡ tôi trong quá trình học tập và nghiên cứu. Và cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, người thân và bạn bè - đồng nghiệp - những người đã luôn bên cạnh tôi những lúc khó khăn nhất, động viên và khích lệ tôi trong cuộc sống và trong công việc. Tôi xin chân thành cảm ơn! Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ MỤC LỤC LỜI CAM ĐOAN ........................................................................................................................ LỜI CẢM ƠN............................................................................................................................ .. MỤC LỤC ................................................................................................................................... DANH MỤC TỪ VIẾT TẮT ..................................................................................................... DANH MỤC HÌNH VẼ .............................................................................................................. LỜI MỞ ĐẦU............................................................................................................................ 1 CHƢƠNG 1. GIỚI THIỆU VỀ CÔNG NGHỆ TÍNH TOÁN LƢỚI ................................. 2 1.1 Giới thiệu về mô hình tính toán lưới ...................................................................... 2 1.1.1 Quá trình phát triển của tính toán lưới ............................................................ 2 1.1.2 Khái niệm tính toán lưới .................................................................................. 4 1.1.3 Lợi ích của tính toán lưới................................................................................. 6 1.1.4 Các dạng tài nguyên trên lưới .......................................................................... 9 1.1.5 So sánh tính toán lưới với các công nghệ khác ............................................. 12 1.2 Phân loại lưới........................................................................................................ 15 1.2.1 Lưới phòng ban (Departmental Grids) .......................................................... 15 1.2.2 Lưới doanh nghiệp (Enterprise Grids) ........................................................... 16 1.2.3 Lưới toàn cầu (Global Grids)......................................................................... 16 1.2.4 Lưới tính toán (Compute Grids) .................................................................... 17 1.2.5 Lưới dữ liệu (Data Grids) .............................................................................. 17 1.2.6 Lưới tiện ích (Utility Grids)........................................................................... 18 1.3 Vấn đề an toàn thông tin và những thách thức đối với tính toán lưới .................. 18 1.3.1 An toàn thông tin trong tính toán lưới ........................................................... 18 1.3.2 Những thách thức với một lưới...................................................................... 20 1.4 Kết luận ................................................................................................................ 20 CHƢƠNG 2. PHÁT TRIỂN ỨNG DỤNG TRÊN MÔI TRƢỜNG TÍNH TOÁN LƢỚI 22 2.1 Cơ sở hạ tầng lưới ................................................................................................ 22 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 2.1.1 Portal/Giao diện người dùng.......................................................................... 22 2.1.2 An toàn và bảo mật (Security) ....................................................................... 23 2.1.3 Bộ môi giới tài nguyên (Broker).................................................................... 23 2.1.4 Bộ lập lịch (scheduler) ................................................................................... 23 2.1.5 Thành phần quản lý dữ liệu (Data management)........................................... 24 2.1.6 Thành phần quản lý công việc và tài nguyên (Job and resource management) ................................................................................................................................ 24 2.1.7 Các thành phần khác ...................................................................................... 24 2.2 Kiến trúc của một lưới .......................................................................................... 25 2.2.1 Bản chất kiến trúc .......................................................................................... 25 2.2.2 Kiến trúc lưới tổng quát ................................................................................. 27 2.2.3 Các chuẩn đối với tính toán lưới.................................................................... 32 2.3 Một số môi trường và công cụ hỗ trợ tính toán lưới ............................................ 38 2.3.1 Alchemi .......................................................................................................... 39 2.3.2 Globus ............................................................................................................ 40 2.3.3 Legion ............................................................................................................ 47 2.3.4 UNICORE...................................................................................................... 48 2.4 Các vấn đề khi lập trình trên lưới ......................................................................... 51 2.4.1 Các yêu cầu đối với lập trình trên lưới .......................................................... 51 2.4.2 Các vấn đề cần quan tâm khi lập trình trên lưới ............................................ 53 2.5 Kết luận ................................................................................................................ 60 CHƢƠNG 3. GIẢI MỘT SỐ BÀI TOÁN ĐỒ THỊ TRÊN MÔI TRƢỜNG LƢỚI ......... 61 3.1 Các khái niệm cơ bản ........................................................................................... 61 3.1.1 Đồ thị ............................................................................................................. 61 3.1.2 Đường đi ........................................................................................................ 62 3.2 Thuật toán Dijkstra ............................................................................................... 63 3.2.1 Thuật toán tuần tự .............................................................................................. 63 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ 3.2.2 Song song thuật toán Dijkstra trên lưới ......................................................... 63 3.2.3 Thực nghiệm chương trình ............................................................................ 64 3.3 Thuật toán tô mầu đồ thị....................................................................................... 66 3.3.1 Thuật toán tuần tự .......................................................................................... 67 3.3.2 Song song trên lưới ........................................................................................ 67 3.3.3 Thực nghiệm chương trình ............................................................................ 68 3. 4 Kết luận ............................................................................................................... 70 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ............................................................................. 71 TÀI LIỆU THAM KHẢO ...................................................................................................... 73 Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ DANH MỤC TỪ VIẾT TẮT Viết tắt Tên đầy đủ Chú giải API Application Programming Interface Giao diện lập trình ứng dụng CMM Common Management Model Quản lý chung mẫu CORBA Common Object Request Broker Architecture Yêu cầu chung kiến trúc đối tượng môi giới CPU Center Processing Unit Bộ xử lý trung tâm DAP Directory Access Protocol Giao thức đặc tả các kỹ thuật định danh đối tượng, tìm kiếm và ghi các khoản mục dữ liệu DCOM Digital Computer Thiết bị không dây DNS Domain Name System Hệ thống phân giải tên miền FTP File Transfer Protocol Giao thức truyền tệp qua mạng TCP GGF Global Grid Forum Diễn đàn lưới toàn cầu GRAM Globus Resource Allocation Management GridFTP Grid File Transfer Protocol Dịch vụ quản lý và định vị tài nguyên lưới GridFTP là mở rộng của giao thức FTP, tích hợp khả năng bảo mật lưới, truyền dữ liệu tốt hơn so với FTP GSH Grid Service Handle Lưới dịch vụ xử lý GSR Grid Service Reference Lưới dịch vụ tham khảo GSS-API Generic Security Service Application Program Interface Giao diện lập trình ứng dụng dịch vụ bảo mật chung Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ GT Globus Toolkit Bộ công cụ được phát triển bởi Globus Alliance, dùng đê phát triên các ứng dụng lưới GTCP Grid Telecontrol Protocol Giao thức điều khiển lưới từ xa GUI Graphical User Interface Giao diện người dùng đồ họa HPC High Performance Computing Tính toán hiệu năng cao HTML Hyper Text Markup Language Ngôn ngữ hiển thị siêu văn bản HTTP Hyper Text Transfer Protocol Giao thức truyền siêu văn bản tập đoàn công nghệ máy tính đa quốc gia có trụ sở tại Armonk, New York, Mỹ Giao thức điều khiển truyền tin trên mạng IBM International Business Machines ICMP Internetwork Control Message Protocol IDB Installation Database Thông số cần khai báo về cơ sở dữ liệu IP Internet Protocal Giao thức Internet IT Information Technology Công nghệ thông tin J2EE Java 2 Enterprise Edittion Java doanh nghiệp phiên bản 2 JMC Job Monitor Component Cấu tạo màn hình công việc LAN Local Area Network Mạng cục bộ MDS Monitoring and Discovery Service Giám sát dịch vụ NCSA National computer security association Hiệp hội an ninh máy tính quốc gia Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ NET Network Mạng lưới NFS National Science Foundation Quỹ khoa học quốc gia NJS Network Job Supervisors Mạng lưới giám sát công việc OGSA Open Grid Service Architecture Kiến trúc dịch vụ lưới OGSI Open Grid Service Infrastructure Hạ tầng dịch vụ lưới mở OSPF Open Shortest Path First Giao thức tìm đường ngắn nhất đầu tiên PC Personal Computer Máy tính cá nhân PU Processing Unit Đơn vị xử lý PVM Parallel Virtual Machine Song song máy ảo QoS Quality of Service Chất lượng dịch vụ RFT Reliable File TransferService Dịch vụ truyền file tin cậy RLS Replica Location Service Dịch vụ định vị bản sao trong kiến trúc lưới dữ liệu Globus, cho phép xác định vị trí của các bản sao của thực thể dữ liệu trong lưới. RMI Remote Method Invocation Gọi phương thức từ xa RPC Remote Procedure Call Lời gọi hàm xa SAML Security Assertion Markup Language Ngôn ngữ đánh dấu liên kết an toàn SDK Software Development Kit Tập công cụ hỗ trợ phát triển phần mềm Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ SOAP Simple Object Acess Protocol Giao thức truy cập đối tượng đơn giản SSL Secure Socket Layer Giao thức bảo mật lưới TCP Transmission Control Protocol Giao thức Điều khiển Giao vận TLS Transport Layer Security Giao thức bảo mật tầng giao vận UDP User Datagram Protocol Giao thức sử dụng gói VO Virtual Organizations Các tổ chức ảo VPN Virtual Private Networks Mạng riêng ảo WAN Wide Area Network Mạng diện rộng WS Web Service Dịch vụ web WSDL Web Service Deployment Descriptor Language Ngôn ngữ đặc tả dịch vụ web WSIL WS- Inspection Language Dịch vụ web kiểm tra ngôn ngữ WSRF Web Services Resource Framework Framework đưa ra bởi GT4 hỗ trợ kiến trúc lập trình mới WWW World Wide Web Mạng lưới toàn cầu Extensible Markup Language Là một cách thức linh động để tạo ra các định dạng thông tin và chia sẻ cả định dạng và dữ liệu trên web XML Soá hoùa bôûi Trung taâm Hoïc lieäu http://lrc.tnu.edu.vn/ DANH MỤC HÌNH VẼ Trang Hình 1.1 Hình 1.2 Mô hình tính toán lưới Tài nguyên lưới dưới quan điểm của người dùng là một khối thống nhất có được nhờ sự ảo hoá. 5 12 Hình 2.1 Kiến trúc lưới tổng quát 27 Hình 2.2 Mối quan hệ giữa OGSA và OGSI 33 Hình 2.3 Kiến trúc của Alchemi 40 Hình 2.4 Mô hình hệ thống hướng dịch vụ web 41 Hình 2.5 Mô hình kiến trúc hoạt động của UNICORE 49 Hình 3.1 Cung (u, v) 61 Hình 3.2 Cạnh (u, v) 61 Hình 3.3 Biểu diễn khuyên 61 Hình 3.4 Đồ thị G cho trước 62 Hình 3.5 Giao diện chương trình trên máy server - thuật toán Dijkstra 65 Hình 3.6 Hướng dẫn sử dụng các chức năng chính 65 Hình 3.7 Giao diện chương trình trên client - thuật toán Dijkstra 66 Hình 3.8 Hình 3.9 Giao diện chương trình trên máy server - thuật toán tô màu đồ thị Giao diện chương trình trên client - thuật toán tô màu đồ thị 69 69 1 LỜI MỞ ĐẦU Nhân loại ngày nay đang chứng kiến sự phát triển mạnh mẽ của ngành Công nghệ Thông tin, một trong những ngành mũi nhọn của nhiều quốc gia trên thế giới. Sự phát triển vượt bậc đó là kết quả tất yếu của sự phát triển kèm theo các thiết bị phần cứng cũng như phần mềm tiện ích. Sự phát triển đó đã kéo theo rất nhiều các ngành khác phát triển theo, trong đó có lĩnh vực nghiên cứu khoa học. Tuy công nghệ ngày càng phát triển, tốc độ xử lý các thiết bị cũng không ngừng tăng cao, nhưng nhu cầu tính toán của con người là không giới hạn, vì thế tính toán lưới đã ra đời nhằm đáp ứng nhu cầu này. Công nghệ tính toán lưới ra đời đánh dấu một bước phát triển mới .Trong lĩnh vực điện toán hiệu năng cao. Nó cho phép tận dụng năng lực xử lý, lưu trữ cùng các tài nguyên nhàn rỗi khác để cung cấp một môi trường tính toán có năng lực xử lý lớn, khả năng lưu trữ dồi dào để giải quyết các bài toán phức tạp - khó có thể giải quyết được với các công nghệ hiện hành hoặc giải quyết được nhưng với chi phí rất cao trong khoa học, thương mại. Tính toán lưới giúp tận dụng tối đa tài nguyên, tăng cường hợp tác, giảm chi phí đầu tư trong khi vẫn cung cấp năng lực tính toán như mong muốn. Hiện nay, đất nước ta đang thực hiện công cuộc công nghiệp hoá, hiện đại hóa, trong đó việc rút ngắn sự tụt hậu, phát triển về khoa học công nghệ là yếu tố then chốt quyết định đến thành công của công cuộc đổi mới. Cấu trúc của luận văn bao gồm các mục sau: Chƣơng 1: Giới thiệu về công nghệ tính toán lưới Chƣơng 2: Phát triển ứng dụng trên môi trường tính toán lưới Chƣơng 3: Giải một số bài toán đồ thị trên môi trường lưới Kết luận, hƣớng phát triển và tài liệu tham khảo được trình bày ở phần cuối của luận văn. 2 CHƢƠNG 1. GIỚI THIỆU VỀ CÔNG NGHỆ TÍNH TOÁN LƢỚI 1.1 Giới thiệu về mô hình tính toán lƣới 1.1.1 Quá trình phát triển của tính toán lưới Cũng như các công nghệ tính toán khác, tính toán lưới (Grid Computing) ra đời xuất phát từ nhu cầu tính toán của con người. Thực tế, ngày càng có nhiều bài toán phức tạp hơn được đặt ra và do đó các tổ chức cũng cần phải có những năng lực tính toán mạnh mẽ hơn. Có thể giải quyết vấn đề này bằng hai cách [1]: Một là: Đầu tư thêm trang thiết bị, cơ sở hạ tầng tính toán (mua thêm máy chủ, máy trạm, siêu máy tính, cụm máy tính (cluster), ...). Hai là: Phân bố lại hợp lý các nguồn tài nguyên trong tổ chức hoặc thuê thêm các nguồn tài nguyên từ bên ngoài (dĩ nhiên là với chi phí rẻ hơn nhiều so với việc đầu tư cho cơ sở hạ tầng tính toán). Cách giải quyết thứ hai này chính là mục tiêu và nguồn gốc yêu cầu cho sự hình thành của tính toán lưới. Các nhà khoa học tại Argone National Laboratory thuộc đại học Chicago (Mỹ) là những người đầu tiên đề xuất ý tưởng về tính toán lưới. Tính toán lưới hướng đến việc chia sẻ và sử dụng hiệu quả các nguồn tài nguyên thuộc về nhiều tổ chức trên một quy mô rộng lớn (thậm chí là quy mô toàn cầu). Chính công nghệ mạng và truyền thông phát triển mạnh mẽ trong những năm qua đã biến những khả năng này dần trở thành hiện thực. Các nghiên cứu về tính toán lưới đã và đang được tiến hành nhằm tạo ra một cơ sở hạ tầng lưới cho phép dễ dàng chia sẻ và quản lý các tài nguyên đa dạng và phân tán trong môi trường lưới. Giống như Internet, khái niệm lưới (Grid) đã phát triển từ những nhu cầu về tính toán khoa học lớn. Internet được phát triển để thoả mãn nhu cầu về một phương tiện liên lạc giữa các trung tâm tính toán lớn do liên bang đầu tư. Những sự liên kết này dẫn tới việc chia sẻ tài nguyên và thông tin giữa các trung tâm này và sau đó là cung cấp sự 3 truy nhập tới các tài nguyên cho các nhiều người sử dụng. Các thủ tục chia sẻ tài nguyên đặc biệt giữa các nhóm này đã hình thành phương thức để chuẩn hoá những giao thức cần để trao đổi thông tin giữa các khu vực hành chính. Công nghệ lưới có thể xem như một mở rộng hoặc một ứng dụng của nền tảng này để tạo nên phương thức chia sẻ tài nguyên tổng quát [13]. Dự án phi lợi nhuận Seti@home là một trong những nhân tố khoa học nổi tiếng thúc đẩy việc tạo ra một dự án tính toán lưới đơn giản bằng cách thu thập tất cả các tài nguyên CPU chưa được sử dụng (những người theo chủ nghĩa lưới thuần túy cho rằng CPUi@home thực chất là một ứng dụng tính toán phân tán bởi nó hầu như không thúc đẩy việc sử dụng bất kỳ một khái niệm lưới nào). Seti@home không phải là dự án đầu tiên mở đường cho kỹ thuật này. Việc tận dụng tài nguyên CPU trên các máy trong mạng cục bộ đã bắt đầu từ thập niên 1970 với những dự án phi lợi nhuận như distributed.net nhưng Seti@home nổi tiếng bởi dự án này được ứng dụng vào rất nhiều dự án khác như dự đoán cấu trúc protein, nghiên cứu thuốc cho bệnh ung thư, giải các bài toán phức tạp và dự báo thời tiết. Hầu hết những dự án này đều thực hiện dưới dạng các tiến trình chạy trên các máy tính cá nhân, xử lý những phần dữ liệu nhỏ khi máy tính ở trạng thái chờ hoặc sử dụng ít tài nguyên. Nhiều dự án như vậy đã bị kéo dài hoặc tốn quá nhiều tiền [13]. Vào năm 1997, một trong những dịch vụ tính toán lưới thương mại đầu tiên đã được Entropia cung cấp, và tới nay có rất nhiều dịch vụ như vậy do các công ty và các phòng thí nghiệm thực hiện. Một điểm khác biệt quan trong giữa các lưới và các dự án gần giống lưới là trong tính toán lưới cho phép di trú các nhiệm vụ tính toán tới tất cả các nút tính toán trên lưới để thực thi. Chẳng hạn chương trình xử lý ảnh viễn vọng Seti@home chứa cả mã xử lý dữ liệu từ kính viễn vọng vô tuyến và mã để lấy dữ liệu từ cơ sở dữ liệu và trả lại kết quả. Hai đoạn mã này được trộn lẫn vào một chương trình. Trong lưới, chỉ có các đoạn mã đòi hỏi phải truy vấn cơ sở dữ liệu và trả về kết 4 quả thì nằm trên các nút tính toán. Mã cần để thực hiện các tác vụ phân tán được gửi riêng rẽ tới các nút. Theo cách này, các nút của lưới có thể dễ dàng lập trình lại [13]. Có thể nói, việc phát triển và xây dựng mô hình tính toán lưới 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 cho các mô hình tính toán lưới ngày càng được ứng dụng để thực hiện được nhiều điều hơn những ý tưởng trước đây. 1.1.2 Khái niệm tính toán lưới Trong mỗi giai đoạn phát triển, mỗi tổ chức, cá nhân tùy theo quan điểm và thực tế xây dựng hệ thống của mình mà đưa ra các định nghĩa khác nhau về tính toán lưới. Dưới đây, luận văn xin trình bày một số định nghĩa về tính toán lưới như sau: Dưới quan điểm cá nhân của tiến sỹ I.Foster và các đồng nghiệp thì [9] "Một lưới là một hệ thống có các đặc trưng như phối hợp các tài nguyên phân tán từ nhiều miền tự trị khác nhau; sử dụng các chuẩn mở và giao thức mở; cung cấp chất lượng dịch vụ không tầm thường" - I. Foster„s Three-Point Checklist (HPCWIRE 20.07.2002). Còn dưới quan điểm của một số công ty và liên minh phát triển lưới uy tín trên thế giới thì tính toán lưới được định nghĩa như sau [6]: Định nghĩa của Oracle: tính toán lưới là việc liên kết nhiều máy chủ và thiết bị lưu trữ thành một siêu máy tính nhằm tối ưu hóa được tính ưu việt của các hệ thống máy chủ cũng như hệ thống ứng dụng, nhờ đó giảm thiểu đến mức thấp nhất chi phí. Định nghĩa của IBM: tính toán lưới là một môi trường tính toán ảo. Môi trường này cho phép bố trí song song, linh hoạt, chia sẻ, tuyển lựa, tập hợp các nguồn tài nguyên hỗn hợp về mặt địa lý, tùy theo mức độ sẵn sàng, hiệu suất, chi phí của các tài nguyên tính toán và yêu cầu về chất lượng dịch vụ của người sử dụng. Định nghĩa của liên minh điện toán lưới: môi trường tính toán lưới được hiểu như một hạ tầng kết nối hệ thống máy tính, hệ thống mạng, hệ thống cơ sở dữ liệu 5 được sở hữu và quản lý bởi nhiều tổ chức, cá nhân nhằm cung cấp môi trường tính toán ảo duy nhất với hiệu năng cao cho người sử dụng. Hình 1.1: Mô hình tính toán lưới Định nghĩa chính thức về một lưới được Ian Foster đưa ra trong bài báo “ What is a Grid?” và trong định nghĩa một lưới có ba đặc điểm chính là:  Tài nguyên tính toán không được quản lý tập trung  Sử dụng các chuẩn mở  Có chất lượng dịch vụ tốt. 6 Trên thực tế, tính toán lưới hấp dẫn đối với các nỗ lực cộng tác nghiên cứu phân tán theo địa lý phi lợi nhuận như các lưới nghiên sinh tin học của trung tâm ứng dụng siêu máy tính NCSA chẳng hạn lưới BIRN (lưới ngoài). Tính toán lưới cũng hấp dẫn đối với các doanh nghiệp thương mại lớn với các bài toán phức tạp, đây là các tổ chức luôn cố gắng tận dụng các tài nguyên tính toán bên trong một cách hiệu quả nhất (lưới nội bộ). Mỗi tác giả khi đưa ra định nghĩa đều đứng trên một số quan niệm nhất định. Để có cái nhìn toàn diện về tính toán lưới, ta không đưa ra một định nghĩa cụ thể nào, thay vào đó chúng ta sẽ xem xét khái niệm tính toán lưới các đặc trưng sau: Kích thước lớn: theo số lượng tài nguyên và khoảng cách địa lý giữa chúng Phân tán: có độ trễ đáng kể trong truyền dữ liệu, tài nguyên trải dài trên các vùng địa lý khác nhau Động: các tài nguyên có thể thay đổi khi ứng dụng đang được thực hiện Hỗn tạp: kiến trúc và tính chất của các nút lưới có thể là hoàn toàn khác nhau. Tài nguyên lưới có thể là các máy đơn hoặc mạng con khác nhau Vượt qua phạm vi một tổ chức: có nhiều trạm và các chính sách truy nhập có thể khác nhau trên các trạm, tổng thể lưới sẽ tạo ra một tổ chức ảo thống nhất. Cơ chế và chính sách an toàn bảo mật phức tạp. Cơ chế quản lý tài nguyên đa dạng, phức tạp. Có thể hình dung đơn giản một lưới bao gồm một tập các tài nguyên đa dạng (còn gọi là các nút lưới - có thể là PC, cluster, hệ thống lưu trữ, ...) thuộc về nhiều tổ chức nhằm giải quyết một bài toán nào đó. 1.1.3 Lợi ích của tính toán lưới Tính toán lưới có thể đem lại những ích lợi rất lớn [10]. 1/. Khai thác, tận dụng các tài nguyên nhàn rỗi 7 Hầu hết các tổ chức đều có một lượng lớn các tài nguyên tính toán nhàn rỗi, các máy tính cá nhân thường chỉ sử dụng hết 5% thời gian xử lý CPU, ngay cả các server cũng thường “rảnh rỗi”. Lưới có thể tối ưu sử dụng các tài nguyên nhàn rỗi này theo nhiều cách khác nhau, ví dụ, gửi một công việc trên một máy tính đang bận rộn đến một máy khác rảnh rỗi hơn để xử lý, hoặc phân nhỏ một công việc rồi gửi các công việc con đến các máy tính nhàn rỗi khác cho xử lý song song, .... Lưới cho phép kết hợp nhiều không gian lưu trữ nhàn rỗi để tạo thành một không gian lưu trữ lớn hơn, được cấu hình để tăng hiệu suất, độ tin cậy hơn so với các máy đơn lẻ thông qua các cơ chế quản lý dữ liệu. Một chức năng của lưới nữa là cân bằng sử dụng tài nguyên tốt hơn. Một tổ chức thường gặp các vấn đề khó khăn khi các hoạt động đòi hỏi thêm nhiều tài nguyên hơn. Với lưới, có thể chuyển hoạt động đến các tài nguyên nhàn rỗi khác, hoặc có thể thêm các tài nguyên mới một cách dễ dàng, từ đó làm tăng khả năng chịu đựng của hệ thống. Lưới có thể quản lý nhiều loại tài nguyên, do đó có thể cho phép theo dõi tổng quan về các hoạt động sử dụng tài nguyên trong các tổ chức lớn, hỗ trợ hoạch định các chiến lược sử dụng tài nguyên. 2/. Sử dụng CPU song song Khả năng sử dụng các CPU song song là một đặc tính tuyệt vời của lưới, ngoài việc hỗ trợ các nhu cầu tính toán của các nhà khoa học, sức mạnh tính toán do lưới cung cấp có thể giúp giải quyết các bài toán đòi hỏi năng lực xử lý lớn trong các ngành khác như y dược, tính toán tài chính, kinh tế, khai thác dầu hoả, dự báo thời tiết, công nghiệp vũ trụ, thiết kế sản phẩm, ... và rất nhiều lĩnh vực khác. 3/. Cho phép hợp tác trên toàn thế giới Một trong những đóng góp quan trọng của công nghệ tính toán lưới là cho phép và đơn giản hoá hợp tác chia sẻ, làm việc giữa một cộng đồng rộng lớn trên toàn thế giới. Các công nghệ tính toán phân tán trước đây cũng cho phép hợp tác nhưng chỉ trong một phạm vi nhỏ, còn lưới cho phép mở rộng trên phạm vi toàn cầu khi đưa ra những 8 chuẩn quan trọng cho phép các hệ thống không đồng dạng làm việc chung với nhau để tạo nên một hệ thống tính toán ảo cung cấp rất nhiều dạng tài nguyên khác nhau. 4/. Cho phép chia sẻ, sử dụng tất cả các loại tài nguyên Không chỉ cho phép chia sẻ các chu kỳ tính toán, dữ liệu, lưới có thể cho phép chia sẻ tất cả các loại tài nguyên mà trước đây chưa được chia sẻ, như băng thông mạng, các thiết bị đặc biệt, phần mềm, bản quyền, các dịch vụ. Ví dụ, nếu một người dùng muốn tăng băng thông kết nối Internet của mình lên để thực hiện một ứng dụng khai thác dữ liệu, ứng dụng đó có thể được gửi đến nhiều máy tính trong lưới có các kết nối Internet riêng, từ đó băng thông truy cập Internet của anh ta tăng lên rất nhiều lần. 5/. Tăng tính tin cậy cho các hệ thống máy tính Hiện nay, các hệ thống tính toán sử dụng các phần cứng chuyên dụng, đắt đỏ để tăng độ tin cậy. Ví dụ, một máy tính có thể sử dụng các bộ vi xử lý đôi, cho phép “cắm nóng”, để khi có một vi xử lý bị hỏng, có thể thay thế cái khác mà không làm ngưng hoạt động của hệ thống. Các giải pháp này làm tăng độ tin cậy của hệ thống, tuy nhiên với chi quá đắt khi phụ kiện đi kèm cũng phải nhân lên. Trong tương lai, các hướng tiếp cận mới để giải quyết vấn đề độ tin cậy dựa nhiều hơn vào các công nghệ phần mềm hơn là các phần cứng đắt tiền. Lưới là sự khởi đầu cho các công nghệ đó. Các hệ thống trong lưới thường rẻ và phân tán theo địa lý, do đó, nếu có sự cố về nguồn điện hay các lỗi hệ thống khác tại một vị trí, toàn bộ phần còn lại không bị ảnh hưởng. Các phần mềm quản trị lưới có khả năng thực thi lại công việc trên một nút khác khi phát hiện có lỗi hệ thống. Nếu quan trọng hơn nữa, trong các hệ thống theo thời gian thực, nhiều bản dự phòng của các các công việc quan trọng có thể được chạy trên nhiều máy tính khác nhau trong lưới để đảm bảo độ tin cậy tối đa. 6/. Tăng khả năng quản trị các hệ thống Mục tiêu ảo hoá tất cả các tài nguyên và cung cấp giao diện quản lý đơn nhất các hệ thống hỗn tạp đem lại những cơ hội mới để quản trị tốt hơn trong các cơ sở hạ tầng công nghệ thông tin lớn, phân tán. Bên cạnh đó, đối với tầm quản lý vĩ mô, có