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

14 Chương 3. Những nghiên cứu về lập lịch trên môi trường tính toán lưới 3.1 Giới thiệu bài toán lập lịch 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. Quá trình lập lịch trên môi trườ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 vì 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 vẫn còn đòi hỏi nhiều công sức nghiên cứu [5]. Có khá nhiều câu hỏi đượ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 • 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 3.2 Các ứng dụng song song, độc lập Trong môi trường tính toán lưới, lớp bài toán gồm các tác vụ độc lập với nhau hiện đang được tập trung nghiên cứu. Bài toán dạng này là một trong những bài toán đặc trưng, thường thấy trên môi trường lưới [6], thông thường sẽ bao gồm N tác vụ độc lập (các tác vụ này có thể thực thi cùng một chức năng tính toán, nhưng 15 trên các tập dữ liệu khác nhau) chạy trên M máy tính phân tán, N sẽ lớn hơn M nhiều lần. Đây là một mô hình tính toán đơn giản nhưng lại được sử dụng nhiều trong những bài toán lớn và hữu ích: phân tích cấu trúc protein, phân tích hoạt động của não bộ, mô phỏng chuyển động và sự va chạm của một hệ thống, phân tích các dữ liệu vật lý, kinh tế… [11]. Việc lập lịch cho các ứng dụng độc lập tưởng chừng như đơn giản, tuy nhiên khi kết hợp vào một số yêu cầu của người dùng như ràng buộc về thời hạn kết thúc (deadline), chi phí hoạt động (budget) và một vài yêu cầu riêng biệt khác sẽ trở thành một bài toán lớn và khá phức tạp. Luận văn cũng sẽ tập trung nghiên cứu các bài toán gồm nhiều tác vụ song song, có thể thực thi hoàn toàn độc lập với nhau trong quá trình hoạt động như hình 3-1 Hình 3-1 Mô hình ứng dụng: các tác vụ độc lập 3.3 Các hướng nghiên cứu trong bài toán lập lịch Hầu hết mọi nghiên cứu về lập lịch trên môi trường lưới ngày nay đều nhắm vào hai mục tiêu: (a) performance-base: tận dụng tối đa hiệu năng của hệ thống, giảm thiểu thời gian hoạt động; (b) economics-base: giảm thiểu chi phí hoạt động của hệ thống [7]. Việc tận dụng tối đa hiệu năng của hệ thống, đưa thời gian cần thiết để giải quyết công việc xuống mức mức thấp nhất là một nhu cầu thực tế, là yếu tố được nghĩ đến đầu tiên khi triển khai ứng dụng trên môi trường lưới. Do đó hiển nhiên đây là một hướng nghiên cứu quan trọng. 16 Ngoài ra, việc lập lịch theo chi phí vận hành hệ thống cũng là một hướng nghiên cứu cần thiết trong thực tế, nhất là trong những hệ thống lưới đã được thương mại hóa. Người sử dụng muốn thực thi ứng dụng của mình trên môi trường lưới cần phải trả phí (phí này có thể tính trên thời gian thực thi của ứng dụng- cost per time, hoặc tính trên số thao tác tính toán của ứng dụng – cost per instruction, tùy theo chính sách của người quản trị tài nguyên qui định). Việc qui định chi phí thực thi sẽ khuyến khích những tổ chức có tài nguyên rảnh (idle resources) tham gia vào hệ thống, mở rộng qui mô hệ thống lưới và việc phân bố các tác vụ sao cho chi phí thực thi thấp nhất là một nhu cầu thiết thực với người sử dụng trên môi trường tính toán lưới. 3.4 Lập lịch theo hiệu năng hệ thống Như đã trình bày, các nghiên cứu dạng 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. Có nhiều hướng tiếp cận khác nhau được đề cập đến trong nghiên cứu [8],[9]: OLB, MCT, Min-Min, Max-Min, Sufferage… 3.4.1 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 đó. 3.4.2 MET (Minimum Execution Time) 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 đó. Thuật giải 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 Ví dụ: 17 Giả sử ta có 2 tác vụ cần thực thi là T1,T2. Các tác vụ lần lượt có kích thước T1=60, T2=120. Hệ thống có 2 máy tính cụm, mỗi máy tính cụm có 2 máy tính (host), năng lực lần lượt là: Cluster 1: H1=30, H2=60 Cluster 2: H3=45, H4=50 Gọi Eij = Ti/Hj là thời gian thực thi của tác vụ i trên host j, ta có: E11=T1/H1=2 E21=T2/H1=4 E12=T1/H2=1 (nhỏ nhất) E22=T2/H2=2 (nhỏ nhất) E13=T1/H3=1.3 E23=T2/H3=2.6 E14=T1/H4=1.2 E24=T2/H4=2.4 Như vậy cả 2 tác vụ đều thực thi trên host H2, makespan của hệ thống = 1 + 2 = 3 3.4.3 MCT (Minimum Completion Time) Dựa trên khái niệm thời gian hoàn thành nhỏ nhất của tác vụ. Thời gian hoàn thành được tính bằng thời gian thực thi của tác vụ cộng với thời gian sẵn sàng của tài nguyên. Việc dựa trên thời gian hoàn thành nhỏ nhất sẽ giúp hệ thống cân bằng tải tốt hơn. Ví dụ: Các số liệu tương tự như mục 3.4.2, ta định nghĩa Cij = Bj + Eij với Cij là thời gian hoàn thành của tác vụ i trên host j, Bj là thời gian sớm nhất host j có thể thực thi tác vụ (thời gian sẵn sàng). C11= B1 + E11 = 0 + 2 = 2 C21= B1 + E21 = 0 + 4 =4 C12= B2 + E12 = 0 + 1 = 1 C22= B2 + E22 = 0 + 2 =2 C13= B3 + E13 = 0 + 1.3 = 1.3 C23= B3 + E23 = 0 + 2.6 = 2.6 C14 =B4 + E14 = 0 + 1.2 = 1.2 C24 = B4 + E24 = 0 + 2.4 = 2.4 18 Tác vụ T1 theo thứ tự được chọn tài nguyên trước, sẽ chọn thực thi trên host H2 (thời gian hoàn thành thấp nhất). Thời gian bắt đầu B2 được cập nhật thành 1, vì chỉ sau thời điểm này H2 mới có thể thực thi các tác vụ khác. Giá trị E22 thay đổi: B2=1 C22 = B2 + E22= 1 + 2 = 3 > 2.4 Như vậy tác vụ T2 sẽ thực thi trên Host H4 vì có C24 nhỏ nhất Thời gian thực thi toàn hệ thống makespan = 2.4 vì T1, T2 chạy song song trên 2 host khác nhau. Chúng ta có thể thấy, dựa vào giá trị MCT hệ thống sẽ cân bằng hơn dựa vào giá trị MET. 3.4.4 Thuật giải Min – Min Thuật giải Min – Min sẽ tính toán thời gian hoàn thành của tất cả các tác vụ trên tất cả các tài nguyên hiện có. Tác vụ nào có giá trị MCT nhỏ nhất sẽ được phép chọn tài nguyên trước. Sau đó cập nhật thời gian sẵn sàng cho tài nguyên được chọn, tính toán lại thông số với tất cả các tác vụ chưa được điều phối. Quá trình lặp lại cho đến khi tất cả các tác vụ đều đã chọn được tài nguyên thực thi. Ta định nghĩa một số khái niệm: T là tập các tác vụ, Hj,k là máy (host) thứ k của cluster j. C(Ti,Hj,k) là thời gian hoàn thành tác vụ Ti trên host Hj,k. Gọi f là một ánh xạ từ Rn vào R, toán tử argmin được định nghĩa: f(argminxєRn f(x))=minxєRn(f(x)) Chú thích: Gía trị C(Ti,Hj,k) là thời gian hoàn thành của tác vụ Ti trên host Hj,k. Lúc này nếu argminj,k(C(Ti,Hj,k)) gồm 2 thành phần (ܿ௜ଵ ,  ݄௜ଵ ) thì giá trị C(Ti,  ܪ௖೔భ,௛೔భ )) là nhỏ nhất. Host ݄௜ଵ trên cluster ܿ௜ଵ là host có khả năng hoàn tất tác vụ Ti sớm nhất. Thuật giải Min-Min: 19 Ví dụ, với các số liệu như mục 3.4.2 C11= B1 + E11 = 0 + 2 = 2 C21= B1 + E21 = 0 + 4 =4 C12= B2 + E12 = 0 + 1 = 1 (min) C22= B2 + E22 = 0 + 2 =2 (min) C13= B3 + E13 = 0 + 1.3 = 1.3 C23= B3 + E23 = 0 + 2.6 = 2.6 C14 =B4 + E14 = 0 + 1.2 = 1.2 C24 = B4 + E24 = 0 + 2.4 = 2.4 Giá trị MCT(T1)= C12 =1 , MCT(T2)=C22=2 MCT(T1) nhỏ hơn, do đó tác vụ T1 được chọn host H1 để thực thi trước. Giá trị E22 thay đổi: B2=1 C22 = B2 + E22= 1 + 2 = 3 > 2.4 Như vậy tác vụ T2 sẽ thực thi trên Host H4 vì có C24 nhỏ nhất Thời gian thực thi toàn hệ thống makespan = 2.4 vì T1, T2 chạy song song trên 2 host khác nhau. 3.4.5 Thuật giải Max-Min Tương tự như thuật giải Min-Min, tuy nhiên thuật giải Max-Min cho phép các tác vụ có MCT lớn hơn được ưu tiên chọn host để thực thi trước. Thuật giải này được đánh giá tốt và cân bằng hơn Min-Min vì trong khi các tác vụ dài hơn được ưu tiên chọn thiết bị tốt để thực thi trước, các tác vụ ngắn có thể luân phiên thực thi ở while (T≠Ø) foreach(TiєT) (ܿ௜ଵ, ݄௜ଵ)=argminj,k(C(Ti,Hj,k)) end foreach s=argmini(C(Ti, ܪ௖೔భ,௛೔భ)) assign Ts to ܪ௖ೞభ,௛ೞభ T = T – {Ts} end while 20 các thiết bị có năng lực yếu hơn. Các tác vụ dài không phải mất thời gian chờ các tác vụ ngắn hơn như ở thuật giải Min-Min. Toán tử argmax được định nghĩa tương tự toán tử argmin f(argmaxxєRn f(x))=maxxєRn(f(x)) Thuật giải Max-Min: Ví dụ: Cũng với các số liệu như mục 3.4.2 C11= B1 + E11 = 0 + 2 = 2 C21= B1 + E21 = 0 + 4 =4 C12= B2 + E12 = 0 + 1 = 1 (min) C22= B2 + E22 = 0 + 2 =2 (min) C13= B3 + E13 = 0 + 1.3 = 1.3 C23= B3 + E23 = 0 + 2.6 = 2.6 C14 =B4 + E14 = 0 + 1.2 = 1.2 C24 = B4 + E24 = 0 + 2.4 = 2.4 Giá trị MCT(T1)= C12 =1 , MCT(T2)=C22=2 Lúc này tác vụ T2 có MCT lớn hơn nên được phép chọn host thực thi trước. T2 sẽ thực thi trên host H2. Giá trị B2 = 2 C12 = B2 + E12 = 2 + 1 =3 > 1.2 Như vậy, sau đó tác vụ T1 sẽ thực thi trên host H4 vì lúc này C14 = 1.2 là nhỏ nhất while (T≠Ø) foreach(TiєT) (ܿ௜ଵ, ݄௜ଵ)=argminj,k(C(Ti,Hj,k)) end foreach s=argmaxi(C(Ti, ܪ௖೔భ,௛೔భ)) assign Ts to ܪ௖ೞభ,௛ೞభ T = T – {Ts} end while 21 Thời gian hoàn thành của hệ thống makespan = 2 vì T1, T2 chạy song song (nhỏ hơn với trường hợp Min-Min) 3.4.6 Thuật giải Sufferage Suferage lấy ý tưởng từ thuật giải Min-Min và Max-Min đã đề ra trước đó. Thuật giải Sufferage tính toán giá trị MCT thấp nhát và thấp nhì đối với từng tác vụ trong hệ thống. Giá trị này được gọi là độ “thiệt hại” (suffering) của một tác vụ khi nó không được thực thi trên tài nguyên tốt nhất. Tác vụ có độ thiệt hại lớn nhất sẽ được ưu tiên chọn tài nguyên để thực thi trước. Thuật giải Sufferage: Thuật giải này đặc biệt hiệu quả nếu tính đến vấn đề vận chuyển dữ liệu đến nơi thực thi tác vụ. Nếu một tài nguyên đã có sẵn dữ liệu của một tác vụ, tác vụ nếu thực thi trên tài nguyên này sẽ tiết kiệm được thời gian rất nhiều so với khi thực thi trên một tài nguyên khác. Tác vụ trong trường hợp này sẽ có giá trị Sufferage cao nên được ưu tiên thực thi trước. Ví dụ: Cũng với các số liệu như mục 3.4.2 C11= B1 + E11 = 0 + 2 = 2 C21= B1 + E21 = 0 + 4 =4 while (T≠Ø) foreach(TiєT) (ܿ௜ଵ, ݄௜ଵ)=argminj,k(C(Ti,Hj,k)) (ܿ௜ଶ, ݄௜ଶ)=argminj≠ci1,k≠hi1(C(Ti,Hj,k)) sufi=C(Ti,Hci2, hi2)-C(Ti, Hci1, hi1) end foreach s=argmaxi(sufi) assign Ts to ܪ௖ೞభ,௛ೞభ T = T – {Ts} end while 22 C12= B2 + E12 = 0 + 1 = 1 (min) C22= B2 + E22 = 0 + 2 =2 (min) C13= B3 + E13 = 0 + 1.3 = 1.3 C23= B3 + E23 = 0 + 2.6 = 2.6 C14 =B4 + E14 = 0 + 1.2 = 1.2 C24 = B4 + E24 = 0 + 2.4 = 2.4 Giá trị Suff(T1)= C14 – C12 = 0.2 Giá trị Suff(T2)= C24 – C22 = 0.4 Vì suff(T2) cao hơn nên tác vụ T2 được phép chọn host H2 để thực thi trước. Giá trị B2 = 2 C12 = B2 + E12 = 2 + 1 = 3 > 1.2 Như vậy, sau đó tác vụ T1 sẽ thực thi trên host H4 vì lúc này C14 = 1.2 là nhỏ nhất Thời gian hoàn thành của hệ thống makespan = 2 vì T1, T2 chạy song song. Ví dụ ở trên khá đơn giản, chỉ có chiều dài tác vụ ảnh hưởng đến thời gian thực thi của tác vụ nên trường hợp Sufferage khá giống Max – Min. 3.4.7 Thuật giải XSufferage Do nhóm nghiên cứu Casanova đề ra [10], phát triển từ thuật toán Sufferage. Các máy tính trong một Máy tính cụm thường có năng lực như nhau, do đó giá trị sufferage thường dần về 0. Điều này khiến một tác vụ Ti, khi rất cần chạy trên máy tính cụm j (ví dụ dữ liệu input của Ti đã nằm sẵn trên máy tính cụm j), nhưng trong trường hợp máy tính cụm này lại có 2 máy năng lực tương đương nhau khiến Suff(Ti) ≈ 0 nên Ti sẽ không có cơ hội chạy trên máy tính cụm j. Cải tiến ở đây là khái niệm Suf sẽ được tính ở mức cluster, không phải ở mức host. Thuật giải XSufferage: while (T ≠ Ø) foreach (Ti є T) foreach cluster j hi,j=argmink(C(Ti,Hj,k)) end foreach ܿ௜ ଵ = argminj(C(Ti,H௝,௛೔,ೕሻሻ //Cluster có MCT nhỏ nhất 23 ܿ௜ ଶ = argmin௝ஷ௖೔భ(C(Ti,H௝,௛೔,ೕሻሻ //Cluster có MCT nhỏ nhì sufi = C(Ti,ܪ௖೔మ,௛೔,೎೔మ ሻ െ CሺTi, ܪ௖೔భ,௛೔,೎೔భ ሻ //Tính suf trên 2 cluster nhỏ nhất và nhì end foreach s=argmaxi(sufi) assign Ts to ܪ௖ೞభ,௛ೞ,೎ೞభ T=T-{Ts} end while Đặc điểm các thuật giải trên: ™ Phải duyệt tất cả các máy trong mọi máy tính cụm có thể dẫn đến độ phức tạp rất lớn ™ Ứng dụng là ứng dụng rất lớn gồm rất nhiều tác vụ chạy song song, các tác vụ đóng vai trò như sau. ™ Một task có thể chạy trên host bất kỳ, không có sự ràng buộc về địa điểm thực thi. 3.4.8 Các thuật giải điều phối cho các ứng dụng vừa và nhỏ Tác giả Trần Công Tú trong luận văn nghiên cứu về lập lịch [20] đã đề xuất một giải pháp lập lịch cho các ứng dụng vừa và nhỏ trong hoàn cảnh Việt Nam. Tác giả đã tập trung gom nhóm mỗi ứng dụng con lên một máy tính cụm, ưu tiên hoàn thành từng ứng dụng một cách nhanh nhất, trước khi tiếp tục cho các ứng dụng chưa được phân tài nguyên. Đây cũng là một hướng tiếp cận mà luận văn này kế thừa và tập trung nghiên cứu sâu hơn. 24 3.5 Lập lịch theo hiệu năng kinh tế Với bài toán lập lịch này, thay vì chỉ chú trọng đến thời gian thực thi của hệ thống ta còn phải quan tâm đến một khía cạnh không kém quan trọng là hiệu quả về mặt kinh tế của hệ thống. Mỗi tác vụ lúc này sẽ có hai ràng buộc đi kèm: - Deadline: thời hạn thực thi cuối cùng của tác vụ, tác vụ phải được thực thi xong trước thời điểm này - Budget: ngân sách của tác vụ, chi phí thực thi tác vụ phải nhỏ hơn ngân sách của tác vụ đó. Việc nghiên cứu về bài toán lập lịch dạng này nhìn chung phức tạp hơn ở trường hợp chỉ chú trọng đến thời gian thực thi, vì bây giờ mỗi tác vụ cần thỏa mãn cùng lúc 2 ràng buộc. Cũng đã có khá nhiều nghiên cứu về các thuật giải lập lịch có chú trọng đến hiệu năng kinh tế của hệ thống 3.5.1 Time Minimization Thuật giải Time Minimization [3] đặt mục tiêu hoàn thành các công việc một cách nhanh nhất có thể trong điều kiện ràng buộc của ngân sách (Budget). Thuật giải có thể được mô tả như sau: • Lấy ra một tác vụ chưa được điều phối: o Với mỗi tài nguyên, tính toán thời gian hoàn thành cho tác vụ đó (đã xem xét đến các tác vụ đang có sẵn tại tài nguyên này trước đó) o Sắp xếp các tài nguyên theo thời gian hoàn thành tăng dần o Điều phối tác vụ vào tài nguyên đầu tiên thỏa mãn ràng buộc (chi phí thực thi trên tài nguyên đó thấp hơn hoặc bằng ngân sách của tác vụ) • Lập lại cho đến khi tất cả các tác vụ đều được điều phối 25 3.5.2 Cost Minimization Thuật giải Cost Minimization [3] đề ra hướng tiếp cận khác so với Time Minimization, tập trung thực thi các tác vụ sao cho chi phí là thấp nhất trong điều kiện ràng buộc về thời điểm kết thúc (Deadline). Thuật giải được mô tả như sau: • Sắp xếp các tài nguyên theo chi phí thực thi tăng dần • Với mỗi tài nguyên theo thứ tự đó, điều phối tối đa số lượng tác vụ lên tài nguyên trong khi chưa vi phạm ràng buộc về Deadline. Cả hai thuật giải này đều chưa chú ý đến việc sắp xếp thứ tự các tác vụ được điều phối và broker phải làm việc trực tiếp với từng tài nguyên trong hệ thống dẫn đến thời gian điều phối có thể rất lớn. 3.5.3 DBC (Deadline and Budget constrained scheduling) Thuật giải DBC [11] được nhóm nghiên cứu Buyya cải tiến dựa trên thuật giải Time Minimization và Cost Minimization, nhắm đến mục tiêu không chỉ tối ưu về chi phí phát sinh mà còn giảm thiểu thời gian thực thi khi điều kiện cho phép. Thuật giải có thể được mô tả như sau: • Sắp xếp các tài nguyên theo giá thành tăng dần, nếu các tài nguyên có cùng chi phí ưu tiên cho các tài nguyên có năng lực tính toán mạnh hơn xếp trước. • Tạo thành các nhóm tài nguyên bao gồm các tài nguyên có cùng chung giá thành • Khi còn tác vụ chưa được điều phối, thực hiện các bước sau với mỗi nhóm tài nguyên: o Ứng với mỗi tác vụ trong tập các tác vụ chưa điều phối: ƒ Với mỗi tài nguyên trong nhóm, tính toán thời gian hoàn thành của tác vụ trên tài nguyên đó ƒ Điều phối tác vụ cho tài nguyên có khả năng hoàn thành tác vụ đó sớm nhất, đánh dấu tác vụ đã được điều phối. 26 ƒ Nếu không có tài nguyên thỏa mãn ràng buộc, tác vụ được giữ nguyên và sẽ tìm kiếm tài nguyên trong các nhóm tài nguyên có giá thành cao hơn. Thuật giải sẽ chia tài nguyên thành các nhóm có giá thành ngang nhau, tìm kiếm tài nguyên tốt nhất trong một nhóm. Khi không thỏa mãn mới chuyển sang nhóm có giá thành cao hơn. Thuật giải đã cố gắng tạo sự cân bằng giữa 2 yếu tố chi phí và thời gian thực thi. 3.5.4 HRED (Highest Rank Earliest Deadline) Được đề ra bởi nhóm nghiên cứu Subodha Kumar và Kaushik Dutta [7], với mục tiêu giảm thiểu chi phí thực thi của hệ thống trong điều kiện ràng buộc về thời gian. Nhóm nghiên cứu tiếp cận bài toán lập lịch theo quan điểm một hệ bất phương trình. Tuy nhiên việc giải một hệ bất phương trình dẫn đến thời gian tính toán quá dài, không khả thi trong thực thế. Nhóm nghiên cứu đề ra thuật giải HRED (Highest Rank Earliest Deadline) nhằm ứng dụng được trong thực tế. Theo các số liệu thực nghiệm của nhóm nghiên cứu, kết quả của thuật giải HRED có chênh lệch khoảng 3% - 4% so với việc giải hệ bất phương trình. Một số qui ước: • tij: thời gian thực thi của tác vụ i trên tài nguyên thứ j. • pj: giá thành của tài nguyên j • Bi: ngân sách của tác vụ i • Li: khoản tiền phải bồi thường khi từ chối thực thi tác vụ i. Tham số này đại diện cho độ ưu tiên của một tác vụ, tác vụ có khoản tiền phạt càng cao càng được hệ thống ưu tiên thực thi. Qui định Li ≥ Bi (khoản tiền phạt lớn hơn ngân sách của một tác vụ). • Vij = (Li – tijpj) là hiệu số của khoản tiền phạt so với chi phí thực thi tác vụ i trên tài nguyên j. Khi hệ thống từ chối một tác vụ Ti, ta có thể tiết kiệm được 27 một phần chi phí thực thi tác vụ tijpj nhưng phải trả khoản tiền phạt Li. Có thể xem Vij là khoản chi phí hệ thống bị thiệt hại khi từ chối thực thi tác vụ Ti. Thuật giải HRED sẽ chú trọng làm cho các khoản thiệt hại này là bé nhất. Thuật giải được mô tả như sau: Bước 1: Tính toán giá trị Vij = (Li – tijpj) cho mỗi tác vụ i và tài nguyên j, sắp xếp tập giá trị V theo thứ tự Vij giảm dần. Bước 2: Xóa bỏ các giá trị Vij âm vì khi đó tijpj > Bi (vì Li ≥ Bi) Bước 3: Gọi ViMax jMax là giá trị lớn nhất trong tập V, T là tập các tác vụ hiện đã được điều phối trên tài nguyên jMax. Bước 4: Tập T’ là kết hợp tác vụ iMax và tập tác vụ T, sắp xếp T’ theo Deadline tăng dần. Cố gắng thực thi tập tác vụ T’ trên tài nguyên jMax theo thứ tự đã sắp xếp. Nếu tập T’ có thể thực thi thành công mà không vi phạm các ràng buộc về giá và thời gian thì tác vụ iMax có khả năng thực thi trên tài nguyên jMax. Bước 5: Nếu điều kiện ở bước 4 thỏa mãn, điều phối tác vụ iMax cho tài nguyên jMax. Xóa bỏ tất cả các tổ hợp của iMax trong tập V. Bước 6: Nếu tập tác vụ V còn tác vụ chưa điều phối, quay trở lại bước 3. Độ phức tạp O(m2nlogm) 3.5.5 Các mô hình thường áp dụng trong bài toán lập lịch theo hiệu năng kinh tế Để phục vụ cho bài toán lập lịch theo hiệu năng kinh tế, có nhiều mô hình đã được đề ra. Các mô hình này đều hoạt động dựa trên quá trình giao tiếp giữa người mua (user) và người bán (resource) nhằm tìm ra chi phí, thời gian thực thi công việc: • Thông thường người mua sẽ mô tả thông tin về ứng dụng: chiều dài, deadline, các yêu cầu đặc biệt về phần cứng, phần mềm. • Người bán dựa trên tài nguyên sẵn có, các công việc hiện đang thực thi, thông tin về ứng dụng do người dùng cung cấp sẽ gửi lời chào giá cho người dùng. 28 Hình 3-2 Hoạt động của hệ thống lưới theo cơ chế chào giá Hình 3-2 mô tả quá trình hoạt động của một hệ thống tiêu biểu dạng này: Người sử dụng sẽ nhờ Broker thực thi các công việc của mình. Broker ở đây đóng vai trò người mua, dựa vào thông tin từ Grid Information Server để biết danh sách các tài nguyên trong hệ thống. Broker sẽ liên lạc với các tài nguyên để yêu cầu chào giá. Quá trình trading tùy theo môi trường sẽ có những thay đổi, nhưng nhìn chung là quá trình chào giá từ phía người bán cho người mua. Từ các thông tin này, người mua sẽ quyết định lựa chọn người bán nào phù hợp nhất. Nhóm tác giả Buyya đã đề ra một số mô hình kinh tế tiêu biểu trong môi trường lưới [12]: - Mô hình commodity market: Các tài nguyên sẽ niêm yết sẵn các thông số về chi phí thực thi của mình. Chi phí có thể được tính theo chiều dài công việc, thời gian thực thi, các yêu cầu đặc biệt về hệ thống… Người mua liên hệ với hệ thống, dựa vào thông tin giá cả để quyết định sẽ lựa chọn tài nguyên nào để sử dụng. - Mô hình posted price: Tương tự như mô hình commodity, tuy nhiên người bán còn thông báo bổ sung các thông tin về các chính sách giảm giá hoặc chính sách đặc biệt theo thời vụ, ví dụ như giảm chi phí thực thi vào các ngày cuối tuần, ban đêm... Người dùng có thể dùng thêm các thông tin này để lựa chọn tài nguyên phù hợp nhất. 29 - Mô hình bargaining: Sau khi lựa chọn được tài nguyên phù hợp, người dùng có thể liên lạc với tài nguyên để thống nhất về chi phí. Chi phí không còn cố định mà sẽ tuân theo quá trình trả giá của hai bên. Người dùng mong muốn có chi phí thấp hơn, người bán mong muốn một giá thành cao hơn. Cả hai sẽ ngả giá cho đến khi đạt được một mức giá thỏa thuận hoặc một trong hai bên không còn muốn tham gia vào quá trình ngả giá. - Mô hình tender/contract: Người dùng sẽ nêu yêu cầu về công việc và quảng bá trên toàn hệ thống, các tài nguyên sẽ chào giá tốt nhất mình có thể đáp ứng. Người dùng lựa chọn tài nguyên thích hợp nhất và ký các cam kết với tài nguyên (contract). Nếu tài nguyên vi phạm, không thực thi được ứng dụng sẽ phải trả tiền phạt. - Mô hình auction: Quá trình ngược lại với mô hình trên. Người bán sẽ chủ động rao bán các tài nguyên rảnh của mình, người dùng nếu muốn sử dụng sẽ phải đấu giá. Người dùng chiến thắng sẽ được sử dụng nguồn tài nguyên để thực thi các ứng dụng của mình. - Mô hình bid-based proportional resource sharing: Tương tự như mô hình trên, tuy nhiên các người dùng sẽ chia sẻ sử dụng chung tài nguyên, tỉ lệ chia sẻ dựa theo tỉ lệ chi phí chấp nhận trả trong các đấu giá của người dùng. 3.5.6 Lập lịch mô phỏng cơ chế thị trường Một trong những thử thách khi đề ra các mô hình trong bài toán lập lịch là làm thể nào để thỏa mãn được nhu cầu của cả người dùng (bên mua) lẫn các tổ chức cung cấp tài nguyên (người bán). Nhóm nghiên cứu của Zhiwei Xu đã đề ra một mô hình nhắm đến việc đồng thời thỏa mãn lợi ích cho cả hai nhóm đối tượng, vận hành mô phỏng theo cơ chế thị trường (market-like) trong thực tế [13] và theo nguyên tắc chào giá tender/contract đề cập ở mục 3.5.4. Hệ thống nhắm đến 2 mục tiêu: • Đối với người dùng, hệ thống sẽ tập trung nâng cao tỉ lệ thực thi thành công các ứng dụng. Định nghĩa 30 ߠ ൌ ∑ ఠ೔బರ೔ಬ೙ ௡ với ߱௜ ൌ ቊ 1, ݊ếݑ  ஼ܶ௜  ൑   ஽ܶ௜   0, ݊ếݑ  ஼ܶ௜ ൐   ஽ܶ௜ trong đó ஼ܶ௜  và  ஽ܶ௜ là thời gian hoàn thành và Deadline của tác vụ Ti Mục tiêu của thuật giải là nâng cao tối đa hiệu năng θ • Đối với các tài nguyên: Bảo đảm nếu các tài nguyên đóng góp cho hệ thống một phần năng lực tương đương nhau thì lợi nhuận thu được cũng sẽ tương đương. Sự công bằng về lợi nhuận được đảm bảo bởi khái niệm độ lệch chuẩn, được định nghĩa: ߪ ؜ ݏݐ݀ௗ௘௩ሺ∆బ,… ,∆೘షభሻ, ݒớ݅ ∆௝ൌ ௝ܲ/∑ ௟ܲ଴ஸ௟ழ௠ ܥ௝/∑ ܥ௟଴ஸ௟ழ௠ Trong đó: Cj và Pj lần lượt là năng lực và lợi nhuận của tài nguyên Rj Thuật giải sẽ chú ý giảm tối đa độ lệch ߪ để bảo đảm công bằng cho các tài nguyên. Hướng tiếp cận của nhóm theo mô hình peer-to-peer, mỗi người dùng cũng như mỗi tài nguyên là một node trong hệ thống. Hình 3-3 Mô hình hoạt động hệ thống theo cơ chế thị trường Khi một người dùng có nhu cầu thực thi công việc sẽ công bố thông tin về công việc này rộng rãi trên phạm vi toàn hệ thống (dưới dạng các job announcement). Các tài nguyên nếu có thê đáp ứng sẽ hồi đáp và đấu giá. Tài nguyên tốt nhất sẽ được nhận công việc. 31 Hình 3-4 Quá trình quảng bá application và chào giá Có một đặc điểm mới được đề cập đến trong nghiên cứu: Khi một tài nguyên nhận được một mô tả công việc, tài nguyên sẽ tính toán và đưa ra lời chào giá. Tài nguyên chưa chắc chắn sẽ nhận được công việc này, nên công việc sẽ tạm được gọi là các công việc chưa được phản hồi (unconfirmed job). Nếu sau đó, một công việc khác lại được gửi đến tài nguyên để tính toán chào giá, sẽ có 2 tình huống xảy ra: Nếu tài nguyên tính toán dựa trên việc xem xét cả những công việc mà nó chưa được phản hồi, rất có thể sẽ không đáp ứng được công việc mới này và phải từ chối đưa ra lời chào giá. Nếu tài nguyên không tính đến các công việc chưa được phản hồi, sẽ đáp ứng và chào giá cho công việc mới. Khi đó có thể cả 2 công việc sẽ được gửi cho tài nguyên thực thi, dẫn đến việc tài nguyên sẽ vi phạm thời hạn deadline và phải trả một khoản tiền phạt cho người dùng. Nghiên cứu cũng đề cập và khảo sát đến những tham số trong trường hợp này. Đây là một nghiên cứu rất mới, đặt ra nhiều vấn đề mới nhưng cũng có một số điểm cần bàn bạc thêm: - Mỗi người dùng đều tham gia vào hệ thống Peer-2-Peer mới có thể thực thi công việc, do đó người dùng cũng như mọi tài nguyên phải sử dụng chung những giao thức đã được chuẩn hóa. Điều này là khá phức tạp, nhất là đối 32 với các hệ thống lưới được xây dựng chưa lâu. Trong khi với các môi trường cũ, người dùng không nhất thiết tham gia vào môi trường lưới mà sẽ thực thi các ứng dụng thông qua các cổng vào (portal). - Có những vấn đề về phạt khi tài nguyên đã chào giá (cam kết) nhưng lại vi phạm thời gian thực thi, điều này đòi hỏi hệ thống lưới phải có những luật qui định chặt chẽ và có những chính sách về điều hành, quản lý chặt - Để đảm bảo cân bằng về lợi nhuận đối với các tài nguyên, các tài nguyên không được tự ấn định chi phí mà chỉ được giao động xung quanh một chi phí chuẩn của hệ thống. Điều này có thể dẫn đến việc không công bằng giữa các tài nguyên có chi phí vận hành lớn. 3.6 Một số dự án về lập lịch đã được triển khai thực tế Hiện nay đã có một số dự án về lập lịch trên môi trường lưới đã được triển khai trên thực tế. Nimrod/G [3],[11]: Nimrod là một broker quản lý và lập lịch cho hệ thống tài nguyên phân tán. Nimrod/G là phiên bản sau của Nimrod, vận hành trên môi trường lưới. Nimrod/G hỗ trợ định nghĩa các ràng buộc về thời điểm kết thúc (deadline) và chi phí thực thi (cost) cho các ứng dụng. Trên môi trường Nimrod, người dùng được cung cấp một ngôn ngữ đặc tả đơn giản để mô tả các ràng buộc của ứng dụng. Nimrod ban đầu được xây dựng để hoạt động trên nền tảng Globus, tuy nhiên ngày nay đã có thể vận hành được trên các môi trường khác. Các thuật giải Cost minimization và Time minimization đã được thử nghiệm trên môi trường Nimrod Condor [14]: Condor là hệ thống broker tương đối hoàn chỉnh phục vụ cho các ứng dụng đòi hỏi thời gian tính toán cao. Condor cung cấp các cơ chế quản lý hàng đợi công việc, các chính sách lập lịch, theo dõi tài nguyên và quản lý tài nguyên. Ứng dụng khi được gửi đến Condor sẽ được đưa vào hàng đợi, sau đó Condor dựa vào các chính sách về lập lịch sẽ quyết định thời điểm và nguồn tài nguyên sẽ thực thi ứng dụng, theo dõi các ứng dụng trong quá trình thực thi và thông báo cho người dùng khi ứng dụng hoàn tất. Cũng như Nimrod, ban đầu Condor chỉ có thể chạy 33 trên môi trường cluster nhưng phiên bản Condor/G được ra đời sau đã hoàn toàn hỗ trợ môi trường lưới. Hiện tại Condor/G có thể vận hành trên hệ thống Globus. Gridbus Broker [15],[16]: Gridbus Broker là một dự án con trong bộ dự án Gridbus được nghiên cứu phát triển bởi đại học Melbourne, Úc. Gridbus Broker hỗ trợ người dùng truy xuất các tài nguyên phân tán qua hàng loạt các cơ chế: phát hiện tài nguyên phù hợp với yêu cầu của ứng dụng, phụ trách việc chuyển dữ liệu và toàn bộ ứng dụng đến tài nguyên để thực thi, thực thi ứng dụng và giám sát kiểm tra lỗi trong quá trình thực thi, hỗ trợ ứng dụng truy xuất các nguồn dữ liệu ở các máy từ xa, tổng hợp và hiển thị kết quả thực thi. Gridbus Broker thực thi rất tốt trên môi trường Globus Apples [17]: Trong môi trường Apples, mỗi ứng dụng sẽ có riêng một broker giúp ứng dụng lựa chọn ra tài nguyên tốt nhất. Do đó môi trường Apples còn được xem như tiếp cận theo hướng application-level scheduling. Do các ứng dụng khác nhau sẽ có những yêu cầu khác nhau, hiện tại Apples chỉ mới hỗ trợ tốt nhất cho nhóm ứng dụng thuộc phân lớp parameter sweep [6],[11]. Apples hỗ trợ cơ chế quản lý lỗi khá mạnh, khi một ứng dụng bị lỗi trong quá trình thực thi sẽ được tự động chuyển sang thực thi tại các tài nguyên khác.