Mở đầu Chương này trình bày động cơ nghiên cứu của đề tài, từ đó đặt ra mục tiêu, phạm vi của đề tài, và phương pháp nghiên cứu. Chương 2: Tổng quan lý thuyết Trình bày tổng quan lý thuyết (literature review) về các giải thuật lập lịch work- flow, giới thiệu các công trình nghiên cứu liên quan. Chương 3: Mô hình toán học Phát biểu mục tiêu tối ưu của bài toán nghiên cứu, đề xuất hai mô hình quy hoạch tuyến tính nguyên cho việc giải bài toán. Chương 4: Lập lịch nhiều ứng dụng workflow Phân tích yêu cầu của bài toán lập lịch đồng thời nhiều ứng dụng workflow trên các cụm tài nguyên có sự giới hạn về tốc độ truyền dẫn và đề xuất giải thuật heuristic cho bài toán này.
Chương 5: Tổng kết Tổng kết những van đề đã làm được trong phạm vi luận văn, những đóng góp va hướng phát triển của luận văn. Chương 2 TONG QUAN LÝ THUYET Trong chương nay sé giới thiệu về nền tang của van đề nghiên cứu, tổng quan về các giải thuật lập lịch các công việc độc lập, lập lịch workflow, giới thiệu bai toán và hướng tiếp cận ở những công trình nghiên cứu liên quan. Những nghiên cứu này là nền tảng để xây dựng mô hình cho bài toán lập lịch workflow sẽ trình bày ở Chương 3, và thiết kế giải thuật heuristic trong Chương 4.1 Giới thiệu Việc tìm hiểu một số giải thuật định thời để có một cái nhìn tổng quan hơn về các phương pháp tiếp cận giải bài toán. Từ đó, đề tài đề xuất giải pháp tốt hơn cho bài toán cụ thể cần giải quyết và cũng từ góc nhìn tổng quan này làm cơ sở để so sánh, đánh giá với giải pháp mà đề tài đề xuất.
Nhìn chung, các giải thuật này đều dựa trên các bước chính như sau: e Dầu tiên, tất cả các công việc đều được xếp có thứ tu vào trong hàng đợi công việc. e Khi có tài nguyên sẵn sàng, công việc có độ ưu tiên cao nhất sẽ được lấy ra khỏi hàng đợi để gán việc thực thi vào tài nguyên này. e Khi có nhiều tài nguyên sẵn sàng cùng lúc thì tùy từng giải thuật sẽ chọn tài nguyên thích hợp. e Quá trình này được lặp cho đến khi tất cả các công việc trong hàng đợi đều được hoàn thành.
Su khác biệt giữa các giải thuật này là cách tính toán độ ưu tiên cho công việc và cách chọn nguồn tài nguyên để gán.2 Lập lịch các công việc độc lập (Independent task scheduling) 2.1 MET (Minimum Excecution Time) Giải thuật MET [15, 18] dua trên ý tưởng tinh ước lượng thời gian thực thi của mỗi tac vu (task) trên các tài nguyên khác nhau, sau đó gán mỗi tác vụ vào tài nguyên mà nó cho là tốt nhất để thực hiện tác vụ đó, không quan tâm tại thời điểm đó tài nguyên này có sẵn sàng hay chưa. Giải thuật này có nhược điểm là không cân bằng tải sử dụng vì nhiều khả năng tất cả các tác vụ sẽ chỉ được gán vào một tài nguyên có khả năng tính toán mạnh. Vi dụ: Giả sử có hai task cần thực hiện, task thứ nhất có kích thước t, = 120, task thứ hai có kích thước tg = 240. Hai tài nguyên có khả năng lần lượt là m, = 60 và mạ = 80.
Gia sử thời gian thực hiện của task 2 trên tài nguyên 7 là hy = 1; / m¿;. Tinh thời gian thực hiện các tác vụ trên các tài nguyên tương ứng, ta được: Eịi = tị/mị = 120/60 = 2.0, Eyy = ty /my = 120/80 = 1.5, Ey = te/my = 240/80 = 3. có giá trị nhỏ nhất nên ?¡ được gan vào ma. Thực hiện tương tự cho các task còn lại: Bx = ty/m, = 240/60 = 4.0, Bx: = te/my = 240/80 = 3.0, —> Fo có giá trị nhỏ nhất nên ?¿ được gan vào me.
Vậy cả hai task t),t2 đều được gan lần lượt trên mg nên thời gian hoàn thành của chúng là makespan = 1.2 MCT (Minimum Completion Time) MCT la giải thuật kết hop MET và cân bang tải, giải thuật [15, 18] thực hiện gan các công việc cho tài nguyên sao cho công việc đó được hoàn thành sớm nhất. Như vậy, giải thuật này dựa vào thời gian hoàn thành chứ không dựa vào thời gian thực thi, khi đó tài nguyên tốt chưa chắc được chọn vì nó dang bận thực thi một tác vụ nào đó (có xét đến thời điểm để một task có thể bắt đầu thực thi). Ví dụ: Cũng với các giả sử có các task và tài nguyên giống trong ví dụ ở phần 2. Gia sử thời gian hoàn thành của task ¿ trên tài nguyên j là 1;; = S; + Ej; với S; là thời điểm có thể bắt đầu thực hiện một task trên tài nguyên j va Ej; = tị/m; là thời gian thực hiện task 7 trên tài nguyên 7.
Tinh thời gian hoàn thành các tác vụ trên các tài nguyên tương ứng, giả sử ban đầu tất cả các tài nguyên đều sẵn sàng ở thời điểm bắt đầu là 0: Fy = 6+ En =0+t1/m, = 120/60 = 2.0, Fy = S; + Ey =0 + te/m, = 240/60 = 4.0, Fyy = So + Ea = 0 +t1/my = 120/80 = 1.5, Foy = Sy + Eon = 0 + te/my = 240/80 = 3. có giá trị nhỏ nhất nên ¡ được gấn vào mz, đồng thời cập nhật So = 1. Lap lại các bước thực hiện với các task còn lại: Fy = 6 + Ey =0 + te/m, = 240/60 = 4.0, Fog = Sp + Egg = 1.5, —> Fy, có giá trị nhỏ nhất nên ?¿ được gan vào my, cập nhật S; = 4. Vậy thời gian hoàn thành của hai task ft, tg là makespan = max {1.3 Min-Min, Max-Min Thuật giải Min-Min [15, 18] sử dung ma trận Minimum Completion Time.
Ở mỗi bước tính, giải thuật ước lượng thời gian hoàn thành của tất cả các task trên tat cả các tài nguyên hiện có. Task nào được gáấn việc thực thi vào tài nguyên tương ứng có thời gian hoàn thành sớm nhất sẽ được chọn. Sau đó xét lại từ đầu các task và tiếp tục như vậy cho đến khi hoàn thành gán tất cả các task. Ví dụ: Cũng với giả sử giống ví dụ ở phần 2.2, giải thuật Min-Min sẽ thực hiện các bước như sau: Tính thời gian hoàn thành của task ? trên các tài nguyên khác nhau: Fy = $+ Ey =0+t,/m, = 120/60 = 2.0, Fig = Sp + Eig = 04+ t)/me = 120/80 = 1.5, Tính thời gian hoàn thành cua task ty trên các tài nguyên khác nhau: Fo, = S1 + Eo, =0 +f¿/mị = 240/60 = 4.0, Fog = Sp + Egg = 0 + te/me = 240/80 = 3.0, => Trong số các thời gian hoàn thành nhỏ nhất của các tác vụ, chon nhỏ nhất một lần nữa: min {min {F\,, Fig}, min { Fo, F22}} = min {1.
Do đó chon task f¡ gan trên mg, cập nhật giá tri Sp = 1. Lap lại các bước trên cho các task chưa gan còn lại: Fo, = S1 + Eo, =0 +f¿/mị = 240/60 = 4.0, Fog = Sp + Egg = 1.5, Vi chi còn một task tf) nên ty được gan trên tài nguyên m1, do có thời gian hoàn thành thực thi nhỏ nhất. Vậy thời gian hoàn thành hai task ¢,,t2: makespan = max {1. Tương tự như thuật giải Min-Min nhưng Max-Min ưu tiên gan những task có thời gian thực hiện lớn.
Trong những task có thời gian hoàn thành nhỏ, task nào có thời gian thực hiện lớn mà hoàn thành sớm thì ưu tiên được chọn.3 Lập lịch workflow (Dependent task schedul- ing) Lập lich workflow là một quá trình phân bổ việc thực thi của các công việc có sự phụ thuộc lẫn nhau lên các tài nguyên phân tán. Phân phối các tài nguyên phù hợp cho các công việc của workflow sao cho việc thực thi được hoàn thành nhằm đấp ứng hàm mục tiêu nào đó được đặt ra bởi người dùng. Về cơ bản, có hai lớp lập lich workflow: best-effort và QoS constraint [1T]. Chiến lược lập lịch best-efort cố gắng tối thiểu hóa thời gian thực thi workflow, bỏ qua các yếu tố khác như chi phí thuê tài nguyên, thỏa mãn yêu cầu về dịch vụ của người dùng (users’ QoS satisfaction).
Ngược lại, lập lịch QoS contraint thì cố gắng tối đa hóa độ hiệu quả dựa theo các ràng buộc về yêu cầu dịch vụ của người dùng, ví dụ như hoàn thành thực thi trong thời hạn cho phép nhưng tối thiểu được chi phí thuê tài nguyên. Mục sau sẽ trình bày các giải thuật ở các công trình nghiên cứu liên quan đến hai lớp lập lịch workflow này.1 Lập lich best-effort 2.1 HEFT (Heterogeneous Earliest-Finish- Time) Giải thuật HEFT [11] bao gồm hai giai đoạn (phase) chính: (1) tính toán độ ưu tiên của các task (task prioritizing), (2) chọn lựa tài nguyên để thực thi task (selection processor), sắp xếp theo thứ tự về độ ưu tiên của các task và gén bừng task đến tài nguyên tốt nhất để thực thi task ấy với thời gian hoàn thành được nhỏ nhất. O giai đoạn tính toán độ ưu tiên của task được tiến hành bằng cách tinh giá trị rank của task trên workflow DAG được duyệt theo chiều hướng lên (bắt đầu tính giá trị rank của task kết thúc), task của giá trị rank cao nghĩa là có độ ưu tiên cao. Giá trị rank của task được tính dựa trên thời gian trung bình để thực thi task trên tất cA tài nguyên và thời gian trung bình để truyền dẫn dữ liệu sinh ra giữa hai task trên tất cả kết nối của tài nguyên.
Cụ thể giá trị rank của một task được tính theo công thức đệ qui truy hồi như sau: rank(tecit) = 10ezir (2.1b) Trong đó, #zz„ là thời gian trung bình để thực thi task trên tất cả tài nguyên, Gj là thời gian trung bình để truyền dẫn dữ liệu sinh ra giữa hai task trên tất cả kết nối của tài nguyên. Trong giai đoạn chọn lựa tài nguyên, các task được định thời theo thứ tự về độ ưu tiên của chúng và mỗi task được gan vào tài nguyên có khả năng hoàn thành thực thi trong thời gian ước lượng là sớm nhất. Algorithm 1 là mã giả của giải thuật HEFT. Algorithm 1 HEF'T algorithm Input: A workflow DAG G = (U, E).
Compute the average execution time for each task u € U. Compute the average data transfer time between tasks and their successors. Compute rank value for each task. Sort the tasks in a scheduling list Q by decreasing order of task rank value.
while Q 4 @ do u < remove the first task from Q. r < find a resource which can complete œ at earliest time.BMCT (Hybrid heuristic) Giải thuật hybrid heuristic [12] được dé xuất cho việc lập lich các task của work- flow DAG trên hệ phan bố.