Mode: Hướng tiếp cận mới cho việc thực thi luồng công việc

Nội dung text: Mode: Hướng tiếp cận mới cho việc thực thi luồng công việc

1. Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường, Trần Đăng Hưng MODE: HƯỚNG TIẾP CẬN MỚI CHO VIỆC THỰC THI LUỒNG CÔNG VIỆC Phan Thanh Toàn1, Nguyễn Thế Lộc2, Nguyễn Doãn Cường3, Trần Đăng Hưng2 1Khoa Sư Phạm Kỹ Thuật, Trường Đại Học Sư Phạm Hà Nội 2Khoa Công Nghệ Thông Tin, Trường Đại Học Sư Phạm Hà Nội 3Viện công nghệ thông tin, Viện Khoa Học và Công Nghệ Quân Sự Tóm tắt: Lập lịch luồng công việc là một vấn đề tuần tự, dữ liệu ra của tác vụ này là dữ liệu vào quan trọng trong thời đại điện toán dám mây. Về của tác vụ kế tiếp. Rất nhiều ứng dụng trong các cơ bản vấn đề này liên quan đến việc tìm kiếm tài lĩnh vực khoa học đều yêu cầu phải xử lí một nguyên và phân bổ các tác vụ dựa trên tài nguyên lượng lớn dữ liệu dưới dạng luồng công việc, dẫn phù hợp. Lập lịch luồng công việc đóng một vai tới nhu cầu lập lịch thực thi luồng công việc sao trò quan trọng trong quản lý hệ thống. Việc lập cho hiệu quả nhất. Trong môi trường điện toán lịch hợp lý có ảnh hưởng đáng kể lên hiệu năng đám mây bản chất của vấn đề này là tìm phương của đám mây. Bài báo này đề xuất một kỹ thuật án ánh xạ những tác vụ của luồng công việc tới lập lịch mới gọi là MODE chạy trong môi trường các máy chủ sao cho thời gian xử lý toàn bộ luồng điện toán đám mây. Giải thuật này được xây dựng công việc là nhỏ nhất. dựa trên việc nghiên cứu chi tiết và phân tích của quá trình tiến hóa khác biệt và áp dụng ưu điểm Nội dung tiếp theo của bài báo gồm những phần của tiến hóa khác biệt và loại trừ nhược điểm của chính như sau. Phần 2 trình bày một số công trình nó. Chúng tôi đã đề xuất một giải thuật tiến hóa liên quan đến bài toán lập lịch luồng công việc. khác dựa trên Modified Opposition để lập lịch Phần 3 mô tả bài toán và trình bày mô hình toán phân luồng nhiệm vụ trong môi trường điện toán học, sau đó phát biểu bài toán và chứng minh đám mây để thời gian thực thi là nhỏ nhất. rằng nó thuộc lớp NP-đầy đủ. Phần 4 giới thiệu thuật toán đề xuất - MODE. Từ khóa: Workflow scheduling, Opposition- Based Differential Evolution, cloud computing, II. NHỮNG CÔNG TRÌNH LIÊN QUAN Differential Evolution.1 Bài toán lập lịch luồng công việc đã được chứng minh là thuộc lớp NP-đầy đủ [2] nghĩa là thời I. GIỚI THIỆU gian để tìm ra lời giải tối ưu là rất lớn, vì vậy đã Điện toán đám mây là môi trường phân tán không có nhiều công trình nghiên cứu nhằm tìm ra lời đồng nhất với sự liên kết của rất nhiều máy chủ giải gần đúng trong thời gian ngắn. ảo và vật lý trên môi trường mạng. Các tài nguyên S. Sadhasivam đã đề xuất thuật toán lập lịch phần cứng, phần mềm được cung cấp một cách luồng công việc dựa trên sự cân bằng tải trong linh động theo nhu cầu của người dùng. Luồng môi trường điện toán đám mây [3]. Thuật toán công việc (workflow) là một chuỗi có thứ tự các không chỉ đáp ứng các yêu cầu từ người sử dụng tác vụ (task) có thể được thực hiện đồng thời hay mà còn cung cấp khả năng sử dụng tài nguyên một Tác giả liên lạc: Phan Thanh Toàn, cách hiệu quả. Đây là thuật toán theo hướng nâng email: pttoan@hnue.edu.vn cao hiệu quả dịch vụ dựa trên Meta-heuristic. Đến tòa soạn: 14/3/2016, chỉnh sửa: 28/4/2016, chấp R. Burya đã trình bày một cách tóm tắt về các nhận đăng: 30/5/2016. chức năng của công cụ mô phỏng CloudSim [4] Tạp chí KHOA HỌC CÔNG NGHỆ Số 1 năm 2016 61 THÔNG TIN VÀ TRUYỀN THÔNG
2. MODE: HƯỚNG TIẾP CẬN MỚI CHO VIỆC THỰC THI LUỒNG CÔNG VIỆC - môi trường mô phỏng cho phép cài đặt và thực cực tiểu thời gian hoàn thành luồng công việc nghiệm các thuật toán lập lịch luồng công việc (Makespan), trong công trình tác giả đã chỉ ra trong môi trường điện toán đám mây. G. Guo- giá trị Makespan tìm được bởi thuật toán đề xuất Ning đã đề xuất một thuật toán lập lịch luồng là nhỏ hơn so với thuật toán PSO. Q. XU và công việc dựa trên giải thuật di truyền [5], trong các cộng sự đã đề xuất thuật toan COODE [11] đó đưa vào nhiều ràng buộc dịch vụ khác nhau (Current Optimum Opposition-Based Differential như thời gian hoàn thành, băng thông, chi phí, độ Evolution) nhằm tìm giá trị tối ưu cho các hàm tin cậy. Tác giả đã sử dụng kết hợp với giải thuật số dựa theo phương pháp tiến hóa vi phân đối luyện thép sau pha lựa chọn, trao đổi chéo, đột xứng, trong công trình tác giả đã đề xuất công biến nhằm tăng cường khả năng tìm kiếm cục bộ thức tìm điểm đối xứng của một điểm dựa theo của giải thuật di truyền. giá trị tối ưu hiện tại nhằm thay đổi toán tử đột biến trong phương pháp tiến hóa vi phân và tác L. Guo đã trình bày một mô hình cho bài toán giả đã so sánh thuật toán COODE với các thuật lập lịch luồng công việc trong môi trường điện toán DE và ODE, kết quả đã chỉ ra thuật toán đề toán đám mây [6] và đề xuất một thuật toán lập xuất COODE tốt hơn các thuật toán đối sánh. lịch luồng công việc dựa trên chiến lược tối ưu bày đàn, kết hợp với luật SPV (Smallest Position Value) nhằm rời rạc hóa các giá trị thực của véc III. MÔ HÌNH LÝ THUYẾT tơ dịch chuyển và véc tơ vị trí của các cá thể trong Biểu diễn luồng công việc bởi đồ thị G=(V,E), với quần thể. Tác giả đã thực nghiệm và chỉ ra thuật • V là tập đỉnh, mỗi đỉnh biểu diễn cho một tác toán đề xuất có chất lượng lời giải tốt hơn các vụ trong luồng công việc. thuật toán CM-PSO (Crossover and Mutation PSO) và L-PSO (Local search Particle Swarm • T = {T1, T2, ,TM } là tập M tác vụ Optimization). S. Pandey [7] đã đề xuất thuật toán • E biểu diễn sự phụ thuộc dữ liệu giữa các tác lập lịch luồng công việc PSO Heuristic (Particle vụ. Cạnh (T , T ) ∈ E thì tác vụ T là tác vụ cha Swarm Optimization Heuristic – PSO_H) trong i j i của tác vụ Tj, dữ liệu sinh ra bởi Ti sẽ được sử môi trường điện toán đám mây dựa trên chiến dụng bởi T . lược tối ưu bày đàn. R. Rajkumar đã đề xuất j một thuật toán lập lịch phân cấp [8] và đưa vào • Tập máy chủ S = {S1, S2, .,SN}. N là số máy các tham số dịch vụ khác nhau, chẳng hạn như chủ. thời gian đáp ứng. Thuật toán sử dụng tham số • Mỗi tác vụ Ti có thể thực hiện tại một máy chủ này như một quyền ưu tiên để lựa chọn các tác ∈ bất kỳ Sj S vụ lập lịch. Q. Cao và các đồng nghiệp đã trình • Khối lượng tính toán của tác vụ T kí hiệu là bày thuật toán lập lịch dựa trên giải thuật ABC i W (flop-floating point operations). (Activity Based Costing) [9]. Thuật toán này gán i mức ưu tiên cho mỗi tác vụ trong luồng công việc • P(Si) : là tốc độ tính toán của máy chủ Si theo các tham số về thời gian, không gian, các tài (MI/s : million instructions/second). nguyên và chi phí, quá trình lập lịch sẽ sử dụng • Băng thông B(Si,Sj) giữa máy chủ Si và Sj mức ưu tiên này để quyết định các tác vụ được được biểu diễn bởi hàm B(): S×S → R+ . Băng chọn trong quá trình lập lịch. thông thỏa mãn các điều kiện : B(Si,Si) = ∞ and B(S ,S ) = B(S ,S ) (Đơn vị đo là Mbps) S. Selvi và các cộng sự đã đề xuất thuật toán lập i j j i lịch luồng công việc trong môi trường điện toán • Dij: khối lượng dữ liệu truyền từ tác vụ Ti đến lưới (Grid) [10], trong công trình tác giả đã vận tác vụ Tj. (Đơn vị đo là Mbit) dụng thuật toán tiến hóa vi phân (Differential Mỗi phương pháp lập lịch được biểu diễn Evolution - DE) vào giải bài toán lập lịch luồng bởi hàm f(): T→S ; f(T ) là máy chủ thực thi tác công việc trên môi trường điện toán lưới nhằm i vụ Ti. Tạp chí KHOA HỌC CÔNG NGHỆ 62 Số 1 năm 2016 THÔNG TIN VÀ TRUYỀN THÔNG
3. Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường, Trần Đăng Hưng Từ các giả thiết trên ta có : IV. GIẢI PHÁP ĐỀ XUẤT • Thời gian thực hiện tác vụ Ti là : Thuật toán tiến hóa vi phân dựa trên thông tin đối xứng (Opposition-based differential evolution – W i (1) ODE) được đề xuất bởi R. Storn và K. Price [13], ( ( )) P f Ti tương tự như các thuật toán tiến hóa khác, thuật • Thời gian truyền dữ liệu giữa tác vụ T và T là toán ODE gồm hai bước chính: khởi tạo quần thể i j và sinh quần thể mới bằng cách áp dụng các toán D ij (2) tử di truyền như đột biến, trao đổi chéo và lựa B( f (Ti ), f (Tj )) chọn tự nhiên. Tuy nhiên thuật toán ODE nâng cao hiệu năng tìm kiếm trong hai bước này bằng Phát biểu bài toán. cách tìm kiếm thêm lời giải trong phần đối xứng của không gian tìm kiếm hiện tại. Để giải quyết Bài toán đang xét, từ đây ký hiệu là WSP - Work- bài toán lập lịch luồng công việc đã đề xuất trong flow Scheduling Problem, được phát biểu như mô hình phần 3, chúng tôi sẽ đề xuất phương sau: giả sử cho trước tài nguyên của đám mây pháp tìm phần tử đối xứng trong quần thể và kết bao gồm tập máy chủ S với tốc độ tính toán và hợp với phương pháp bánh xe quay vòng dựa băng thông được biểu diễn như trên. Giả sử tập trên hạng cá thể nhằm tìm ra các cá thể tốt cho tác vụ T được biểu diễn bởi đồ thị G = (V,E) như quá trình đột biến qua đó nâng cao hiệu năng của trên. Hàm mục tiêu đặt ra là cực tiểu thời gian thuật toán. thực thi luồng công việc: Định nghĩa 1: giả sử x là số thực và x ∈ [a,b], khi makespan → min đó phần tử đối xứng của x kí hiệu là x và được trong đó thời gian thực thi (ký hiệu là makespan) tính như sau: xabx=+− (3) là đại lượng được tính từ lúc tác vụ đầu tiên bắt đầu được khởi động cho tới khi tác vụ cuối cùng Định nghĩa 2: gọi P(x1, x2, ,xD) là một véc tơ ∈ được hoàn thành. D-chiều, với xi [ai, bi]; i = 1, 2, , D. Khi đó véc P= ( xx , , , x ) Bổ đề: WSP là bài toán thuộc lớp NP-Complete tơ đối xứng của P kí hiệu là 12 D và được tính như sau: xabxi=+− iii (4) Chứng minh: A. Biểu diễn cá thể Xét bài toán SCHED [12] sau đây: giả sử cho trước tập máy chủ và tập tác vụ gồm các thành Mỗi cá thể trong quần thể được biểu diễn bởi một phần như đã định nghĩa ở bài toán WSP trên đây, vec tơ có độ dài bằng số tác vụ trong luồng công ngoài ra bổ sung thêm điều kiện là tập S gồm các việc. Giá trị tương ứng với mỗi vị trí i trong véc máy chủ giống hệt nhau về tốc độ tính toán. tơ biểu diễn số hiệu của máy chủ thực thi tác vụ i. Ví dụ: xét luồng công việc với 5 tác vụ T = {T , Sinnen đã chứng mình rằng bài toán SCHED 1 T , ,T }, tập máy chủ gồm 3 máy S = {S , S , thuộc lớp NP-đầy đủ [12]. Quay về bài toán WSP 2 5 1 2 S }. Khi đó cá thể x =(1, 2, 1, 3, 2) được biểu đang xét, dễ thấy rằng bài toán SCHED chỉ là một 3 i trường hợp riêng của bài toán WSP khi bổ sung diễn như sau: thêm điều kiện ràng buộc sau đây: T1 T2 T3 T4 T5 S S S S S ∀ 1 2 1 3 2 P(Si) = P(Sj) i,j =1 , N. B. Phương pháp tính đối xứng cho cá thể Vì vậy rõ ràng bài toán WSP cũng thuộc lớp NP- đầy đủ. Trong phương pháp ODE ta cần phải tìm cá thể đối xứng cho mỗi cá thể trong quần thể hiện tại, Tạp chí KHOA HỌC CÔNG NGHỆ Số 1 năm 2016 63 THÔNG TIN VÀ TRUYỀN THÔNG
4. MODE: HƯỚNG TIẾP CẬN MỚI CHO VIỆC THỰC THI LUỒNG CÔNG VIỆC trong bài báo này chúng tôi đề xuất phương pháp Algorithm: RBRWS algorithm tìm cá thể đối xứng như sau: Input: population p = (x1, x2, ,xPopSize) Output: particle p ∀ s Gọi a = Max{P(Si)} và b = Min{P(Si)}; i = 1, 2, Begin , N; với P(Si) là tốc độ tính toán của máy chủ Si 1. Sắp xếp các cá thể theo chiều tăng dần của hàm mục tiêu fi 2. for i=1 to PopSize do Giả sử ta có cá thể xi = (Siπ(1), Siπ(2), ,Siπ(M)); Siπ(j) ∈ S, ∀j=1,2, ,M; cá thể đối xứng của x kí hiệu là 3. pos[i] ← PopSize – 1 i 4. for i=1 to PopSize do 5. calculate ranki by equation (7) xι và xSι = ( ιπ(1), S ιπ (2) , S ιπ (M ) ) 6. rand ← Random(0,SP) 7. s← PopSize Sιπ ()J = abS + −ιπ ()jj; ∀= 1,2, M (5) 8. while(rank[s] 0)s=s-1 return xs End. Sau đó sẽ gán các giá trị tương ứng với mỗi vị trí Thuật toán MODE j trong véc tơ x bởi số hiệu máy chủ có tốc độ ι Kết hợp các nội dung trên chúng tôi đề xuất thuật tính toán gần giá trị Sιπ ()J nhất: toán lập lịch luồng công việc trong môi trường điện toán đám mây dựa trên thông tin đối xứng xij ← k nÕu PS( k ) −≤ Sijππ( ) PS( r ) −∀ Sij( ) Sr (6) và gọi là MODE như sau: Algorithm: OP_Algorithm Algorithm MODE ( ) Input: population p = (x , x , ,x ) Input: T, S, size of workload W[1×M], P[1×N], B[N×N], 1 2 PopSize D[M×M], the constant K, the deviation ε, the number Output: opposite of population OP of particle NoP 1. for i=1 to PopSize do Output: the best position gbest 2. x← opposite ( x ) ; 1. Khởi tạo quần thể P gồm PopSize cá thể một cách ii ngẫu nhiên 2. OP ← OP_Algorithm ; tính quần thể đối xứng của { xi được tính theo công thức (5)} quần thể hiện tại 3. Gán số hiệu máy chủ cho các vị trí j của véc tơ 3. Chọn PopSize cá thể tốt nhất từ P ∪ OP 4. while(Điều kiện lặp)do xi theo (6) 5. for i=1 to PopSize do 6. Lựa chọn cá thể p theo thuật toán RBRWS 4. end for 1 7. Lựa chọn cá thể p2 theo thuật toán RBRWS 5. return OP 8. F ← Random(1,0) 9. v ← pbest + F×(p – p ) C. Phương pháp bánh xe quay vòng dựa trên i 1 2 10. Gán số hiệu máy chủ cho mỗi vị trí j của véc tơ vi hạng cá thể theo (6) 11. randi,j ← Random(0,1) Bánh xe quay vòng dựa trên hạng cá thể là một 12. Irand ← random(1,M) phương pháp lựa chọn cá thể cho các thế hệ kế ≤= 13. vi, j nÕu randi, j CR hoÆc i Irand tiếp. Trong phương pháp này mỗi cá thể được xếp u =  ij, x nÕu rand≥≠ CR hoÆc i I hạng theo một hàm xác định, sau đó sẽ tính sắc  i,, j i j rand xuất lựa chọn các cá thể theo hạng của chúng. 14. if (makespan(ui) < makespan(xi)) 15. x ← u Trong bài báo này chúng tôi đề xuất hàm tính i i 16. end if hạng cho các cá thể như sau: 17. end for 18. rand ← Random(0,1) pos 19. if(rand < J ) rank( pos) =−2 SP + (2 ×( SP −× 1) ) (7) r PopSize 20. OP ← OP_Algorithm 21. Lựa chọn PopSize cá thể tốt nhất tử P ∪ OP Trong đó: 1.0 ≤ SP ≤ 2.0; pos: vị trí cá thể cần 22. end if 23. End while tính hạng. 24. Return gbest; Tạp chí KHOA HỌC CÔNG NGHỆ 64 Số 1 năm 2016 THÔNG TIN VÀ TRUYỀN THÔNG
5. Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường, Trần Đăng Hưng Bước khởi tạo: khởi tạo ngẫu nhiên quần thể P xử lý Intel Core i5 2.2 GHz, RAM 4GB, hệ điều gồm PopSize cá thể, quấn thể đối xứng OP của hành Windows 7 Ultimate. P theo (5), (6), chọn ra PopSize cá thể tốt nhất từ P ∪ OP. A. Phân nhóm dữ liệu thực nghiệm Dữ liệu sử dụng trong các thực nghiệm bao gồm : Trong mỗi bước lặp chọn ra hai cá thể p1, p2 theo phương pháp bánh xe quay vòng dựa trên hạng • Dữ liệu về tốc độ tính toán của các máy chủ các cá thể. Véc tơ đột biến của mỗi cá thể i được và băng thông giữa các máy chủ được lấy ← × tính theo công thức: vi pbest + F (p1 – p2) từ các công ty cung cấp dịch vụ cloud như Amazon [16]. trong đó: pbest là cá thể tốt nhất hiện tại • Dữ liệu luồng công việc được lấy từ các bộ Sau bước đột biến toán tử trao đổi chéo được áp dữ liệu thử nghiệm được xây dựng theo độ trù dụng cho mỗi cá thể xi để sinh ra cá thể mới ui mật khác nhau và các luồng công việc từ các ứng dụng thực tế như ứng dụng Montage [17]. vi, j nÕu randi, j ≤= CR hoÆc i Irand u =  ij, ≥≠ • Dựa theo tính chất của môi trường điện toán xi,, j nÕu randi j CR hoÆc i Irand đám mây, đây là một môi trường tính toán không đồng nhất, năng lực các máy chủ và Trong đó rand ∈[0,1], Irand ∈[1,M], CR ∈[0,1]. i,j băng thông không đồng đều, đồng thời cũng Toán tử lựa chọn được áp dụng để quyết định cá dựa theo tính chất các luồng công việc, số thể nào được sống sót cho thế hệ kế tiếp lượng tác vụ, độ trù mật của đồ thị luồng công việc chúng tôi đã tiến hành phân loại dữ liệu u, if makespan( u) < makespan() x theo các nhóm với quan hệ về năng lực tính x = iii i toán các máy chủ và băng thông khác nhau, xi , otherwise độ trù mât của đồ thị luồng công việc cũng được thử nghiệm qua hệ số α khác nhau. Chi Sau khi trao đổi chéo và lựa chọn, tính quần tiết các nhóm dữ liệu như sau theo số lượng thể đối xứng OP của P theo (5), (6) và chọn ra máy chủ N, số tác vụ M và hệ số α như sau: PopSize cá thể tốt nhất từ P ∪ OP. • Nhóm 1: M=5, N=3; Nhóm 2: M=10, N=3, Quá trình tiến hóa của quần thể sẽ được thực hiện Nhóm 3: M=20, N=8, Nhóm 4: M=25, N=8 qua các toán tử đột biến, trao đổi chéo và lấy đối • Mỗi nhóm lại bao gồm ba thực nghiệm khác xứng quần thể. Sau mỗi thế hệ chúng ta sẽ tính giá nhau về tỷ lệ số cạnh trên số đỉnh của đồ thị trị hàm mục tiêu (Makespan) của các phương án luồng công việc, ký hiệu là α và tính bởi công xếp lịch và đối sánh với giá trị tốt nhất trong cá thể thức: gbest, nếu có một cá thể cho giá trị makespan tốt hơn thì cá thể đó sẽ thay thế cá thể gbest hiện tại. B. Tham số cấu hình Các tham số cấu hình của đám mây được thiết lập V. KẾT QUẢ THỰC NGHIỆM trong miền giá trị như sau: Để kiểm chứng thuật toán đề xuất MODE chúng • Tốc độ tính toán P của các máy chủ: từ 1 đến tôi đã sử dụng công cụ mô phỏng Cloudsim [1] để 250 (million instructions/s); khối lượng dữ tạo lập môi trường đám mây. Đối tượng so sánh liệu D giữa các tác vụ: từ 1 đến 10000 (Mega là thuật toán tiến hóa mạnh như PSO Heuristic bit); băng thông giữa các máy chủ B:từ 10 đến [14], và thuật toán Random [15]. 100 (Mega bit/s). Các chương trình mô phỏng được viết bằng ngôn • Hệ số vi sai F=0.5; hệ số trao đổi chéo CR=0.9; α ngữ Java và chạy trên máy tính cá nhân với bộ vi Jr=0.3; PopSize=50; : từ 0.2 tới 0.7. Tạp chí KHOA HỌC CÔNG NGHỆ Số 1 năm 2016 65 THÔNG TIN VÀ TRUYỀN THÔNG
6. MODE: HƯỚNG TIẾP CẬN MỚI CHO VIỆC THỰC THI LUỒNG CÔNG VIỆC C. Quá trình tiến hành thực nghiệm 97%, điều đó chứng tỏ thuật toán MODE có chất lượng lời giải tốt hơn các thuật toán đối sánh và Để đánh giá hiệu năng của thuật toán đề xuất độ ổn định trong các lần chạy cũng tốt hơn. MODE chúng tôi đã tiến hành thực nghiệm và so sánh kết quả của MODE với các thuật toán tiến hóa mạnh hiện nay như PSO_H và Random. Dữ liệu thực nghiệm được lấy từ ứng dụng Montage và các các luồng công việc ngẫu nhiên theo độ trù mật khác nhau, các tham số băng thông, tốc độ tính toán của máy chủ được thiết lập thống nhất cho tất cả các thực nghiệm. Với mỗi bộ dữ liệu chúng tôi tiến hành chạy chương trình 30 lần độc Hình 1. So sánh các thuật toán với M=10,N=5 lập. Kết quả thực nghiệm được trình bày chi tiết trong Bảng I và các Hình 1, 2, 3, 4, các hình đó đã chỉ ra kết quả so sánh giữa giá trị trung bình tính được bởi thuật toán MODE với các thuật toán đối sánh, trong hầu hết các trường hợp thuật toán MODE đều cho kết quả tốt hơn các thuật toán đối sánh, giá trị trung bình tìm được bởi MODE tốt hơn giá trị trung bình tìm được bởi PSO_H từ Hình 2. So sánh các thuật toán với M=20,N=3 6% - 88% và tốt hơn giá trị trung bình tìm được bởi thuật toán Random từ 39% - 85%. Hình 1, 2, 3, 4 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 sánh, qua đó ta thấy giá trị tốt nhất tìm được bởi MODE tốt hơn giá trị tốt nhất tìm được bởi PSO_H từ 2% - 19%, chỉ duy nhất trong bộ dữ liệu thực nghiệm thứ nhất thuật toán MODE có Hình 3. So sánh các thuật toán với M = 20,N = 8 giá trị tốt nhất lớn hơn giá trị tốt nhất tìm được bởi PSO_H là 3%, giá trị tốt nhất tìm được bởi MODE tốt hơn giá trị tốt nhất tìm được bởi Random từ 20% - 40%. Cuối cùng các Hình 1, 2, 3, 4 chỉ ra kết quả so sánh giữa độ lệch chuẩn tìm được bởi thuật toán MODE với các thuật toán đối sánh, giá trị độ lệch chuẩn của MODE tốt hơn PSO_H từ 6% - 88% và tốt hơn Random từ 82% - Bảng I. Kết quả thực hiện các thuật toán M N MODE PSO_H RANDOM α Best Mean STD Best Mean STD Best Mean STD 10 3 0.26 16.9 17.3 0.4z 16.4 20.4 2.4 21.4 28.6 3.2 10 5 0.26 75.5 78.2 0.9 86.0 107.5 13.2 123.3 184.1 42.4 20 5 0.15 27.5 29.3 1.4 29.6 41.0 5.0 45.8 59.0 6.8 20 3 0.31 32.5 33.9 0.8 33.2 41.9 4.6 47.4 65.6 7.8 20 8 0.31 29.9 31.7 1.2 37.1 44.7 6.1 51.6 67.6 6.8 50 8 0.3 11.1 12.6 0.8 12.1 14.0 0.9 13.9 87.1 25.2 Tạp chí KHOA HỌC CÔNG NGHỆ 66 Số 1 năm 2016 THÔNG TIN VÀ TRUYỀN THÔNG
7. Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường, Trần Đăng Hưng VI. KẾT LUẬN 11. Lập lịch luồng công việc là một vấn đề phức tạp [5]. G. Guo-Ning and H. Ting-Lei, Genetic nhưng rất quan trọng vì nó quyết định hiệu năng Simulated Annealing Algorithm for Task của đám mây điện toán. Để đạt được mục tiêu lập Scheduling based on Cloud Computing lịch là tối thiểu hóa thời gian thực thi, bài báo đã Environment, In Proceedings of trình bày những kết quả chính sau đây: International Conference on Intelligent Computing and Integrated Systems, pp. 60- • Đề xuất một mô hình lý thuyết cho bài toán 63, 2010. lập lịch luồng công việc trong môi trường [6]. L. Guo, Task Scheduling Optimization điện toán đám mây. in Cloud Computing Based on Heuristic • Đề xuất phương pháp tính đối xứng cho các Algorithm, Journal of networks, vol. 7, no. cá thể. 3, pp. 547-552, 2012. • Dựa trên phương pháp đó, bài báo đề xuất [7]. S. Pandey, L. Wu1, S. M. Guru, R. Buyya1, thuật toán MODE hoạt động theo thuật toán A Particle Swarm Optimization (PSO)- tiến hóa vi phân kết hợp với phương pháp đối based Heuristic for Scheduling Workflow xứng nhằm tìm ra phương án thực thi tốt nhất. Applications in Cloud Computing Tiếp theo chúng tôi dự định cải tiến phương pháp Environments, Proc. of 24th IEEE lựa chọn cá thể và cơ chế lai ghép nhằm tìm ra cá International Conference on Advanced thể tốt hơn cho các thế hệ kế tiếp. Information Networking and Applications (AINA), pp. 400-407, 2010. [8]. R. Rajkumar, T. Mala, Achieving Service TÀI LIỆU THAM KHẢO Level Agreement in Cloud Environment [1]. R. N. Calheiros, R. Ranjan,A. Beloglazov, Cesar using Job Prioritization in Hierarchical A. F. De Rose, and R. Buyya, “CloudSim: A Scheduling, Proceeding of International Toolkit for Modeling and Simulation of Cloud Conference on Information System Design Computing Environments and Evaluation and Intelligent Application, vol 132, pp of Resource Provisioning Algorithms”, 547-554, 2012. Software: Practice and Experience, vol. 41, no. 1, pp. 23-50, 2011 [9]. Q. Cao, W. Gong and Z. Wei, An Optimized Algorithm for Task Scheduling Based [2]. J.D. Ullman, NP-complete scheduling On Activity Based Costing in Cloud problems, Journal of Computer and System Computing, In Proceedings of Third Sciences, vol. 10, no. 3, pp.384-393, 1975 International Conference on Bioinformatics [3]. Dr. Sudha Sadhasivam, R. Jayarani, Dr. and Biomedical Engineering, pp.1-3, 2009. N. Nagaveni, R. Vasanth Ram, Design [10]. S.Selvi, Dr. D.Manimegalai, and Implementation of an efficient Dr.A.Suruliandi, Efficient Job Scheduling Twolevel Scheduler for Cloud Computing on Computational Grid with Differential Environment, In Proceedings of Evolution Algorithm, International Journal International Conference on Advances in of Computer Theory and Engineering, Vol. Recent Technologies in Communication 3, No. 2, April, 2011. and Computing, 2009 [11]. Q. Xu, L. wang, He. Baomin, N. Wang, [4]. R. Burya, R. Calheiros, Modeling and Modified Opposition-Based Differential Simulation of Scalable Cloud Environment Evolution for Function Optimization, and the Cloud Sim Toolkit: Challenges and Journal of Computational Information Opportunities, IEEE publication 2009,pp1- Systems, pp. 1582-1591, 2011. Tạp chí KHOA HỌC CÔNG NGHỆ Số 1 năm 2016 67 THÔNG TIN VÀ TRUYỀN THÔNG
8. MODE: HƯỚNG TIẾP CẬN MỚI CHO VIỆC THỰC THI LUỒNG CÔNG VIỆC [12]. O. Sinnen, Task Scheduling for Phan Thanh Toàn Parallel Systems, John Wiley & Sons, Sinh năm 1974 tại Thái Nguyên. pp. 83, 2007. Tốt nghiệp đại học và thạc sĩ tại trường đại học Bách Khoa Hà Nội, nghiên cứu sinh năm 2012 tại [13]. R. Storn and K. Price, Differential học viện Khoa học công nghệ quân sự. Evolution-A Simple and Efficient Hiện đang công tác tại trường đại học Sư Phạm Heuristic for Global Optimization over Hà Nội Continuous Spaces, Journal of Global Lĩnh vực nghiên cứu : các phương pháp gần Optimization, pp. 341-359, 1997. đúng giải bài toán lập lịch luồng công việc trong môi trường điện toán đám mây, xử lý [14]. J. Kennedy, R.C. Eberhart, Particle song song và phân tán. swarm optimization, Proc. of IEEE Điện thoại : 0912.069.762 International Conference on Neural Nguyền Thế Lộc Networks, pp. 1942–1948, 1995. Sinh năm 1972, tại Hà Nội. [15]. M. Mitzenmacher, E. Upfal, Probability Tốt nghiệp đại học 1989 1993 khoa Toán Tin đại học Sư Phạm Hà Nội, Tốt nghiệp thạc sĩ CNTT and Computing: Randomized tại đại học Bách Khoa Hà Nội, tiến sỹ 2004-2007 Algorithms and Probabilistic Analysis, viện nghiên cứu khoa học công nghệ Nhật Bản Cambridge University Press (2005). JAIST. Lĩnh vực nghiên cứu hiện nay: mạng máy tính [16]. J. V. Vliet, F. Paganelli, Programming và truyền thông, xử lý song song và phân tán Amazon EC2, O’Reilly Media, 2011. Điện thoại : 0988.765.837 [17]. E-mail : locnt@hnue.edu.vn Nguyễn Doãn Cường MODE: A NOVEL APPROACH FOR Sinh năm 1977 tại Tuyên Quang. EXECUTING DATA WORKFLOW Tốt nghiệp đại học tại học viện kĩ thuật quân sự, nghiên cứu sinh tại Trường Đại học Tổng hợp Abstract: Workflow scheduling is a big issue Kỹ thuật điện Quốc gia Saint-Peterburg - CHLB in the era of Cloud computing. Basically it is Nga 2006. Hiện đang công tác tại : viên CNTT-viên Khoa the issue related to the discovering resources học công nghệ quân sự and allocating tasks on suitable resources. Điện thoại : 0976.210.686 Workflow scheduling plays a vital role in the E-mail : cuongvncntt@yahoo.com system management. Proper scheduling can Lĩnh vực công tác và hướng nghiên cứu: Công have significant impact on the performance nghệ phần mềm , Data Mining and Knowledge of the Cloud. In this paper, a novel workflow Discovery, cơ sở dữ liệu lớn, cơ sở dữ liệu chuỗi thời gian, Bảo mật. scheduling called MODE, running on the cloud computing environments, is Trần Đăng Hưng proposed. The algorithm is built through Sinh năm 1979, tại Hà Tĩnh. Tốt nghiệp Khoa Toán-Tin, Trường ĐH Sư Phạm Hà Nội năm 2001; a comprehensive study and analysis of tốt nghiệp Thạc sĩ tại Trường ĐH Công nghệ, Differential Evolution strategy with applying ĐHQGHN năm 2006. Tốt nghiệp Tiến sĩ tại Viện the advantages of the Differential Evolution Khoa học và Công nghệ tiên tiến Nhật Bản năm and covers its disadvantages. We propose 2009. Lĩnh vực nghiên cứu: Khai phá dữ liệu, Học máy, a Modified Opposition-Based Differential Tin-sinh học. Evolution algorithm for scheduling workflow Điện thoại: 0904 68 72 82 tasks in the cloud environments so that the Email: hungtd@hnue.edu.vn execution time of the workflow (makespan) is minimized. Tạp chí KHOA HỌC CÔNG NGHỆ 68 Số 1 năm 2016 THÔNG TIN VÀ TRUYỀN THÔNG