Luận văn Nghiên cứu và phát triển giải thuật định thời cho lớp bài toán parameter sweep trên môi trường tính toán lưới

8 Chương 3. ĐỊNH THỜI TRÊN MÔI TRƯỜNG TÍNH TOÁN LƯỚI 3.1. Định thời trên lưới Công nghệ tính toán mạng lưới hiện nay cho phép chúng ta chia sẻ được nguồn tài nguyên máy tính trên diện rộng cũng như kết hợp được các nguồn tài nguyên máy tính khác nhau trên thế giới. Mối quan hệ của các nguồn tài nguyên chia sẻ có thể là quan hệ tĩnh và dài hạn (ví dụ như quan hệ chia sẻ tài nguyên giữa các trung tâm tài nguyên lớn của một công ty hay một viện đại học) hoặc có thể là quan hệ động (ví dụ như quan hệ chia sẻ giữa các tài nguyên của các thành viên với nhau trong một nghiên cứu khoa học mang tính chất tạm thời). Trong cả hai trường hợp, người sử dụng không biết hoặc biết rất ít về các tài nguyên mà các thành viên đóng góp trong tổ chức ảo đó. Điều này gây nên cho họ một trở ngại rất lớn trong việc sử dụng các tài nguyên chia sẻ. Để giải quyết vấn đề này, lưới tính toán có một số dịch vụ hỗ trợ như dịch vụ thông tin và bộ định thời (lập lịch). Dịch vụ thông tin đã được phát triển để có thể đáp ứng được nhu cầu về quản trị và giám sát (sự tồn tại, đặc tính của các nguồn tài nguyên, các dịch vụ, các hệ thống tính toán và các thực thể khác) của một hệ thống mạng lưới. Các dịch vụ thông tin tài nguyên kể trên được sử dụng đến trong rất nhiều khái niệm về việc khai thác hạ tầng mạng lưới. Bộ định thời là một dịch vụ hướng các yêu cầu tính toán đến các máy “tốt nhất có thể” trong một hệ thống Grid gồm rất nhiều máy tính mạnh. “Tốt nhất có thể” ở đây bao gồm các thông tin tốt nhất về kiến trúc tài nguyên đó, các phần mềm đã được cài đặt sẵn, hiệu suất hoạt động, tính sẵn sàng, các chính sách sử dụng của tài nguyên cũng như sự tập trung dữ liệu trên các tài nguyên. Nguồn thông tin tài nguyên lại là các máy tính và nguồn thông tin này liên quan đến cả các thông tin tĩnh như cấu hình của hệ thống (kiến trúc hệ thống, phiên bản hệ điều hành, các chính sách truy cập tài nguyên) và cả các thông tin động như năng lực tính toán, không gian lưu trữ, mức độ tải đồng thời, 9 dự đoán về tính sẵn sàng của tài nguyên trong tương lai. Tất cả được kết nối qua Internet và một phần mềm tầng giữa (middleware). Bộ định thời trên lưới (Grid scheduler) thường được gọi là nhà môi giới tài nguyên (resource broker) - hoạt động như là một giao tiếp giữa người dùng và các tài nguyên phân tán và giấu đi sự phức tạp của tính toán lưới. Nó thực hiện việc khai thác tài nguyên, ánh xạ các công việc đến các tài nguyên (định thời), tổ chức (dàn xếp) ứng dụng với dữ liệu để xử lý (triển khai), thực thi công việc và cuối cùng là nhận các kết quả trả về. Nó cũng chịu trách nhiệm giám sát và lưu vết quá trình thực thi các ứng dụng cùng với việc thích ứng những thay đổi trong môi trường thời gian thực của lưới (Grid runtime environment), thay đổi về khả năng chia sẻ tài nguyên hay những lỗi vấp phải khi thực thi. Quan trọng nhất là nhà môi giới lưới (Grid broker) có nhiệm vụ định thời cho ứng dụng trên các tài nguyên phân tán mà ở đó nó không có đầy đủ quyền điều khiển, chỉ có bộ định thời cục bộ mới thực sự có những quyền hạn thực hiện việc cấp phát (các) tài nguyên cho (các) công việc của người dùng. 3.2. Một số dự án và sản phẩm Một số dự án đang nghiên cứu có triển khai hệ thống định thời và quản lý tài nguyên lưới như Condor, Globus, Legion, AppLes, NetSolve và DISCWorld,… [17]. Chúng sử dụng chiến lược định thời tập trung (system- centric scheduling strategies); và Spawm cung cấp một khung chương trình thực hiện việc trao đổi (auction) dựa trên việc định vị (phân bổ) tài nguyên. Dự án AppLes (Application-Level Scheduling) [9] xây dựng các tác nhân (agents) cho mỗi ứng dụng chịu trách nhiệm đề xuất một cơ chế định thời. Nó sử dụng một hệ thống có chính sách định thời tập trung với mục đích tối thiểu hóa thời gian hoàn thành mà không quan tâm đến chi phí của quá trình xử lý các tác vụ khi chọn lựa nguồn tài nguyên. Hệ thống APST được phát triển gần đây phục vụ cho các ứng dụng parameter sweep cũng sử dụng chiến lược lập lịch trung tâm. Điểm mạnh của AppLes là chấp nhận được sai số, nghĩa là các lỗi phát sinh 10 đều được xử lý và đệ trình lại trên các tài nguyên khác mà không cần sự can thiệp của người dùng. NetSolve là một hệ thống client-agent-server, nó cho phép người dùng giải quyết các vấn đề khoa học phức tạp từ xa [14]. NetSolve định thời bằng cách tìm kiếm nguồn tài nguyên sao cho nó hoạt động hiệu quả nhất trên mạng. Các ứng dụng được xây dựng bằng cách sử dụng một trong những hàm API được cung cấp bởi NetSolve để thực hiện những tính toán như RPC (Remote Procedure Call). NetSolve cũng cung cấp một API (Application Programming Interface) để tạo các ứng dụng luân phiên tác vụ. Hệ thống định thời ánh xạ các tác vụ đến các tài nguyên có các thư viện thích hợp mà không phải lưu tâm đến chi phí để xử lý các tác vụ trên đó. DISCWorld (Distributed Information Systems Control World) [11] là một môi trường siêu điện toán (metacomputing) hướng dịch vụ, dựa trên mô hình client-server. Những người dùng ở xa có thể đăng nhập vào môi trường này thông qua Internet, yêu cầu truy xuất dữ liệu và triệu gọi các dịch vụ hay thực hiện các thao tác trên dữ liệu có thể dùng. DISCWorld tập trung vào việc truy cập thông tin từ xa, chiến lược định thời được sử dụng trong hệ thống này cũng là hệ thống có tính chất trung tâm (system-centric in nature). Một công cụ liên quan khác sử dụng khái niệm lưới điện toán có quan tâm chi phí là REXEC [19], một môi trường thực thi từ xa để cộng tác với các hệ thống phân tán như cluster với bộ quản lý định thời trung tâm. Bằng dòng lệnh, người dùng có thể định rõ tỉ lệ cao nhất (theo phút) mà họ sẵn sàng trả theo thời gian thực hiện của CPU. REXEC client chọn một nút (node) thích hợp nhất với yêu cầu của người dùng rồi thực thi ứng dụng trên đó. Hệ thống REXEC cung cấp một tiện ích mở rộng cho việc thực thi từ xa các ứng dụng trên các cluster. Chiến lược định thời của nó là nhắm tới các hệ thống trung tâm và phân phối tài nguyên chia sẻ tương xứng với sự ước lượng của người dùng trên các công việc của họ. 11 Vấn đề định thời hạn cuối (deadline) trong các hệ thống thời gian thực cũng được nghiên cứu tỉ mỉ. Tuy nhiên, chúng hầu như xét đến các tham số về thời hạn cho từng tác vụ cụ thể hơn là một nhóm các tác vụ. 3.3. Các giải thuật định thời liên quan Định thời trên lưới là vấn đề hết sức khó khăn vì số lượng tài nguyên cũng như số lượng ứng dụng là rất lớn. Mục tiêu thông thường nhất của các giải thuật định thời là đưa ra được makespan (thời gian để hoàn thành tất cả các ứng dụng) tốt. Tuy nhiên, trong tính toán lưới, makespan thực tế và lý thuyết khác nhau rất nhiều vì năng lực tính toán còn lại của các tài nguyên trên mạng thay đổi theo thời gian. Vì thế, nếu sử dụng makespan làm tiêu chuẩn đo lường mức độ hiệu quả của giải thuật thì phải ước tính được năng lực tính toán của các tài nguyên theo thời gian. Có hai lớp thuật giải cho vấn đề này: + Thuật giải định thời tĩnh: là giải thuật mà mọi quyết định được thực hiện trước khi thực thi việc định thời. + Ngược lại, thuật giải định thời động là giải thuật mà một số hoặc tất cả các quyết định sẽ được thực hiện trong quá trình định thời. Trong hệ thống tính toán lưới, năng lực của các nguồn tài nguyên thay đổi theo thời gian, vì vậy định thời động chính xác hơn định thời tĩnh. Nhược điểm của các giải thuật định thời động là có độ phức tạp cao. Sau đây chúng ta 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. Từ đó, đề tài đề xuất mộ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ừ cái nhìn tổng quan này ta có cơ sở để so sánh với giải pháp mà đề tài đề xuất. Các thuật giải này đều dựa trên nguyên tắc chính như sau: - Đầu tiên, tất cả các tác vụ đều được xếp vào trong hàng đợi các tác vụ. - Khi có tài nguyên sẵn sàng, tác vụ có độ ưu tiên cao nhất sẽ được lấy ra khỏi hàng đợi để thực thi. 12 - 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. - Quá trình này được lặp cho đến khi tất cả các tác vụ đều hoàn thành. Sự 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 tác vụ và cách chọn nguồn tài nguyên. 3.3.1. MET (Minimum Excecution Time)  Ý tưởng của thuật giải MET [4] [21] là ước lượng thời gian thực thi của mỗi tác vụ 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 không. Thuật giải này có nhược điểm là không cân bằng tải vì nhiều khả năng tất cả các tác vụ sẽ chỉ tập trung vào một tài nguyên có khả năng tính toán mạnh. Ví dụ: Giả sử có 2 tác vụ cần thực hiện, tác vụ thứ nhất có kích thước T1=60, tác vụ thứ hai có kích thước T2=120. Có 2 nguồn tài nguyên có kích thước lần lượt là H1=30 và H2=40. Giả sử thời gian thực hiện của tác vụ i trên tài nguyên j là Eij=Ti/Hj. Tính 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: E11 = T1/H1 = 60/30 = 2 E12 = T1/H2 = 60/40 = 1.5 (nhỏ nhất) E21 = T2/H1 = 120/30 = 4 E22 = T2/H2 = 120/40 = 3 Suy ra tác vụ 1 được định thời trước trên tài nguyên 2. Tiếp theo ta lại thấy: E21 = T2/H1 = 120/30 = 4 E22 = T2/H2 = 120/40 = 3 (nhỏ nhất) Suy ra tác vụ 2 được định thời trên tài nguyên 2. Vậy thời gian hoàn thành 2 tác vụ trên là makespan = 1.5+3 = 4.5 (do 2 tác vụ cùng lần lượt thực hiện trên tài nguyên 2). 13 3.3.2. MCT (Minimum Completion Time)  Đây là thuật giải kết hợp MET và cân bằng tải, MCT [4] [21] thực hiện gán các tác vụ (theo thứ tự bất kỳ) cho tài nguyên sao cho tác vụ đó được hoàn thành sớm nhất. Như vậy thuật giải này dựa vào thời gian hoàn thành chứ không phải 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ó đang bận thực hiện một tác vụ nào đó. Do đó cách định thời này cân bằng tải tốt hơn MET. Ví dụ: Cũng với các giả sử giống trong ví dụ ở phần 3.3.1 (T1=60, T2=120, H1=30 và H2=40). Giả sử thời gian hoàn thành của tác vụ i trên tài nguyên j là Cij=Bj + Eij với Bj là thời điểm có thể bắt đầu thực hiện công việc mới của tài nguyên j và Eij=Ti/Hj là thời gian thực hiện tác vụ i trên tài nguyên j. Tính thời gian hoàn thành các tác vụ trên các tài nguyên tương ứng, ta được (giả sử ban đầu tất cả các tài nguyên đều có thời điểm bắt đầu là 0): C11 = B1 + E11 = 0 + T1/H1 = 0 + 60/30 = 2 C12 = B2 + E12 = 0 + T1/H2 = 0 + 60/40 = 1.5 (nhỏ nhất) C21 = B1 + E21 = 0 + T2/H1 = 0 + 120/30 = 4 C22 = B2 + E22 = 0 + T2/H2 = 0 + 120/40 = 3 Suy ra tác vụ 1 được định thời trước trên tài nguyên 2 (cập nhật B2=1.5). Tiếp theo ta lại thấy: C21 = B1 + E21 = 0 + T2/H1 = 0 + 120/30 = 4 (nhỏ nhất) C22 = B2 + E22 = 1.5 + T2/H2 = 1.5 + 120/40 = 4.5 Suy ra tác vụ 2 được định thời trên tài nguyên 1. Vậy thời gian hoàn thành 2 tác vụ trên là makespan = max(1.5,4) = 4 (do 2 tác vụ được thực hiện đồng thời trên 2 tài nguyên). So sánh ta thấy MCT có makespan (bằng 4) tốt hơn makespan của MET (bằng 4.5). 3.3.3. RR (Round­Robin)  Thuật giải RR [16] thực hiện ánh xạ lần lượt và xoay vòng tất cả các tác vụ lên các tài nguyên. Khi tất cả các tác vụ đã được ánh xạ mà có tài nguyên nào 14 rảnh thì nó sẽ tạo bản sao tác vụ và ánh xạ bản sao này cho tài nguyên rảnh đó. Thuật giải này có ưu điểm là tận dụng được tối đa nguồn tài nguyên nhưng đó cũng chính là nhược điểm của nó vì khi tận dụng tối đa nguồn tài nguyên thì không còn tài nguyên để phục vụ các công việc khác. Một ưu điểm khác của thuật giải này là nó không cần đến bất kỳ thông tin cho trước nào về tài nguyên cơ sở (như tốc độ bộ xử lý). 3.3.4. DFPLTF (Dynamic Fastest Processor to Largest Task First)  DFPLTF [15] được cải tiến từ “static FPLTF” (là cách định thời tĩnh đưa ra makespan tốt trên máy song song) để nó thích hợp hơn với môi trường lưới. Bản thân tên thuật giải đã nói lên ý tưởng chính của nó, đó là ánh xạ công việc có khối lượng lớn nhất cho nguồn tài nguyên mạnh nhất. Tuy nhiên không phải lúc nào ánh xạ công việc lớn lên tài nguyên mạnh cũng tốt vì có thể tại thời điểm đó tài nguyên mạnh này đang thực hiện một công việc khác và rất lâu sau nó mới sẵn sàng thực hiện công việc vừa được ánh xạ. 3.3.5. Min­Min  Thuật giải Min-Min [4] [21] sử dụng ma trận MCT (Minimum Completion Time), nhưng tại mỗi bước tính, nó ước lượng 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 ánh xạ 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 tác vụ và cứ thế tiếp tục cho đến khi hoàn thành tất cả các tác vụ. Hình 3.1 là thuật giải Min-Min, trong đó T là tập các tác vụ, Hj,k biểu thị máy (host) thứ k của tài nguyên (resource) j. C(Ti, Hj,k) là ước lượng thời gian hoàn thành tác vụ Ti trên host Hj,k. Toán tử argmin được định nghĩa như sau: Cho hàm f là một ánh xạ từ Rn vào R ݂൫ܽݎ݃݉݅݊௫אோ೙݂ሺݔሻሻ ൌ ݉݅݊௫אோ೙݂ሺݔሻ൯. 15 while (T ≠ ׎) foreach (TiאT) ሺܿ௜ଵ, ݄௜ଵሻ ൌ ܽݎ݃݉݅݊௝,௞ሺܥሺ ௜ܶ, ܪ௝,௞ሻሻ end foreach ݏ ൌ ܽݎ݃݉݅݊௜ሺܥሺ ௜ܶ, ܪ௖೔భ,௛೔భሻሻ assign Ts to ܪ௖ೞభ,௛ೞభ T = T – {Ts} end while Hình 3.1: Thuật giải Min-Min Ví dụ: Cũng với giả sử giống ví dụ ở phần 3.3.2, thuật giải Min-Min thực hiện như sau: Tính thời gian hoàn thành của tác vụ thứ nhất trên các tài nguyên khác nhau: C11 = B1 + E11 = 0 + T1/H1 = 0 + 60/30 = 2 C12 = B2 + E12 = 0 + T1/H2 = 0 + 60/40 = 1.5 (nhỏ nhất) Tính thời gian hoàn thành của tác vụ thứ hai trên các tài nguyên khác nhau: C21 = B1 + E21 = 0 + T2/H1 = 0 + 120/30 = 4 C22 = B2 + E22 = 0 + T2/H2 = 0 + 120/40 = 3 (nhỏ nhất) Trong số các thời gian hoàn thành nhỏ nhất của các tác vụ, chọn nhỏ nhất một lần nữa. Suy ra chọn tác vụ 1 thực hiện trên tài nguyên 2 (do 1.5<3). Cập nhật B2=1.5. Lặp lại các bước trên: C21 = B1 + E21 = 0 + T2/H1 = 0 + 120/30 = 4 (nhỏ nhất) C22 = B2 + E22 = 1.5 + T2/H2 = 1.5 + 120/40 = 4.5 Vì chỉ còn 1 tác vụ nên tác vụ 2 được định thời trên tài nguyên 1 (do có thời gian hoàn thành nhỏ nhất). Vậy thời gian hoàn thành 2 tác vụ trên là makespan = max(1.5,4) = 4 (do 2 tác vụ được thực hiện đồng thời trên 2 tài nguyên). 16 Thuật giải này không đảm bảo được vấn đề cân bằng tải vì các tác vụ nhỏ sẽ được thực hiện trước, sau đó các tác vụ lớn hơn sẽ thực hiện sau. Nhược điểm của giải thuật này là lúc các tác vụ lớn thực hiện thì có nhiều nguồn tài nguyên đang ở trạng thái rảnh rỗi. Thuật giải Max-Min giải quyết được vấn đề này. 3.3.6. Max­Min  Tương tự như thuật giải Min-Min nhưng Max-Min [4] [21] ưu tiên ánh xạ những tác vụ có thời gian thực hiện lớn. Trong nhóm những tác vụ có thời gian hoàn thành nhỏ, tác vụ nào có thời gian thực hiện lớn mà hoàn thành sớm thì ưu tiên. Thuật giải này tốt hơn Min-Min vì nó không để một tác vụ phải chờ quá lâu, từ đó cân bảng tải cũng tốt hơn. Thuật giải Max-Min cũng dựa vào MTC nhưng nó xét các tác vụ chưa được ánh xạ mỗi khi quyết định còn MCT chỉ xét một lần. Hình 3.2 mô tả thuật giải Max-Min, các ký hiệu tương tự thuật giải Min- Min. while (T ≠ ׎) foreach (TiאT) ሺܿ௜ଵ, ݄௜ଵሻ ൌ ܽݎ݃݉݅݊௝,௞ሺܥሺ ௜ܶ, ܪ௝,௞ሻሻ end foreach ݏ ൌ ܽݎ݃݉ܽݔ௜ሺܥሺ ௜ܶ, ܪ௖೔భ,௛೔భሻሻ assign Ts to ܪ௖ೞభ,௛ೞభ T = T – {Ts} end while Hình 3.2: Thuật giải Max-Min Ví dụ: Cũng với giả sử giống ví dụ ở phần 3.3.2, thuật giải Max-Min thực hiện như sau: Tính thời gian hoàn thành của tác vụ thứ nhất trên các tài nguyên khác nhau: C11 = B1 + E11 = 0 + T1/H1 = 0 + 60/30 = 2 C12 = B2 + E12 = 0 + T1/H2 = 0 + 60/40 = 1.5 (nhỏ nhất) 17 Tính thời gian hoàn thành của tác vụ thứ hai trên các tài nguyên khác nhau: C21 = B1 + E21 = 0 + T2/H1 = 0 + 120/30 = 4 C22 = B2 + E22 = 0 + T2/H2 = 0 + 120/40 = 3 (nhỏ nhất) Chọn tác vụ có thời gian hoàn thành lớn nhất trong số các thời gian hoàn thành nhỏ nhất vừa tính được. Suy ra chọn tác vụ 2 thực hiện trên tài nguyên 2 (do 3>1.5). Cập nhật B2=3. Lặp lại các bước trên: C11 = B1 + E11 = 0 + T1/H1 = 0 + 60/30 = 2 (nhỏ nhất) C12 = B2 + E12 = 3 + T1/H2 = 3 + 60/40 = 4.5 Vì chỉ còn 1 tác vụ nên tác vụ 1 được định thời trên tài nguyên 1 (do có thời gian hoàn thành nhỏ nhất). Vậy thời gian hoàn thành 2 tác vụ trên là makespan = max(3,2) = 3 (do 2 tác vụ được thực hiện đồng thời trên 2 tài nguyên). 3.3.7. Duplex   Thuật giải Duplex [21] là một sự kết hợp của thuật giải Min-Min và Max- Min. Nó thực hiện cả 2 thuật giải Min-Min và Max-Min, sau đó chọn giải pháp tốt hơn. Thuật giải Duplex chỉ được đánh giá tốt khi cả Min-Min và Max-Min được thực hiện với chi phí không đáng kể. 3.3.8. Partitioning  Ý tưởng của thuật giải Partitioning [3] là phân nhóm nguồn tài nguyên thành các nhóm có số bộ xử lý là các lũy thừa của 2. Sau đó ánh xạ các tác vụ lên các tài nguyên sao cho ít có bộ xử lý bị thừa (rãnh rỗi) ở các nhóm nhất. 3.3.9. Sufferage  Sufferage [8] lấy ý tưởng từ các thuật giải Max-Min và Min-Min, tuy nhiên môi trường lưới là một môi trường động và hỗn tạp, do đó khi chọn được một ánh xạ tương ứng (tác vụ, tài nguyên) mà ta ước lượng là tốt nhất thì khi thực thi trên môi trường lưới không có gì đảm bảo lựa chọn ánh xạ đó là tốt nhất. Thuật giải Sufferage hạn chế được những rủi ro đó bằng cách đưa ra một giá trị suf. Với mỗi tác vụ, giá trị suf này chính là độ sai lệch giữa thời gian hoàn 18 thành nhỏ nhất và thời gian hoàn thành nhỏ nhì của nó. Tác vụ nào có giá trị suf lớn nhất sẽ được chọn. Hình 3.3 là thuật giải Sufferage với các ký kiệu như trong thuật giải Min-Min. while (T ≠ ׎) foreach (TiאT) ሺܿ௜ଵ, ݄௜ଵሻ ൌ ܽݎ݃݉݅݊௝,௞ሺܥሺ ௜ܶ, ܪ௝,௞ሻሻ ሺܿ௜ ଶ, ݄௜ ଶሻ ൌ ܽݎ݃݉݅݊௝ஷ௖೔భ,௞ஷ௛೔భሺܥሺ ௜ܶ, ܪ௝,௞ሻሻ ݏݑ ௜݂ ൌ ܥሺ ௜ܶ, ܪ௖೔మ,௛೔మሻ െ ܥሺ ௜ܶ, ܪ௖೔భ,௛೔భሻ end foreach ݏ ൌ ܽݎ݃݉ܽݔ௜ሺݏݑ ௜݂ሻ assign Ts to ܪ௖ೞభ,௛ೞభ T = T – {Ts} end while Hình 3.3: Thuật giải Sufferage Ví dụ: Cũng với giả sử giống ví dụ ở phần 3.3.2, thuật giải Sufferage thực hiện như sau: Tính thời gian hoàn thành của tác vụ thứ nhất trên các tài nguyên khác nhau: C11 = B1 + E11 = 0 + T1/H1 = 0 + 60/30 = 2 (nhỏ nhì) C12 = B2 + E12 = 0 + T1/H2 = 0 + 60/40 = 1.5 (nhỏ nhất) suf1 = 2 – 1.5 = 0.5 Tính thời gian hoàn thành của tác vụ thứ hai trên các tài nguyên khác nhau: C21 = B1 + E21 = 0 + T2/H1 = 0 + 120/30 = 4 (nhỏ nhì) C22 = B2 + E22 = 0 + T2/H2 = 0 + 120/40 = 3 (nhỏ nhất) suf2 = 4 – 3 = 1 (lớn nhất) Do suf2 > suf1 nên tác vụ 2 (có giá trị suf lớn nhất) được định thời trên tài nguyên 2 (có thời gian hoàn thành nhỏ nhất). Cập nhật B2=3. Lặp lại các bước trên: 19 C11 = B1 + E11 = 0 + T1/H1 = 0 + 60/30 = 2 (nhỏ nhất) C12 = B2 + E12 = 3 + T1/H2 = 3 + 60/40 = 4.5 Suf1 = 4.5 – 2 = 2.5 (lớn nhất) Vì chỉ còn 1 tác vụ nên suf1 cũng là giá trị suf lớn nhất nên tác vụ 1 được định thời trên tài nguyên 1 (do có thời gian hoàn thành nhỏ nhất). Vậy thời gian hoàn thành 2 tác vụ trên là makespan = max(3,2) = 3 (do 2 tác vụ được thực hiện đồng thời trên 2 tài nguyên). Thuật giải Sufferage vẫn còn hạn chế của nó, đó là trong môi trường lưới nhưng có nhiều máy tính cụm (cluster), các tài nguyên trong cùng một cluster thường có năng lực tính toán gần như nhau, dẫn đến giá trị MCT sẽ tốt gần như nhau, khi đó giá trị suf của tác vụ tương ứng sẽ rất nhỏ và dĩ nhiên tác vụ này không được chọn mặc dù nó có MCT thật sự tốt. XSufferage chính là thuật giải giải quyết được vấn đề này.  3.3.10. XSufferage  XSufferage [8] là thuật giải cải tiến từ Sufferage. Trong XSufferage, giá trị suf không phải là dựa vào MCT mà chính xác là cluster-level MCT. Nghĩa là với mỗi tác vụ, nó tính giá trị MCT trên tất cả các host trong mỗi cluster và chọn ra MCT tốt nhất trong cluster đó. Tương tự như vậy cho các cluster khác, sau đó giải thuật sẽ chọn ra 2 cluster có MCT nhỏ nhất và nhỏ nhì để tính giá trị suf. Tác vụ nào có giá trị suf lớn sẽ được quyền ưu tiên. Hìn