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

rs L ist Hình 4-1 Mô hình hoạt động Mỗi thành phần giữ vai trò khác nhau trong hệ thống: - Users: Các người dùng sẽ gửi ứng dụng để thực thi trong môi trường lưới. - System Broker: Bộ điều phối tập trung của hệ thống. Là nơi tiếp nhận các ứng dụng của người dùng và quyết định tài nguyên trong hệ thống sẽ thực thi ứng dụng. Broker đóng vai trò như một lối vào (portal) cho người dùng, thông qua broker người dùng có thể thực thi được ứng dụng mà không cần tham gia hay hiểu cấu trúc của hệ thống tính toán lưới. Broker cũng là sẽ thành phần trả kết quả thực thi cho người dùng sau khi hoàn tất. 35 - GIS - Grid Information Service: System Broker sẽ liên hệ với GIS để lấy danh sách các providers trong hệ thống cùng đặc điểm của các providers này. - Clusters: Là các hệ thống máy tính cụm, chịu trách nhiệm thực thi ứng dụng của người dùng. Số lượng máy tính cụm trong hệ thống có thể rất lớn, nhiều máy tính cụm sẽ tập hợp thành một vùng tài nguyên, do một provider đại diện. - Provider – Nhà cung cấp: Đại diện cho các máy tính cụm trong vùng mình quản lý. System Broker sẽ gửi thông tin đặc tả về ứng dụng của người dùng cho provider (thông qua các Request). Provider dựa vào tình trạng tài nguyên còn lại và các ứng dụng hiện đang thực thi trong vùng sẽ tính toán giá tiền cũng như thời gian hoàn tất dự kiến cho ứng dụng và gửi lời chào giá (các offer) về system broker. - Dựa vào các thông tin chào giá (offer) của các providers, system broker sẽ quyết định thực thi một ứng dụng cụ thể của người dùng tại vùng tài nguyên nào phù hợp nhất. Một trong những điểm mới của luận văn đề xuất là sự xuất hiện của mô hình nhà cung cấp - provider, giúp giảm độ phức tạp cho hệ thống: Số lượng máy tính cụm (clusters) trong một mô hình lưới thường sẽ rất nhiều (có thể đạt số lượng hàng ngàn), nếu system broker phải liên lạc với tất cả các máy tính cụm này sẽ dẫn đến sự quá tải cho broker. Khi đưa vào mô hình provider, system broker chỉ liên lạc trực tiếp với các providers; provider sẽ có trách nhiệm quản lý các máy tính cụm trong vùng mình phụ trách tạo thành các vùng tài nguyên (như vùng tài nguyên TP. Hồ Chí Minh, vùng tài nguyên của Hà Nội …) Lúc này hệ thống được phân cấp quản lý thành 2 cấp: System broker đóng vai trò quản lý chung, provider ở mức địa phương. Mỗi cấp quản lý có thể có mục tiêu riêng của mình, ví dụ: 36 - System broker: hoạt động vì lợi nhuận hoặc vì mục tiêu phục vụ nhiều người dùng, phi lợi nhuận - Provider: Vì lợi nhuận hoặc vì mục tiêu tận dụng tối đa tài nguyên rảnh của các máy tính cụm nội bộ… 4.2 Mô hình ứng dụng Các nghiên cứu thuật giải hiện tại được đề cập trong chương 3 chủ yếu giải quyết cho trường hợp ứng dụng rất lớn, gồm vài ngàn hoặc thậm chí vài trăm ngàn tác vụ con (hình 4-2a). Điển hình của bài toán có qui mô lớn ở mức độ này là các ứng dụng parameter sweep [6], [10], [11]. Ứng dụng dạng này gồm rất nhiều tác vụ thực thi cùng một tính năng tính toán, phân tích nhưng trên các bộ tham số khác nhau nhằm đánh giá ảnh hưởng của các tham số đầu vào lên một hệ thống, cũng như tìm kiếm các tham số tối ưu. Loại ứng dụng này thường thấy trong các dự án nghiên cứu lớn đang được triển khai trên môi trường lưới như phân tích cấu trúc protein, cấu trúc gen, mô phỏng hoạt động não bộ, điều chế thuốc trong y học… [11] Trong điều kiện hiện tại của Việt Nam, chúng ta chưa có nhiều những ứng dụng quá lớn ở qui mô này. Môi trường lưới của Việt Nam tại một thời điểm cũng sẽ nhiều công việc, tuy nhiên đó là nhiều ứng dụng khác nhau, trong đó mỗi ứng dụng gồm không quá nhiều các tác vụ con. Các ứng dụng này hoạt động độc lập với nhau, không có sự ràng buộc trong quá trình thực thi (hình 4-2b). Luận văn sẽ tập trung nghiên cứu các thuật giải lập lịch phù hợp với điều kiện và hoàn cảnh của Việt Nam theo hình 4-2b. (a) Một ứng dụng lớn, gồm rất nhiều tác vụ 37 (b) Nhiều ứng dụng vừa và nhỏ, mỗi ứng dụng có không quá nhiều tác vụ Hình 4-2 Sự khác nhau trong mô hình ứng dụng giữa thế giới và VN Mô tả ứng dụng: Mỗi ứng dụng gồm không quá nhiều tác vụ (task/job), các tác vụ được thực thi song song và độc lập với nhau. Mỗi tác vụ có chiều dài (Length), ngân sách (Budget) và thời hạn thực thi (Deadline) riêng. Ngân sách của một tác vụ là chi phí người dùng sẵn sàng chi trả cho hệ thống để thực thi tác vụ, thời hạn kết thúc (Deadline) là thời điểm trễ nhất mà tác vụ phải hoàn thành. Qui ước: Ứng dụng app gồm n tác vụ T1 … Tn - Li là chiều dài (length) của tác vụ Ti - Di là thời hạn kết thúc (deadline) của tác vụ Ti - Bi là ngân sách (budget) giành cho tác vụ Ti Người dùng sẽ gửi ứng dụng của mình lên môi trường lưới, khi ứng dụng hoàn tất – là thời điểm tác vụ cuối cùng của ứng dụng được thực thi xong – kết quả sẽ được trả về cho người dùng. Người dùng sẽ chỉ nhận kết quả trả về cũng như chi trả chi phí cho ứng dụng khi toàn bộ ứng dụng hoàn tất, không xét riêng khi từng tác vụ riêng lẻ thực thi xong. Với đặc điểm trên, để tăng tính uyển chuyển và khả năng ứng dụng được thực thi thành công hệ thống sẽ mở rộng khái niệm Budget và Deadline cho ứng dụng như sau: Length(app) = ∑ L௡௜ୀଵ i : chiều dài của ứng dụng Deadline(app)= max (Di, i=1…n ): thời hạn thực thi của ứng dụng 38 Budget(app)= ∑ B௡௜ୀଵ i : ngân sách của toàn ứng dụng Việc mở rộng này không gây thiệt hại cho người dùng: - Người dùng không phải chi trả thêm so với ngân sách ban đầu đề ra - Thời điểm kết thúc của tác vụ trễ nhất trong ứng dụng không thay đổi, do đó thời gian kết thúc của toàn ứng dụng vẫn như cũ. Trong các nghiên cứu của nhóm Grid Computing thuộc bộ môn Mạng Máy Tính, chúng tôi đã gặp khá nhiều các ứng dụng dạng này. Đơn cử như quá trình nghiên cứu hệ thống quét virus trên môi trường lưới cho các tổ chức [18], tập hợp các thư mục, tập tin của một tổ chức có thể xem như một ứng dụng, trong đó mỗi file là một tác vụ của ứng dụng. 4.3 Những điểm chưa phù hợp với hoàn cảnh Việt Nam của các thuật giải đã có 4.3.1 Hiệu suất thực thi kém - Mỗi một tác vụ chịu sự ràng buộc bởi 2 điều kiện là thời hạn kết thúc (deadline) và ngân sách (budget). Trong quá trình điều phối, sẽ có một số tác vụ mà hệ thống không thể cùng lúc đáp ứng 2 điều kiện này nên bị từ chối thực thi. Việc tác vụ nào bị từ chối thực thi do bản chất mỗi thuật giải lập lịch quyết định, mặt khác mọi tác vụ đều đóng vai trò như nhau nên sẽ dẫn đến trường hợp như hình 4.3. (a) Chưa có ràng buộc về ứng dụng, các tác vụ có vai trò như nhau 39 (b) Có sự ràng buộc về ứng dụng dẫn đến tất cả ứng dụng đều không thực thi thành công Hình 4-3 Tỉ lệ thực thi thành công kém Ở hình 4-3a dù nhiều tác vụ bị từ chối thực thi nhưng các tác vụ khác vẫn được hoàn tất. Ở hình 4-3b, có sự bổ sung ràng buộc về ứng dụng. Mỗi ứng dụng đều có tác vụ bị từ chối thực thi, dẫn đến không có ứng dụng nào thực sự hoàn tất dù vẫn có nhiều tác vụ khác được thực thi. Điều này dẫn đến tỉ lệ các ứng dụng thực thi hoàn tất là rất thấp. Các thuật giải đề xuất trong luận văn sẽ xem toàn bộ một ứng dụng là một đơn vị thống nhất, do đó sẽ chỉ có trường hợp toàn bộ một ứng dụng được thực thi hoặc toàn bộ một ứng dụng bị từ chối. Không dẫn đến trường hợp như hình 4-3b - Mô hình ứng dụng do luận văn đề xuất đã mở rộng khái niệm ngân sách (budget) và thời hạn kết thúc (deadline) ở mức ứng dụng, cao hơn ở mức từng tác vụ riêng lẻ. Do điều kiện đã được nới lỏng nên khả năng một ứng dụng được thực thi thành công sẽ cao hơn. Ví dụ: trong một ứng dụng có một số tác vụ có chi phí thực thi cao hơn ngân sách cho phép. Tuy nhiên trong cùng ứng dụng đó, một số tác vụ lại chưa dùng hết ngân sách của mình. Số dư này có thể giúp các tác vụ khác bù đắp và được phép thực thi, dẫn đến toàn bộ ứng dụng vẫn thực thi thành công. Với các nghiên cứu trước đó, khi tác vụ vi phạm điều kiện ngay lập tức bị hủy bỏ dẫn đến toàn ứng dụng không thể hoàn tất. 40 4.3.2 Thời gian thực thi ứng dụng cao Hình 4-4 Thời gian thực thi ứng dụng cao Do các nghiên cứu trước chưa đề ra các ràng buộc ở mức ứng dụng, toàn bộ các tác vụ xem như độc lập không có mối quan hệ gì với nhau, do đó sẽ xảy ra trường hợp trong cùng một ứng dụng của người dùng có những tác vụ được điều phối thực thi từ rất sớm, có những tác vụ được thực thi rất trễ dẫn đến thời gian thực thi tác vụ rất cao. 4.4 Hướng giải quyết của luận văn Do một ứng dụng có kích thước không quá lớn, luận văn đề xuất thực thi toàn bộ mỗi ứng dụng trên một máy tính cụm (cluster) duy nhất. Việc xử lý toàn bộ một ứng dụng trên một máy tính cụm giúp đơn giản hóa quá trình vận chuyển dữ liệu đến nơi thực thi cũng như việc tổng hợp kết quả khi ứng dụng hoàn tất. Ngoài ra hướng tiếp cận này còn đơn giản hóa việc tính chi phí thực thi cho ứng dụng so với việc thực thi một ứng dụng ở nhiều nơi khác nhau. 41 Hình 4-5 Thực thi một ứng dụng trên một máy tính cụm Nghiên cứu của tác giả Trần Công Tú [20] cũng theo hướng tiếp cận ở hình 4- 5. Tuy nhiên, tác giả chỉ giải quyết bài toán lập lịch theo hiệu năng hệ thống, các ứng dụng chỉ chịu ràng buộc về thời gian thực thi. Luận văn nghiên cứu và giải quyết bài toán lập lịch theo hiệu năng kinh tế, mỗi ứng dụng có hai ràng buộc: về thời gian và về kinh phí nên vấn đề cần giải quyết phức tạp hơn. 4.5 Các thuật giải ở System Broker Ý tưởng chung: Các ứng dụng sẽ được quản lý tập trung tại system broker. Dựa theo mỗi thuật giải, broker sẽ sắp xếp các ứng dụng của người dùng theo một độ ưu tiên xác định. Theo thứ tự đã sắp xếp, broker sẽ tuần tự gửi thông tin mô tả của từng ứng dụng đến lần lượt các providers dưới dạng các lời yêu cầu (request). Mỗi provider sẽ tính toán và trả lời cho broker biết thời điểm kết thúc và giá thành ước lượng ứng với ứng dụng đó thông qua các offer chào giá. Trong số những lời chào giá thỏa yêu cầu về thời hạn và chi phí từ phía các providers, system broker sẽ lựa ra provider chào giá thấp nhất và giao cho provider này thực thi ứng dụng. Provider sau khi nhận được một ứng dụng sẽ phải cập nhật các thông số về tài nguyên vì kết quả của những lần chào giá sau phải tính đến những ứng dụng mình đang được xử lý trước đó. Khi ứng dụng thực thi hoàn tất, kết quả được trả về phía system broker và từ đây sẽ trả về cho người dùng. 42 Điểm khác biệt ở đây là quá trình sắp xếp các ứng dụng tại phía system broker. Thứ tự sắp xếp khác nhau sẽ cho những kết quả thực thi rất khác nhau nhằm phục vụ cho những mục tiêu khác nhau. 4.5.1 Thuật giải điều phối ADeadline Thuật giải điều phối ADeadline chú trọng đến thời hạn hoàn tất của ứng dụng (Application’s Dealine). System Broker sẽ sắp xếp các ứng dụng theo Deadline tăng dần, sau đó duyệt các ứng dụng theo thứ tự này để gửi đến các providers. Mô tả: - Bước 1: Sắp xếp các ứng dụng trong tập A theo thứ tự Deadline tăng dần, các ứng dụng có thời hạn kết thúc sớm hơn được ưu tiên xếp trước - Bước 2:Duyệt danh sách các ứng dụng theo thứ tự đã sắp xếp, ứng với mỗi ứng dụng: o Gửi thông tin về ứng dụng cho tất cả các providers o Provider tính toán và gửi lời chào giá cho ứng dụng o Trong số các lời chào giá thỏa yêu cầu của ứng dụng, Broker lựa ra lời chào giá có chi phí thấp nhất và giao cho provider đó thực thi - Bước 3: Bỏ ứng dụng vừa xét ra khỏi tập ứng dụng A. Nếu còn ứng dụng trong tập A, trở lại Bước 2. Thuật giải: Gọi A là tập các ứng dụng trong hệ thống, P là tập các providers. Finish_Time(Oij): thời gian hoàn tất dự kiến của ứng dụng Ai trên Provider Pj Cost(Oij): chi phí dự kiến của ứng dụng Ai trên Provider Pj A = sort (A, BY_DEADLINE_ASC); //sort các ứng dụng theo Deadline tăng dần while (A≠Ø) Ai=get_first(A); //ứng dụng có deadline thấp nhất O=Ø; //Tập các offer từ provider 43 foreach Pj in P //Duyệt tất cả provider send_request(Ai,Pj); //Gửi yêu cầu đến provider Pj recv(Pj,Oij); //Nhận lời chào giá từ Pj cho ứng dụng Ai if (Finish_Time(Oij) ≤ Deadline(Ai) && Cost(Oij) ≤ Budget(Ai) ) then //Lời chào giá thỏa yêu cầu O=O+{Oij} //Thêm lời chào giá vào tập Offer end foreach if ( O ≠ Ø ) then //Nếu có provider thỏa yêu cầu Oik = min_cost (O); //Lựa ra Offer có giá thấp nhất send_app(Ai,Pk); //Gửi Ai cho provider Pk thực thi end if A = A \ {Ai}; //Loại Ai khỏi tập Application end while Độ phức tạp ứng với Broker: Mỗi ứng dụng lần được gửi cho mỗi provider, do đó độ phức tạp là O(n*m) với n là số lượng ứng dụng, m là số lượng các providers. Ở giải thuật này có quá trình sắp xếp danh sách các ứng dụng có độ phức tạp O(n*log(n)), tuy nhiên quá trình này thật sự chỉ là quá trình sắp xếp một mảng tại phía broker nên diễn ra rất nhanh. Khi xem xét độ phức tạp, luận văn chỉ tính đến quá trình chào giá đến các providers, là quá trình đòi hỏi nhiều thời gian. Đặc điểm: - Ưu tiên các ứng dụng có nguy cơ bị trễ hạn được thực thi trước -> nâng cao khả năng hoàn thành của các ứng dụng. - Số lượng ứng dụng thực thi thành công sẽ cao nhất trong các thuật giải được đề ra trong luận văn, do đó sẽ phục vụ được số lượng người dùng cao nhất. - Chưa chú trọng đến ngân sách của các ứng dụng thực thi, do đó lợi nhuận thu được của hệ thống có thể không cao. - Thuật giải này có thể áp dụng cho các hệ thống mới thiết lập, chú trọng đến việc thu hút nhiều người dùng hơn việc nâng cao tối đa chi phí thu vào. 44 Thuật giải cũng có thể áp dụng cho các hệ thống phục vụ cộng đồng, tạo cơ hội tiếp xúc với môi trường lưới cho nhiều người dùng. 4.5.2 Thuật giải điều phối ACostPI Định nghĩa khái niệm Cost Per Instruction (CostPI): CostPI Ai= ஻௨ௗ௚௘௧ ஺೔ ௅௘௡௚௧௛ ஺೔ Khái niệm CostPI của một ứng dụng là một đại lượng cho biết độ quan trọng của một ứng dụng, thể hiện khả năng chi trả của khách hàng cho ứng dụng này. Thuật giải điều phối ACostPI quan tâm đến giá trị CostPI của các ứng dụng: để công bằng đối với khách hàng, hệ thống sẽ ưu tiên cho các ứng dụng có CostPI cao hơn được quyền chọn tài nguyên và thực thi trước. Mô tả: Tương tự thuật giải điều phối ADeadline, chỉ khác ở Bước 1 – Sắp xếp các ứng dụng - Bước 1: Sắp xếp các ứng dụng trong tập A theo thứ tự CostPI giảm dần, các ứng dụng có đại lượng CostPI cao hơn được ưu tiên xếp trước - Bước 2:Duyệt danh sách các ứng dụng theo thứ tự đã sắp xếp, ứng với mỗi ứng dụng: o Gửi thông tin về ứng dụng cho tất cả các providers o Provider tính toán và gửi lời chào giá cho ứng dụng o Trong số các lời chào giá thỏa yêu cầu của ứng dụng, Broker lựa ra lời chào giá có chi phí thấp nhất và giao cho provider đó thực thi - Bước 3: Bỏ ứng dụng ra khỏi tập ứng dụng A. Nếu còn ứng dụng trong tập A, trở lại Bước 2. Thuật giải: A = sort (A, BY_COSTPI_DES); //sort các ứng dụng theo CostPI giảm dần while (A≠Ø) 45 Ai=get_first(A); //ứng dụng có COSTPI cao nhất O=Ø; //Tập các offer từ provider foreach Pj in P //Duyệt tất cả provider send_request(Ai,Pj); //Gửi yêu cầu đến provider Pj recv(Pj,Oij); //Nhận lời chào giá từ Pj cho ứng dụng Ai if (Finish_Time(Oij) ≤ Deadline(Ai) && Cost(Oij) ≤ Budget(Ai) ) then O=O+{Oij} //Thêm lời chào giá vào tập Offer end foreach if ( O ≠ Ø ) then //Nếu có provider thỏa yêu cầu Oik = min_cost (O); //Lựa ra Offer có giá thấp nhất send_app(Ai,Pk); //Gửi Ai cho provider Pk thực thi end if A = A \ {Ai}; //Loại Ai khỏi tập Application end while Độ phức tạp: hoàn toàn tương tự thuật giải điều phối theo Deadline, độ phức tạp là O(n*m) Đặc điểm: - Chú ý nhiều hơn đến lợi nhuận vì sắp xếp các ứng dụng theo CostPI giảm dần - Ưu tiên hơn cho những khách hàng chấp nhận trả giá cao cho ứng dụng, đây là một yếu tố quan trọng giúp thuật giải gần với thực tế hơn. - Độ phức tạp không quá cao, ở mức chấp nhận được - Thích hợp cho các hệ thống muốn có sự cân bằng về lợi nhuận thu được và thời gian chạy thuật giải điều phối. 4.5.3 Thuật giải điều phối ABenefit Thuật giải điều phối theo CostPI chỉ chú trọng đến ngân sách (budget) khách hàng chấp nhận trả cho ứng dụng, và giả định các ứng dụng có CostPI cao sẽ mang lại lợi nhuận cao. 46 Cách tiếp cận này vẫn có nhược điểm là chưa quan tâm đến chi phí thực thi do các providers chào giá. Chi phí thực thi này không hẳn chỉ tuân theo chiều dài của ứng dụng mà có thể bị chi phối bởi nhiều yếu tố khác. Một số ví dụ tiêu biểu: - Hệ thống có provider A và provider B cách xa nhau về mặt địa lý. Provider B có chính sách giảm giá cho tất cả các ứng dụng của khách hàng địa phương 25%. - Provider B là một provider vừa thành lập, có chính sách giảm giá 10% cho những ứng dụng có chi phí thực thi cao hơn 5000$ - Một ứng dụng Ai chuyên về tính toán số học, yêu cầu thư viện Matlab trong quá trình thực thi. Nếu ứng dụng Ai này chạy trên các máy tính cụm đã có sẵn thư viện Matlab sẽ giảm được chi phí, nếu thực thi trên các máy tính cụm khác phải chi trả thêm 15% phí thuê tài nguyên bên ngoài máy tính cụm. Lúc này broker phải ưu tiên ứng dụng Ai được phép chọn tài nguyên thực thi trước các ứng dụng khác. Để điều phối các ứng dụng trong trường hợp các providers có chính sách uyển chuyển về giá, ta định nghĩa khái niệm Benefit (lợi nhuận) cho ứng dụng: Benefit Aij=  ஻௨ௗ௚௘௧ ஺೔ –஼௢௦௧ ஺೔ೕ ௅௘௡௚௧௛ ஺೔ Trong đó Cost Aij là chi phí thực thi của ứng dụng Ai trên tài nguyên Rj Đại lượng Benefit thể hiện lợi nhuận thu được (Budget Ai – Cost Aij) trên một đơn vị chiều dài của ứng dụng Ai khi thực thi trên tài nguyên Rj Mô tả: Tập A: tập các ứng dụng tại Broker Tập O: tập các lời chào giá cho các ứng dụng. Bước 1: Ứng với mỗi ứng dụng, yêu cầu tất cả các providers báo giá chi phí thực thi ứng dụng trên provider đó 47 Bước 2: Trong số những lời chào giá thỏa yêu cầu của ứng dụng, tìm ra lời chào giá cho giá trị Benefit cao nhất. Điều phối ứng dụng cho provider tương ứng. Bước 3: Nếu ở bước 2 không có lời chào giá nào thỏa yêu cầu, dừng thuật giải. Bước 4: Loại bỏ ứng dụng vừa điều phối ra khỏi tập ứng dụng. Nếu vẫn còn ứng dụng chưa điều phối, quay lại bước 1. Thuật giải: while (A≠Ø) O=Ø; foreach Ai in A foreach Pj in P send_request(Ai,Pj); recv(Oij); if (Finish_Time(Oij) ≤ Deadline(Ai) && Cost(Oij) ≤ Budget(Ai) ) then O=O+{Oij} //Thêm lời chào giá vào tập Offer end foreach end foreach if (O≠Ø) then OiMax jMax = max_benefit(A,O); send(AiMax,PjMax); else return;//Kết thúc thuật giải end if A=A \ {AiMax}; end while Độ phức tạp: 48 Dựa vào đoạn pseudo code, nhận thấy thuật giải phải lặp lại khi còn ứng dụng chưa điều phối, trong mỗi lần lập thì mỗi ứng dụng phải được chào giá lên tất cả provider. Do đó độ phức tạp của thuật giải là O(n2*m). Có thể rút ngắn thuật giải: Khi điều phối một ứng dụng Ai lên provider Pj, nếu môi trường lưới không có sự biến động quá lớn của các tài nguyên, ta chỉ cần chào giá các ứng dụng còn lại với chính provider Pj này, không cần chào giá lại với các providers khác. Do đó độ phức tạp trong trường hợp tốt nhất là O(n2) Đặc điểm: - Quan tâm đến giá thành thực thi của ứng dụng, do đó lợi nhuận của hệ thống sẽ cao hơn thuật toán CostPI đã đề xuất - Độ phức tạp cao - Thích hợp cho các hệ thống chú trọng tối đa lợi nhuận thu được hoặc chính sách giá thay đổi nhiều với các providers khác nhau. Ở system broker, ba thuật giải định thời ADeadline, ACostPI, ABenefit được đề xuất nhằm thỏa mãn các tiêu chí khác nhau của hệ thống. Thuật giải ADeadline chú trọng đến việc thực thi được nhiều ứng dụng của người dùng nhất, thuật giải ACostPI và ABenefit lại chú trọng đến doanh thu của hệ thống. Những đặc điểm này sẽ được kiểm chứng trong phần 5.1 của chương 5. 4.6 Thuật giải điều phối công việc tại một máy tính cụm Khi provider nhận được lời yêu cầu (request) từ phía system broker, provider sẽ chuyển thông tin về ứng dụng đến từng máy tính cụm (cluster) do provider quản lý. Mỗi máy tính cụm sẽ tự tính toán, ước định và gửi lời chào giá trở lại cho provider. Mỗi máy tính cụm vẫn là tài sản riêng của các tổ chức, do đó broker hay provider không thể ép các máy tính cụm phải điều phối ứng dụng theo một trình tự cụ thể mà mỗi máy tính cụm sẽ có một chính sách riêng, có thể là FIFO (First In First Out), SJF (Shortest Job First) hoặc Round Robin… 49 Tuy không yêu cầu các máy tính cụm phải tuân theo một chính sách điều phối cụ thể, luận văn cũng sẽ đề xuất một thuật giải điều phối cho các máy tính cụm khi nhận được một ứng dụng. Thuật giải cố gắng cân bằng giữa thời gian thực thi ứng dụng và độ phức tạp của quá trình điều phối. Thuật giải dựa trên thuật giải MAX_MIN đã trình bày ở mục 3.4.5, đây là một trong những thuật giải được chứng minh giúp thực thi các ứng dụng một cách nhanh chóng. Thuật giải: Khi một ứng dụng được chuyển đến cho máy tính cụm, nó được đặt vào cuối cùng trong hàng đợi công việc của máy tính cụm đó. Xét ở mức ứng dụng, các ứng dụng sẽ được thực thi lần lượt theo nguyên lý FIFO, ứng dụng vào hàng đợi trước sẽ thực thi trước. Một ứng dụng có nhiều tác vụ, xét riêng ở mức một ứng dụng cụ thể các tác vụ này sẽ được thực thi theo thuật giải MAX-MIN Ví dụ: Tại máy tính cụm có 3 ứng dụng được xếp theo thứ tự sau Queue Application 1 Application 2 Application 3 Các tác vụ trong ứng dụng: Application 1 40 90 Application 2 20 90 Application 3 60 30 50 Máy tính cụm này có 2 máy tính con, có năng lực tương ứng là 10 và 15. Các ứng dụng sẽ được điều phối theo mô hình FIFO, ứng dụng 1 sẽ được ưu tiên thực thi trước sau đó mới đến ứng dụng 2, ứng dụng 3. Các tác vụ trong từng ứng dụng sẽ theo mô hình MAX_MIN, tác vụ dài hơn sẽ được ưu tiên trước. Kết quả: Thời gian(s) 0 3 4 5 6 11 Máy Tính 1 (10) 40/10=4 (App1) 20/10=2 (App 2) 60/10=6 (App3) Thời gian(s) 0 5 6 11 12 13 Máy Tính 2 (15) 90/15=6 (App1) 90/15=6 (App2) 30/15=2 (App3) Với thuật giải điều phối như trên, quá trình tính toán và chào giá của máy tính cụm khi nhận được thông tin về một ứng dụng sẽ như sau: Qui ước: Một máy tính cụm có nhiều máy tính con. Trong đó Power(Mj) là năng lực tính toán của máy Mj, Cost(Mj) là chi phí sử dụng máy Mj tính theo giây, Start(Mj) là thời điểm máy Mj sẵn sàng để thực thi công việc kế tiếp. Thuật giải định giá: evaluate (Application a){//Định giá cho ứng dụng a Task T = getTasks(a); //Lấy danh sách các tác vụ trong A T = sort (T, BY_LENGTH_DES);//sort T theo Length giảm dần totalCost=0;//Chi phí thực thi ứng dụng JobEnd= Ø;//Ghi nhận thời gian hoàn thành của các tác vụ while ( T ≠ Ø) Ti=getFirst(T);//Tác vụ dài nhất, theo nguyên lý Max-Min Ei=Ø; //Tìm thời gian hoàn thành sớm nhất của tác vụ Ti foreach Mj in Machine//Duyệt danh sách các máy trong cluster Endij=Start(Mj) + Length(Ti)/Power(Mj); 51 //Thời gian hoàn thành tác vụ Ti trên máy Mj Ei=Ei+{Endij}; end foreach Ei jMin=min(Ei);//Thời gian hoàn thành sớm nhất của tác vụ Ti send(Ti,MjMin);//Giao tác vụ Ti cho máy MjMin Start(MjMin)=Ei jMin;//Tăng thời điểm sẵn sàng phục vụ của MjMin //Giá thực thi của tác vụ Ti totalCost+=Length(Ti)/Power(MjMin) * Cost(MjMin); JobEnd=JobEnd+{Ei jMin};//Ghi nhận thời gian hoàn thành tác vụ end while Deadline=max(JobEnd); //Thời gian hoàn thành của Ứng Dụng là thời gian hoàn thành của tác vụ trễ nhất Budget=totalCost; send(Deadline, Budget, a);//Gửi lời chào giá cho ứng dụng a. } 4.7 Các đề xuất cho Provider – Nhà cung cấp Theo sơ đồ hoạt động ở hình 4-1, hoạt động của provider bị chi phối khá nhiều bởi system broker. System broker sẽ là nơi sắp xếp các ứng dụng, sau đó gửi thông tin lần lượt từng ứng dụng cho provider. Provider mặc dù không thể can thiệp vào quá trình sắp xếp, lựa chọn của broker nhưng người quản trị hoàn toàn có thể lựa chọn các phương pháp chào giá khác nhau cho provider. Provider sẽ nhận được rất nhiều lời chào giá cho mỗi ứng dụng từ phía các máy tính cụm (clusters) do provider đó quản lý. Vậy provider nên gửi lên system broker lời chào giá nào để đạt được hiệu quả cao nhất? Ở đây, chúng ta giả định các providers hoạt động vì lợi nhuận. Với các ứng dụng được gửi từ broker, provider sẽ chào giá sao cho chi phí thu được là cao nhất. Có một số phương án được đề ra: - Chào giá cao nhất từ các máy tính cụm gửi lên. 52 - Chào giá thấp nhất từ các máy tính cụm gửi lên. - Đề ra phương án động, tùy theo số lượng các ứng dụng provider nhận được Hình 4-6 Các phương án chào giá của provider 4.7.1 Chào giá COST_MAX Khi provider nhận được các lời chào giá từ các máy tính cụm (clusters) do nó quản lý, provider luôn gửi lời chào có giá cao nhất lên system broker. Ý tưởng: Gửi lời chào giá cao nhất để thu lợi nhuận cao nhất Tuy nhiên, phương pháp này có nhiều điểm bất lợi, ví dụ: Theo sơ đồ ở hình 4-6, hệ thống có 2 providers cùng hoạt động. Provider 1 có thể cung ứng với các mức giá lần lượt là 30$ và 40$, provider 2 có thể cung ứng với các mức giá lần lượt là 35$ và 45$. Nếu cả 2 providers đều hoạt động theo nguyên tắc chào mức giá cao nhất, mức giá 40$ và mức giá 45$ sẽ được gửi lên System Broker. System Broker luôn chọn mức giá thấp nhất được gửi lên từ phía các providers, do đó provider 1 sẽ được chọn để thực thi ứng dụng, cụ thể sẽ được thực thi tại máy tính cụm B với mức giá 40$. 53 Khi số lượng ứng dụng tăng lên nhiều, máy tính cụm B sẽ không thể đáp ứng ràng buộc của mọi ứng dụng (chủ yếu vi phạm ràng buộc về Deadline). Do đó provider 1 sẽ chào giá từ máy tính cụm còn lại là máy cụm A với mức giá 30$. Tại thời điểm này provider 2 vẫn không nhận được ứng dụng vì mức giá 30$ thấp hơn 45$, đến khi provider 1 hoàn toàn quá tải, các ứng dụng mới được gửi cho provider 2. Nhận xét: Ta có thể nhận thấy, việc chào giá cao nhất từ các máy tính cụm sẽ làm giảm khả năng cạnh tranh của provider, từ đó cũng dẫn đến hệ thống không cân bằng. Đây không phải là một phương án chào giá tốt. 4.7.2 Chào giá COST_MIN Ngược lại với trường hợp trên, các providers sẽ luôn chào giá thấp nhất được gửi lên từ các máy tính cụm. Ý tưởng: Tăng sức cạnh tranh cho provider Cũng theo hình 4-6, ta thấy system broker ban đầu sẽ chọn mức giá 30$ từ provider 1. Khi máy tính cụm A quá tải, provider 1 sẽ chào mức giá kế tiếp là 40$. Mức giá này cao hơn mức giá provider 2 đang chào là 35$ (mức giá thấp nhất của provider 2). Do đó các ứng dụng sau đó sẽ chuyển sang provider 2 cho đến khi máy tính cụm C tại provider 2 quá tải. Nhận xét: Với hình thức chào giá thấp nhất, các providers sẽ tăng tính cạnh tranh hơn rất nhiều, hoạt động của hệ thống cũng cân bằng hơn. 4.7.3 Adaptive Provider Phương thức chào giá thấp nhất thật sự đã nâng khả năng cạnh tranh cho các providers. Tuy nhiên đây chưa phải là phương pháp tối ưu, thu lại lợi nhuận cao nhất cho các providers, nhất là trong trường hợp các providers nằm rải rác ở nhiều khu vực khác nhau nên có các mức giá rất khác nhau 54 Hình 4-7 Lợi nhuận giảm khi chào giá thấp nhất Hình 4-7 minh họa một trường hợp provider 2 có mức giá cao hơn rất nhiều so với provider 1. Nếu provider 1 vẫn tuân thủ nguyên tắc chào giá thấp nhất sẽ không thu được doanh thu cao, mặc dù hầu như luôn nhận được các ứng dụng để thực thi. Luận văn đề nghị một phương pháp hoạt động uyển chuyển hơn cho các providers, giá thực thi sẽ thay đổi tùy theo số lượng các ứng dụng mà provider đó nhận được. Ở đây tạm gọi là các Adaptive Provider – provider có tính thích nghi. Nguyên tắc hoạt động của các providers này gần giống như trường hợp chào giá thấp nhất: Ban đầu provider luôn chào giá thấp nhất mình có thể cung ứng để tăng tính cạnh tranh. Nếu số lượng các ứng dụng liên tiếp nhận được vượt quá một ngưỡng đề ra (ví dụ 5 ứng dụng liên tiếp), nghĩa là provider hiện đang chào giá quá thấp nên ta có thể tăng chi phí trước khi gửi cho system broker. Ngược lại, nếu số lượng các ứng dụng liên tiếp không nhận được vượt quá một ngưỡng đề ra (ví dụ 3 ứng dụng), nghĩa là provider đang chào giá quá cao nên ta sẽ hạ chi phí trước khi chào giá cho system broker. Giá sàn của trường hợp này là giá thấp nhất các máy tính cụm có thể cung cấp, và giá trần là ngân sách (budget) của ứng dụng đó. Nếu đã đạt giá sàn, ta sẽ không giảm giá; ngược lại nếu đã đạt giá trần ta sẽ không tiếp tục tăng giá vì như vậy sẽ vi phạm ràng buộc của ứng dụng. 55 Vấn đề đặt ra là các providers không có bất kỳ mối liên hệ nào với nhau, làm sao để biết khi nào một provider không nhận được một ứng dụng để thực thi. Xét tình huống minh họa sau: Giữa broker và provider có 2 thông điệp chính: - Request: Broker gửi thông tin về ứng dụng, yêu cầu provider báo giá - Submit Application: Broker chấp nhận lời chào giá của provider, gửi ứng dụng cho provider thực thi Thông điệp Request từ Broker Thông điệp Submit Application Application 1 Application 1 Application 2 Application 3 Application 3 Application 4 Bảng 4-1 Minh họa adaptive provider Bảng 4-1 minh họa provider được nhận ứng dụng 1 và ứng dụng 3, không được nhận ứng dụng 2. Có thể rút ra qui luật: Khi nhận được 1 request mới, nếu ứng dụng được thực thi gần nhất và ứng dụng được chào giá gần nhất khác nhau thì provider đã bị lỡ mất một ứng dụng không được broker giao cho thực thi. Ví dụ: Khi nhận được request cho ứng dụng Application 3, ứng dụng được thực thi gần nhất là Application 1, ứng dụng được chào giá gần nhất là Application 2. Hai ứng dụng này khác nhau nên có thể kết luận provider không được broker giao cho thực thi ứng dụng Applcation 2. Dựa vào qui luật trên, ta xây dựng thuật giải chào giá Adaptive. Thuật giải: Sử dụng 2 biến got (đếm số lượng ứng dụng provider thực thi liên tiếp), và missed (đếm số lượng ứng dụng không được thực thi liên tiếp). //Ban đầu missed=0; got=0; 56 //Nhận thông điệp từ system broker: switch (event): { case REQUEST://Nhận._.