Nghiên cứu và ứng dụng các thuật toán lập lịch vào môi trường tính toán lưới

Bài báo nghiên cứu và ứng dụng thuật toán lập lịch trong mô hình tính toán lưới với mục đích làm giảm thiểu thời gian hệ thống cần thiết để hoàn tất các ứng dụng. Một số thuật toán được nghiên cứu đó là: OLB, MCT, Min-Min, Max-Min, Sufferage; đồng thời trong bài báo này đưa ra kết quả so sánh về tính hiệu quả giữa các thuật toán này khi được áp dụng vào mô hình cụ thể.
Nội dung trích xuất từ tài liệu:
Nghiên cứu và ứng dụng các thuật toán lập lịch vào môi trường tính toán lưới Tăng Cẩm Nhung Tạp chí KHOA HỌC & CÔNG NGHỆ 65(03): 134 - 138 NGHIÊN CỨU VÀ ỨNG DỤNG CÁC THUẬT TOÁN LẬP LỊCH VÀO MÔI TRƯỜNG TÍNH TOÁN LƯỚI Tăng Cẩm Nhung Trường Đại học Kỹ thuật Công nghiệp – ĐH Thái Nguyên TÓM TẮT Nhờ có nhiều tiến bộ trong công nghệ mạng và các nguồn tài nguyên máy tính phong phú, công nghệ tính toán lưới đã ra đời và hiện nay là một lĩnh vực nghiên cứu khá hiệu quả. Một đặc điểm nổi bật của tính toán lưới đó là có thể kết hợp các nguồn tài nguyên phân tán rộng khắp và cung cấp số lượng dịch vụ không nhỏ cho người sử dụng. Để đạt được các mục tiêu đó, hệ thống lập lịch hiệu quả là một phần thiết yếu của lưới. Bài báo nghiên cứu và ứng dụng thuật toán lập lịch trong mô hình tính toán lưới với mục đích làm giảm thiểu thời gian hệ thống cần thiết để hoàn tất các ứng dụng. Một số thuật toán được nghiên cứu đó là: OLB, MCT, Min-Min, Max-Min, Sufferage; đồng thời trong bài báo này đưa ra kết quả so sánh về tính hiệu quả giữa các thuật toán này khi được áp dụng vào mô hình cụ thể. Từ khóa: Tính toán lưới, lập lịch,OLB, MET,MCT,Max-Min, Min – Min, Sufferage, xSufferage ĐẶT VẤN ĐỀ 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ế, càng ngày càng có nhiều bài toán lớn và 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: Thứ nhất: Đầ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, cluster...). Rõ ràng là cách làm này hết sức tốn kém. Thứ hai: Một cách thực hiện hiệu quả hơn 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). Đây là mục tiêu chính của tính toán lưới Môi trường lưới cho phép kết hợp các hệ thống xử lý lại với nhau để giải quyết một cách hiệu quả các nhu cầu ngày càng cao của con người [6]. Đặc biệt, đây là một công nghệ có khả năng kết hợp các nguồn tài nguyên từ những tổ chức khác nhau, phân tán trên phạm vi địa lý rộng và đặc biệt là không đòi hỏi các nguồn tài nguyên phải tương đồng về cấu trúc [7]. Bài toán lập lịch là một trong những vấn đề quan trọng được nghiên cứu trong các môi trường tính toán, đặc biệt là các môi trường * * Tel: 0988724824; Email: tính toán phân tán như môi trường tính toán lưới. Do đặc thù của môi trường lưới như: số lượng công việc và các nguồn tài nguyên thường rất lớn. Mặt khác các tài nguyên này còn nằm phân tán và hỗn tạp, mỗi nguồn tài nguyên có thể do một tổ chức riêng biệt quản lý, có các chính sách và chi phí hoạt động khác nhau, bên cạnh đó tải (load) và tính sẵn sàng (availability) của các hệ thống cũng rất khác nhau; do đó vấn đề lập lịch (scheduling) trong hệ thống lưới có nhiều khó khăn và thách thức hơn so với môi trường khác, hiện tại vẫn còn đòi hỏi nhiều công sức nghiên cứu [3] GIỚI THIỆU BÀI TOÁN LẬP LỊCH TRONG MÔI TRƯỜNG LƯỚI[1] Bài toán lập lịch là một trong những vấn đề quan trọng được nghiên cứu trong các môi trường tính toán, đặc biệt là các môi trường tính toán phân tán như môi trường tính toán lưới. Quá trình lập lịch là quá trình quyết định sẽ thực thi công việc tại một nguồn tài nguyên cụ thể nào và vào thời điểm nào là thích hợp nhất do đó sẽ ảnh hưởng rất lớn đến hiệu năng hoạt động của hệ thống. Có khá nhiều vấn đề được đặt ra và cần giải quyết khi nghiên cứu về quá trình lập lịch trong môi trường tính toán lưới:  Mối liên hệ và tác động lẫn nhau giữa các ứng dụng trong quá trình thực thi.  Những đòi hỏi, yêu cầu khác nhau của từng ứng dụng trong hệ thống.  Sự không đồng nhất và biến động của các nguồn tài nguyên trong môi trường. 134 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn Tăng Cẩm Nhung Tạp chí KHOA HỌC & CÔNG NGHỆ  Mô hình hoạt động và các chính sách về truy xuất, bảo mật … của hệ thống. CÁC THUẬT TOÁN ÁP DỤNG TRONG BÀI TOÁN LẬP LỊCH THEO HIỆU NĂNG CỦA HỆ THỐNG Mục đích của phương pháp này hướng đến mục đích giảm tối đa thời gian hệ thống cần thiết để hoàn tất các ứng dụng, thời gian này được gọi là makespan của hệ thống. Một số hướng tiếp cận được đề cập đến như OLB, MCT, Min-Min, Max-Min, Sufferage… OLB (Opportunistic Load Balancing) Đây là chiến lược rất đơn giản, phân phối công việc cho tài nguyên có thời điểm sẵn sàng sớm nhất mà không quan tâm đến thời gian thực thi của công việc trên tài nguyên đó. MET (Minimum Execution Time)[3] Ngược lại với OLB, phân phối công việc vào các tài nguyên có khả năng thực thi công việc nhanh nhất, không quan tâm đến thời điểm bắt đầu và kết thúc của công việc trên tài nguyên đó. Giải thuật này thường có nhược điểm là không cân bằng tải vì hầu như các công việc đều được tập trung thực thi trên các tài nguyên có năng lực cao nhất Giả sử ta có 2 tác vụ cần thực t ...