1. Trang Chủ
  2. Quản trị mạng
  3. Cai tien viec lap lich luong cong viec trong moi truong dien toan dam may dua tren phuong phap PSO lan can-Quan tri mang

Cai tien viec lap lich luong cong viec trong moi truong dien toan dam may dua tren phuong phap PSO lan can-Quan tri mang

Bài viết trình bày việc xây dựng một mô hình bài toán luồng công việc trong môi trường điện toán đám mây và đề xuất một thuật toán dựa trên phương pháp tối ưu bày đàn cục bộ để sắp xếp luồng công việc thực thi trên môi trường điện toán đám mây đảm bảo thời gian hoàn thành luồng công việc nhỏ nhất. CẢI TIẾN VIỆC 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 PHƯƠNG PHÁP PSO LÂN CẬN Phan Thanh Toàn * Nguyễn Thế Lộc+ * Khoa Sư phạm kỹ thuật, trường đại học Sư phạm Hà Nội + Kho

Category Tài liệu Quản trị mạng

Page count 9

Created date 5/4/2020 1:41:48 PM +00:00

File type PDF

File size 0.80 M

Tên tệp 1267673 pdf

Tải Cai tien viec lap lich luong cong viec trong moi t... (.pdf)

  1. CẢI TIẾN VIỆC 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 PHƯƠNG PHÁP PSO LÂN CẬN Phan Thanh Toàn * Nguyễn Thế Lộc+ * Khoa Sư phạm kỹ thuật, trường đại học Sư phạm Hà Nội + Khoa Công nghệ thông tin, trường đại học Sư phạm Hà Nội Tóm tắt: Luồng công việc là một dãy có thứ tự các luồng công việc như ứng dụng Montage [1], tác vụ cần phải thực thi để đạt được một mục đích, CyberShake [2], Epigenomics [3], LIGO [4], v.v. Bài toán lập lịch luồng công việc là bài toán sắp Phần tiếp theo của bài báo có cấu trúc như sau. xếp các tác vụ cho thực thi trên một số máy xác Phần II giới thiệu một số công trình nghiên cứu có định sao cho đạt hiệu quả tốt nhất, đây chính là liên quan về bài toán lập lịch luồng công việc.Trong bài toán quan trọng nhất tại các trung tâm điện phần III chúng tôi trình bày mô hình lý thuyết để biểu toán đám mây. Trong bài báo này chúng tôi sẽ xây diễn năng lực tính toán và truyền thông của đám mây, dựng một mô hình bài toán luồng công việc trong dựa trên mô hình lý thuyết này, phần IV đề xuất: môi trường điện toán đám mây và đề xuất một (i) phương thức mới để cập nhật vị trí của cá thể thuật toán dựa trên phương pháp tối ưu bày đàn cục bộ để sắp xếp luồng công việc thực thi trên môi (ii) giải pháp để chương trình thoát ra khỏi vùng cực trường điện toán đám mây đảm bảo thời gian trị địa phương và di chuyển tới một vùng mới hoàn thành luồng công việc nhỏ nhất. trong không gian tìm kiếm Keyword: Workflow scheduling, Particle Swarm (iii) thuật toán lập lịch mới tên là LOSPSO Optimization, cloud computing, local search. Phần V mô tả các thực nghiệm được tiến hành dựa I. GIỚI THIỆU trên công cụ mô phỏng Cloudsim [5] và phân tích những số liệu thực nghiệm thu được. Phần VI tóm tắt Trong những năm gần đây điện toán đám mây đã những kết quả chính của bài báo và hướng nghiên cứu được ứng dụng rộng rãi trong nhiều lĩnh vực khác sẽ tiến hành trong tương lai. nhau của cuộc sống và nghiên cứu khoa học. Trong môi trường điện toán đám mây mọi tài nguyên phần II. NHỮNG CÔNG TRÌNH LIÊN QUAN cứng, phần mềm đều được cung cấp cho khách hàng dưới dạng dịch vụ, khách hàng chỉ phải chi trả phí sử 2.1. Những nghiên cứu về bài toán lập lịch dụng theo tài nguyên thực dùng. Bài toán lập lịch luồng công việc tổng quát đã được Luồng công việc (workflow) là một chuỗi có thứ chứng minh là thuộc lớp NP-Khó [6] nghĩa là thời tự các tác vụ (task) có thể được thực hiện đồng thời gian để tìm ra lời giải tối ưu tăng rất nhanh theo kích hay tuần tự nếu dữ liệu đầu ra của tác vụ này là đầu cỡ dữ liệu đầu vào, vì vậy đã có nhiều công trình vào của tác vụ kế tiếp. Rất nhiều ứng dụng trong các nghiên cứu nhằm tìm ra lời giải đúng hoặc gần đúng lĩnh vực khoa học khác nhau đều yêu cầu phải xử lí một lượng lớn dữ liệu được tổ chức theo dạng luồng của bài toán này. công việc. Vấn đề lập lịch luồng công việc trong môi N.S.Grigoreva [7] đã đề xuất thuật toán lập lịch trường điện toán đám mây về bản chất là tìm phương án ánh xạ những tác vụ của luồng công việc tới các điều phối các tác vụ của luồng công việc vào thực máy chủ của đám mây sao cho thời gian xử lý toàn bộ hiện trên một hệ thống đa bộ vi xử lý nhằm cực tiểu luồng công việc là nhỏ nhất, biết rằng khối lượng tính hóa thời gian hoàn thành luồng công việc. Tác giả đã toán và yêu cầu dữ liệu của các tác vụ, tốc độ tính sử dụng kết hợp phương pháp nhánh cận và kỹ thuật toán và truyền thông của các máy chủ là khác nhau. Bài toán lập lịch luồng công việc là một bài toán tìm kiếm nhị phân để tìm ra phương án xếp lịch có đã được nghiên cứu từ những năm 1950, và bài toán thời gian hoàn thành luồng công việc là nhỏ nhất. này đã được chứng minh thuộc lớp NP-Khó. R. Rajkumar [8] đã đề xuất thuật toán lập lịch Trong những năm gần đây đã có rất nhiều ứng luồng công việc dựa trên nhu cầu của khách hàng như dụng khoa học được mô hình hóa bởi dạng đồ thị Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 40
  2. thời gian hoàn thành, chi phí thực thi,… qua đó sẽ [5],[14],[15] đã đề xuất các kiến trúc lân cận Star, điều phối các tác vụ vào thực hiện trên các máy chủ Ring, Von Neuman. Thuật toán PSO cục bộ mỗi cá thể sẽ trao đổi thông tin với một số cá thể lân cận, số nhằm thỏa mãn tốt nhất nhu cầu của khách hàng. cá thể được trao đổi thông tin phụ thuộc vào mô hình Các tác giả trong bài báo [9] đã đề xuất thuật toán kiến trúc lân cận sử dụng trong thuật toán. Công thức EGA (Enhanced Genetic Algorithm) lập lịch bằng cập nhật vector vị trí của cá thể như sau : phương pháp di truyền. Trong công trình các tác giả v i k+1 = ω×v i k + c 1 rand 1 × (pbest i - x i k) + c 2 rand 2 × (lbest i - x i k) (5) sử dụng thuật toán Enhanced Max Min trong bước Phương pháp PSO toàn cục thường cho tốc độ hội khởi tạo quần thể nhằm tìm ra các cá thể tốt cho quá tụ nhanh hơn phương pháp PSO cục bộ tuy nhiên chất trình tiến hóa. lượng lời giải không tốt bằng phương pháp PSO cục Pandey [10] đã đề xuất thuật toán lập lịch luồng bộ vì quần thể hay bị mắc kẹt tại các điểm cực trị địa phương [16]. công việc PSO Heuristic (Particle Swarm Optimization Heuristic – PSO_H) trong môi trường điện toán đám mây dựa trên chiến lược tối ưu bày đàn. Rajkumar đã đề xuất một thuật toán lập lịch phân cấp [10] và đưa vào các tham số dịch vụ khác nhau, chẳng hạn như thời gian đáp ứng. Thuật toán sử dụng a. Star b. Ring c. Von Neumann tham số này như một quyền ưu tiên để lựa chọn các Hình 1. Các kiến trúc lân cận tác vụ lập lịch. Q.Cao và các đồng nghiệp đã trình bày Function Ring(x i ) thuật toán lập lịch dựa trên giải thuật ABC (Activity Input: current position x i Based Costing) [11]. Thuật toán này gán mức ưu tiên Output: x where Fitness(x) = cho mỗi tác vụ trong luồng công việc theo các tham min{Fitness(x i ), Fitness(Left(x i )), số về thời gian, không gian, các tài nguyên và chi phí, Fitness(Right(x i ))} quá trình lập lịch sẽ sử dụng mức ưu tiên này để quyết III. MÔ HÌNH LÝ THUYẾT CỦA BÀI TOÁN định các tác vụ được chọn trong quá trình lập lịch. Đồ thị luồng công việc được biểu diễn bởi đồ thị có Selvi và các cộng sự đã đề xuất thuật toán lập lịch hướng, không có chu trình G=(V,E). luồng công việc trong môi trường điện toán lưới Trong đó: (Grid) [12], trong công trình tác giả đã vận dụng thuật • V là tập đỉnh, mỗi đỉnh tương ứng với một tác vụ toán tiến hóa vi phân (DE) vào giải bài toán lập lịch trong đồ thị luồng công việc. luồng công việc trên môi trường điện toán lưới nhằm cực tiểu thời gian hoàn thành luồng công việc • T={T1 , T2 ,…,TM }là tập các tác vụ (makespan), trong công trình tác giả đã chỉ ra giá trị Makespan tìm được bởi thuật toán đề xuất là nhỏ hơn • E là tập cạnh, biểu diễn mối quan hệ giữa các tác so với thuật toán PSO. Xu và các cộng sự đã đề xuất vụ. Nếu e = (Ti , Tk) là một cạnh của đồ thị G, có thuật toán COODE [13] (Current Optimum nghĩa tác vụ Ti là tác vụ cha của tác vụ T k , và tác Opposition-based Differential Evolution) nhằm tìm vụ T i sẽ gửi tới tác vụ T k một khối lượng dữ liệu giá trị tối ưu cho các hàm số dựa theo phương pháp là tdatak. tiến hóa vi phân đối xứng, trong công trình tác giả đã đề xuất công thức tìm điểm đối xứng của một điểm • S = {S1, S2,….,SN}là tập N máy chủ trong môi dựa theo giá trị tối ưu hiện tại nhằm thay đổi toán tử trường điện toán đám mây. Mỗi máy chủ được xác đột biến trong phương pháp tiến hóa vi phân và tác định bởi một năng lực tính toán xác định là P(Si ), giả đã so sánh thuật toán COODE với các thuật toán đơn vị đo là MI/s (million instructions/second). DE và ODE, kết quả đã chỉ ra thuật toán đề xuất COODE tốt hơn các thuật toán đối sánh. 2.2. Phương pháp PSO lân cận Trong phương pháp PSO chuẩn (PSO toàn cục) 1 mỗi cá thể sẽ trao đổi thông tin với toàn bộ các cá thể khác trong quần thể, vector dịch chuyển của mỗi cá thể được cập nhật dựa trên thông tin tốt nhất của cá thể đó và thông tin tốt nhất của toàn bộ quần thể. 2 3 4 Vector dịch chuyển và vector vị trí được cập nhật theo công thức sau: v i k+1= ωv i k + c 1 rand 1 ×(pbest i - x i k) + c 2 rand 2 ×(gbest - x i k) (3) 5 x i k+1 = x i k + v i k (4) Tuy nhiên trong thực tế có nhiều kiến trúc khác Hình 2. Đồ thị biểu diễn một luồng công việc nhau để biểu diễn mối quan hệ giữa các cá thể trong với 5 tác vụ. quần thể, một số công trình nghiên cứu như • M Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 41
  3. ỗi cặp máy chủ đều được kết nối với nhau bởi một Để giải quyết mâu thuẫn này, một số nghiên cứu đường truyền riêng, và có băng thông là B(Si , Sj ). trước đây như [10] đã làm tròn giá trị số thực ở vế Băng thông được xác định bởi một hàm phải rồi gán cho biến vị trí x i k+1[t] ở vế trái. Kết quả là nếu giá trị của vế phải là 3.2 thì phân phối tác vụ tới B(): S×S → R+ thực thi tại máy chủ có số thứ tự là 3, còn nếu vế phải B(Si ,Si ) = ∞ và B(Si ,Sj ) = B(Sj ,Si ) là 3.8 thì tác vụ sẽ được phân cho máy chủ có số thứ tự là 4. Cách làm có vẻ tự nhiên này thực chất là gán Khái niệm lịch biểu một vị trí được tính toán cẩn thận theo chiến lược Mỗi lịch biểu được biểu diễn bởi một hàm f() : PSO cho máy chủ mà số thứ tự của nó tình cờ đúng T→ S. Trong đó f(T i ) là máy chủ được giao để thực bằng giá trị nguyên sau khi làm tròn. Cách làm như hiện tác vụ T i . vậy đã phá hỏng quá trình tiến hóa từng bước của Wi phương pháp PSO. • Thời gian tính toán của tác vụ T i là: Để giải quyết vấn đề trên, bài báo này đề xuất P( f (Ti )) cách giải quyết như sau: giá trị thực của vế phải (x i k[t] (i=1,2, ... M) + v i k[t]) sẽ được để nguyên không làm tròn, còn vế (1) trái x i k+1[t] sẽ được gán bởi định danh của máy chủ có • Thời gian truyền dữ liệu giữa tác vụ T i và tác vụ tốc độ tính toán gần với giá trị của vế phải nhất so với con T là Dij các máy chủ còn lại. Làm như vậy tác vụ sẽ được gán (2) B( f (Ti ), f (T j )) j cho máy chủ có năng lực phù hợp với giá trị được tính toán theo PSO. Hàm mục tiêu: Bài báo này định nghĩa hàm mục tiêu 𝑥𝑖𝑘+1 [𝑡] ← 𝑗 𝑛ế𝑢 �𝑃�𝑆𝑗 � − �𝑥𝑖𝑘 [𝑡] + 𝑣𝑖𝑘 [𝑡]�� ≤ là: Makespan → min trong đó Makespan là thời gian �𝑃(𝑆𝑟 ) − �𝑥𝑖𝑘 [𝑡] + 𝑣𝑖𝑘 [𝑡]�� ∀𝑆𝑟 ∈ 𝑆; 𝑡 = hoàn thành luồng công việc, được tính từ khi tác vụ gốc được khởi động cho tới thời điểm tác vụ cuối 1,2 … 𝑀 6) cùng được thực hiện xong. Ví dụ 2: giả thiết tập máy chủ S trong ví dụ 1 có tốc độ tính toán được liệt kê trong Bảng 1 sau đây IV. GIẢI PHÁP ĐỀ XUẤT Bảng 1. Tốc độ tính toán của các máy chủ Máy chủ S i Tốc độ xử lý P(S i ) (MI/s) 4.1. Mã hóa cá thể Theo phương pháp PSO, tại bước lặp thứ k, cá thể S1 3.1 thứ i trong đàn được xác định bởi vector vị trí x i k (cho S2 5.2 biết vị trí hiện tại) và vector dịch chuyển v i k (cho biết S3 4.1 hướng dịch chuyển hiện tại). Trong bài toán xếp lịch đang xét, hai vector đó đều có số chiều bằng số tác vụ trong luồng công việc, ký hiệu là M. Cả vector vị trí Giả sử ở bước thứ k+1 tổng x i k + v i k = [4.4 ; 2.1 ; và vector dịch chuyển đều được biểu diễn bằng cấu 6.7 ; 5.6 ; 10.2] thì vector vị trí x i k+1 sẽ được gán bằng trúc dữ liệu bảng băm trong ngôn ngữ lập trình java. [3; 1; 2; 2; 2] ; nghĩa là cá thể đó tương ứng với Ví dụ 1: giả sử luồng công việc gồm tập tác vụ phương án xếp lịch sau đây: T={T 1 , T 2 , T 3 , T 4 , T 5 }, đám mây có tập máy chủ S = T1 T2 T3 T4 T5 {S 1 , S 2 , S 3 }. Khi đó cá thể x i được biểu diễn S3 S1 S2 S2 S2 bằng vector vị trí [1 ; 2 ; 1 ; 3 ; 2] chính là phương án xếp lịch mà theo đó tác vụ T 1 , T 3 được bố trí thực Thật vậy, thành phần thứ nhất của vector vị trí, hiện bởi máy chủ S 1 , tác vụ T 2 , T 5 được thực hiện x i k+1[1] , sẽ nhận giá trị 3, nghĩa là tác vụ T 1 sẽ được trên S 2 còn tác vụ T 4 được thực hiện bởi S 3 như dưới gán cho máy chủ S 3 bởi vì : đây 𝑥𝑖𝑘+1 [1] ← 3 𝑣ì |𝑃(𝑆3 ) − 4.4| ≤ |𝑃(𝑆𝑟 ) − (4.4)| ∀𝑆𝑟 T1 T2 T3 T4 T5 ∈𝑆 S1 S2 S1 S3 S2 Nghĩa là trong 3 máy chủ thì máy S 3 có tốc độ tính toán gần với giá trị 4.4 nhất so với 2 máy chủ còn 4.2. Phương pháp cập nhật vị trí cá thể lại, theo bảng 1, do đó tác vụ T 1 được gán cho máy chủ S 3 để thực hiện, tức là f(T 1 ) = S 3 . Phép gán tương Khi áp dụng công thức cập nhật vị trí của cá thể tự cũng được thực hiện với bốn tác vụ còn lại : T 2 , (4) vào bài toán lập lịch đang xét, chúng ta gặp một T 3 ,T 4 ,T 5 . vấn đề. Các thành phần của vector dịch chuyển v i k là Vấn đề tương tự cũng xảy ra với phép trừ hai số thực do công thức (5) tính vector dịch chuyển có vector vị trí trong công thức (1): (pbest i - x i k ) và những tham số là số thực như rand 1 , rand 2 , c 1 ,c 2 . (gbest - x i k). Một số công trình hiện có như [10] chỉ Nhưng vì tập máy chủ S là hữu hạn và đếm được nên đơn giản thực hiện phép trừ các thành phần số nguyên các thành phần của vector vị trí x i phải là số nguyên rồi gán cho máy chủ có số thứ tự tương ứng. Ví dụ để có thể ánh xạ tới một máy chủ nào đó nơi mà tác nếu pbest i = [2,4,3,3,5] và x i k = [1,3,2,1,2] thì pbest i vụ tương ứng sẽ được thực hiện, chẳng hạn vector vị - x i k =[2-1,4-3,3-2,3-1,5-2] = [1,1,1,2,3]. Như đã giải trí x i trong ví dụ 1 có các thành phần là x i [1] =1, x i [2] thích ở trên, cách làm này thực chất là gán các tác vụ =2, x i [1] =1, x i [4] =3, x i [5] =2. Hậu quả là hai vế của cho những máy chủ mà số thứ tự của nó tình cờ đúng phép gán (2) khác kiểu nhau, vế trái x i k+1[t] thuộc bằng kết quả phép trừ. Cách làm mang tính ngẫu kiểu số nguyên còn vế phải x i k[t] + v i k[t] thuộc kiểu số nhiên như vậy đã phá hỏng quá trình từng bước tiếp thực. cận tới vị trí cực trị của phương pháp PSO. Bài báo Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 42
  4. này đề xuất một "phép trừ vector" áp dụng riêng cho 3. Khởi tạo giá trị r ngẫu nhiên công thức (5) như sau. Giả sử: trong đoạn [1, M] pbest i = [x i1 , x i2 ,…x iM ] với x ik ∈ S (∀k) và x j = [x j1 , 4. x i ← RotateRight(x i , r) x j2 ,…x jM ] với x jk ∈ S (∀k) 5. Khởi tạo 2 giá trị ngẫu nhiên Khi đó kết quả phép trừ pbest i - x j được tính như rand 1 , rand 2 trong đoạn [1,M] sau: pbest i - x j =[y 1 , y 2 ,….y M ] với các thành phần y k 6. x k ← Exchange (x i , rand 1 , rand 2 ) là các số thực được tính như sau 7. if f(x k ) < f(x i ) then return x k ∑𝑞∈𝑆 𝐵(𝑥𝑖𝑘 ,𝑥𝑞 ) 𝑦𝑘 = �𝑃(𝑥𝑖𝑘 ) + � − �𝑃�𝑥𝑗𝑘 � + 5. else return x i 𝑁−1 ∑𝑞∈𝑆 𝐵�𝑥𝑗𝑘 ,𝑥𝑞 � 6. t ← t+1 � 𝑣ớ𝑖 𝑘 = 1,2, … 𝑀 7. End while 𝑁−1 ( End Function 7) Theo cách tính này, các máy chủ được xếp thứ tự theo 4.4. Thuật toán đề xuất LOSPSO tốc độ tính toán và băng thông của những đường Tổng hợp những cải tiến nói trên, thuật toán đề xuất truyền kết nối tới nó. Ví dụ 3 sau đây sẽ minh họa cụ với tên gọi LOSPSO được mô tả như sau. thể hơn. Algorithm LOSPSO Ví dụ 3: Input: tập T, tập S, mảng W[1×M], Ta tiếp tục sử dụng tập máy chủ trong ví dụ 2. mảng P[1×N], mảng B[N×N], mảng Giả sử lbest j = [2,1,2,1,1] ; x j = [3,2,1,2,1] ; D[M×M], hằng số K, độ lệch ε, số cá Vậy lbest j – x j = [y 1 , y 2 , y 3 ,y 4 ,y 5 ] với y 1 được tính thể SCT như sau Output: lời giải tốt nhất gbest 𝐵(𝑆 ,𝑆 )+𝐵(𝑆2 ,𝑆3 ) 𝑦1 = �𝑃(𝑆2 ) + 2 1 � − �𝑃(𝑆3 ) + 1. Khởi tạo vector vị trí và vector 3−1 𝐵(𝑆3 ,𝑆1 )+𝐵(𝑆3 ,𝑆2 ) dịch chuyển của cá thể i một � cách ngẫu nhiên 3−1 Cách tính tương tự được áp dụng cho các thành 2. Khởi tạo bước lặp t← 0 ; phần y 2 , y 3 … y 5 còn lại. 3. while (điều kiện lặp) do 4.3. Biện pháp thoát khỏi cực trị địa phương 4. for i=1 to SCT do Phương pháp PSO nói riêng và các phương pháp 5. Tính vector vị trí x i theo tìm kiếm tiến hóa nói chung đôi khi bị mắc kẹt tại các công thức (6) lời giải cực trị địa phương mà không thể thoát ra để đi 6. end for tới lời giải tốt hơn. Bài báo này đề xuất sử dụng 7. for i=1 to SCT do phương pháp PSO kết hợp với thủ tục tìm kiếm lân 8. Cập nhật pbest i cận để định hướng cá thể tốt nhất chuyển sang vùng 9. end for tìm kiếm mới mỗi khi chương trình bị sa vào vùng 10. Cập nhật gbest cực trị địa phương. 11. for(i=1 to SCT do) 12. lbest i := Ring(x i ) ; 4.3.1.Thủ tục tìm kiếm lân cận 13. end for Tìm kiếm lân cận [16] là phương pháp tìm kiếm 14. for i=1 to SCT do bắt đầu từ một giải pháp ban đầu s 0 của bài toán và sử 15. Cập nhật vector dịch chuyển dụng các toán tử để di chuyển sang một giải pháp v i k theo công thức (5) và (6) khác của bài toán theo một cấu trúc lân cận xác định 16. Tính x i theo (4) nhằm tìm ra một lời giải tốt hơn. Bài báo này đề xuất 2 toán tử Exchange và RotateRight sử dụng cho quá 17. end for trình tìm kiếm lân cận (xem Hình 3.a và 3.b) 18. t++ ; 19. if (sau K thế hệ mà độ lệch 3 1 2 3 1 giữa các gbest không vượt quá 3 1 2 3 1 ε) then 20. gbest=LocalSearch(gbest); Hình 3.a. Toán tử RotateRight 21. end if 22. end while 3 3 2 1 1 return gbest Hình 3.b. Toán tử Exchange Thuật toán hoạt động theo phương pháp PSO theo đó tại mỗi bước lặp các cá thể cập nhật vị trí của mình 4.3.2. Giải thuật tìm kiếm lân cận hướng tới vị trí tốt nhất của các cá thể lân cận (lbest i ) Function LocalSearch (vector vị trí x i ) đồng thời có dựa trên kinh nghiệm cá nhân (pbest i ). Nếu sau K thế hệ liên tiếp mà cả quần thể không cải Input: vector vị trí x i thiện được một cách đáng kể giá trị gbest (mức chênh Output: vector vị trí x k có f(x k ) < không vượt quá ε) thì chứng tỏ quần thể đang hội tụ f(x i ) tại một cực trị địa phương. Khi đó thủ tục 1. Khởi tạo bước lặp t ← 0 LocalSearch được gọi tìm ra cá thể gbest mới và cá 2. while (điều kiện lặp) thể này sẽ di cư cả quần thể tới một vùng không gian mới, tại đó quá trình tìm kiếm được tái khởi động. Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 43
  5. Độ phức tạp của thuật toán LOSPSO. Trước khi 5.2. Tham số cấu hình hệ thống thực hiện thuật toán chính LOSPSO ta cần phải sắp Các tham số cấu hình của đám mây được thiết lập xếp các máy chủ thực thi theo thứ tự tăng dần của tốc trong miền giá trị như sau: độ thực hiện, giải thuật sắp xếp có độ phức tập về thời • Tốc độ tính toán P của các máy chủ: từ 1 đến gian là O(n.log(n)), thủ tục tính ma trận thời gian thực 250 (million instructions/s) thi của mỗi tác vụ trên các máy chủ có độ phức tạp thời gian tính toán là O(M×N); với M là số tác vụ, N • Khối lượng dữ liệu D giữa các tác vụ: từ 1 đến là số máy chủ. Thủ tục tính ma trận thời gian truyền 10000 (Mega bit) dữ liệu giữa các máy chủ có độ phức tạp tính toán là • Băng thông giữa các máy chủ B:từ 10 đến 100 O(N2). Trong thuật toán LOSPSO thì thủ tục khởi tạo (Mega bit/s) sẽ khởi tạo các cá thể của quần thể một cách ngẫu nhiên, mỗi cá thể được mã hóa bởi một véc tơ độ dài • Hệ số quán tính: ω = 0.729 M do vậy độ phức tạp của thủ tục khởi tạo là • Hệ số gia tốc: c 1 = c 2 = 1.49445 O(M×SCT) ; với SCT là số cá thể trong quần thể, trong thực nghiệm chúng tôi sử dụng SCT là 100. • Hằng số : K = 30 Hàm tính thời gian thực hiện (makespan) của mỗi phương án xếp lịch là O(M2). • Số cá thể SCT: SCT=25 Thủ tục RotateRight có độ phức tạp là O(M), thủ • Độ lệch ε : 0.21 tục Exchange có độ phức tạp là hằng số, do vậy thủ tục tìm kiếm lân cận LocalSearch có độ phức tạp là • α: từ 0.2 tới 0.7 O(M). Trong bài toán lập lịch luồng công việc thường số 5.3. Quá trình tiến hành thực nghiệm tác vụ lớn hơn số máy chủ (M > N) do vậy độ phức Để kiểm chứng thuật toán đề xuất LOSPSO tạp của thuật toán LOSPSO là (Số thế hệ )× O(M2). chúng tôi đã sử dụng công cụ mô phỏng Cloudsim [5] để tạo lập môi trường đám mây kết hợp với dữ liệu V. KẾT QUẢ THỰC NGHIỆM luồng công việc của ứng dụng Montage [18]. Các hàm của gói thư viện Jswarm [5] được sử dụng để 5.1. Phân nhóm dữ liệu thực nghiệm thực hiện các phương thức Tối ưu bày đàn. Đối tượng Dữ liệu sử dụng trong các thực nghiệm bao gồm: so sánh là thuật toán PSO_H [10], thuật toán EGA [9] • Dữ liệu về tốc độ tính toán của các máy chủ và và thuật toán Round Robin [19]. băng thông giữa các máy chủ được lấy từ các công Các chương trình mô phỏng được viết bằng ngôn ty cung cấp dịch vụ cloud [17] và địa chỉ website ngữ Java và chạy trên máy tính cá nhân với bộ vi xử (http://aws.amazon.com/ec2/pricing). lý Intel Core i5 2.2 GHz, RAM 4GB, hệ điều hành Windows 7 Ultimate. Thực nghiệm được tiến hành • Dữ liệu luồng công việc được lấy từ các bộ dữ liệu một cách độc lập 30 lần trên mỗi bộ dữ liệu thực thử nghiệm được xây dựng theo độ trù mật khác nghiệm. nhau và các luồng công việc từ các ứng dụng thực tế như ứng dụng Montage [18] 5.4. Kết quả thực nghiệm • Những dữ liệu đó được tổng hợp lại và chia thành Hình 4,5,6 cho thấy sự chênh lệch về thời gian xử hai nhóm, nhóm 1 là các luồng công việc ngẫu lý (makespan) của lời giải tốt nhất mà thuật toán đề nhiên với sự khác nhau về hệ số α, nhóm 2 là các xuất LOSPSO và các thuật toán đối chứng (PSO_H, luồng công việc từ ứng dụng Montage. EGA và Round Robin) tìm được khi chạy trên các bộ dữ liệu khác nhau thuộc cả 2 nhóm luồng công việc |E| ngẫu nhiên và luồng công việc từ ứng dụng Montage. α= M × (M − 1)/2 • Tham số α cho biết đồ thị G phân thành bao nhiêu cấp, mỗi cấp có nhiều hay ít tác vụ, nói cách 20.00 khác α phản ánh độ trù mật của đồ thị G. Khi làm 15.00 thực nghiệm với mỗi nhóm, số máy chủ và số tác 10.00 vụ được giữ cố định còn tỷ lệ α lần lượt thay đổi như trong các Hình 4,5,6. 5.00 • Tham số về máy chủ và số tác vụ của luồng công 0.00 việc được xác định qua ký hiệu của bộ dữ liệu thực RRTSM PSO_H LOSPSO EGA nghiệm, ví dụ T2086 sẽ có 20 tác vụ trong luồng công việc và thực hiện xếp lịch trên 8 máy chủ STD Mean Best trong hệ thống điện toán đám mây. Trong quá trình thực nghiệm chúng tôi đã sử dụng các đồ thị luồng công việc với số tác vụ từ 5 đến 50 và hệ Hình 4: So sánh các thuật toán với bộ dữ liệu T532 thống điện toán đám mây với số máy chủ từ 3 đến 8. Chi tiết về tham số cấu hình hệ thống được trình bày trong phần 5.2. Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 44
  6. • Đề xuất một phương thức mới để cập nhật vị trí 25.00 của cá thể bằng cách ánh xạ một giá trị thực tới máy chủ có tốc độ tính toán và băng thông gần với 20.00 giá trị đó nhất. 15.00 • Đề xuất công thức tính vector dịch chuyển của cá 10.00 thể thứ i theo giá trị gbest và lbest i • Đề xuất thủ tục LocalSearch để chương trình thoát 5.00 ra khỏi cực trị địa phương bằng cách chuyển các 0.00 cá thể tới một miền không gian tìm kiếm mới. RRTSM PSO_H LOSPSO EGA • Đề xuất thuật toán LOSPSO sử dụng phương thức cập nhật vị trí cá thể và thủ tục LocalSearch để tìm STD Mean Best kiếm lời giải cho bài toán lập lịch thực thi luồng công việc trong môi trường đám mây. Hình 5: So sánh các thuật toán với bộ dữ liệu T1051 Những kết quả thực nghiệm được tiến hành với nhiều bộ dữ liệu thực nghiệm khác nhau đã chứng tỏ chất lượng lời giải tìm được bởi thuật toán đề xuất tốt hơn so với các thuật toán đối chứng là thuật toán 200.00 PSO_H, thuật toán EGA và thuật toán Round Robin. 150.00 Về hướng công việc tiếp theo chúng tôi dự định đề xuất một kiến trúc lân cận mới phù hợp với bài toán 100.00 nhằm nâng cao khả năng tìm kiếm tổng thể qua đó 50.00 nhằm đạt được lời giải có chất lượng tốt hơn. 0.00 TÀI LIỆU THAM KHẢO RRTSM PSO_H LOSPSO EGA [1] G. B. Berriman, et al, Montage: A Grid Enabled Engine for Delivering Custom Science-Grade STD Mean Best Mosaics On Demand", in SPIE Conference, 2004. [2] P. Maechling, et al, SCEC CyberShake Workflows, Automating Probabilistic Seismic Hazard Analysis Calculations”, Springer, 2006. Hình 6: So sánh các thuật toán với bộ dữ liệu M2032 [3] "USC Epigenome Center". http://epigenome.usc.edu. [Online]. http://epigenome.usc.edu Kết quả thực nghiệm được trình bày chi tiết trong [4] LIGO Project. LIGO - Laser Interferometer bảng 2, 3 và các hình 4,5,6, kết quả so sánh giữa giá Gravitational Wave Observatory. trị trung bình tính được bởi thuật toán LOSPSO với [Online]. http://www.ligo.caltech.edu. các thuật toán đối sánh, trong hầu hết các trường hợp [5] Buyya R., Ranjan R., Calheiros R.N. - Modeling and thuật toán LOSPSO đều cho kết quả tốt hơn các thuật simulation of scalable Cloud computing environments toán đối sánh, giá trị trung bình tìm được bởi and the CloudSim toolkit: Challenges and opportunities, Proceedings of the Conference on High LOSPSO nhỏ hơn giá trị trung bình tìm được bởi Performance Computing and Simulation (2009) 1–11. PSO_H từ 4% - 11% và nhỏ hơn giá trị trung bình tìm (http://www.cloudbus.org/cloudsim/). được bởi thuật toán EGA từ 2% - 7%. [6] J.D. Ullman, NP-complete scheduling problems, Journal of Computer and System Sciences, pages Hình 1,2,3,4 cũng so sánh giữa giá trị tốt nhất tìm 384-393, volume 10, issue 3, 1975 được bởi thuật toán LOSPSO với các thuật toán đối [7] N.S.Grigoreva, Branch and Bound Method for sánh, qua đó ta thấy giá trị tốt nhất tìm được bởi Scheduling Precedence Constrained Tasks on LOSPSO nhỏ hơn giá trị tốt nhất tìm được bởi Parallel Identical Processors, Proceedings of the World Congress on Engineering, Vol II, 2014 PSO_H từ 2% - 9%, và nhỏ hơn giá trị tốt nhất tìm [8] R. Rajkumar, T. Mala, Achieving Service Level được bởi Random từ 20% - 40%, giá trị tốt nhất tìm Agreement in Cloud Environment using Job được bởi thuật toán LOSPSO nhỏ hơn giá trị tốt nhất Prioritization in Hierarchical Scheduling, Proceeding tìm được bởi thuật toán EGA từ 1% - 8% . Cuối cùng of International Conference on Information System các hình 1,2,3,4 chỉ ra kết quả so sánh giữa độ lệch Design and Intelligent Application, 2012, vol 132, pp chuẩn tìm được bởi thuật toán LOSPSO với các thuật 547-554. toán đối sánh, giá trị độ lệch chuẩn của LOSPSO đều [9] S. Singh, M.Kalra, Task scheduling optimization of independent tasks in cloud computing using enhanced nhỏ hơn độ lệch chuẩn của các thuật toán RRTSM, genetic algorithm, International Journal of PSO_H và EGA, điều đó chứng tỏ thuật toán Application or Innovation in Engineering & LOSPSO có chất lượng lời giải tốt hơn các thuật toán Management, V.3, Issue 7, 2014. đối sánh và độ ổn định trong các lần chạy cũng tốt [10] S. Pandey, L. Wu1, S. M. Guru, R. Buyya1, A hơn. Particle Swarm Optimization (PSO)-based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments, Proc. of 24th IEEE VI. KẾT LUẬN International Conference on Advanced Information Bài báo này đã trình bày một giải thuật tìm kiếm Networking and Applications (AINA), pages 400- 407, 2010 theo phương pháp Tối ưu bày đàn cục bộ (Local PSO) [11] Q. Cao, W. Gong and Z. Wei, An Optimized để tìm lời giải gần đúng cho bài toán lập lịch thực thi Algorithm for Task Scheduling Based On Activity luồng công việc trong môi trường điện toán đám mây. Based Costing in Cloud Computing, In Proceedings of Những kết quả chính gồm có: Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 45
  7. Third International Conference on Bioinformatics and Biomedical Engineering, 2009, pp.1-3 Nguyễn Thế Lộc [12] S.Selvi, Dr. D.Manimegalai, Dr.A.Suruliandi, Tốt nghiệp ĐH khoa Toán Tin, ĐH Efficient Job Scheduling on Computational Grid with Differential Evolution Algorithm, , International Sư phạm Hà Nội năm 1993, Tốt Journal of Computer Theory and Engineering, Vol. 3, nghiệp Thạc sĩ CNTT tại trường No. 2, April, 201 ĐH Bách khoa Hà Nội, nhận bằng [13] Q. XU, L.WANG, HE. Baomin, N.WANG, Modified tiến sỹ tại Viện Nghiên cứu Khoa Opposition-Based Differential Evolution for Function học Công nghệ Nhật Bản JAIST Optimization, Journal of Computational Information Systems, pp. 1582-1591, 2011. năm 2007. Lĩnh vực nghiên cứu: mạng máy [14] A. E. M. Zavala, “EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary tính và truyền thông, xử lý song Computation IIA Comparison, A Comparison Study of song và phân tán PSO Neighborhoods”, Springer Verlag Berlin Điện thoại : 0988.765.837 Heideberg, pages 251-295, ISBN 978-3-642-32725-4, E-mail: locnt@hnue.edu.vn. 2013. [15] H.Matsushita, Swarm-Based Optimization with Dynamically-Changing Topology, IEEE Workshop on Nonlinear Circuit Networks, pp. 63-66, December 2012. [16] P.Hansen, Variable neighborhood search: Principles and applications, European Journal of Operational Research 130, pp. 449-467, 2001. [17] Vliet J. V., Paganelli F. - Programming Amazon EC2, O'Reilly Media, ISBN 1449393683, 2011. [18] Bruce Berriman G., Deelman E. - Montage: A grid enabled engine for delivering custom science-grade mosaics on demand, in SPIE, 2004 (http://montage.ipac.caltech.edu) [19] M. Mitzenmacher, E. Upfal, “Probability and Computing: Randomized Algorithms and Probabilistic Analysis”, Cambridge University Press (2005). Abstract: Cloud computing is a new trend of information and communication technology that enables resource distribution and sharing at a large scale. The Cloud consists of a collection of virtual machine that promise to provision on-demand computational and storage resources when needed. End-users can access these resources via the Internet and have to pay only for their usage. Scheduling of scientific workflow applications on the Cloud is a challenging problem that has been the focus of many researchers for many years. In this work, we propose a new algorithm for workflow scheduling that is derived from the Particle Swarm Optimization. SƠ LƯỢCVỀ TÁC GIẢ Phan Thanh Toàn Sinh năm 1974 tại Thái Nguyên. Tốt nghiệp ĐH và Thạc sĩ tại trường ĐH Bách khoa Hà Nội, nghiên cứu sinh năm 2012 tại Học viện Khoa học Công nghệ Quân sự. Hiện đang công tác tại trường ĐH Sư phạm Hà Nội. Lĩnh vực nghiên cứu: phương pháp tiến hóa, tối ưu, xử lý song song và phân tán. Điện thoại : 0912.069.762 E-mail: pttoan@hnue.edu.vn Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 46
  8. Bảng 2. kết quả thực hiện thuật toán với các bộ dữ liệu ngẫu nhiên Kí hiệu RRTSM PSO_H LOSPSO EGA STD Mean Best STD Mean Best STD Mean Best STD Mean Best T532 - 18.7 18.7 4.7 9.9 6.8 0.0 6.8 6.8 3.4 9.8 6.8 T1031 - 33.1 33.1 2.4 20.4 16.4 1.1 18.3 16.2 1.2 20.4 16.4 T1032 - 16 16 2.0 8.2 3.5 1.2 5.1 3.5 1.8 8.1 3.5 T1035 - 18.9 18.9 2.5 9.6 4.2 1.8 6.7 2.9 2.3 9.5 4.9 T1051 - 23.7 23.7 1.8 19.5 16.4 1.0 17.6 14.8 1.4 19.1 16.1 T1054 - 25.2 25.2 2.0 20.7 17.9 0.9 19.0 17.5 1.3 20.5 17.5 T2081 - 72.7 72.7 5.2 44.2 35.0 2.7 37.8 32.3 3.7 41.9 35.0 T2083 - 20.3 20.3 2.2 21.2 18.8 0.5 19.4 18.4 1.4 20.3 19.1 T2084 - 72.0 72.0 6.1 44.7 37.1 2.7 39.3 34.8 3.2 42.5 37.5 T2086 - 32.5 32.5 1.5 26.2 23.8 1.2 21.4 17.8 1.4 25.4 22.5 Bảng 3. kết quả thực hiện thuật toán với các bộ dữ liệu từ ứng dụng Montage Kí hiệu RRTSM PSO_H LOSPSO EGA STD Mean Best STD Mean Best STD Mean Best STD Mean Best M2032 - 162.7 162.7 4.9 142.1 130.6 3.6 128.4 130.0 5.3 135.5 132.1 M2051 - 146.6 146.6 5.4 132 122.8 3.3 123.4 118.7 4.5 131.7 125.3 M2531 - 465.0 465.0 18.7 373.4 341.5 13.0 346.4 338.1 7.0 352.7 340.4 M2532 - 183.8 183.8 3.9 110.7 102.5 1.5 104.7 101.7 1.4 112.1 104.5 M2533 - 322.9 322.9 4.0 315.4 311.7 0.5 312.5 311.6 0.5 315.2 311.8 M2581 - 300.6 300.6 15 260.3 235.1 6.1 236.1 228.4 6.5 246.2 234.9 M2582 - 133.9 133.9 5.1 84.8 75.9 4.7 81.4 74.3 2.9 85.1 77.3 M2583 - 236.5 236.5 8.3 239 225 5.3 224.3 215.7 4.7 233.5 222.4 M5081 - 155.8 155.8 6.3 108.0 95.0 5.5 101.7 91.1 3.2 107.8 96.4 M5082 - 82.1 82.1 0.9 14.0 12.1 0.8 12.6 11.1 0.5 14.0 11.8 M5083 - 101.7 101.7 4.3 98.3 88.8 4.3 90.0 80.8 1.8 95.3 87.5 Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 47
  9. Bảng 2. kết quả thực hiện thuật toán với các bộ dữ liệu ngẫu nhiên Kí hiệu RRTSM PSO_H LOSPSO EGA STD Mean Best STD Mean Best STD Mean Best STD Mean Best T532 - 18.7 18.7 4.7 9.9 6.8 0.0 6.8 6.8 3.4 9.8 6.8 T1031 - 33.1 33.1 2.4 20.4 16.4 1.1 18.3 16.2 1.2 20.4 16.4 T1032 - 16 16 2.0 8.2 3.5 1.2 5.1 3.5 1.8 8.1 3.5 T1035 - 18.9 18.9 2.5 9.6 4.2 1.8 6.7 2.9 2.3 9.5 4.9 T1051 - 23.7 23.7 1.8 19.5 16.4 1.0 17.6 14.8 1.4 19.1 16.1 T1054 - 25.2 25.2 2.0 20.7 17.9 0.9 19.0 17.5 1.3 20.5 17.5 T2081 - 72.7 72.7 5.2 44.2 35.0 2.7 37.8 32.3 3.7 41.9 35.0 T2083 - 20.3 20.3 2.2 21.2 18.8 0.5 19.4 18.4 1.4 20.3 19.1 T2084 - 72.0 72.0 6.1 44.7 37.1 2.7 39.3 34.8 3.2 42.5 37.5 T2086 - 32.5 32.5 1.5 26.2 23.8 1.2 21.4 17.8 1.4 25.4 22.5 Bảng 3. kết quả thực hiện thuật toán với các bộ dữ liệu từ ứng dụng Montage Kí hiệu RRTSM PSO_H LOSPSO EGA STD Mean Best STD Mean Best STD Mean Best STD Mean Best M2032 - 162.7 162.7 4.9 142.1 130.6 3.6 128.4 130.0 5.3 135.5 132.1 M2051 - 146.6 146.6 5.4 132 122.8 3.3 123.4 118.7 4.5 131.7 125.3 M2531 - 465.0 465.0 18.7 373.4 341.5 13.0 346.4 338.1 7.0 352.7 340.4 M2532 - 183.8 183.8 3.9 110.7 102.5 1.5 104.7 101.7 1.4 112.1 104.5 M2533 - 322.9 322.9 4.0 315.4 311.7 0.5 312.5 311.6 0.5 315.2 311.8 M2581 - 300.6 300.6 15 260.3 235.1 6.1 236.1 228.4 6.5 246.2 234.9 M2582 - 133.9 133.9 5.1 84.8 75.9 4.7 81.4 74.3 2.9 85.1 77.3 M2583 - 236.5 236.5 8.3 239 225 5.3 224.3 215.7 4.7 233.5 222.4 M5081 - 155.8 155.8 6.3 108.0 95.0 5.5 101.7 91.1 3.2 107.8 96.4 M5082 - 82.1 82.1 0.9 14.0 12.1 0.8 12.6 11.1 0.5 14.0 11.8 M5083 - 101.7 101.7 4.3 98.3 88.8 4.3 90.0 80.8 1.8 95.3 87.5 Số 02 & 03 (CS.01) 2017 TẠP CHÍ KHOA HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG 48
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học