Giải thuật tối thiểu hóa chi phí thực thi luồng công việc trong môi trường điện toán đám mây

Bài viết này đề xuất một mô hình bài toán luồng công việc và một giải thuật heuristic cải tiến dựa trên thuật toán PSO để lập lịch thực thi luồng công việc trên môi trường điện toán đám mây đảm bảo chi phí nhỏ nhất.
Nội dung trích xuất từ tài liệu:
Giải thuật tối thiểu hóa chi phí thực thi luồng công việc trong môi trường điện toán đám mâyJOURNAL OF SCIENCE OF HNUE DOI: 10.18173/2354-1059.2015-0007Natural Sci. 2015, Vol. 60, No. 4, pp. 47-55This paper is available online at http://stdb.hnue.edu.vnGIẢI THUẬT TỐI THIỂU HÓA CHI PHÍ THỰC THI LUỒNG CÔNG VIỆC TRONG MÔI TRƯỜNG ĐIỆN TOÁN ĐÁM MÂY Phan Thanh Toàn 1, Nguyễn Thế Lộc2, Nguyễn Doãn Cường1 và Đỗ Như Long1 1 Khoa Sư phạm Kĩ thuật, Trường Đại học Sư phạm Hà Nội 2 Khoa Công nghệ thông tin, Trường Đại học Sư phạm Hà Nội Tóm tắt. Luồng công việc là một dãy có thứ tự các tác vụ cần thực thi để đạt được một mục đích, bài toán lập lịch luồng công việc là bài toán sắp xếp các tác vụ cho thực thi trên một số máy xác định sao cho hiệu quả là tốt nhất, đây chính là bài toán thường gặp và có tính quan trọng nhất trong môi trường điện toán đám mây. Bài toán lập lịch thực thi luồng công việc là bài toán NP- Complete và thực nghiệm đã chỉ ra là không có lời giải tối ưu tuyệt đối. Bài báo này đề xuất một mô hình bài toán luồng công việc và một giải thuật heuristic cải tiến dựa trên thuật toán PSO để lập lịch thực thi luồng công việc trên môi trường điện toán đám mây đảm bảo chi phí nhỏ nhất. Từ khóa: Lập lịch luồng công việc, ứng dụng luồng công việc, điện toán đám mây.1. Mở đầu Điện toán đám mây là một công nghệ được phát triển dựa trên nền tảng của các công nghệ trướcđây như điện toán lưới (grid computing), tính toán phân tán và song song. Trong mô hình điện toánđám mây các tác vụ (task) sẽ được phân phối và thực hiện tại các trung tâm điện toán đám mây. Lậplịch thực thi luồng công việc là một vấn đề quan trọng nhất trong môi trường điện toán đám mây và đãcó nhiều công trình nghiên cứu nhằm tìm ra các giải pháp lập lịch tối ưu. Tuy nhiên thực nghiệm đãchỉ ra bài toán lập lịch thực thi luồng công việc là bài toán thuộc lớp NP-Complete [1] do vậy bài toánlập lịch luồng công việc thường được thực hiện bằng các giải thuật heuristic trong đó lớp các giải thuậttiến hóa là một hướng tiếp cận được sử dụng khá rộng rãi trong thời gian gần đây.2. Nội dung nghiên cứu2.1. Bài toán tối thiểu hóa chi phí * Phát biểu bài toán Xét bài toán cần sắp xếp lịch biểu cho một luồng công việc gồm M tác vụ (task - từ đây viết tắt làtask), trong một môi trường điện toán đám mây với các yêu cầu như sau: + Luồng công việc gồm có M tác vụ; + Các tác vụ có quan hệ thứ tự trước - sau; + Mỗi tác vụ cần một khối lượng dữ liệu vào và sẽ xuất ra một lượng dữ liệu xác định; + Luồng công việc chỉ có duy nhất một Task gốc (task vào) và một task ra (output); + Môi trường thực thi luồng công việc là môi trường điện toán đám mây với N máy chủ tính toánvà K máy chủ lưu trữ; + Mỗi tác vụ (task) có thể được thực thi trên một máy chủ bất kì và chỉ được thực thi trên mộtmáy chủ duy nhất;Ngày nhận bài: 23/1/2015. Ngày nhận đăng: 22/4/2015.Tác giả liên lạc: Phan Thanh Toàn, địa chỉ e-mail: pttoan@hnue.edu.vn 47 Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường và Đỗ Như Long + Mỗi máy chủ thực thi và máy chủ lưu trữ dữ liệu đều có một đơn giá xác định do nhà cung cấpdịch vụ cung cấp; Mô hình toán học bài toán tối thiểu chi phí thực thi luồng công việc trong môi trường điệntoán đám mây 1-Tập các máy chủ S = {S1, S2,….,SN}. 2-Luồng công việc được biểu diễn bởi một đồ thị G = (V, E), với V là tập các đỉnh của đồ thị vàlà tập các task, E là tập cạnh của đồ thị thể hiện mối quan hệ giữa các task. 3-Tập các task : V = {T1, T2,…,TM}. 4-Nếu e = (Ti, Tj)  E, có nghĩa là Task Ti thực hiện trước và sẽ chuyển cho Task Tj một khốilượng dữ liệu xác định. 5-Khối lượng tính toán của một Task Ti kí hiệu là Wi (Workload) đo bằng flop (floating pointoperations). 6-Năng lực xử lí của một máy chủ được (Processing capacity) được biểu diễn bởi một hàm số: P: S  R+ Si  P(Si) 7-Đơn giá cước tính toán, nghĩa là chi phí thực thi một đơn vị flop trên máy chủ (Excution cost)được tính bằng dolar/flop và là một hàm số: E: S  R+ Si  E(Si) 8-Mỗi cặp máy chủ S i, Sj ( 1  i, j  N ) đều có một kênh truyền kết nối chúng, băng thông củakênh truyền kí hiệu là B (Bandwidth), và là một hàm số: B: SxS  R+ (Si, Sj)  B(Si, Sj) Giả sử hàm B thỏa mãn điều kiện: + B(Si, Si) =  (băng ...