I. Giới thiệu
Luận văn thạc sĩ này tập trung vào việc lập lịch quản lý tính toán hiệu năng cao trong lĩnh vực khoa học máy tính. Nghiên cứu này nhằm giải quyết các bài toán liên quan đến việc tối ưu hóa thời gian thực thi các workflow khoa học trên nền tảng điện toán đám mây. Workflow là mô hình phổ biến để mô tả các ứng dụng khoa học, đòi hỏi sức mạnh tính toán vượt trội và khả năng quản lý tài nguyên hiệu quả.
1.1 Động cơ nghiên cứu
Nghiên cứu này xuất phát từ nhu cầu thực tế về việc xử lý các workflow khoa học với khối lượng dữ liệu lớn và yêu cầu tính toán phức tạp. Điện toán đám mây cung cấp nền tảng lý tưởng để thực thi các workflow này, nhưng việc lập lịch hiệu quả vẫn là thách thức lớn. Việc phân bổ tài nguyên và di chuyển dữ liệu giữa các tác vụ có thể làm tăng thời gian thực thi tổng thể, đặc biệt với các workflow có kích thước dữ liệu lớn.
1.2 Mục tiêu và phạm vi nghiên cứu
Mục tiêu chính của nghiên cứu là giảm thiểu thời gian thực thi tổng thể (makespan) của các workflow trên nền tảng điện toán đám mây. Nghiên cứu đề xuất hai mô hình quy hoạch tuyến tính nguyên (ILP) và một giải thuật heuristic để giải quyết bài toán lập lịch. Phạm vi nghiên cứu tập trung vào việc tối ưu hóa thời gian thực thi và đánh giá hiệu quả của các giải pháp đề xuất.
II. Tổng quan lý thuyết
Chương này trình bày tổng quan về các giải thuật lập lịch trong khoa học máy tính, bao gồm lập lịch các công việc độc lập và lập lịch workflow. Các giải thuật như MET, MCT, Min-Min, và Max-Min được phân tích để làm cơ sở cho việc đề xuất giải pháp mới. Ngoài ra, nghiên cứu cũng giới thiệu các công trình liên quan đến lập lịch workflow trên nền tảng điện toán đám mây.
2.1 Lập lịch các công việc độc lập
Các giải thuật MET và MCT được sử dụng để lập lịch các công việc độc lập. MET tập trung vào việc gán tác vụ vào tài nguyên có thời gian thực thi ngắn nhất, trong khi MCT xem xét thời gian hoàn thành sớm nhất. Cả hai giải thuật đều có ưu điểm và hạn chế riêng, đặc biệt trong việc cân bằng tải sử dụng tài nguyên.
2.2 Lập lịch workflow
Lập lịch workflow liên quan đến việc phân bổ các công việc có sự phụ thuộc dữ liệu lên các tài nguyên phân tán. Các chiến lược best-effort và QoS constraint được sử dụng để tối ưu hóa thời gian thực thi và đáp ứng các yêu cầu dịch vụ của người dùng. Giải thuật HEFT là một trong những phương pháp phổ biến để lập lịch workflow hiệu quả.
III. Mô hình toán học
Chương này trình bày các mô hình toán học được đề xuất để giải quyết bài toán lập lịch workflow. Hai mô hình quy hoạch tuyến tính nguyên (ILP) được xây dựng để tối ưu hóa thời gian thực thi. Các mô hình này được phân tích và so sánh thông qua các kết quả mô phỏng, nhằm đánh giá hiệu quả và khả năng ứng dụng thực tế.
3.1 Phát biểu bài toán
Bài toán lập lịch workflow được phát biểu dưới dạng tối ưu hóa thời gian thực thi tổng thể. Các yếu tố như thời gian thực thi, chi phí thuê tài nguyên, và sự phụ thuộc giữa các tác vụ được xem xét để xây dựng mô hình toán học.
3.2 Mô hình quy hoạch tuyến tính nguyên
Hai mô hình ILP được đề xuất để giải quyết bài toán lập lịch workflow. Mô hình thứ nhất tập trung vào việc tối ưu hóa thời gian thực thi, trong khi mô hình thứ hai kết hợp cả yếu tố chi phí. Các mô hình này được kiểm nghiệm trên tập dữ liệu thực tế để đánh giá hiệu quả.
IV. Lập lịch nhiều ứng dụng workflow
Chương này tập trung vào việc lập lịch đồng thời nhiều workflow trên các cụm tài nguyên phân bố. Giải thuật heuristic MM-HEFT được đề xuất để giải quyết bài toán này. Giải thuật này được so sánh với các phương pháp hiện có và đánh giá thông qua các kết quả thực nghiệm.
4.1 Giải thuật MM HEFT
Giải thuật MM-HEFT kết hợp các ưu điểm của Min-Min và HEFT để tối ưu hóa thời gian thực thi của nhiều workflow. Giải thuật này được thiết kế để xử lý các tác vụ có sự phụ thuộc dữ liệu và phân bổ chúng một cách hiệu quả trên các tài nguyên phân tán.
4.2 Thực nghiệm và đánh giá
Các kết quả thực nghiệm cho thấy giải thuật MM-HEFT có hiệu suất vượt trội so với các phương pháp truyền thống. Thời gian thực thi tổng thể được giảm thiểu đáng kể, đồng thời đảm bảo cân bằng tải sử dụng tài nguyên.
V. Tổng kết
Nghiên cứu này đã đề xuất các mô hình toán học và giải thuật heuristic để giải quyết bài toán lập lịch workflow trên nền tảng điện toán đám mây. Các kết quả thực nghiệm cho thấy hiệu quả của các giải pháp đề xuất trong việc giảm thiểu thời gian thực thi và tối ưu hóa sử dụng tài nguyên. Nghiên cứu cũng mở ra hướng phát triển mới trong lĩnh vực lập lịch quản lý tính toán hiệu năng cao.
