Luận án tiến sĩ toán học: Thuật toán lập lịch phân phối tài nguyên trong hệ thống tính toán lưới - Trịnh Thị Thúy Giang, ĐHQG Hà Nội

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ---------------------------- Trịnh Thị Thúy Giang MỘT SỐ THUẬT TOÁN LẬP LỊCH ĐỂ PHÂN PHỐI TÀI NGUYÊN TRONG HỆ THỐNG TÍNH TOÁN LƯỚI Chuyên ngành: Bảo ñảm toán học cho máy tính và hệ thống tính toán Mã số: 62 46 35 01 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. Nguyễn Thanh Thủy 2. Hoàng Chí Thành Hà Nội - 2011 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỤC LỤC LỜI CAM ĐOAN .3 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT.6 DANH MỤC CÁC BẢNG.7 DANH MỤC CÁC HÌNH VẼ. TỔNG QUAN VỀ HỆ THỐNG TÍNH TOÁN LƯỚI .1 Giới thiệu chung .1 Hệ thống tính toán lưới là gì .2 Các mô hình tính toán lưới.3 Các thành phần chính của hệ thống tính toán lưới .4 So sánh mô hình tính toán lưới với một số mô hình tính toán khác .5 Những ứng dụng cơ bản của hệ thống tính toán lưới .6 Các công cụ hỗ trợ xây dựng hệ thống tính toán lưới .7 Một số hệ thống tính toán lưới.2 Các thách thức ñối với mô hình tính toán lưới và một số vấn ñề nghiên cứu .1 Các xu hướng trong tính toán.3 Một số hướng nghiên cứu.3 Mục tiêu của luận án .4 Các kết quả ñã ñạt ñược của luận án.

BÀI TOÁN LẬP LỊCH TRONG TÍNH TOÁN LƯỚI.1 Một số bài toán lập lịch truyền thống .41 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 Bài toán lập lịch trên hai máy và giải thuật gia công Johnson .2 Giải thuật xếp lịch heuristic .3 Phương pháp duyệt nhánh cận .4 Phương pháp qui hoạch ñộng.5 Phương pháp làm mịn kết quả.6 Phương pháp Hung-ga-ri .2 Bài toán lập lịch trong hệ thống tính toán lưới .1 Phát biểu bài toán .2 Một số khó khăn trong lập lịch ñối với hệ thống tính toán lưới.3 Một số cách tiếp cận .4 Độ khó của bài toán .3 Mô hình lập lịch trong hệ thống tính toán lưới .1 Các mô hình lập lịch trong hệ thống tính toán lưới .2 Mô hình Buyya lập lịch trong hệ thống tính toán lưới.3 Thực hiện công việc lập lịch trong hệ thống tính toán lưới.64 Kết luận chương 2. MỘT SỐ GIẢI THUẬT CHO BÀI TOÁN LẬP LỊCH TRONG TÍNH TOÁN LƯỚI.1 Các giải thuật lập lịch tối ưu theo thời gian, chi phí .1 Giải thuật lập lịch tối ưu về thời gian.2 Giải thuật tối ưu về chi phí.3 Giải thuật tối ưu về thời gian - chi phí.2 Giải thuật tham lam lam .2 Các kết quả thử nghiệm.3 Giải thuật di truyền .79 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 Giới thiệu về giải thuật di truyền.2 Giải thuật di truyền trong lập lịch .3 Các kết quả thử nghiệm.4 Giải thuật tối ưu hóa theo nhóm bầy (PSO) .1 Giải thuật PSO.2 Giải thuật PSO cho bài toán lập lịch trong hệ thống tính toán lưới .3 Các kết quả thực nghiệm .96 Kết luận chương 3. MÔ HÌNH HỆ THỐNG THỬ NGHIỆM .1 Giới thiệu về hệ thống thử nghiệm TestGrid.1 Kiến trúc chung của TestGrid .2 Mô tả chức năng bộ lập lịch .3 Thiết kế bộ lập lịch.4 Cơ chế lập lịch của TestGrid.5 Xử lý và chống lỗi .2 Bộ lập lịch của TestGrid với các giải thuật ñề xuất .1 Mô hình triển khai thực nghiệm bộ lập lịch trên lưới.2 Yêu cầu tương thích giữa giải thuật lập lịch với khung phần mềm thực nghiệm. 114 Kết luận chương 4.

119 KẾT LUẬN CHUNG. 120 DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN. 122 TÀI LIỆU THAM KHẢO. 123 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT BOINC The Berkeley Open Cơ sở hạ tầng mở Berkeley cho tính Infrastructure for Network toán mạng Computing CDAC Center for Development of Trung tâm Phát triển Công nghệ Tính Advance Computing toán Tiên tiến (Ấn Độ) CORBA Common Object Request Kiến trúc môi giới yêu cầu ñối tượng Broker Architecture chung DCOM Distributed Component Mô hình hướng ñối tượng thành phần Object Model phân tán GA Genetic Algorithm Giải thuật di truyền MDS Meta Directory Service Dịch vụ siêu thư mục MPI Message Passing Interface Giao diện truyền thông ñiệp P2P Peer - to - Peer Hệ thống tính toán ngang hàng PSO Particle Swarm Optimization Tối ưu theo nhóm bầy OGSA Open Grid Services Kiến trúc dịch vụ lưới mở Architecture OGSI Open Grid Services Cơ sở hạ tầng dịch vụ lưới mở Infrastructure SA Simulated Annealing Giải thuật mô phỏng tôi luyện SP Service Providers Nhà cung cấp dịch vụ UR User Requirements Yêu cầu người dùng 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DANH MỤC CÁC BẢNG Bảng 2.

Mối ràng buộc giữa giới hạn thời gian và kinh phí trong lập lịch. Ma trận thông tin tài nguyên. So sánh hiệu quả của giải thuật mô phỏng tôi luyện và giải thuật tham lam. Hiệu quả của giải thuật di truyền khi giá trị α thay ñổi - Kịch bản 1.

Hiệu quả của giải thuật di truyền khi giá trị α thay ñổi - Kịch bản 2. Hiệu quả của giải thuật di truyền khi giá trị α thay ñổi - Kịch bản 3. So sánh hiệu quả của các giải thuật - Kịch bản 1. So sánh hiệu quả của các giải thuật - Kịch bản 2.

So sánh hiệu quả của các giải thuật - Kịch bản 3. So sánh hiệu quả của giải thuật di truyền và PSO. So sánh thời gian chạy của giải thuật di truyền và PSO.95 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DANH MỤC CÁC HÌNH VẼ Hình 1. Mô hình lưới nội tuyến.

Mô hình lưới liên tuyến. Các thành phần của một lưới tính toán. Tổ chức ảo. Mô hình bài toán lập lịch trong hệ thống tính toán lưới.

Mô hình lập lịch trung tâm. Mô hình lập lịch phân tán giao tiếp trực tiếp. Mô hình lập lịch phân tán giao tiếp gián tiếp. Mô hình lập lịch phân cấp.

Mô hình Pull cho khám phá tài nguyên. Mô hình Push cho khám phá tài nguyên. Mô hình Push-Pull cho khám phá tài nguyên. Mã giả cho giải thuật tham lam.

So sánh hiệu quả của giải thuật mô phỏng tôi luyện (SA) và giải thuật tham lam (Greedy). Mã giả cho giải thuật di truyền với tối ưu ña mục tiêu. So sánh hiệu quả của các giải thuật mô phỏng tôi luyện (SA) và giải thuật di truyền (GA)- theo Makespan. So sánh hiệu quả của các giải thuật mô phỏng tôi luyện (SA) và giải thuật di truyền (GA) - theo Flowtime.

Mã giả của giải thuật PSO cho bài toán lập lịch. So sánh thời gian chạy của các giải thuật di truyền (GA) và PSO. Kiến trúc TestGrid. Trường hợp sử dụng của bộ lập lịch.

Mô hình triển khai thực nghiệm. Đệ trình công việc lên lưới. Các job 1 - 2 -4 -6 chạy trên máy bkluster. Các job 3-5 chạy trên máy rocks-200.

114 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỞ ĐẦU Khoa học và công nghệ ngày càng phát triển vượt bậc và ñược ứng dụng rộng rãi trong tất cả các lĩnh vực của ñời sống xã hội. Công nghệ thông tin cũng phát triển như vũ bão. Cuộc sống và công việc của chúng ta trở nên thuận tiện do máy tính và Internet. Việc trao ñổi thông tin với thế giới bên ngoài sẽ không còn tốn thời gian và tiền bạc như trước ñây.

Trong thực tế, ngày càng có nhiều bài toán ñặt ra với yêu cầu dữ liệu lớn, tốc ñộ xử lý cao. Trong khi ñó, tồn tại nhiều nguồn tài nguyên dư thừa. Sự phát triển rộng khắp, mạnh mẽ của mạng Internet toàn cầu ñã làm nảy sinh một nhu cầu tất yếu, ñó là tận dụng nguồn tài nguyên dư thừa ñể xử lý các bài toán với yêu cầu tính toán lớn. Công nghệ tính toán lưới ra ñời, cho phép giải quyết vấn ñề nêu trên.

Hệ thống tính toán lưới cung cấp các dịch vụ, cho phép chia sẻ năng lực của các máy tính và dung lượng của kho dữ liệu khổng lồ thông qua Internet. Lưới tính toán dựa trên truyền thông giữa các máy tính kết nối với nhau và các dịch vụ hỗ trợ làm cho mạng máy tính toàn cầu trở thành một tài nguyên tính toán rộng lớn. Toàn bộ tài nguyên tính toán này ñược coi như một tổ chức ảo ñộng và khổng lồ. Người sử dụng chỉ cần ñệ trình công việc lên lưới tính toán và nhận lại kết quả thông qua các dịch vụ hỗ trợ của máy ảo khổng lồ này.

Ban ñầu, công nghệ tính toán lưới thu hút ñược sự quan tâm của các nhà khoa học, chuyên gia nghiên cứu và triển khai. Hiện nay, nó ñã ñược ñông ñảo các tổ chức, doanh nghiệp quan tâm ñầu tư. Tính ưu việt của công nghệ tính toán lưới, cung cấp khả năng tính toán phân tán toàn cầu ñi kèm với nhiều thách thức cần giải quyết. Trên thế giới ñã xuất hiện các bộ công cụ mã nguồn mở cho tính toán lưới.

Tuy nhiên, các bộ công cụ này ñược xây dựng chung cho tất cả các ứng dụng, vì vậy trên thực tế, tồn tại khá nhiều hạn chế. 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Một trong những vấn ñề người sử dụng quan tâm khi ñệ trình công việc lên lưới tính toán ñó là thời gian thực hiện công việc và giá thành. Lưới tính toán phải giải quyết một bài toán khó là lập lịch và lựa chọn tài nguyên ñáp ứng yêu cầu người dùng trong một môi trường ñộng không ñồng nhất. Bài toán lập lịch là một bài toán khó.

Bài toán lập lịch trong tính toán lưới còn phức tạp hơn rất nhiều do phải xem xét trong một môi trường phân tán, ñộng, với tài nguyên không ñồng nhất và phải giải quyết trong thời gian thực. Xuất phát từ những tìm hiểu, nghiên cứu về tính toán lưới trên thế giới và Việt Nam, chúng tôi ñã lựa chọn ñề tài “Một số thuật toán lập lịch ñể phân phối tài nguyên trong hệ thống tính toán lưới”. Nội dung nghiên cứu của luận án thực sự có ý nghĩa với thực tế Việt Nam khi cơ sở hạ tầng mạng và máy tính còn dư thừa và ñiều kiện kinh tế không cho phép ñầu tư ñể xây dựng những hệ thống siêu máy tính cỡ lớn. Luận án gồm 4 chương.

Chương I giới thiệu tổng quan về hệ thống tính toán lưới; Chương II giới thiệu về bài toán lập lịch trong hệ thống tính toán lưới; Chương III ñề xuất áp dụng một số giải thuật cho bài toán lập lịch trong hệ thống tính toán lưới; Chương IV trình bày mô hình cài ñặt thử nghiệm và cuối cùng là Phần kết luận. Luận án ñã ñề xuất 3 giải thuật giải quyết bài toán lập lịch trong hệ thống tính toán lưới.