Thuật toán LPSO lập lịch thực thi luồng công việc cho các ứng dụng khoa học trong môi trường điện toán đám mây

Chia sẻ: Wang Ziyi | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

34
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài báo này đề xuất thuật toán metaheuristic LPSO để tìm kiếm phương án lập lịch dựa trên phương pháp Tối ưu bày đàn. Thực nghiệm được tiến hành trên công cụ mô phỏng CloudSim đã chứng tỏ thuật toán đề xuất cho kết quả tốt hơn ba thuật toán đối chứng là PSO, Random và RoundRobin và lời giải tìm được có độ sai lệch rất bé so với lời giải tối ưu. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thuật toán LPSO lập lịch thực thi luồng công việc cho các ứng dụng khoa học trong môi trường điện toán đám mây

Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) THUẬT TOÁN LPSO LẬP LỊCH THỰC THI LUỒNG CÔNG VIỆC CHO CÁC ỨNG DỤNG KHOA HỌC TRONG MÔI TRƯỜNG ĐIỆN TOÁN ĐÁM MÂY Phan Thanh Toàn1, Nguyễn Thế Lộc2, Nguyễn Doãn Cường3 1 Khoa Sư phạm kỹ thuật, Trường Đại học Sư Phạm Hà Nội 2 Khoa Công nghệ thông tin, Trường Đại học Sư Phạm Hà Nội 3 Viện Công nghệ thông tin, Viện Khoa học công nghệ quân sự pttoan@hnue.edu.vn, locnt@hnue.edu.vn, cuongvncntt@yahoo.com Tóm tắt (iii) thuật toán lập lịch mới tên là LPSO (mục 4.4). Ứng dụng dạng luồng công việc đã được sử dụng rộng rãi Phần V mô tả các thực nghiệm được tiến hành dựa trên công trong nhiều công trình nghiên cứu khoa học, đây là loại ứng dụng cụ mô phỏng Cloudsim [1] và phân tích những số liệu thực có qui mô phức tạp và thường phải xử lí một lượng dữ liệu rất lớn nghiệm thu được. Phần VI tóm tắt những kết quả chính của bài do vậy các môi trường tính toán phân tán như điện toán lưới (grid báo và hướng nghiên cứu sẽ tiến hành trong tương lai. computing), hay điện toán đám mây (cloud computing) thường II. CÁC CÔNG TRÌNH LIÊN QUAN được sử dụng. Bài toán lập lịch từ lâu đã được chứng minh là thuộc lớp NP-complete trong khi mô hình dịch vụ trên môi trường 2.1. Các hướng tiếp cận bài toán điện toán đám mây yêu cầu phải tìm ra lời giải trong thời gian ngắn để khách hàng không phải chờ đợi. Bài báo này đề xuất thuật Bài toán lập lịch luồng công việc đã được chứng minh là toán metaheuristic LPSO để tìm kiếm phương án lập lịch dựa trên thuộc lớp NP-đầy đủ [2] nghĩa là thời gian để tìm ra lời giải tối phương pháp Tối ưu bày đàn. Thực nghiệm được tiến hành trên ưu là rất lớn, vì vậy đã có nhiều giải thuật metaheuristic được công cụ mô phỏng CloudSim đã chứng tỏ thuật toán đề xuất cho nghiên cứu nhằm tìm ra lời giải gần đúng trong thời gian ngắn. kết quả tốt hơn ba thuật toán đối chứng là PSO, Random và S. Parsa [3] đã đề xuất một thuật toán lập lịch nhằm tối thiểu RoundRobin và lời giải tìm được có độ sai lệch rất bé so với lời giải thời gian thực thi trong môi trường lưới tính toán Grid. J.M. tối ưu. Cope và đồng nghiệp đã phân tích hiệu năng của giải thuật FRMTL và FRMAS [4] trong môi trường lưới tính toán Từ khóa: workflow scheduling, particle swarm optimization, cloud TeraGrid, một dạng đặc biệt của đám mây điện toán. A. computing Agarwal đã đề xuất thuật toán tham lam [5] trong đó mỗi tác vụ I. ĐẶT VẤN ĐỀ được gán một thứ tự ưu tiên dựa vào khối lượng công việc của tác vụ, mỗi máy chủ cũng được gán một thứ tự ưu tiên theo tốc Luồng công việc (workflow) là một chuỗi có thứ tự các độ xử lý của máy chủ sau đó gán các tác vụ vào các máy chủ tác vụ (task) có thể được thực hiện đồng thời hay tuần tự nếu theo các thứ tự ưu tiên đã tính toán. Cách làm này có nhược dữ liệu đầu ra của tác vụ này là đầu vào của tác vụ kế tiếp. Rất điểm là khiến những tác vụ có mức ưu tiên thấp phải chờ đợi nhiều ứng dụng trong các lĩnh vực khoa học khác nhau đều yêu lâu và bỏ qua yếu tố tốc độ truyền dữ liệu giữa các máy chủ cầu phải xử lí một lượng lớn dữ liệu được tổ chức theo dạng trong đám mây. luồng công việc. Vấn đề lập lịch luồng công việc trong môi trường điện toán đám mây về bản chất là tìm phương án ánh xạ Một số tác giả khác như M.Wieczorek [6] đã nghiên những tác vụ của luồng công việc tới các máy chủ của đám cứu và đề xuất thuật toán lập lịch thực thi luồng công việc theo mây sao cho thời gian xử lý toàn bộ luồng công việc là nhỏ phương pháp GA (Genetic Algorithm - Gen di truyền), tuy nhất, biết rằng khối lượng tính toán và yêu cầu dữ liệu của các nhiên các nghiên cứu [7] [8] đã nhận định rằng phương pháp tác vụ, tốc độ tính toán và truyền thông của các máy chủ là PSO (Particle Swarm Optimization - Tối ưu bày đàn) có ưu thế khác nhau. hơn so với phương pháp GA khi giải bài toán lập lịch luồng công việc trong những môi trường tính toán phân tán như Lưới Phần tiếp theo của bài báo có cấu trúc như sau. Phần II (Grid Computing) hay Đám mây (Cloud Computing). Theo giới thiệu một số công trình nghiên cứu có liên quan về bài hướng đó, S. Pandey [9] đã đề xuất thuật toán theo phương toán lập lịch luồng công việc.Trong phần III chúng tôi trình pháp PSO nhằm cực tiểu hóa chi phí thực thi. Thay vì tìm bày mô hình lý thuyết để biểu diễn năng lực tính toán và truyền phương án có tổng chi phí thực thi tại các máy chủ là bé nhất, thông của đám mây, dựa trên mô hình lý thuyết này, phần IV S. Pandey lại định nghĩa hàm mục tiêu để tìm phương án có chi đề xuất: phí thực thi của máy chủ tốn kém nhất (máy có tổng chi phí lớn (i) phương thức mới để cập nhật vị trí của cá thể (mục 4.2) hơn mọi máy khác) là nhỏ nhất so với các phương án khác. (ii) giải pháp để chương trình thoát ra khỏi vùng cực trị địa Cách làm này có xu hướng “cào bằng” nghĩa là thiên về các lời phương và di chuyển tới một vùng mới trong không gian giải có chi phí thực thi của các máy chủ là xấp xỉ nhau. Chúng tìm kiếm (mục 4.3) tôi nhận thấy, qua lý thuyết và các thực nghiệm kiểm chứng, ISBN: 978-604-67-0635-9 194 194
Hội Hội Thảo Quốc Thảo GiaGia Quốc 2015 vềvềĐiện 2015 ĐiệnTử, Tử,Truyền TruyềnThông Thông và CôngNghệ và Công NghệThông ThôngTinTin (ECIT (ECIT 2015) 2015) cách làm này thường khiến chương trình sớm hội tụ về những B: S×S → R+ giá trị cực tiểu địa phương thay vì tìm ra cực trị toàn cục. (Si,Sj) → B(Si,Sj) 1 2.2. Phương pháp Tối ưu bày đàn - Giả thiết hàm băng thông B() thỏa mãn các điều kiện 2 3 4 Phương pháp tối ưu bày đàn (PSO - Particle Swarm sau: Optimization) được đề xuất bởi Kennedy và Eberhart [10] là phương pháp tìm kiếm tiến hóa dựa theo hành vi tìm thức ăn  B(Si,Si) = ∞ : thời gian theo đàn của các loài động vật như chim hay cá, mỗi cá thể truyền tại chỗ bằng không 5 trong đàn sẽ di chuyển dựa theo kinh nghiệm của bản thân và  B(Si,Sj) = B(Sj,Si) : tốc độ Hình 1: Đồ thị biểu diễn một của các cá thể khác trong quần thể. Tại bước lặp thứ k, hướng truyền hai chiều bằng nhau luồng công việc với 5 tác vụ di chuyển của cá thể thứ i trong đàn được cập nhật theo các  Giá trị B(Si,Sj) được cho công thức sau: trước (i,j). vik+1= vik + c1 rand1×(pbesti - xik) + c2 rand2 ×(gbest - xik) (1) - Khối lượng dữ liệu do tác vụ Ti chuyển tới tác vụ Tj, kí xik+1 = xik + vik (2) hiệu là Dij với đơn vị là Megabit, là giá trị cho trước (i,j). Trong đó - Mỗi phương án xếp lịch thực thi luồng công việc tương  vik, vik+1 :vector dịch chuyển của cá thể i ở bước lặp k và k+1 đương với một hàm f()  xik, xik+1 : vị trí của cá thể i ở bước lặp thứ k và k+1 ω: hệ số quán tính f:T→S  c1, c2 : hệ số gia tốc Ti → f(Ti) Trong đó f(Ti) là máy chủ chịu trách nhiệm thực thi tác vụ Ti  rand1, rand2 : các hệ số ngẫu nhiên trong đoạn [0,1] Từ các giả thiết trên ta suy ra:  pbesti : vị trí tốt nhất của cá thể i tính tới thời điểm hiện tại  lbesti : vị trí tốt nhất của cá thể i trong lân cân.  Thời gian tính toán của tác vụ Ti là: Wi (i=1,2, ... M) (3) P f Ti  Có hai phiên bản của phương pháp PSO là PSO toàn cục  Thời gian truyền dữ liệu giữa tác vụ Ti và tác vụ con Tj là và PSO cục bộ, với phiên bản PSO toàn cục vector dịch Dij chuyển của mỗi cá thể được cập nhật theo vị trí tốt nhất của cá (4) thể và vị trí tốt nhất của cả quần thể, ngược lại phiên bản PSO B f Ti , f T j  cục bộ vector dịch chuyển của mỗi cá thể được cập nhật theo Bài báo này định nghĩa hàm mục tiêu là: Makespan → min vị trí tốt nhất của cá thể và vị trí tốt nhất của các lân cận của cá trong đó Makespan là thời gian hoàn thành luồng công việc, thể đó. PSO toàn cục có tốc độ hội tụ nhanh tuy nhiên thường được tính từ khi tác vụ gốc được khởi động cho tới thời điểm bị rơi vào cục bộ địa phương do vậy lời giải thường không tốt tác vụ cuối cùng được thực hiện xong. bằng PSO cục bộ. IV. THUẬT TOÁN ĐỀ XUẤT III. MÔ HÌNH LÝ THUYẾT 4.1. Mã hóa cá thể Giả sử cần sắp xếp lịch biểu cho một luồng công việc trong Theo phương pháp PSO, tại bước lặp thứ k, cá thể thứ i môi trường đám mây với các giả thiết như sau : trong đàn được xác định bởi vector vị trí xik (cho biết vị trí - Luồng công việc được biểu diễn bởi đồ thị G=(V, E), với hiện tại) và vector dịch chuyển vik (cho biết hướng dịch V là tập đỉnh của đồ thị, mỗi đỉnh biểu thị cho một tác vụ. chuyển hiện tại). Trong bài toán xếp lịch đang xét, hai vector - T ={T1, T2,…,TM} là tập các tác vụ, M là số lượng tác vụ đó đều có số chiều bằng số tác vụ trong luồng công việc, ký của luồng công việc đang xét. hiệu là M. Cả vector vị trí và vector dịch chuyển đều được biểu diễn bằng cấu trúc dữ liệu bảng băm. - E là tập cạnh thể hiện mối quan hệ cha-con giữa các tác vụ. Cạnh (Ti, Tj)  E cho biết tác vụ Ti là cha của tác vụ Ví dụ 1: giả sử luồng công việc gồm tập tác vụ T={T1, T2, T3, Tj, dữ liệu đầu ra của Ti sẽ là dữ liệu đầu vào cho tác vụ Tj T4, T5}, đám mây có tập máy chủ S = {S1, S2, S3}. Khi đó cá (xem Hình 1) thể xi được biểu diễn 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ụ T1, T3 được bố trí thực - Tập máy chủ của đám mây ký hiệu là S = {S1, S2,….,SN}, hiện bởi máy chủ S1, tác vụ T2, T5 được thực hiện trên S2 còn N là số lượng máy chủ của đám mây. tác vụ T4 được thực hiện bởi S3 như dưới đây - Mỗi tác vụ có thể được thực thi trên một máy chủ bất kì, T1 T2 T3 T4 T5 máy chủ đó phải thực hiện toàn bộ tác vụ từ đầu đến cuối. - Khối lượng tính toán (Workload) của tác vụ Ti kí hiệu là S1 S2 S1 S3 S2 Wi với đơn vị đo là flop (floating point operations: phép 4.2. Phương thức cập nhật vị trí của cá thể tính trên số thực dấu phảy động). Wi được cho trước (i = 1,2, …M) Khi áp dụng công thức cập nhật vị trí của cá thể (2) vào - Tốc độ tính toán của máy chủ Si , đơn vị là MI/s (million bài toán lập lịch đang xét, chúng ta gặp một vấn đề. Các thành instructions/second), được ký hiệu bởi P(Si), là giá trị phần của vector dịch chuyển vik là số thực do công thức (1) được cho trước (i = 1,2, …M) tính vector dịch chuyển có những tham số là số thực như rand1, rand2, c1,c2. Nhưng vì tập máy chủ S là hữu hạn và đếm - Giữa hai máy chủ Si, Sj bất kỳ (1≤i,j≤N) có một đường được nên các thành phần của vector vị trí xi phải là số nguyên truyền với băng thông, đơn vị là Megabit/s, được biểu thị để có thể ánh xạ tới một máy chủ nào đó nơi mà tác vụ tương bởi hàm hai biến B() được định nghĩa như sau: 195 195
HộiHội Thảo Thảo QuốcGia Quốc Gia2015 2015về vềĐiện Điện Tử, Tử,Truyền Truyền Thông Thông và vàCông CôngNghệ NghệThông TinTin Thông (ECIT 2015) (ECIT 2015) ứng sẽ được thực hiện, chẳng hạn vector vị trí xi trong ví dụ 1 phép trừ. Cách làm mang tính ngẫu nhiên như vậy đã phá hỏng có các thành phần là xi[1] =1, xi[2] =2, xi[1] =1, xi[4] =3, xi[5] quá trình từng bước tiếp cận tới vị trí cực trị của phương pháp =2. Hậu quả là hai vế của phép gán (2) khác kiểu nhau, vế trái PSO. Bài báo này đề xuất một "phép trừ vector" áp dụng xik+1[t] thuộc kiểu số nguyên còn vế phải xik[t] + vik[t] thuộc riêng cho công thức (1) như sau. Giả sử: kiểu số thực. pbesti = [xi1, xi2,…xiM] với xik S (k) và xj = [xj1, xj2,…xjM] Để giải quyết mâu thuẫn này, một số nghiên cứu trước với xjk S (k) đây như [9] [11] đã làm tròn giá trị số thực ở vế phải rồi gán Khi đó kết quả phép trừ pbesti - xj được tính như sau: pbesti - cho biến vị trí xik+1[t] ở vế trái. Kết quả là nếu giá trị của vế xj =[y1, y2,….yM] với các thành phần yk là các số thực được tính phải là 3.2 thì phân phối tác vụ tới thực thi tại máy chủ có số như sau thứ tự là 3, còn nếu vế phải 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 một vị trí được tính toán cẩn thận theo chiến lược PSO cho máy chủ mà số thứ tự của nó tình cờ đúng bằng giá ( ) trị nguyên sau khi làm tròn. Cách làm như vậy đã phá hỏng Theo cách tính này, các máy chủ được xếp thứ tự theo tốc độ quá trình tiến hóa từng bước của phương pháp PSO. tính toán và băng thông của những đường truyền kết nối tới Để giải quyết vấn đề trên, bài báo này đề xuất cách giải nó. Ví dụ 3 sau đây sẽ minh họa cụ thể hơn. quyết như sau: giá trị thực của vế phải (xik[t] + vik[t]) sẽ được Ví dụ 3: để nguyên không làm tròn, còn vế trái xik+1[t] sẽ được gán bởi định danh của máy chủ có tốc độ tính toán gần với giá trị của Ta tiếp tục sử dụng tập máy chủ trong ví dụ 2. vế phải nhất so với các máy chủ còn lại. Làm như vậy tác vụ Giả sử gbest = [2,1,2,1,1] ; xj = [3,2,1,2,1] ; sẽ được gán cho máy chủ có năng lực phù hợp với giá trị được Vậy gbest – xj = [y1, y2, y3,y4,y5] với y1 được tính như sau tính toán theo PSO. ( ) ( ) ( ) ( ) xik+1[t]←j if │P(Sj) - (xik[t] + vik[t])│≤│P(Sr) - (xik[t] + vik[t])│ { ( ) } { ( ) } SrS ; t =1,2 .. M (5) Cách tính tương tự được áp dụng cho các thành phần y2, y3 … Ví dụ 2: giả thiết tập máy chủ S trong ví dụ 1 có tốc độ tính y5 còn lại. toán được liệt kê trong bảng 1 sau đây Bảng 1: Tốc độ tính toán của các máy chủ 4.3. Biện pháp thoát khỏi cực trị địa phương Phương pháp PSO nói riêng và các phương pháp tìm Máy chủ Si Tốc độ xử lý P(Si) (MI/s) kiếm tiến hóa nói chung đôi khi bị mắc kẹt tại các lời giải cực S1 3.1 trị địa phương mà không thể thoát ra để đi tới lời giải tốt hơn. S2 5.2 Bài báo này đề xuất sử dụng phương pháp PSO kết hợp với S3 4.1 thủ tục tìm kiếm lân cận để định hướng cá thể tốt nhất chuyển sang vùng tìm kiếm mới mỗi khi chương trình bị sa vào vùng Giả sử ở bước thứ k+1 tổng xik + vik = [4.4 ; 2.1 ; 6.7 ; 5.6 ; cực trị địa phương. 10.2] thì vector vị trí xik+1 sẽ được gán bằng [3; 1; 2; 2; 2] nghĩa là cá thể đó tương ứng với phương án xếp lịch sau đây: Tìm kiếm lân cận là phương pháp tìm kiếm bắt đầu từ một giải pháp ban đầu s0 của bài toán và sử dụng các toán tử T1 T2 T3 T4 T5 để di chuyển sang một giải pháp khác của bài toán theo một S3 S1 S2 S2 S2 cấu trúc lân cận xác định 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á trình tìm kiếm lân cận (xem hình 3.a và 3.b) Thật vậy, thành phần thứ nhất của vector vị trí, xik+1[1] , sẽ nhận giá trị 3, nghĩa là tác vụ T1 sẽ được gán cho máy chủ S3 3 1 2 3 1 3 1 2 3 1 bởi vì : [ ] | ( ) | | ( ) ( )| a. Toán tử RotateRight Nghĩa là trong 3 máy chủ thì máy S3 có tốc độ tính toán gần 3 3 2 1 1 với giá trị 4.4 nhất so với 2 máy chủ còn lại, theo bảng 1, do đó tác vụ T1 được gán cho máy chủ S3 để thực hiện, tức là f(T1) Hình. 3. Các toán tử tìm kiếm lân cận b. Toán tử Exchange = S3. Phép gán tương tự cũng được thực hiện với bốn tác vụ còn lại : T2, T3,T4,T5. Function LocalSearch (vector vị trí xi ) Vấn đề tương tự cũng xảy ra với phép trừ hai vector vị trí Input: vector vị trí xi trong công thức (1): (pbesti - xik ) và (gbest - xik). Một số công Output: vector vị trí xk có f(xk) < f(xi) trình hiện có như [9] [11] chỉ đơn giản thực hiện phép trừ các 1. Khởi tạo bước lặp t  0 thành phần số nguyên rồi gán cho máy chủ có số thứ tự tương ứng. Ví dụ nếu pbesti = [2,4,3,3,5] và xik = [1,3,2,1,2] thì 2. while (điều kiện lặp) pbesti - xik =[2-1,4-3,3-2,3-1,5-2] = [1,1,1,2,3]. Như đã giải 3. r1, r2, r3  Random(1, M) thích ở trên, cách làm này thực chất là gán các tác vụ cho 4. xi  RotateRight(xi, r1) những máy chủ mà số thứ tự của nó tình cờ đúng bằng kết quả 196 196
HộiHội Thảo Quốc Thảo Gia Quốc 2015 Gia 2015vềvềĐiện ĐiệnTử, Tử,Truyền TruyềnThông và Công Thông và CôngNghệ NghệThông ThôngTinTin (ECIT (ECIT 2015) 2015) 5. xk  Exchange (xi, r2, r3) lượt được khảo sát cho tới khi toàn bộ không gian lời giải 6. if f(xk) < f(xi) then return xk được duyệt hết, thuật toán trở thành duyệt vét cạn. Để tránh 7. else return xi tình huống này, chúng tôi cũng sử dụng giải pháp chung thường được áp dụng trong các giải thuật tiến hóa, đó là đặt 8. t  t+1 một giá trị ngưỡng tối đa, khi quá trình tiến hóa của quần thể 9. End while đạt tới số thế hệ vượt quá giá trị ngưỡng đã đinh thì quá trình End Function tìm kiếm kết thúc. Trong phần thực nghiệm tiếp theo giá trị ngưỡng cho số thế hệ là 3000, giá trị K được đặt là 100 và độ 4.4. Thuật toán đề xuất LPSO lệch  được ấn định là 0.21. Tổng hợp những cải tiến nói trên, thuật toán đề xuất với tên gọi LPSO được mô tả như sau. V. THỰC NGHIỆM Algorithm LPSO 5.1. Phân nhóm dữ liệu thực nghiệm Input: tập T, tập S, mảng W[1×M], mảng P[1×N], mảng B[N×N], mảng D[M×M], hằng số K, độ lệch , số cá thể SCT Dữ liệu sử dụng trong các thực nghiệm bao gồm : Output: lời giải tốt nhất gbest  Dữ liệu về tốc độ tính toán của các máy chủ và băng 1. Khởi tạo xi, vi một cách ngẫu nhiên thông giữa các máy chủ được lấy từ các công ty cung 2. Khởi tạo bước lặp t 0 ; cấp dịch vụ cloud trong nước [13][14] và quốc tế 3. while (điều kiện lặp) do [15][16] 4. for i=1 to SCT do  Dữ liệu luồng công việc được lấy từ các bộ dữ liệu 5. Tính vector xi theo công thức (5) 6. end for thử nghiệm được xây dựng theo độ trù mật khác nhau 7. for i=1 to SCT do và các luồng công việc từ các ứng dụng thực tế như 8. Cập nhật pbesti ứng dụng Montage [17]. Thông tin chi tiết về luồng 9. end for công việc Montage được trình bày qua hình 4 và bảng 10. Cập nhật gbest dữ liệu 2 14. for i=1 to SCT do 15. Cập nhật vik theo công thức (1) 1 1 1 1 16. Tính xi theo (2) 17. end for 18. t++ ; 19. if (sau K thế hệ mà độ lệch giữa các 2 2 2 2 2 2 gbest không vượt quá ) then 20. gbest  LocalSearch(gbest); 21 end if 3 Data Aggregation 22. end while 23. return gbest 4 Data Partitioning Thuật toán hoạt động theo phương pháp PSO theo đó tại mỗi bước các cá thể cập nhật vị trí của mình hướng tới vị trí tốt nhất của cả quần thể (gbest) đồng thời có dựa trên kinh 5 5 5 5 nghiệm các cá thể lân cận (lbesti). Nếu sau K thế hệ liên tiếp mà cả quần thể không cải thiện được một cách đáng kể giá trị gbest (mức chênh không vượt quá ) thì chứng tỏ quần thể 6 Data Aggregation đang hội tụ tại một cực trị địa phương. Khi đó thủ tục LocalSearch được gọi tìm ra cá thể gbest mới và cá thể này sẽ di cư cả quần thể tới một vùng không gian mới, tại đó quá 7 Pipeline trình tìm kiếm được tái khởi động. Điều kiện lặp ở đây là mức chênh của giá trị gbest so với K vòng lặp trước đó lớn hơn độ lệch  ( ấn định từ trước), 1 mProjectPP 8 3 mConcatFit nghĩa là thuật toán LPSO sẽ dừng nếu như sau K lần di cư (thông qua thủ tục LocalSearch) mà giá trị gbest tìm được vẫn không cải thiện được một cách đáng kể (mức chênh không 2 mDiffFit 9 4 mBgModel vượt quá ). Trong trường hợp thuật toán hội tụ nhanh nhất, nghĩa là 5 mBackground 6 mImgTbl sau K lần thực hiện LocalSearch thì chương trình hội tụ tới cực trị, điều kiện dừng lặp được thỏa mãn nên chương trình kết thúc sau K2 thế hệ. Ngược lại, trong trường hợp tồi nhất, 7 mAdd 8 mShrink 9 mJPEG chương trình luôn tìm được lời giải tốt hơn sau mỗi lần di cư (thông qua thủ tục LocalSearch) thì các vùng tìm kiếm sẽ lần Hình. 4. Luồng công việc Montage với 20 tác vụ 197 197
HộiHội ThảoThảo Quốc Quốc Gia Gia 2015vềvềĐiện 2015 ĐiệnTử, Tử,Truyền TruyềnThông Thông và và Công CôngNghệ NghệThông ThôngTinTin (ECIT 2015) (ECIT 2015) Bảng 2: Thông tin dữ liệu vào/ra của các tác vụ trong ứng dụng Montage i5 2.2 GHz, RAM 4GB, hệ điều hành Windows 7 Ultimate. Thực nghiệm được lặp lại 300 lần trên mỗi nhóm thực nghiệm. Name and number Execution Input data Output of Tasks time (s) (MB) Data 5.4. Kết quả thực nghiệm (MB) Hình 5,6,7,8 cho thấy sự chênh lệch về thời gian xử lý mProject (45) 13.59 4.03 7.94 (makespan) của lời giải tốt nhất mà thuật toán đề xuất LPSO mDiffFit (107) 10.59 15.88 0.54 và các thuật toán đối chứng (PSO, Random và Round Robin) mConcatFit (1) 13.60 0.03 0.02 tìm được khi chạy trên 4 nhóm dữ liệu thực nghiệm khác mBgModel (1) 10.88 0.03 0.00 nhau. mBackground (45) 10.74 7.95 7.94 Bảng 3: Kết quả thực nghiệm mImgtbl (1) 10.69 357.27 0.01 mAdd (1) 30.34 357.28 330.86 M N  LPSO PSO Random Round Robin 5 3 0.2 7.8 9.0 30.75 28.6 mShrink (1) 12.26 165.43 6.62 5 3 0.4 4.6 6.6 21.45 19.9 mJPEG (1) 10.96 6.62 0.32 5 3 0.6 7.1 7.6 14.1 12.6 Những dữ liệu đó được tổng hợp lại và chia thành bốn nhóm 10 3 0.3 13.4 15.9 41.5 40.7 dựa theo số lượng máy chủ N và số lượng tác vụ M bao gồm: 10 3 0.4 14.5 18.1 50.8 41.7  Nhóm 1: M=5, N=3 10 3 0.7 14.8 18.3 49.7 38.6  Nhóm 2: M=10, N=3 20 8 0.2 9.2 12.1 58.4 52.7  Nhóm 3: M=20, N=8 20 8 0.3 8.2 12.4 55.5 49.1 20 8 0.5 11.5 14.3 57.4 51.2  Nhóm 4: M=25, N=8 (luồng công việc Montage) 25 8 0.2 2.8 3.8 15.1 13.5 Mỗi nhóm lại bao gồm ba thực nghiệm khác nhau về tỷ lệ số cạnh trên số đỉnh của đồ thị luồng công việc, ký hiệu là  40 Makespan (s) | | 30 ( ) α = 0.2 20 Tham số  cho biết đồ thị G phân thành bao nhiêu cấp, mỗi α = 0.4 10 cấp có nhiều hay ít tác vụ, nói cách khác  phản ánh độ trù α = 0.6 mật của đồ thị G. Khi làm thực nghiệm với mỗi nhóm, số máy 0 chủ và số tác vụ được giữ cố định còn tỷ lệ  lần lượt thay đổi LPSO PSO Random Round như trong các hình 5,6,7. Robin 5.2. Tham số cấu hình hệ thống Hình. 5. Lời giải tìm được bởi các thuật toán trong trường hợp M=5, N=3 Các tham số cấu hình của đám mây được thiết lập trong miền giá trị như sau: 60  Tốc độ tính toán P của các máy chủ: từ 1 đến 250 (million 50 Makespan (s) instructions/s) 40  Khối lượng dữ liệu D giữa các tác vụ: từ 1 đến 10000 α= 0.3 30 (Mega bit) 20 α = 0.4  Băng thông giữa các máy chủ B: từ 10 đến 100 (Mega bit/s) 10 α = 0.7  Hệ số quán tính:  = 0.729 0  Hệ số gia tốc: c1 = c2 = 1.49445 LPSO PSO Random Round  Hằng số : K = 30 Robin  Số cá thể SCT: SCT=25  Độ lệch  : 0.21 Hình. 6. Lời giải tìm được bởi các thuật toán trong trường hợp M=10, N=3  : từ 0.2 tới 0.7 80 5.3. Quá trình tiến hành thực nghiệm Makespan (s) 60 Để kiểm chứng thuật toán đề xuất LPSO chúng tôi đã sử dụng công cụ mô phỏng Cloudsim [1] để tạo lập môi α = 0.2 40 trường đám mây kết hợp với dữ liệu luồng công việc của ứng α = 0.3 dụng Montage [17]. Các hàm của gói thư viện Jswarm [1] 20 được sử dụng để thực hiện các phương thức Tối ưu bày đàn. 0 α = 0.5 Đối tượng so sánh là thuật toán PSO [9], thuật toán Random LPSO PSO Random Round [12] và thuật toán Round Robin [13]. Robin Các chương trình mô phỏng được viết bằng ngôn ngữ Java và chạy trên máy tính cá nhân với bộ vi xử lý Intel Core Hình. 7. Lời giải tìm được bởi các thuật toán trong trường hợp M=20, N=8 198 198
HộiHội Thảo Quốc Thảo Gia Quốc 2015 Gia 2015vềvềĐiện ĐiệnTử, Tử,Truyền TruyềnThông và Công Thông và CôngNghệ NghệThông ThôngTinTin (ECIT (ECIT 2015) 2015) 16 TÀI LIỆU THAM KHẢO 14 [1]. Công cụ mô phỏng CloudSim http://www.cloudbus.org/cloudsim/ 12 [2]. J.D. Ullman, “NP-complete scheduling problems”, Journal of 10 Computer and System Sciences, Volume 10, Issue 3, 1975 8 [3]. S. Parsa, R. E. Maleki “RASA: A New Task Scheduling Algorithm in Grid Environment”, International Journal of Digital Content 6 α = 0.15 Technology and its Applications, Vol. 3, No. 4, 2009 4 [4]. J.M. Cope, N. Trebon, H.M. Tufo, P. Beckman, “Robust data 2 placement in urgent computing environments”, IEEE International 0 Symposium on Parallel & Distributed Processing, IPDPS 2009 [5]. A. Agarwal, S. Jain, “Efficient Optimal Algorithm of Task LPSO PSO Random Round Scheduling in Cloud Computing Environment”, International Journal Robin of Computer Trends and Technology (IJCTT), vol. 9, 2014 [6]. M.Wieczorek, “Marek Scheduling of Scientific Workflows in the Hình. 8. Lời giải tìm được bởi các thuật toán trong trường hợp M=25, N=8 ASKALON Grid Environment”, ACM SIGMOD Record Journal, Vol. 34, Issue 3, 2005. Các thông số ở bảng 3 cho thấy thuật toán được kiểm [7]. A. Salman, “Particle swarm optimization for task assignment chứng trên nhiều bộ dữ liệu khác nhau về qui mô của luồng Problem”, Microprocessors and Microsystems, 2002. công việc (số tác vụ M và số máy chủ N) và độ trù mật  của [8]. S. Pandey, A. Barker, K. K. Gupta, R. Buyya, “Minimizing đồ thị luồng công việc. Kết quả thực nghiệm cho thấy trong Execution costs when using globally distributed cloud services”, 24th hầu hết các trường hợp thuật toán đề xuất LPSO đều cho lời IEEE International Conference on Advanced Information giải tốt hơn các thuật toán PSO, Random và Round Robin. Networking and Applications, 2010. Riêng với nhóm thực nghiệm thứ nhất (số tác vụ bằng 5 và số [9]. J. Kennedy, RC. Eberhart, “Particle swarm optimization”, in Proc. máy chủ bằng 3) thì thuật toán LPSO cho lời giải gần xấp xỉ IEEE Int’l. Conference on Neural Networks, vol. IV, 1995. với lời giải tốt tuyệt đối tìm được bằng phương pháp duyệt vét [10]. T. Davidovic, M. Selmic, D. Teodorovic, D. Ramljak “Bee colony cạn: 7.8 giây so với 7.7 giây. optimization for scheduling independent tasks to identical processors”, Journal of Heuristics, 2012. VI. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN [11]. M. Mitzenmacher, E. Upfal, “Probability and Computing: Randomized Algorithms and Probabilistic Analysis”, Cambridge Bài báo này đã trình bày một giải thuật tìm kiếm theo University Press, 2005. phương pháp Tối ưu bày đàn để tìm lời giải gần đúng cho bài [12]. Don Fallis, “The Reliability of Randomized Algorithms”, British toán lập lịch thực thi luồng công việc trong môi trường điện Journal for the Philosophy of Science, 2000. toán đám mây. Những kết quả chính gồm có: [13]. https://www.ngoisaoso.net/Cloud-Server.html - Đề xuất một phương thức mới để cập nhật vị trí của cá thể [14]. http://vdo.vn/may-chu-vps-vdc bằng cách ánh xạ một giá trị thực tới máy chủ có tốc độ [15]. http://www.rackspace.com/cloud/servers tính toán và băng thông gần với giá trị đó nhất. [16]. http://aws.amazon.com/ec2/pricing/ [17]. http://montage.ipac.caltech.edu - Đề xuất công thức tính vector dịch chuyển của cá thể thứ i theo giá trị gbest và lbesti ABSTRACT - The key factor which rules the cloud’s - Đề xuất thủ tục LocalSearch để chương trình thoát ra khỏi performance is the workflow scheduling, one of the well- known problems have proven to be NP-complete. Many cực trị địa phương bằng cách chuyển các cá thể tới một algorithm in the literature have been targeting the workflow miền không gian tìm kiếm mới. scheduling problem, however, handful efficient solutions - Đề xuất thuật toán LPSO sử dụng phương thức cập nhật have been proposed. This paper proposes a metaheuristic vị trí cá thể và thủ tục LocalSearch để tìm kiếm lời giải algorithm called LPSO which based on the Particle Swarm Optimization method. Our experiments which arranged by cho bài toán lập lịch thực thi luồng công việc trong môi using the simulation tool CloudSim show that LPSO is trường đám mây. superior to the general algorithms called Random and Những kết quả thực nghiệm được tiến hành với nhiều bộ RoundRobin, moreover the deviation between the solution found by LPSO and the optimal solution is negligible. 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 Key words: workflow scheduling, particle swarm optimization, đối chứng là thuật toán PSO gốc, thuật toán Random và thuật cloud computing toán Round Robin. Về hướng công việc tiếp theo, ngoài hai yếu tố hiện nay là kinh nghiệm cá nhân (pbest) và kinh nghiệm từ cả quần thể (gbest) chúng tôi dự định đưa thêm vào yếu tố kinh nghiệm của các cá thể trong một lân cận xác định theo lược đồ Von Neuman hoặc Star để cập nhật vị trí mới cho mỗi cá thể nhằm đạt được lời giải có chất lượng tốt hơn. 199 199