Giải thuật tối thiểu hóa chi phí thực thi luồng công việc trong môi trường điện toán đám mây

Tóm tắt. Luồng công việc là một dãy có thứ tự các tác vụ cần thực thi để đạt được một mục đích, bài toán lập lịch luồng công việc là bài toán sắp xếp các tác vụ cho thực thi trên một số máy xác định sao cho hiệu quả là tốt nhất, đây chính là bài toán thường gặp và có tính quan trọng nhất trong môi trường điện toán đám mây. Bài toán lập lịch thực thi luồng công việc là bài toán NPComplete và thực nghiệm đã chỉ ra là không có lời giải tối ưu tuyệt đối. Bài báo này đề xuất một mô hình bài toán luồng công việc và một giải thuật heuristic cải tiến dựa trên thuật toán PSO để lập lịch thực thi luồng công việc trên môi trường điện toán đám mây đảm bảo chi phí nhỏ nhất.

pdf9 trang | Chia sẻ: thanhle95 | Lượt xem: 507 | Lượt tải: 1download
Bạn đang xem nội dung tài liệu Giải thuật tối thiểu hóa chi phí thực thi luồng công việc trong môi trường điện toán đám mây, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
JOURNAL OF SCIENCE OF HNUE DOI: 10.18173/2354-1059.2015-0007 Natural Sci. 2015, Vol. 60, No. 4, pp. 47-55 This paper is available online at Ngày nhận bài: 23/1/2015. Ngày nhận đăng: 22/4/2015. Tác giả liên lạc: Phan Thanh Toàn, địa chỉ e-mail: pttoan@hnue.edu.vn 47 GIẢI THUẬT TỐI THIỂU HÓA CHI PHÍ THỰC THI LUỒNG CÔNG VIỆ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ường1 và Đỗ Như Long1 1 Khoa 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 Tóm tắt. Luồng công việc là một dãy có thứ tự các tác vụ cần thực thi để đạt được một mục đích, bài toán lập lịch luồng công việc là bài toán sắp xếp các tác vụ cho thực thi trên một số máy xác định sao cho hiệu quả là tốt nhất, đây chính là bài toán thường gặp và có tính quan trọng nhất trong môi trường điện toán đám mây. Bài toán lập lịch thực thi luồng công việc là bài toán NP- Complete và thực nghiệm đã chỉ ra là không có lời giải tối ưu tuyệt đối. Bài báo này đề xuất một mô hình bài toán luồng công việc và một giải thuật heuristic cải tiến dựa trên thuật toán PSO để lập lịch thực thi luồng công việc trên môi trường điện toán đám mây đảm bảo chi phí nhỏ nhất. Từ khóa: Lập lịch luồng công việc, ứng dụng luồng công việc, điện toán đám mây. 1. Mở đầu Điện toán đám mây là một công nghệ được phát triển dựa trên nền tảng của các công nghệ trước đây như điện toán lưới (grid computing), tính toán phân tán và song song. Trong mô hình điện toán đám mây các tác vụ (task) sẽ được phân phối và thực hiện tại các trung tâm điện toán đám mây. Lập lịch thực thi luồng công việc là một vấn đề quan trọng nhất trong môi trường điện toán đám mây và đã có nhiều công trình nghiên cứu nhằm tìm ra các giải pháp lập lịch tối ưu. Tuy nhiên thực nghiệm đã chỉ ra bài toán lập lịch thực thi luồng công việc là bài toán thuộc lớp NP-Complete [1] do vậy bài toán lập lịch luồng công việc thường được thực hiện bằng các giải thuật heuristic trong đó lớp các giải thuật tiến hóa là một hướng tiếp cận được sử dụng khá rộng rãi trong thời gian gần đây. 2. Nội dung nghiên cứu 2.1. Bài toán tối thiểu hóa chi phí * Phát biểu bài toán Xét bài toán cần sắp xếp lịch biểu cho một luồng công việc gồm M tác vụ (task - từ đây viết tắt là task), trong một môi trường điện toán đám mây với các yêu cầu như sau: + Luồng công việc gồm có M tác vụ; + Các tác vụ có quan hệ thứ tự trước - sau; + Mỗi tác vụ cần một khối lượng dữ liệu vào và sẽ xuất ra một lượng dữ liệu xác định; + Luồng công việc chỉ có duy nhất một Task gốc (task vào) và một task ra (output); + Môi trường thực thi luồng công việc là môi trường điện toán đám mây với N máy chủ tính toán và K máy chủ lưu trữ; + Mỗi tác vụ (task) có thể được thực thi trên một máy chủ bất kì và chỉ được thực thi trên một máy chủ duy nhất; Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường và Đỗ Như Long 48 + Mỗi máy chủ thực thi và máy chủ lưu trữ dữ liệu đều có một đơn giá xác định do nhà cung cấp dịch vụ cung cấp; Mô hình toán học bài toán tối thiểu chi phí thực thi luồng công việc trong môi trường điện toán đám mây 1-Tập các máy chủ S = {S1, S2,.,SN}. 2-Luồng công việc được biểu diễn bởi một đồ thị G = (V, E), với V là tập các đỉnh của đồ thị và là tập các task, E là tập cạnh của đồ thị thể hiện mối quan hệ giữa các task. 3-Tập các task : V = {T1, T2,,TM}. 4-Nếu e = (Ti, Tj)  E, có nghĩa là Task Ti thực hiện trước và sẽ chuyển cho Task Tj một khối lượng dữ liệu xác định. 5-Khối lượng tính toán của một Task Ti kí hiệu là Wi (Workload) đo bằng flop (floating point operations). 6-Năng lực xử lí của một máy chủ được (Processing capacity) được biểu diễn bởi một hàm số: P: S  R+ Si  P(Si) 7-Đơn giá cước tính toán, nghĩa là chi phí thực thi một đơn vị flop trên máy chủ (Excution cost) được tính bằng dolar/flop và là một hàm số: E: S  R+ Si  E(Si) 8-Mỗi cặp máy chủ Si, Sj ( Nji  ,1 ) đều có một kênh truyền kết nối chúng, băng thông của kênh truyền kí hiệu là B (Bandwidth), và là một hàm số: B: SxS  R+ (Si, Sj)  B(Si, Sj) Giả sử hàm B thỏa mãn điều kiện: + B(Si, Si) =  (băng thông tại chỗ bằng vô cùng, tức là chi phí truyền bằng 0) + B(Si, Sk) + B(Sk, Sj) ≤ B(Si, Sj) (bất đẳng thức tam giác) + B(Si, Sj ) = B(Sj, Si) (tính chất đối xứng). Tập giá trị của hàm băng thông B( ) giữa các máy chủ được cung cấp bởi nhà cung cấp dịch vụ và được biểu diễn ở Bảng 1. Bảng 1. Bảng biểu diễn băng thông giữa các server 1 2 ... N B(1, 1) =  B(1, 2) ... B(1, N) B(2, 1) B(2, 2) =  ... ... ... ... ... ... B(N, 1) B(N, 2) ... B(N, N) =  9-Khối lượng dữ liệu giữa Task Ti và Task Tk được kí hiệu là Dik là một hằng số cho trước và được biểu diễn ở Bảng 2. Bảng 2. Bảng biểu diễn lượng dữ liệu giữa các tác vụ 1 2 ... M D11 D12 ... D1N D21 D22=  ... ... ... ... ... ... DN1 DN2 ... DNN =  10-Đơn giá cước truyền thông giữa 2 máy chủ (Communication Cost), đơn vị là dolar/bit được kí hiệu là C và là một hàm số: Giải thuật tối thiểu hóa chi phí thực thi luồng công việc trong môi trường điện toán đám mây 49 C: SxS  R+ (Si, Sk)  C(Si, Sk) Giả sử chi phí truyền thỏa mãn các điều kiện : C(Si, Sk) = C(Sk, Si) 11- Mỗi phương án xếp lịch thực thi luồng công việc là một ánh xạ f f: T  S Ti  f(Ti) Với f(Ti) là máy chủ chịu trách nhiệm thực thi tác vụ (Task) Ti, hay nói cách khác Task Ti được đặt thực thi trên máy chủ f(Ti) Từ đó suy ra: - Thời gian tính toán của task Ti là:   i i TfP W (I = 1,2, ... M) - Chi phí tính toán của task Ti là: Wi E(f(Ti)) - Thời gian truyền dữ liệu giữa task Ti và task con Tk là:     ki ik TfTfB D , - Chi phí truyền thông giữa task Ti và task con Tk là: DikC(f(Ti),f(Tk)) 12- Chi phí thực thi một Task Ti trên một máy chủ f(Ti) là chi phí tính toán của Task Ti và tổng chi phí truyền thông giữa các Task Tj với Ti trong đó các Task Tj là các Task cha của Task Ti. Và chi phí thực thi luồng công việc là tổng chi phí để thực hiện tất cả các Task trong luồng. Hàm mục tiêu là:           MinTfTfCDTfEW M i M k kiik M i ii     1 11 , (1) 2.2. Lập lịch thực thi luồng công việc dựa trên chiến lược tối ưu bày đàn 2.2.1. Chiến lược tối ưu bày đàn PSO (Particle Swarm Optimization) PSO là thuật toán tiến hóa thông minh được đề xuất bởi Russell C. Eberhart [2] and James Kennedy [3] in 1995, PSO là thuật toán tiến hóa quần thể dựa theo hoạt động tìm kiếm thức ăn của các loài động vật như đàn kiến, đàn chim. Khởi đầu thuật toán PSO sẽ tạo ra một quần thể các cá thể, mỗi cá thể thực chất là một phương án của bài toán, sau đó các cá thể sẽ di chuyển trong không gian lời giải để tìm kiếm lời giải tối ưu. Mỗi cá thể được biểu diễn bởi một vector n - chiều (n là số chiều của không gian tìm kiếm) tương ứng với một điểm trong không gian n - chiều, mỗi cá thể có một vector chuyển động được sử dụng để xác định hướng dịch chuyển của cá thể trong không gian tìm kiếm, trong quá trình tìm kiếm mỗi các thể sẽ lưu lại các vị trí tốt nhất của cá thể (được đánh giá theo hàm mục tiêu đặt ra), đồng thời các cá thể sẽ sử dụng một giá trị gbest là giá trị tốt nhất (xác định dựa vào hàm mục tiêu đặt ra) của các cá thể lân cận trong quá trình tìm kiếm để xác định hướng chuyển động của mình.  ix : Vị trí hiện tại của cá thể thứ pi  iv : Vector chuyển động của cá thể pi   ii ppbest : Vector lưu trữ vị trí tốt nhất của cá thể pi   gpgbest : Vector lưu vị trí tốt nhất của quần thể Sau mỗi bước lặp các cá thể sẽ cập nhật lại vector dịch chuyển và vị trí của cá thể theo công thức sau: )()( 2211   igiiii xprandxprandwvv  (2) Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường và Đỗ Như Long 50   iii vxx (3) Giả sử hàm mục tiêu là f, thuật toán PSO như sau: Algorithm 1: Particle Swarm algorithm Procedure PSO_Algorithm 1. Khởi tạo quần thể gồm n cá thể P= {p1, p2,,pn} với vị trí xi và véc tơ chuyển động vi của mỗi cá thể một cách ngẫu nhiên. 2. Repeat 3. Tính f(pi) i=1,2,..,n 4. If bước lặp =0 Then 5. Gán vị trí tốt nhất của mỗi cá thể pi là xi và pbesti =f(pi) 6. Tính gbest = f(pj), với f(pj)= min{f(pi) ; i=1,2,..,n} và g=j 7. End if 8. Foreach pi In P 9. If(f(pi)< pbest) Then 10. pbesti = pi 11. xi = pi //Cập nhật vị trí tốt nhất của cá thể pi 12. End If 13. End for 14. Foreach pi In P 15. If (f(Pi) < gbest) Then 16. g = i 17. gbest = f(pi) //Cập nhật vị trí tốt nhất của quần thể 18 End if 19. End for 20. Foreach pi In P 21. Cập nhật véc tơ chuyển động của cá thể theo công thức (2) 22. Cập nhật vị trí mới của mỗi cá thể theo công thức (3) 23. End For 24. Until thỏa mãn điều kiện lặp 25. end procedure trong đó : 21, là các hằng số biểu diễn sự ảnh hưởng của cá thể và quần thể tới hướng dịch chuyển của cá thể trong không gian tìm kiếm. rand1, rand2 là các hằng số ngẫu nhiên và w là trọng số quán tính dịch chuyên của các cá thể. 2.2.2. Thuật toán đề xuất Dựa theo phương pháp tối ưu bày đàn PSO và 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 đã giới thiệu ở trên, chúng tôi đề xuất một giải thuật, với tên là MPSO-WS (Modified PSO for Workflow Scheduling) như sau: Mã hóa cá thể: Mỗi phương án lập lịch là một cách sắp xếp các tác vụ vào thực hiện trên một máy cụ thể, theo mô hình đã đề xuất mỗi máy có thể thực hiện nhiều tác vụ, mỗi tác vụ chỉ được thực hiện trên một máy duy nhất, do vậy ta có thể biểu diễn một phương án xếp lịch như một véc tơ n chiều như sau (n là số tác vụ): T1 T2 T3 T4 T5 PC1 PC2 PC1 PC3 PC2 Dựa vào cấu trúc bảng băm trong ngôn ngữ lập trình java, cấu trúc cá thể trong giải thuật PSO và cách xếp lịch như trên mỗi cá thể trong quần thể được biểu diễn bởi 2 thành phần là véc tơ vị trí Giải thuật tối thiểu hóa chi phí thực thi luồng công việc trong môi trường điện toán đám mây 51 (positon) và véc tơ chuyển động (velocity). Trong đó véc tơ vị trí có số chiều bằng số tác vụ (task) trong luồng công việc và được mô tả như một cấu trúc dữ liệu hàm băm. Vector chuyển động cũng được biểu diễn như một cấu trúc dữ liệu bảng băm. Hashtable position Hashtable velocity Mã hóa tác vụ (task): Mỗi task sẽ được xác định bởi 3 đại lượng là số lệnh cần thực hiện (đơn vị là MI : milion instruction), kích thước dữ liệu xuất ra của task và danh sách các task phụ thuộc. Danh sách này được biểu diễn như một cấu trúc danh sách ArrayList. Biểu diễn các dữ liệu: Dữ liệu ở đây là chi chí thực thi các task trên các máy chủ, chi phí truyền thông giữa các máy chủ và khối lượng dữ liệu vào/ra giữa các task. - Chi phí thực thi các task trên các máy chủ được biểu diễn như một ma trận và chúng tôi sử dụng cấu trúc hàm băm để lưu trữ chi phí thực thi một task trên một máy chủ như sau: Hashtable> TH_matrix; Bảng 3. Chi phí thực thi của mỗi Ti trên các PCj TP[5x3] PC1 PC2 PC3 T1 1.23 1.12 1.15 T2 1.17 1.17 1.28 T3 1.13 1.11 1.11 T4 1.26 1.12 1.14 T5 1.19 1.14 1.22 - Chi phí truyền thông giữa các PC được biểu diễn như một ma trận và cũng được lưu trữ bằng một cấu trúc hàm băm như sau: Hashtable> HH_matrix; Bảng 4. Chi phí truyền thông giữa các PCj PP[3x3] PC1 PC2 PC3 PC1 0 0.17 0.21 PC2 0.17 0 0.22 PC3 0.21 0.22 0 trong đó: PP[i,j] = chi phí truyền thông giữa hai PCi và PCj (giá trị theo đơn vị $/MB/giây). - Dữ liệu vào/ra giữa các task trong luồng công việc được biểu diễn bởi một ma trận và ta sử dụng cấu trúc dữ liệu hàm băm như sau để lưu trữ: Hashtable> edge_weight Bảng 5. Kích thước input/output của task i DST2,T3,T4 [2x2] total data DST5 [2x2] total data Input 10 Input 30 Output 10 Output 60 trong đó: Input = dữ liều vào, output = dữ liệu ra của các tác vụ (đơn vị MB) Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường và Đỗ Như Long 52 Khởi tạo quần thể một cách ngẫu nhiên Tính giá trị hàm fitness cho các cá thể Cập nhật véc tơ dịch chuyển và vị trí mới cho các cá thể Kiểm tra điều kiện dừng Đúng Sai BEGIN END Thuật toán đề xuất MPSO-WS procedure MPSO-WS 1. Tính ma trận chi phí thực thi các task trên các host 2. Tính ma trận chi phí truyền thông giữa các host 3. Tính ma trận khối lượng dữ liệu vào/ra giữa các task 4. Khởi tạo danh sách các task sẵn sàng là danh sách tất cả các task 5. Khởi tạo danh sách các task chưa lập lich là danh sách tất cả các task 6. repeat 7. foreach ti in readyTasks do 8. Gán ti cho thực hiện bởi PCj theo thuật toán PSO dựa vào công thức (1) và (2) 9. end for 10. Chờ xử lí công việc (phụ thuộc dữ liệu đầu vào và đầu ra giữa task cha-con). 11. Cập nhật lại các task ở trạng thái “ready” 12. Cập nhật lại chi phí giao tiếp giữa các tài nguyên theo trạng thái mạng hiện tại. 13. Tính toán PSO({ it }). 14. Until không có task chưa được lập lịch. end procedure Các chiến lược PSO thường sử dụng hệ số quán tính w là hằng số dẫn đến việc các cá thể dịch chuyển theo một quán tính cố định, hậu quả là trong quá trình tìm kiếm các cá thể có thể bị mắc kẹt tại các vị trí cực trị địa phương mà không thể dịch chuyển tiếp để tìm tới giá trị cực trị toàn cục. Để khắc phục các vấn đề đó chúng tôi đề xuất sử dụng trọng số quán tính được thay đổi theo các lần lặp và sử Giải thuật tối thiểu hóa chi phí thực thi luồng công việc trong môi trường điện toán đám mây 53 dụng thêm vị trí tồi nhất của quần thể và cá thể để cập nhật vector vị trí của các cá thể. Công thức cập nhật vector vị trí cho các cá thể như sau: )()()()( 444333222111   iwiwiigiiii xpkrcxpkrcxpkrcxpkrcwvv (4)   iii vxx (5) p wwjww endstartstart )(   (6) trong đó:  ix : Vị trí hiện tại của cá thể thứ i (pi);  iv : Vector chuyển động của cá thể pi;   ii ppbest : Vector lưu trữ vị trí tốt nhất của cá thể pi ;   gpgbest : Véc tơ lưu vị trí tốt nhất của quần thể;   wii ppworst : véc tơ lưu trữ vị trí tồi nhất của các thể pi ;   wi pgworst : lưu trữ vị trí tồi nhất của quần thể. 2.3. Kết quả thực nghiệm Để thực hiện mô phỏng việc lập lịch workflow trong môi trường đám mây, chúng tôi cài đặt giải thuật MPSO-WS bằng ngôn ngữ Java với sự trợ giúp của gói thư viện JSwarm [4] và công cụ mô phỏng CloudSim [1, 5, 6]. Bảng 7 cho thấy kết quả thực nghiệm được so sánh giữa giải thuật MPSO- WS với 3 giải thuật: PSO_Heuristic, Random [7, 8], RoundRobin [9] với dữ liệu tính toán dưới đây. Bảng 6. Ma trận dữ liệu TP, PP, DS cho bộ dữ liệu Test TP[5x3] PC1 PC2 PC3 T1 0,1*25 0,2*25 0,3*25 T2 0,1*25 0,2*25 0,3*25 T3 0,1*25 0,2*25 0,3*25 T4 0,1*25 0,2*25 0,3*25 T5 0,1*25 0,2*25 0,3*25 PP[3x3] PC1 PC2 0,3*25 PC1 0 0,1 0,1 PC2 0,1 0 0,1 PC3 0,1 0,1 0 DST2,T3,T4 [2x2] Data Size (MB) DST5 [2x2]= DataSize (MB) Input 10 Input 30 Output 10 Output 60 trong đó: số cá thể = 25; số thế hệ = 30; số lần lặp = 300; trọng số quán tính w theo công thức (6) và hệ số gia tốc: C1 = 1,5, C2 = 0,5, C3 =1,5, C4 = 0,5, Wstart = 0,9, Wend = 0,4. Nhận xét: giải thuật lập lịch MPSO-WS cho kết quả khác nhau ở các lần chạy phụ thuộc vào việc thiết lập các hệ số quán tính w, hệ số gia tốc C1, C2, trong bài báo này chúng tôi không sử dụng hệ số Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường và Đỗ Như Long 54 quán tính là một hằng số mà sử dụng hệ số quán tính thay đổi theo các bước lặp xác định như ở công thức (6) để tránh hiện tượng các cá thể di chuyển theo hướng cố định và sẽ bị mắc kẹt ở các điểm cực trị địa phương, hệ số gia tốc C1 = 1,5 và C2 = 0,5, C3 = 1,5, C4 = 0,5, kết quả được thử nghiệm với số cá thể là 25, số lần lặp là 300 lần, như bảng kết quả đã chỉ ra chi phí của luồng công việc tính toán được bởi thuật toán MPSO-WS có khác nhau ở các lần chạy nhưng đều cho kết quả tốt hơn so với thuật toán Random và Round Robin. Thuật MPSO-WS và thuật toán PSO_ Heuristic đều cho kết quả tốt nhất như nhau tuy nhiên thuật toán MPSO-WS cho kết quả tối ưu ổn định hơn trong các lần chạy. Đặc biệt khi số công việc trong luồng công việc và số máy chủ tăng lên; số tác vụ là 25, số máy chủ là 12 thì chi phí luồng công việc tính được bằng giải thuật MPSO-WS sẽ cho kết quả nhỏ nhất và tránh được hiện tượng tối ưu cục bộ. Bảng 7. So sách kết quả các thuật toán MPSO-WS, PSO, Random, Round Robin sau 30 lần chạy Lần lặp MPSO-WS PSO gốc Random Round Robin 1 12.500 12.500 45500 40000 2 12.500 12.500 52500 40000 3 12.500 25.000 35500 40000 4 16.000 12.500 58000 40000 5 12.500 12.500 36500 40000 6 12.500 12.500 46500 40000 7 12.500 12.500 42000 40000 8 16.500 18.500 64500 40000 9 12.500 12.500 56500 40000 10 12.500 12.500 25000 40000 11 12.500 12.500 53000 40000 12 16.500 12.500 27000 40000 13 12.500 18.500 35500 40000 14 12.500 12.500 42500 40000 15 12.500 12.500 36500 40000 16 12.500 12.500 27000 40000 17 16.500 12.500 35500 40000 18 12.500 18.500 42500 40000 19 12.500 25.000 36500 40000 20 12.500 12.500 46500 40000 21 12.500 12.500 42000 40000 22 12.500 12.500 64500 40000 23 16.000 12.500 56500 40000 24 12.500 12.500 25000 40000 25 16.000 18.500 45500 40000 26 12.500 25.000 52500 40000 27 12.500 12.500 35500 40000 28 12.500 12.500 58000 40000 29 12.500 12.500 36500 40000 30 12.500 18.500 46500 40000 Giải thuật tối thiểu hóa chi phí thực thi luồng công việc trong môi trường điện toán đám mây 55 3. Kết luận Bài báo đã xây dựng một mô hình toán học cho bài toán luồng công việc trong môi trường điện toán đám mây nhằm cực tiểu hóa chi phí thực thi luồng công việc, đây là yêu cầu hết sức cần thiết trong môi trường điện toán đám mây vì điện toán đám mây là một môi trường dịch vụ tích hợp được cung cấp bởi các nhà cung cấp dịch vụ và người sử dụng phải trả chi phí cho các dịch vụ mà họ sử dụng. Đồng thời chúng tối đã đề xuất một giải thuật lập lịch heuristic dựa trên chiến lược tối ưu bày đàn và cài đặt thử nghiệm trên môi trường mô phỏng cloudSim, kết quả chỉ ra việc tính toán chi phí tốt hơn các thuật toán đã có như Random hay Round Robin. Thuật toán đã cho kết quả chấp nhận được tuy nhiên bản chất của bài toán lập lịch luồng công việc là bài toán tối ưu tổ hợp với tập các phương án của bài toán là rời rạc, đồng thời chi phí thực thi luồng công việc phụ thuộc nhiều vào tốc độ xử lí và băng thông kết nối giữa các server chính vì vậy để thuật toán làm việc tốt hơn chúng tôi sẽ cải thiện thuật toán theo hướng giải thuật PSO rời rạc với các trọng số về tốc độ xử lí và băng thông giữa các server. TÀI LIỆU THAM KHẢO [1] Z. Yingfeng, L. Yulin, 2003. Grid Computing Resource Management Scheduler Based on Evolution Algorithm. Computer Engineering Conference, 29(15):1102175. [2] Suraj Pandey, Linlin Wu, Siddeswara Guru, and Rajkumar Buyya, 2010. A Particle Swarm Optimization (PSO)-based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments. AINA 2010, Australia. [3] Suraj Pandey, Rajkumar Buyya, 2009. Scheduling and Management Techniques for Data- Intensive Application Workflows. IGI Global, USA. [4] Silberschatz Abraham, Galvin Peter B., Gagne Greg, 2010. Process Scheduling. Operating System Concepts (8th ed.). John_Wiley_&_Sons (Asia). pp. 194. ISBN 978-0-470-23399-3. [5] Rodrigo N. Calheiros, Rajiv Ranjan, Anton Beloglazov, Cesar A. F. De Rose, and Rajkumar Buyya, 2011. CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms, Volume 41, Number 1, Pages: 23-50, Wiley Press, USA. [6] Thư viện JSwarm [7] Rajkumar Buyya, Rajiv Ranjan and Rodrigo N. Calheiros, 2009. Modeling and Simulation of Scalable Cloud Computing Environments and the CloudSim Toolkit: Challenges and Opportunities. HPCS IEEE Press, New York, USA. [8] Michael Mi
Tài liệu liên quan