Luận văn Nghiên cứu giải thuật định thời cho các bài toán song song, độc lập trên môi trường tính toán lưới

7 Chương 1. Giới thiệu Tính toán lưới (Grid Computing [1]) là một lĩnh vực được nghiên cứu và phát triển mạnh mẽ trong thời gian gần đây. Môi trường tính toán lưới cho phép kết hợp các hệ thống xử lý với nhau để giải quyết một cách hiệu quả những nhu cầu ngày càng cao của con người. Ưu điểm của công nghệ lưới so với các công nghệ ra đời trước đó là khả năng kết hợp các tài nguyên thuộc những tổ chức khác nhau, phân tán rộng về mặt địa lý và không đòi hỏi các nguồn tài nguyên này phải tương đồng về cấu trúc cũng như năng lực xử lý. Bài toán lập lịch trên môi trường tính toán lưới là một lĩnh vực đòi hỏi nhiều công sức nghiên cứu và còn rất nhiều thử thách. Quá trình lập lịch chịu trách nhiệm quyết định thời điểm và tài nguyên đảm nhận thực thi ứng dụng do đó ảnh hưởng trực tiếp đến hiệu năng của hệ thống. Môi trường lưới là một môi trường biến động về số lượng cũng như năng lực các nguồn tài nguyên; do đó những nghiên cứu về lập lịch trên môi trường này có nhiều đặc điểm riêng so với các môi trường khác. Lớp bài toán được nghiên cứu và triển khai nhiều trên môi trường lưới là lớp ứng dụng gồm các tác vụ song song và độc lập với nhau (ví dụ như lớp ứng dụng parameter sweep [11] gồm các tác vụ thực thi cùng một tính năng tính toán nhưng trên các bộ tham số đầu vào khác nhau). Đây là một lớp ứng dụng phát huy hiệu quả cao trên môi trường tính toán lưới; lớp ứng dụng này được thấy nhiều trong các lĩnh vực như phân tích số liệu kinh tế, vật lý, sinh học … Đã có nhiều nghiên cứu về lập lịch trên môi trường lưới cho lớp ứng dụng song song độc lập, tuy nhiên các nghiên cứu này chủ yếu nhắm đến các ứng dụng rất lớn nên có một số đặc điểm chưa phù hợp với mô hình thực tế tại Việt Nam. Luận văn tập trung nghiên cứu lập lịch trong điều kiện môi trường lưới có một số lượng lớn các ứng dụng vừa và nhỏ, có thể thực thi toàn bộ một ứng dụng trên một cụm tài nguyên tính toán như máy tính cụm (clusters). Vấn đề được nghiên cứu trong luận văn là bài toán lập lịch theo hiệu năng kinh tế, mỗi ứng dụng chịu chi 8 phối bởi hai ràng buộc chính là ngân sách thực thi (budget) và thời hạn hoàn tất (deadline). Ba giải thuật định thời ADeadline, ACostPI và ABenefit được phát triển trong luận văn nhằm thỏa mãn cho các tiêu chí khác nhau của hệ thống. Mô hình lý thuyết và các kết quả thực nghiệm cho thấy những giải thuật này phù hợp hơn với mô hình các ứng dụng tại Việt Nam. Luận văn cũng đề xuất mô hình nhà cung cấp - provider, quản lý phân khu các nguồn tài nguyên tính toán. Mô hình này giúp giảm tải cho hệ thống cũng như hạ thấp độ phức tạp của giải thuật lập lịch. Ngoài ra, các phương án hoạt động khác nhau của provider được phân tích, kiểm nghiệm để tìm ra phương án phù hợp. Các giải thuật được đề xuất trong luận văn hoàn toàn có thể được tích hợp để hoạt động bên trong các bộ điều phối (broker) có sẵn của các hệ thống lưới hiện nay. Phần còn lại của luận văn được chia thành 5 chương: Chương 2 giới thiệu về công nghệ Grid Computing - tính toán lưới, các dự án Grid đang được nghiên cứu và triển khai. Chương 3 giới thiệu về đặc điểm và những hướng tiếp cận của bài toán lập lịch cho các ứng dụng song song, độc lập trên môi trường lưới. Chương 4 trình bày mô hình hệ thống và những giải thuật định thời được luận văn đề xuất cho các ứng dụng trên môi trường lưới. Các thử nghiệm và phân tích được trình bày ở chương 5. Chương 6 là những đánh giá, kết luận và hướng phát triển của đề tài.