Thuận toán MODE giải bài toán lập lịch luồng công việc

Nội dung text: Thuận toán MODE giải bài toán lập lịch luồng công việc

1. Các công trình nghiên cứu phát triển CNTT và Truyền thông Tập V-1, Số 17 (37), tháng 6/2017 Thuận toán MODE giải bài toán lập lịch luồng công việc An Algorithm MODE for Workflow Scheduling Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cƣờng Abstract: Cloud computing is a new trend of phát triển của môi trường điện toán đám mây (Cloud information and communication technology that Computing) đã tạo ra các cơ hội cho việc giải quyết enables resource distribution and sharing at a large bài toán lập lịch luồng công việc, với khả năng về tài scale. The Cloud consists of a collection of virtual nguyên dự phòng và luôn sẵn dùng sẽ giúp giảm bớt machine that promise to provision on-demand thời gian chờ đợi giữa các tác vụ trong luồng công computational and storage resources when needed. việc, khả năng cung cấp tài nguyên theo nhu cầu End-users can access these resources via the Internet khách hàng cũng là một lợi thế lớn của điện toán đám and have to pay only for their usage. Scheduling of mây, khả năng này sẽ cho phép các ứng dụng dạng scientific workflow applications on the Cloud is a luồng công việc có thể bắt đầu được thực hiện ngay khi chỉ có một phần tài nguyên được đáp ứng mà challenging problem that has been the focus of many không cần phải chờ đợi cho đến khi đủ tất cả các tài researchers for many years. In this work, we propose nguyên cần thiết. Ngoài ra, khả năng co giãn trong a novel algorithm for workflow scheduling that is môi trường điện toán đám mây cũng là một đặc trưng derived from the Opposition-based Differential hữu ích với các ứng dụng dạng luồng công việc vì nó Evolution method. This algorithm does not only cho phép các hệ thống luồng công việc dễ dàng tăng, ensure fast convergence but it also averts getting giảm các tài nguyên của ứng dụng theo nhu cầu. Bản trapped into local extrema. Our CloudSim-based chất của vấn đề lập lịch luồng công việc trong môi simulations show that our algorithm is superior to its trường điện toán đám mây là gán các tác vụ của luồng predecessors. Moreover, the deviation of its solution công việc vào thực thi trên các tài nguyên của đám from the optimal one is negligible. mây sao cho thời gian hoàn thành luồng công việc Keyword: Workflow scheduling, Opposition-Based (Makespan) là nhỏ nhất. Differential Evolution, cloud computing, Differential Nội dung tiếp theo của bài báo gồm những phần Evolution. chính như sau. Phần II trình bày một số công trình liên quan đến bài toán lập lịch luồng công việc. Phần III I. GIỚI THIỆU mô tả bài toán và trình bày mô hình toán học, sau đó Bài toán lập lịch luồng công việc là một bài toán phát biểu bài toán và chứng minh rằng nó thuộc lớp đã được nghiên cứu từ những năm 1950, và bài toán NP-Khó. Phần IV giới thiệu thuật toán đề xuất - này đã được chứng minh thuộc lớp NP-Khó. Trong MODE. Để kiểm chứng hiệu năng của thuật toán những năm gần đây đã có rất nhiều ứng dụng khoa MODE, Phần V trình bày quá trình thực nghiệm trên học được mô hình hóa bởi dạng đồ thị luồng công việc một số luồng công việc khoa học mẫu trong môi như ứng dụng Montage [1], CyberShake [2], trường đám mây thông qua công cụ mô phỏng Epigenomics [3], LIGO [4], v.v. một trong những CloudSim và gói thư viện Jswarm [5] và phân tích số thách thức của bài toán lập lịch luồng công việc là liệu thu được, từ đó đưa ra những nhận xét so sánh. phải hoàn thành luồng công việc với thời gian nhỏ Phần VI trình bày kết luận và hướng nghiên cứu tiếp nhất trong điều kiện giới hạn về nguồn tài nguyên. Sự theo. - 51 -
2. Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 II. NHỮNG CÔNG TRÌNH LIÊN QUAN thời gian, không gian, các tài nguyên và chi phí, quá Bài toán lập lịch luồng công việc đã được chứng trình lập lịch sẽ sử dụng mức ưu tiên này để quyết minh là thuộc lớp NP-Khó [6] nghĩa là thời gian để định các tác vụ được chọn trong quá trình lập lịch. tìm ra lời giải tối ưu tăng rất nhanh theo kích cỡ dữ Selvi đã đề xuất thuật toán lập lịch luồng công việc liệu đầu vào, vì vậy đã có nhiều công trình nghiên cứu trong môi trường điện toán lưới (Grid) [14], tác giả đã nhằm tìm ra lời giải gần đúng trong thời gian ngắn. vận dụng thuật toán tiến hóa vi phân (DE) vào giải bài Sadhasivam đã đề xuất thuật toán lập lịch luồng toán lập lịch luồng công việc trên môi trường điện công việc dựa trên sự cân bằng tải trong môi trường toán lưới nhằm cực tiểu thời gian hoàn thành luồng điện toán đám mây [7]. Thuật toán không chỉ đáp ứng công việc (makespan). Tác giả đã chỉ ra giá trị các yêu cầu từ người sử dụng mà còn cung cấp khả Makespan tìm được bởi thuật toán đề xuất là nhỏ hơn năng sử dụng tài nguyên một cách hiệu quả. Đây là so với thuật toán PSO. Xu đã đề xuất thuật toán thuật toán theo hướng nâng cao hiệu quả dịch vụ dựa COODE [15] (Current Optimum Opposition-based trên Meta-heuristic. Burya đã trình bày một cách tóm Differential Evolution) nhằm tìm giá trị tối ưu cho các tắt về các chức năng của công cụ mô phỏng CloudSim hàm số dựa theo phương pháp tiến hóa vi phân đối [8] - môi trường mô phỏng cho phép cài đặt và thực xứng, tác giả đã đề xuất công thức tìm điểm đối xứng nghiệm các thuật toán lập lịch luồng công việc trong của một điểm dựa theo giá trị tối ưu hiện tại nhằm môi trường điện toán đám mây. Guo-Ning đã đề xuất thay đổi toán tử đột biến trong phương pháp tiến hóa một thuật toán lập lịch luồng công việc dựa trên giải vi phân và tác giả đã so sánh thuật toán COODE với thuật di truyền [9]. Trong đó đưa vào nhiều ràng buộc các thuật toán DE và ODE. Kết quả cho thấy thuật dịch vụ khác nhau như thời gian hoàn thành, băng toán đề xuất COODE tốt hơn các thuật toán đối sánh. thông, chi phí, độ tin cậy. Tác giả đã sử dụng kết hợp Các công trình nêu trên đều chưa hướng tới mục với giải thuật luyện thép sau pha lựa chọn, trao đổi tiêu duy nhất là giảm thiểu thời gian hoàn thành của chéo, đột biến nhằm tăng cường khả năng tìm kiếm cục bộ của giải thuật di truyền. luồng công việc với các cấu trúc phức tạp và sự đa dạng về dữ liệu truyền qua lại giữa các tác vụ trong Các tác giả trong bài báo [10] đã đề xuất thuật toán luồng công việc và chưa trình bày rõ ràng về mô hình EGA (Enhanced Genetic Algorithm) lập lịch bằng toán học của bài toán lập lịch luồng công việc. phương pháp di truyền. Trong công trình các tác giả sử dụng thuật toán Enhanced Max Min trong bước III. MÔ HÌNH LÝ THUYẾT khởi tạo quần thể nhằm tìm ra các cá thể tốt cho quá trình tiến hóa. Hệ thống tính toán Giả thiết cho trước hệ thống tính toán bao gồm: Pandey [11] đã đề xuất thuật toán lập lịch luồng công việc PSO Heuristic (Particle Swarm Tập hợp N máy chủ trong môi trường điện toán Optimization Heuristic – PSO_H) trong môi trường đám mây S = {S1, S2, SN}. điện toán đám mây dựa trên chiến lược tối ưu bày đàn. Luồng công việc cần thực hiện biểu diễn bởi đồ thị Rajkumar đã đề xuất một thuật toán lập lịch phân cấp có hướng, không có chu trình G = (V, E), mỗi đỉnh [12] và đưa vào các tham số dịch vụ khác nhau, chẳng biểu thị một tác vụ, mỗi cạnh biểu diễn mối quan hạn như thời gian đáp ứng. Thuật toán sử dụng tham hệ cha-con giữa một cặp tác vụ. số này như một quyền ưu tiên để lựa chọn các tác vụ Tập các tác vụ T = {T1, T2, TM} với M là số lập lịch. Cao và các đồng nghiệp đã trình bày thuật lượng tác vụ. toán lập lịch dựa trên giải thuật ABC (Activity Based Khối lượng tính toán của tác vụ Ti ký hiệu là Wi , Costing) [13]. Thuật toán này gán mức ưu tiên cho đo bằng đơn vị flop (floating point operations: mỗi tác vụ trong luồng công việc theo các tham số về phép tính trên số thực dấu phảy động). - 52 -
3. Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 ( ) * + Tốc độ tính toán của máy tính, đo bằng đơn vị { ( )} ( ) flop/s (số phép tính thực hiện được trên giây), ký (3) hiệu P( ), là hàm số được định nghĩa như sau: với tf(Ti) là thời điểm kết thúc và ts(Ti) là thời điểm + P: S R bắt đầu thực hiện của tác vụ Ti Si P(Si) Mục tiêu của bài toán Mọi cặp máy chủ (Si, Sk) bất kỳ đều có đường Mục tiêu của bài toán là tìm lịch biểu F sao cho truyền để trao đổi dữ liệu với nhau (1 ≤ i, k ≤ N). ( ) Băng thông của đường truyền, ký hiệu B( ), là tốc độ truyền dữ liệu giữa các máy chủ, đo bằng đơn vị Phát biểu và chứng minh độ phức tạp bit trên giây (bps), là hàm số được định nghĩa như Bài toán đang xét, từ đây ký hiệu là WSP - sau: Workflow Scheduling Problem, được phát biểu như + sau: giả sử cho trước tài nguyên của đám mây bao B: S S R gồm tập máy chủ S với tốc độ tính toán và băng thông (Si, Sk) B(Si, Sk) Hàm băng thông B( ) tuân theo các ràng buộc sau: được biểu diễn như trên. Giả sử tập tác vụ T được biểu diễn bởi đồ thị G = (V, E) như trên. Hàm mục + B(Si, Si) = : thời gian truyền từ một máy chủ tới chính nó bằng 0, nghĩa là nếu tác vụ cha và tác vụ con tiêu đặt ra là cực tiểu thời gian hoàn thành luồng được bố trí trên cùng một máy chủ thì không mất thời công việc gian để truyền dữ liệu giữa chúng vì dữ liệu đó được makespan → min lưu trữ và sử dụng ngay tại chỗ. Bổ đề: WSP là bài toán thuộc lớp NP-Khó Chứng minh: + B(Si, Sk ) = B(Sk, Si): kênh truyền hoạt động từ hai đầu với tốc độ tương đương nhau. Xét bài toán SCHED [16] sau đây: giả sử cho trước tập máy chủ và tập tác vụ gồm các thành phần như đã Khối lượng dữ liệu cần truyền giữa hai tác vụ Ti và định nghĩa ở bài toán WSP trên đây, ngoài ra bổ sung Tk, ký hiệu là Dik, là các giá trị cho trước, Dik 0 thêm điều kiện là tập S gồm các máy chủ giống hệt khi và chỉ khi Ti là tác vụ cha của Tk, trong trường nhau về tốc độ tính toán. hợp ngược lại Dik = 0. Sinnen đã chứng mình rằng bài toán SCHED thuộc Khái niệm lịch biểu lớp NP-Khó [16]. Quay về bài toán WSP đang xét, dễ Một phương án xếp lịch F, còn gọi là lịch biểu F, thấy rằng bài toán SCHED chỉ là một trường hợp được xác định bởi hai hàm (ts , proc) trong đó riêng của bài toán WSP khi bổ sung thêm điều kiện ; ts(Ti) là thời điểm mà tác vụ n T bắt ràng buộc sau đây: P(Si) = P(Sj) i, j = 1 N. đầu được thực hiện. Vì vậy, rõ ràng bài toán WSP cũng thuộc lớp NP- ; proc(Ti) là máy tính được phân công Khó. thực hiện tác vụ Ti T. IV. GIẢI PHÁP ĐỀ XUẤT Từ các giả thiết trên suy ra thời gian tính toán của Thuật toán tiến hóa vi phân dựa trên thông tin đối tác vụ Ti là: xứng (Opposition-based differential evolution – ODE) Wi (i = 1, , M) (1) P proc T được đề xuất bởi Storn và Price [17]. Tương tự như i các thuật toán tiến hóa khác, thuật toán ODE gồm hai Thời gian truyền dữ liệu giữa tác vụ T và T là: i k bước chính: khởi tạo quần thể và sinh quần thể mới D ik (i,k = 1, , M) (2) bằng cách áp dụng các toán tử di truyền như đột biến, B proc Ti , proc Tk trao đổi chéo và lựa chọn tự nhiên. Tuy nhiên, thuật Makespan của lịch biểu F biểu diễn theo như sau: toán ODE nâng cao hiệu năng tìm kiếm trong hai bước này bằng cách tìm kiếm thêm lời giải trong phần đối - 53 -
4. Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 xứng của không gian tìm kiếm hiện tại. Để giải quyết ̅̅ ̅ ̅(̅ ̅) ( ) bài toán lập lịch luồng công việc đã đề xuất trong mô Sau đó sẽ gán các giá trị tương ứng với mỗi vị trí j hình phần III, chúng tôi sẽ đề xuất phương pháp tìm trong véc tơ ̅ bởi số hiệu máy chủ có tốc độ tính toán phần tử đối xứng trong quần thể và kết hợp với gần giá trị ̅̅ ̅ ̅̅(̅ ̅) nhất: phương pháp bánh xe quay vòng dựa trên hạng cá thể ̅̅̅̅̅̅ nhằm tìm ra các cá thể tốt cho quá trình đột biến qua ̅̅ ̅ | ( ) ( )| | ( ) ( )| (6) đó nâng cao hiệu năng của thuật toán. Algorithm: OP_Algorithm Định nghĩa 1: Giả sử x là số thực và x [a, b], khi Input: population p = (x1, x2, ,xPopSize) đó phần tử đối xứng của x kí hiệu là ̅ và được tính Output: opposite of population OP như sau: 1. for i=1 to PopSize do 2. ̅ ( ) ( ) ̅ (3) 3. Gán số hiệu máy chủ cho các vị trí Định nghĩa 2: Gọi P(x1, x2, ,xD) là một véc tơ D- j của véc tơ ̅ theo(6) chiều, với xi [ai, bi]; i = 1, 2, , D. Khi đó, véc tơ 4. end for return OP đối xứng của P kí hiệu là ̅ ( ̅̅ ̅ ̅ ̅ ̅ ̅̅̅ ̅) và được tính như sau: IV.3. Phƣơng pháp bánh xe quay vòng dựa trên ̅ (4) hạng cá thể IV.1. Biểu diễn cá thể Bánh xe quay vòng dựa trên hạng cá thể là một Mỗi cá thể trong quần thể được biểu diễn bởi một phương pháp lựa chọn cá thể cho các thế hệ kế tiếp. vec tơ có độ dài bằng số tác vụ trong luồng công việc. Trong phương pháp này, mỗi cá thể được xếp hạng Giá trị tương ứng với mỗi vị trí i trong véc tơ biểu theo một hàm xác định, sau đó sẽ tính xác suất lựa chọn các cá thể theo hạng của chúng. Trong bài báo diễn số hiệu của máy chủ thực thi tác vụ i. này, chúng tôi đề xuất hàm tính hạng cho các cá thể Ví dụ: Xét luồng công việc với 5 tác vụ T = {T1, như sau: T , ,T }, tập máy chủ gồm 3 máy S = {S , S , S }. 2 5 1 2 3 ( ) ( ( ) ) Khi đó cá thể xi = (1, 2, 1, 3, 2) được biểu diễn như sau: (7) Trong đó: 1.0 SP 2.0; pos: vị trí cá thể cần tính T1 T2 T3 T4 T5 hạng S1 S2 S1 S3 S2 IV.2. Phƣơng pháp tính đối xứng cho cá thể Algorithm: RBRWS algorithm Input: population p = (x , x , ,x ) Trong phương pháp ODE, ta cần phải tìm cá thể 1 2 PopSize Output: particle ps đối xứng cho mỗi cá thể trong quần thể hiện tại. Trong Begin bài báo này, chúng tôi đề xuất phương pháp tìm cá thể 1. Sắp xếp các cá thể theo chiều tăng dần của hàm mục tiêu f đối xứng như sau: i 2. for i=1 to PopSize do Gọi a = Max{P(Si)} và b = Min{P(Si)};  i = 1, 2, 3. pos[i]  PopSize – 1 4. for i=1 to PopSize do , N; với P(Si) là tốc độ tính toán của máy chủ Si 5. calculate ranki by equation (7) Giả sử ta có cá thể xi = (Si (1), Si (2), ,Si (M)); Si (j) 6. rand  Random(0,SP) S,  j = 1, 2, , M; cá thể đối xứng của xi kí hiệu là 7. s  PopSize 8. while(rank[s] 0)s— ̅ return xs và ̅ ( ̅̅ ̅ ̅̅(̅ ̅)̅ ̅̅ ̅ ̅(̅ ̅̅) ̅ ̅ ̅ ̅̅(̅ ̅̅)); (5) End. - 54 -
5. Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 IV.4. Thuật toán MODE thể. Véc tơ đột biến của mỗi cá thể i được tính theo Kết hợp các nội dung trên chúng tôi đề xuất thuật công thức: vi  pbest + F (p1 – p2) toán lập lịch luồng công việc trong môi trường điện Trong đó: pbest là cá thể tốt nhất hiện tại toán đám mây dựa trên thông tin đối xứng và gọi là Sau bước đột biến toán tử trao đổi chéo được áp MODE như sau: dụng cho mỗi cá thể xi để sinh ra cá thể mới ui Algorithm MODE ( ) { Input: T, S, size of workload W[1×M], P[1×N], B[N×N], D[M×M], the constant K, the deviation , the number of Trong đó randi,j [0,1], Irand [1,M], CR [0,1]. particle NoP Output: the best position gbest Toán tử lựa chọn được áp dụng để quyết định cá 1. Khởi tạo quần thể P gồm PopSize cá thể nào được sống sót cho thế hệ kế tiếp thể một cách ngẫu nhiên ( ) ( ) 2. OP  OP_Algorithm ; tính quần thể { } đối xứng của quần thể hiện tại 3. Chọn PopSize cá thể tốt nhất từ P Sau khi trao đổi chéo và lựa chọn, tính quần thể đối  OP xứng OP của P theo (5), (6) và chọn ra PopSize cá thể 4. while(Điều kiện lặp)do 5. for i=1 to PopSize do tốt nhất từ P  OP. 6. Lựa chọn cá thể p1 theo thuật Quá trình tiến hóa của quần thể sẽ được thực hiện toán RBRWS qua các toán tử đột biến, trao đổi chéo và lấy đối xứng 7. Lựa chọn cá thể p2 theo thuật toán RBRWS quần thể. Sau mỗi thế hệ chúng ta sẽ tính giá trị hàm 8. F  Random(1,0) mục tiêu (Makespan) của các phương án xếp lịch và 9. vi  pbest + F (p1 – p2) đối sánh với giá trị tốt nhất trong cá thể gbest, nếu có 10. Gán số hiệu máy chủ cho mỗi vị một cá thể cho giá trị makespan tốt hơn thì cá thể đó trí j của véc tơ vi theo (6) 11. randi,j  Random(0,1) sẽ thay thế cá thể gbest hiện tại. 12. I  random(1,M) rand V. KẾT QUẢ THỰC NGHIỆM 13. { Để kiểm chứng thuật toán đề xuất MODE chúng 14. if (makespan(ui) < makespan(xi)) tôi đã sử dụng công cụ mô phỏng Cloudsim [5] để tạo 15. xi  ui lập môi trường đám mây. Đối tượng so sánh là thuật 16. end if 17. end for toán tiến hóa mạnh như PSO Heuristic [14], và thuật 18. rand  Random(0,1) toán Random [18], và EGA [10]. 19. if(rand < J ) r Các chương trình mô phỏng được viết bằng ngôn 20. OP  OP_Algorithm 21. Lựa chọn PopSize cá thể tốt nhất ngữ Java và chạy trên máy tính cá nhân với bộ vi xử lý tử P  OP Intel Core i5 2.2 GHz, RAM 4 GB, hệ điều hành 22. end if Windows 7 Ultimate. 23. End while Return gbest; V.1. Phân nhóm dữ liệu thực nghiệm Bước khởi tạo: khởi tạo ngẫu nhiên quần thể P gồm Dữ liệu sử dụng trong các thực nghiệm bao gồm: PopSize cá thể, quần thể đối xứng OP của P theo (5), Dữ liệu về tốc độ tính toán của các máy chủ và (6), chọn ra PopSize cá thể tốt nhất từ P  OP. băng thông giữa các máy chủ được lấy từ các công Trong mỗi bước lặp chọn ra hai cá thể p1, p2 theo ty cung cấp dịch vụ cloud như Amazon [19]. phương pháp bánh xe quay vòng dựa trên hạng các cá Dữ liệu luồng công việc được lấy từ các bộ dữ liệu thử nghiệm được xây dựng theo độ trù mật khác - 55 -
6. Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 nhau và các luồng công việc từ các ứng dụng thực V.3. Quá trình tiến hành thực nghiệm tế như ứng dụng Montage [1]. Để đánh giá hiệu năng của thuật toán đề xuất Dựa theo tính chất của môi trường điện toán đám MODE chúng tôi đã tiến hành thực nghiệm và so sánh mây, đây là một môi trường tính toán không đồng kết quả của MODE với các thuật toán tiến hóa mạnh nhất, tốc độ tính toán các máy chủ và băng thông hiện nay như PSO_H và Random. Dữ liệu thực không đồng đều, đồng thời cũng dựa theo tính chất nghiệm được lấy từ ứng dụng Montage và các luồng các luồng công việc, số lượng tác vụ, độ trù mật công việc ngẫu nhiên theo độ trù mật khác nhau, các của đồ thị luồng công việc chúng tôi đã tiến hành tham số băng thông, tốc độ tính toán của máy chủ phân loại dữ liệu theo các nhóm với quan hệ về tốc được thiết lập thống nhất cho tất cả các thực nghiệm. độ tính toán các máy chủ và băng thông khác nhau, Với mỗi bộ dữ liệu chúng tôi tiến hành chạy chương độ trù mật của đồ thị luồng công việc cũng được trình 30 lần độc lập. Kết quả thực nghiệm được trình thử nghiệm qua hệ số khác nhau. Chi tiết các bày chi tiết trong Bảng 1, 2 và các Hình 1, 2. Các hình nhóm dữ liệu theo số lượng máy chủ N, số tác vụ này đã chỉ ra kết quả so sánh giữa giá trị trung bình M và hệ số như sau: tính được bởi thuật toán MODE với các thuật toán đối Nhóm 1: M = 5, N = 3; Nhóm 2: M = 10, N = 3, sánh, trong hầu hết các trường hợp thuật toán MODE Nhóm 3: M = 20, N = 8, Nhóm 4: M = 25, N = 8 đều cho kết quả tốt hơn các thuật toán đối sánh, giá trị Mỗi nhóm lại bao gồm ba thực nghiệm khác nhau trung bình tìm được bởi MODE nhỏ hơn giá trị trung về tỷ lệ số cạnh trên số đỉnh của đồ thị luồng công bình tìm được bởi PSO_H từ 8% - 29% và nhỏ hơn việc, ký hiệu là và tính bởi công thức: giá trị trung bình tìm được bởi thuật toán EGA từ 6% | | - 25%. ( ) Hình 1, 2 cũng so sánh giữa giá trị tốt nhất tìm được bởi thuật toán MODE với các thuật toán đối V.2. Tham số cấu hình sánh, qua đó ta thấy giá trị tốt nhất tìm được bởi Các tham số cấu hình của đám mây được thiết lập MODE nhỏ hơn giá trị tốt nhất tìm được bởi PSO_H trong miền giá trị như sau: từ 3% - 19%, chỉ duy nhất trong bộ dữ liệu thực Tốc độ tính toán P của các máy chủ: từ 1 đến 250 nghiệm thứ 5 thuật toán MODE có giá trị tốt nhất nhỏ (million instructions/s); khối lượng dữ liệu D giữa hơn giá trị tốt nhất tìm được bởi PSO_H là 0.25%, giá các tác vụ: từ 1 đến 1000 (MB); băng thông giữa trị tốt nhất tìm được bởi MODE nhỏ hơn giá trị tốt các máy chủ B:từ 10 đến 100 (Mega bit/s). nhất tìm được bởi EGA từ 2% - 20%. Hệ số vi sai F = 0.5; hệ số trao đổi chéo CR = 0.9; Jr = 0.3; PopSize = 50; : từ 0.2 tới 0.7. Bảng 1. Kết quả thực hiện các thuật toán với luồng công việc Montage (đơn vị tính: phút) M N MODE PSO_H RANDOM EGA Best Mean STD Best Mean STD Best Mean STD Best Mean STD 20 8 0.15 29.1 31.0 1.0 35.90 44.2 5.2 56.3 63.3 3.8 35.6 42.0 3.7 20 8 0.31 29.9 31.7 1.2 37.1 44.7 6.1 51.6 67.6 6.8 37.5 42.5 3.2 25 8 0.2 218.0 219.7 1.2 225.0 239.0 8.3 238.0 304.9 33.0 222.4 235.5 4.7 50 8 0.1 81.2 86.3 3.1 95.0 108.0 6.3 110.5 196.8 32.8 96.4 103.5 3.3 Bảng 2. Kết quả thực hiện các thuật toán với luồng công việc Epigenomics (đơn vị tính: giờ) M N MODE PSO_H RANDOM EGA Best Mean STD Best Mean STD Best Mean STD Best Mean STD 100 10 0.25 38.7 40.9 1.2 38.8 44.9 2.8 49.4 75.7 12.5 39.2 41.9 1.4 100 20 0.12 23.0 27.3 1.9 34.1 40.5 3.4 42.9 73.1 14.9 34.4 37.7 1.9 - 56 -
7. Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 Hình 1, 2, cũng so sánh giữa độ lệch chuẩn tìm Dựa trên phương pháp đó, bài báo đề xuất thuật được bởi thuật toán MODE với các thuật toán đối toán MODE hoạt động theo thuật toán tiến hóa vi sánh. Giá trị độ lệch chuẩn của MODE luôn nhỏ hơn phân kết hợp với phương pháp đối xứng nhằm tìm độ lệch chuẩn của tất cả các thuật toán đối sánh, ra phương án thực thi tốt nhất. chứng tỏ thuật toán MODE có chất lượng lời giải tốt Tiếp theo chúng tôi dự định sẽ cải tiến phương hơn các thuật toán đối sánh và độ ổn định trong các pháp lựa chọn cá thể và cơ chế lai ghép nhằm tìm ra lần chạy cũng tốt hơn. cá thể tốt hơn cho các thế hệ kế tiếp. 200 TÀI LIỆU THAM KHẢO 150 [1] G. B. Berriman, et al, Montage: A Grid Enabled Engine for Delivering Custom Science-Grade Mosaics 100 Best On Demand", in SPIE Conference, 2004. 50 Mean [2] P. Maechling, et al, SCEC CyberShake 0 STD Workflows, Automating Probabilistic Seismic Hazard Analysis Calculations”, Springer, 2006. [3] "USC Epigenome Center". [Online]. Hình 1. So sánh các thuật toán với M=50, N=8 [4] LIGO Project. LIGO - Laser Interferometer Gravitational Wave Observatory. [Online]. 80 [5] R. N. Calheiros, R. Ranjan, A. 60 Beloglazov, Cesar A. F. De Rose, and R. 40 Best Buyya, CloudSim: A Toolkit for Modeling and Mean Simulation of Cloud Computing Environments and 20 Evaluation of Resource Provisioning Algorithms, STD 0 Software: Practice and Experience, volume 41, Number 1, Pages: 23-50, Wiley Press, USA, 2011 [6] J.D. Ullman, NP-complete scheduling problems, Journal of Computer and System Sciences, pages 384- Hình 2. So sánh các thuật toán với M=100, N=20 393, volume 10, issue 3, 1975 [7] R. Rajkumar, T. Mala, Achieving Service Level VI. KẾT LUẬN Agreement in Cloud Environment using Job Prioritization in Hierarchical Scheduling, Proceeding Lập lịch luồng công việc là một vấn đề phức tạp of International Conference on Information System nhưng rất quan trọng vì nó quyết định hiệu năng của Design and Intelligent Application, 2012, vol 132, pp đám mây điện toán. Để đạt được mục tiêu lập lịch là 547-554. tối thiểu hóa thời gian thực thi, bài báo đã trình bày [8] R. Burya, R. Calheiros, Modeling and những kết quả chính sau đây: Simulation of Scalable Cloud Environment and the Cloud Sim Toolkit: Challenges and Opportunities, Đề xuất một mô hình lý thuyết cho bài toán lập lịch IEEE publication 2009,pp1-11. luồng công việc trong môi trường điện toán đám [9] G. Guo-Ning and H. Ting-Lei, Genetic Simulated mây. Annealing Algorithm for Task Scheduling based on Đề xuất phương pháp tính đối xứng cho các cá thể. Cloud Computing Environment, Proceedings of International Conference on Intelligent Computing and Integrated Systems, 2010, pp. 60-63 - 57 -
8. Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT Tập V-1, Số 17 (37), tháng 6/2017 [10] S. Singh, M.Kalra, Task scheduling optimization SƠ LƢỢC VỀ TÁC GIẢ of independent tasks in cloud computing using enhanced genetic algorithm, International Journal of PHAN THANH TOÀN Application or Innovation in Engineering & Sinh năm 1974 tại Thái Nguyên. Management, V.3, Issue 7, 2014. Tốt nghiệp ĐH và Thạc sĩ tại [11] S. Pandey, L. Wu1, S. M. Guru, R. Buyya1, A trường ĐH Bách khoa Hà Nội, Particle Swarm Optimization (PSO)-based Heuristic nghiên cứu sinh năm 2012 tại for Scheduling Workflow Applications in Cloud Học viện Khoa học Công nghệ Computing Environments, Proc. of 24th IEEE Quân sự. International Conference on Advanced Information Hiện đang công tác tại trường ĐH Sư phạm Hà Nội Networking and Applications (AINA), pages 400-407, 2010 Lĩnh vực nghiên cứu: các phương pháp gần đúng giải bài toán lập lịch luồng công việc trong môi trường [12] R. Rajkumar, T. Mala, Achieving Service Level điện toán đám mây, xử lý song song và phân tán. Agreement in Cloud Environment using Job Prioritization in Hierarchical Scheduling, Proceeding Điện thoại : 0912.069.762 of International Conference on Information System E-mail: pttoan@hnue.edu.vn Design and Intelligent Application, 2012, vol 132, pp 547-554. NGUYỄN THẾ LỘC Tốt nghiệp ĐH khoa Toán Tin, ĐH [13] Q. Cao, W. Gong and Z. Wei, An Optimized Algorithm for Task Scheduling Based On Activity Sư phạm Hà Nội năm 1993, Tốt Based Costing in Cloud Computing, In Proceedings of nghiệp Thạc sĩ CNTT tại trường Third International Conference on Bioinformatics and ĐH Bách khoa Hà Nội, nhận bằng Biomedical Engineering, 2009, pp.1-3 tiến sỹ tại Viện Nghiên cứu Khoa [14] S.Selvi, Dr. D.Manimegalai, học Công nghệ Nhật Bản JAIST Dr.A.Suruliandi, Efficient Job Scheduling on năm 2007. Computational Grid with Differential Evolution Lĩnh vực nghiên cứu: mạng máy Algorithm, , International Journal of Computer Theory tính và truyền thông, xử lý song song và phân tán and Engineering, Vol. 3, No. 2, April, 2011 Điện thoại : 0988.765.837 [15] Q. XU, L.WANG, HE. Baomin, N.WANG, E-mail: locnt@hnue.edu.vn Modified Opposition-Based Differential Evolution for Function Optimization, Journal of Computational NGUYỄN DOÃN CƢỜNG Information Systems, pp. 1582-1591, 2011. Sinh năm 1977 tại Tuyên Quang. [16] O. Sinnen, Task Scheduling for Parallel Systems, Tốt nghiệp ĐH tại Học viện Kỹ John Wiley & Sons, 2007, pp. 83 thuật Quân sự, nghiên cứu sinh tại [17] R. Storn and K. Price, Differential Evolution-A Trường ĐH Tổng hợp Kỹ thuật Simple and Efficient Heuristic for Global Optimization điện Quốc gia Saint-Peterburg - over Continuous Spaces, Journal of Global CHLB Nga năm 2006. Optimization, 1997, pp. 341-359. Hiện đang công tác tại Viện CNTT- [18] M. Mitzenmacher, E. Upfal, Probability and Viện Khoa học Công nghệ Quân sự. Computing: Randomized Algorithms and Probabilistic Lĩnh vực nghiên cứu: Công nghệ phần mềm, Data Analysis, Cambridge University Press (2005) Mining and Knowledge Discovery, cơ sở dữ liệu lớn, [19] J. V. Vliet, F. Paganelli, Programming Amazon cơ sở dữ liệu chuỗi thời gian, bảo mật. EC2, O'Reilly Media, ISBN 1449393683, 2011 Điện thoại : 0976.210.686 E-mail: cuongvncntt@yahoo.com Nhận bài ngày: 21/04/2016 - 58 -