zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

Bài toán lập lịch phân bổ tài nguyên trong môi trường điện toán đám mây

Chia sẻ: ViMoscow2711 ViMoscow2711 | Ngày: | Loại File: PDF | Số trang:9

Báo xấu

42
lượt xem 4
download

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

Bài viết này trình bày một giải thuật lập lịch động (HPSO*) dựa trên phương pháp PSO để đưa ra một phương án lập lịch ứng dụng có tính đến chi phí tính toán và chi phí truyền tải dữ liệu. Bài viết cũng trình bày những kết quả thử nghiệm các giải thuật trên các bộ dữ liệu để thấy được hiệu quả của giải thuật HPSO*.

Chủ đề:

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

Lưu

Nội dung Text: Bài toán lập lịch phân bổ tài nguyên trong môi trường điện toán đám mây

JOURNAL OF SCIENCE OF HNUE DOI: 10.18173/2354-1059.2015-0009 Natural Sci. 2015, Vol. 60, No. 4, pp. 62-70 This paper is available online at http://stdb.hnue.edu.vn BÀI TOÁN LẬP LỊCH PHÂN BỔ TÀI NGUYÊN TRONG MÔI TRƯỜNG ĐIỆN TOÁN ĐÁM MÂY Nguyễn Thị Thùy Liên và Đỗ Như Long Khoa Công nghệ thông tin, Trường Đại học Sư phạm Hà Nội Tóm tắt. Tài nguyên trong môi trường điện toán đám mây được lưu trữ tại nhiều vị trí khác nhau. Điện toán đám mây cung cấp hạ tầng cho các ứng dụng dưới dạng các nguồn tài nguyên ảo hóa một cách tự động. Yêu cầu thiết yếu khi lập lịch trên môi trường điện toán đám mây là đưa ra một phương án ánh xạ các tác vụ tới những tài nguyên tương ứng với những ràng buộc được đưa ra. Bài báo này trình bày một giải thuật lập lịch động (HPSO*) dựa trên phương pháp PSO để đưa ra một phương án lập lịch ứng dụng có tính đến chi phí tính toán và chi phí truyền tải dữ liệu. Bài báo cũng trình bày những kết quả thử nghiệm các giải thuật trên các bộ dữ liệu để thấy được hiệu quả của giải thuật HPSO*. Từ khóa: Điện toán đám mây, lập lịch công việc, giải thuật lập lịch. 1. Mở đầu Điện toán đám mây (cloud computing) là mô hình mới cho lĩnh vực tính toán phân tán. Nó cung cấp hạ tầng nền tảng và các ứng dụng dưới dạng các dịch vụ được tạo sẵn và phục vụ khách hàng theo phương thức trả phí cho những gì họ sử dụng. Ngoài ra điện toán đám mây còn cung cấp linh hoạt tài nguyên tính toán dựa theo yêu cầu, lựa chọn vị trí lưu trữ dữ liệu trên toàn cầu. Để đạt được hiệu quả về tính toán và chi phí bộ lập lịch của đám mây phải có các chiến lược thay đổi theo các hàm mục tiêu khác nhau: tối thiểu tổng thời gian thực thi, tối thiểu tổng chi phí thực thi, cân bằng tải trên các tài nguyên… Bài báo này tập trung vào chiến lược giảm thiểu hóa tổng chi phí thực thi của ứng dụng trên các tài nguyên bằng cách sử dụng thuật toán lập lịch động dựa trên giải thuật tối ưu bầy đàn-PSO. Phần thực nghiệm được tiến hành dựa trên số liệu về dịch vụ đám mây của Amazon và GoGrid. Lập lịch (scheduling) là vấn đề phát sinh trong rất nhiều lĩnh vực. Vấn đề lập lịch có thể hiểu là xác định một tập hợp các hoạt động để chia sẻ tài nguyên có giới hạn và cần được xử lí với nhiều hạn chế (chủ yếu là thời gian và nguồn lực). Theo các định nghĩa của Fox (1994) [1] thì lập lịch là việc “phân chia các nguồn tài nguyên cho mỗi hoạt động, để các tác vụ tuân theo những hạn chế về thời gian và giới hạn của tập tài nguyên được chia sẻ”. Thực tế thì có thể không tồn tại một giải pháp lịch biểu đáp ứng tất cả các hạn chế về thời gian và nguồn lực, nhất là khi việc sử dụng tài nguyên lại gắn liền với nhiều yêu cầu ràng buộc khác nhau. Bài toán lập lịch và phân bổ tài nguyên trong môi trường điện toán đám mây (SRAP) nhằm mục đích tìm ra một phương án tối ưu giảm thiểu tổng chi phí thực hiện các tác vụ (Task) trên các nguồn tài nguyên bao gồm chi phí tính toán trên tài nguyên, chi phí truyền thông và hoàn thành trong thời gian do người dùng chỉ định. Một luồng công việc có thể được biểu diễn bởi đồ thị DAG, cho G = (V, E), với V = {t1, t2, ..., tn} là tập các tác vụ và E là tập các phụ thuộc dữ liệu giữa các tác vụ này, fj,k = (Tj, T k)  E là tập tin đầu ra của Tj và là tập tin đầu vào của Tk. Một tập của các máy chủ lưu trữ S = {1, ...,i}, một tập các máy tính tính toán H = {1, ..., j} và một tập số các tác vụ T = { 1, ..., k} [2]. Với những giả thiết của bài toán: Ngày nhận bài: 31/3/2015. Ngày nhận đăng: 20/5/2015. Tác giả liên lạc: Nguyễn Thị Thùy Liên, địa chỉ e-mail: lienntt@hnue.edu.vn 62
Bài toán lập lịch phân bổ tài nguyên trong môi trường điện toán đám mây Thời gian tính toán của tác vụ Tk trên nguồn tài nguyên tính toán Hj được giả sử là đã biết. Chi phí tính toán của một tác vụ trên một H tỉ lệ nghịch với thời gian tính toán. Chi phí truy cập dữ liệu di, j từ một nguồn Hi đến Hj được giả sử là đã biết (trong thực tế chi phí truy cập được ấn định bởi nhà cung cấp dịch vụ). Chi phí truyền thông được tính theo kích thước khối dữ liệu truyền giữa các nơi lưu trữ và không có phụ thuộc vào thời gian. Giả định rằng các chi phí này là không âm, đối xứng và đáp ứng các bất đẳng thức tam giác: di, j = dj, i với mọi i, j  N, và di,j+dj, k ≥ di, k với mọi i, j, k  N. Mục tiêu của bài toán là: “Tìm phương án lập lịch M sao cho chi phí thực thi là tối thiểu” Gọi Cexe(M)j là tổng chi phí của tất cả các nhiệm vụ được giao cho một nguồn tài nguyên tính toán Hj theo phương án M [2]. C exe ( M ) j  k kj M (k )  j  với kj là trọng số của các nút (là chi phí thực hiện của một nhiệm vụ k trên tài nguyên tính toán Hj).Ký hiệu Ctx(M)j là tổng chi phí truy cập (bao gồm cả chi phí truyền thông) giữa các tác vụ được giao cho một Hj thực thi trong phương án M. M ( k1)  j và M ( k 2)  j C tx ( M ) j   d k 1 T k 2  T e M ( k 1 ), M ( k 2 ) k 1 , k 2 trong đó: ek1,k2 là kích thước tập tin đầu ra giữa hai nhiệm vụ k1 và k2  k; M (k1) là nhiệm vụ k1 được thực thi trên Hj theo phương án M; M (k2) là nhiệm vụ k2 không được thực thi trên Hj theo phương án M; dM(k1),M(k2) là chi phí truyền thông trung bình của các đơn vị dữ liệu giữa hai Host. Các chi phí truyền thông được áp dụng chỉ khi hai tác vụ có tập tin phụ thuộc giữa chúng, tức là ek1,k2 > 0. Đối với các tác vụ thực hiện trên cùng một tài nguyên thì chi phí truyền thông là 0. Gọi Ctotal (M)j là tổng chi phí của Hj bao gồm tổng chi phí thực thi và chi phí truy cập. C total ( M ) j  C exe ( M ) j  C tx ( M ) j Kí hiệu Cost(M) là tổng tất cả các chi phí của các H trong phương án lập lịch Cost(M )  max(Costtotal (M ) j ) Mục tiêu của bài toán là tìm ra phương án M có chi phí thấp nhất Min (Cost (M))  M 2. Nội dung nghiên cứu 2.1. Giải thuật Particle Swarm Optimization (PSO) Tối ưu bầy đàn (Partical Swarm Optimization – PSO) là một kĩ thuật tối ưu dựa theo mô hình hành vi xã hội ở động vật hoặc côn trùng, PSO được giới thiệu vào năm 1995 tại một hội nghị của IEEE bởi James Kenedy và kỹ sư Russell C.Eberhart [3]. Giải thuật tối ưu hóa bầy đàn (PSO) lấy ý tưởng từ hành vi xã hội của bầy đàn trong tự nhiên như đàn chim tìm thức ăn hay đàn cá tự bảo vệ mình khỏi kẻ thù. Mỗi các thể trong PSO tương tự như một con chim hay ong bay trong không giam tìm kiếm. Mỗi cá thể có một vận tốc ban đầu và giữa các cá thể có kênh liên lạc với nhau. Sự chuyển động của mỗi cá thể là sự phối hợp của vận tốc bao gồm cả mức độ và hướng. Mỗi vị trí của các thể chịu ảnh hưởng bởi vị trí tốt nhất của mình và vị trí tốt nhất của không gian lời giải. Các cá thể được đánh giá bằng một hay nhiều tiêu chuẩn thích nghi (giá trị thích nghi - fitness). Dần dần các cá thể sẽ di chuyển về phía những cá thể đang ở vị trí tốt hơn trong bày đàn. Tương tự như các giải thuật tiến hóa khác, trong PSO, quần thể là tập hợp các cá thể hoạt động trong không gian tìm kiếm – còn gọi là bầy đàn. Ban đầu tất cả các cá thể đều được sinh ngẫu nhiên. Mỗi cá thể được đặc trưng bởi một giá trị thích nghi (fitness) được tính toán dựa trên hàm đo độ thích nghi. PSO tìm phương án tối ưu bằng cách cập nhật cá thể thông qua các thế hệ. Trong mỗi thế hệ, từng cá thể được cập nhật theo hai giá trị. Giá trị thứ nhất là vị trí tốt nhất đạt được cho tới thời điểm hiện tại của cá thể đó ký hiệu là pbest. Giá trị thứ hai là vị trí tối ưu toàn cục của cả bầy đàn ký hiệu là gbest. vik+1 = w.vki+c1 . rand1().(pbesti – xik) + c2.rand2().(gbest – xik) xik+1 = xit + vk+1 i (vk=0 i = 0) 63
Nguyễn Thị Thùy Liên và Đỗ Như Long trong đó: xik, vik: vector vị trí, vector vận tốc cá thể thứ i tại thế hệ thứ k xik+1, vik+1: vector vị trí, vector vận tốc cá thể thứ i tại thế hệ thứ k + 1 pbesti: Vị trí tốt nhất của cá thể thứ i cho đến thời điểm hiện tại gbesti: Vị trí tốt nhất của quần thể cho đến thời điểm hiện tại. w : trọng số quán tính c1, c2 : các tham số học hoặc hệ số gia tốc đặc trưng cho kinh nghiệm và tính xã hội của các cá thể trong quần thể (có thể lấy c1≈c2≈ 2 hoặc c1 + c2 ≤ 4) rand1, rand2 : hai vector ngẫu nhiên mỗi thành phần lấy giữa 0 và 1 được sinh ra tại mỗi bước lặp. Mã hóa cá thể Bài toán lập lịch được biểu diễn dưới dạng đồ thị DAG trong đó mỗi nút tương ứng với một nhiệm vụ, mỗi cạnh tương ứng với một mỗi liên hệ cha-con giữa hai nhiệm vụ . Số chiều của cá thể d bằng số tác vụ n [4]. Giá trị của mỗi chiều trong cá thể đại diện cho một tài nguyên tương ứng. Trong quá trình tìm kiếm, các giá trị của mỗi chiều của cá thể trong hệ thống tài nguyên thay đổi và tái xây dựng một cá thể mới sau khi tiến hóa theo vị trí mới của mỗi chiều. Ví dụ hình dưới xây dựng một cá thể. Cá thể có 10 chiều đại diện cho 10 tác vụ, giá trị của mỗi chiều đại diện cho tài nguyên được lựa chọn để thực hiện tác vụ đó. Mã hóa cá thể tương ứng Task 1 2 3 4 5 6 7 8 9 10 Host 2 3 1 0 3 5 4 6 2 5 Partical 2 3 1 0 3 5 4 6 2 5 2.2. Giải thuật Heuristic dựa trên PSO (HPSO) Giải thuật lập lịch động dựa PSO thực hiện tìm kiếm và đưa ra phương án ánh xạ tác vụ - tài nguyên với chi phí gần tối ưu dựa trên giải thuật tối ưu bầy đàn. Quá trình tìm phương án tối ưu được thực hiện qua 2 bước: - Bước 1. Sheduling heuristic: Chi phí tính toán của tất cả các tác vụ trên tất cả các tài nguyên tính toán được tính bằng chi phí thực hiện của mỗi tác vụ trên từng tài nguyên. Giải thuật Scheduling heuristic 1. Tính toán chi phí thực thi trung bình của tất cả các tác vụ trên tất cả các tài nguyên 2. Tính toán chi phí truyền thông dữ liệu giữa các nguồn tài nguyên 3. Thiết lập trọng số các nút wkj là chi phí tính toán trung bình 4. Thiết lập trọng số cạnh ek1,k2 là kích thước của dữ liệu truyền giữa các tác vụ 5. Tính PSO({ti}) /* tập các tác vụ i ϵ k*/ 6. repeat 7. for tất cả các tác vụ “ready” {ti} T do 8. Gán tác vụ {ti} cho tài nguyên {hj} dựa theo kết quả thực thi PSO 9. endfor 10. Gửi tất cả tác vụ đã được lập lịch 11. Đợi polling_time 12. Cập nhật danh sách các tác vụ ready 13. Cập nhật chi phí truyền thông trung bình giữa các tài nguyên dựa theo hiện trạng của mạng hiện tại. 14. Tính PSO({ti}) 15. until không có tác vụ nào chưa được lập lịch Hình 1. Giải thuật Scheduling heuristic 64
Bài toán lập lịch phân bổ tài nguyên trong môi trường điện toán đám mây Giải thuật PSO 1. Thiết lập số chiều cá thể bằng kích thước của tập các tác vụ sẵn sàng {ti} T 2. Khởi tạo các cá thể với vị trí ngẫu nhiên {1,…host_numbers}và vận tốc ngẫu nhiên [0,1] 3. For each cá thể p, 4. Tính giá trị thích nghi fitness 5. Nếu giá trị thích nghi fitness của cá thể hiện tại tốt hơn Pbest tốt nhất trước đó, thiết lập lại giá trị Pbest bằng giá trị mới. 6. End for 7. Chọn cá thể tốt nhất coi là Gbest 8. Tính toán vận tốc và cập nhật lại vị trí đối với từng cá thể Hình 2. Giải thuật PSO - Bước 2. PSO Giải thuật lập lịch động dựa PSO là động (online) vì nó cập nhật chi phí truyền thông dựa trên chi phí truyền thông giữa các tài nguyên) trong mỗi vòng lặp. Giải thuật cũng tái ánh xạ task-resource vì vậy giúp tối ưu chi phí tính toán dựa trên trạng thái tài nguyên và mạng hiện tại. 2.3. Giải thuật Heuristic dựa trên PSO * (HPSO*) HPSO* cung cấp một phương án ánh xạ các tác vụ với một tập các tài nguyên thông qua hai bước: sử dụng giải thuật Scheduling Heuristic và sử dụng biến thể PSO như Hình 3. Giải thuật PSO* 1. Thiết lập số chiều cá thể bằng kích thước của tập các tác vụ sẵn sàng {ti} T 2. Khởi tạo các cá thể với vị trí ngẫu nhiên {1,…host_numbers}và vận tốc ngẫu nhiên [0,1] 3. For each cá thể p, 4. Tính giá trị thích nghi fitness 5. Nếu giá trị thích nghi fitness của cá thể hiện tại tốt hơn Pbest tốt nhất trước đó, thiết lập lại giá trị Pbest bằng giá trị mới. 6. End for 7. Chọn cá thể tốt nhất coi là Gbest 8. Repeat a. Chọn ngẫu nhiên m = [log2(n)] chiều từ vector vị trí n chiều của cá thể gbest và trao đổi giá trị của chúng theo từng cặp b. Tính lại giá trị fitness của gbest* c. Cập nhật gbest* làm gbest nếu gbest* có fitness tốt hơn Until thỏa điều kiện dừng hoặc số lần lặp tối đa 9. Tính toán vận tốc và cập nhật lại vị trí đối với từng cá thể 10. Nếu các điều kiện dừng và số lần lặp tối đa chưa đáp ứng lặp lại bước 3 Hình 3. Giải thuật PSO* 65
Nguyễn Thị Thùy Liên và Đỗ Như Long 2.4. Thực nghiệm và nhận xét 2.4.1. Kết quả thực nghiệm Thực nghiệm chọn thông số Thực nghiệm chọn thông số m cặp giá trị ngẫu nhiên từ vector vị trí của cá thể gbest để trao đổi giá trị của chúng trong giải thuật PSO* bằng thực nghiệm trên 10 bộ dữ liệu. Thực nghiệm 5 lần trên từng bộ dữ liệu và lấy giá trị trung bình tương ứng với mỗi giá trị m chạy từ 1 đến 5 như Bảng 1. Qua so sánh kết quả thực nghiệm, nhận thấy với các bộ dữ liệu có số tác vụ khác nhau có sự phù hợp khác nhau với các giá trị của thông số m, tác giả tiến hành chọn thông số m = [log2(n/2)] áp dụng cho giải thuật PSO* trong đó n là số tác vụ. Biểu đồ so sánh tổng chi phí thực hiện trên các bộ dữ liệu ứng với các giá trị khác nhau của thông số n được biểu diễn trong Hình 4. Bảng 1 Thực nghiệm chọn thông số m – số cặp giá trị trao đổi ngẫu nhiên của vector vị trí Gbest trong giải thuật PSO* Stt bộ dữ liệu 1 2 3 4 5 6 7 8 9 10 Số tác vụ (n) 5 8 53 44 124 16 25 77 81 42 m 1 35,1 138,1 44,1 139,9 44,1 6,2 19,4 58,2 244,4 54,7 2 36,6 264,5 30,9 79,6 39,0 6,3 16,2 83,2 212,2 47,4 3 36,6 131,6 29,1 80,8 35,8 5,8 10,4 85,7 219,4 56,3 4 39,1 215,1 33,8 90,8 40,5 4,9 16,4 80,9 174,4 51,1 5 40,1 209,7 42,8 77,4 35,5 6,8 13,5 62,0 224,2 59,7 [log2(n)/2] 35,1 138,1 30,9 79,6 35,8 6,3 16,2 85,7 219,4 47,4 Hình 4. Biểu đồ so sánh tổng chi phí thực hiện trên các bộ dữ liệu với giá trị thông số m thay đổi Tiến hành thử nghiệm các giải thuật trên 6 tài nguyên tính toán 10 bộ dữ liệu trong đó, bộ dữ liệu thử nghiệm số 1 gồm 5 tác vụ được lấy từ bài báo của tác giả Suraj Pandey, Linlin Wu [4], bộ dữ liệu số 3 gồm 53 tác vụ (AIRSN workflow, Hình 5), bộ dữ liệu số 4,5 gồm 44 và 124 tác vụ (Chimera workflow, Hình 5-http://toolkit.globus.org), các bộ dữ liệu thử nghiệm số 6, 7, 8, 9, 10 được sinh ngẫu nhiên từ bộ sinh dữ liệu Montage (Montage:http://montage.ipac.caltech.edu). 66
Bài toán lập lịch phân bổ tài nguyên trong môi trường điện toán đám mây AIRSN 53 (3) Chimera 124(5) Hình 5. AIRSN và Chimera workflow được sử dụng trong thực nghiệm Bài toán SRAP có tổng chi phí được tính là tổng của chi phí thực thi các tác vụ trên các tài nguyên và tổng chi phí truyền thông giữa các tác vụ. Như vậy, tổng chi phí của bài toán SRAP phụ thuộc khá lớn vào chi phí truyền thông, trong khi đó, với môi trường điện toán đám mây các tài nguyên có thể ở khắp mọi nơi trên thế giới với cơ sở hạ tầng mạng rất khác nhau ảnh hưởng không nhỏ đến chi phí truyền thông. Vì vậy tác giả tiến hành thực nghiệm 30 lần và lấy kết quả trung bình trên mỗi bộ dữ liệu ứng với 3 trường hợp: chi phí truyền thông không đáng kể (đặc trưng cho cơ sở hạ tầng mạng rất tốt), chi phí truyền thông trung bình (đặc trưng cho cơ sở hạ tầng, đường truyền mức trung bình), chi phí truyền thông đáng kể (đặc trưng cho cơ sở hạ tầng, đường truyền mạng rất kém). Kết quả thử nghiệm được tổng hợp trong Bảng 2. Bảng 2. Tổng hợp kết quả thử nghiệm (chi phí) trên các bộ dữ liệu ứng với các trường hợp chi phí truyền thông rất nhỏ, chi phí truyền thông trung bình và chi phí truyền thông đáng kể Chi phí truyền thông Chi phí truyền thông nhỏ Chi phí truyền thông trung bình Bộ Số đáng kể tác dữ vụ H H H H H H liệu P P P n Ran Round P P Ran Round P P Ran Round P P S S S dom Robin S S dom Robin S S dom Robin S S O O O O O* O O* O O* 1 5 34,2 35,0 32,92 18,32 18,32 31,247 35,0 35,047 18,48 18,8 31,25 35,0 45,33 18,09 17,85 2 8 72,76 50,0 60,59 27,69 28,10 57,543 50,0 60,923 27,52 27,69 58,05 50,0 92,8 27,02 29,77 3 53 3,193 2,843 3,378 0,788 0,539 72,77 78,778 34,816 15,19 21,07 779,8 798,98 646,1 560 675 4 44 1,914 2,532 2,007 0,619 0,515 228,75 234,3 89,21 46,62 32,77 2577 2629 2249,88 2222 2124 5 124 47924 61510 68872 16274 12855 47272 61762 6484 17334 13068 47831 64394 63343 19985 18796 6 16 1,020 3,012 0,672 0,122 0,094 12,352 13,738 5,922 3,672 3,425 125,2 134,4 97,28 84,12 79,43 7 25 1,254 1,414 1,346 0,315 0,242 45,19 46,06 13,772 13,59 11,18 504,6 500 379,4 402,7 412,9 8 77 3,196 3,354 4,109 0,989 0,800 110,5 115,36 54,243 38,51 40,785 1214 1229,3 1080 994,5 1016,7 9 81 3,604 3,029 4,861 1,148 0,915 381,1 369,8 164,83 117,9 85,37 4318 4252 3755, 3760,9 3400,78 10 42 1,682 1,330 1,659 0,594 0,442 121,442 124,08 44,49 22,85 13,799 1369, 1359,9 1048 947,8 974,1 67
Nguyễn Thị Thùy Liên và Đỗ Như Long Nhận thấy giải thuật PSO ứng dụng giải bài toán lập lịch cho kết quả không tốt hơn hai giải thuật khá phố biến là Random và RoundRobin trong trường hợp chi phí truyền thông rất nhỏ (Hình 6). Khi chi phí truyền thông nhỏ, không đáng kể thì tổng chi phí của bài toán xấp xỉ bằng tổng chi phí tính toán các tác vụ trên các tài nguyên trong khi đó giải thuật PSO có tính toán đến chi phí truyền thông không phát huy hết ưu điểm của mình. Khi chi phí truyền thông tăng lên, kết quả thử nghiệm cho thấy giải thuật PSO cho kết quả tốt hơn hẳn hai giải thuật Random và RoundRobin (Hình 7). Qua Bảng 3, 4 chúng tôi nhận thấy giải thuật HPSO và HPSO* có mức độ giảm tổng chi phí rất lớn so với giải thuật PSO khi chi phí truyền thông còn tương đối nhỏ. Bảng 3. So sánh chi phí thử nghiệm giữa các giải thuật HPSO so với PSO, HPSO* so với PSO và HPSO trên các bộ dữ liệu (đơn vị %) với chi phí truyền thông rất nhỏ HPSO HPSO* Bộ dữ liệu Số tác vụ (PSO) (PSO) (HPSO) 1 5 -44.34 -44.34 0 2 8 -54.30 -53.62 +1.46 3 53 -76.69 -84.06 -31.61 4 44 -69.13 -74.32 -16. 5 124 -76.31 -81.31 -21.13 6 16 -81.89 -86.08 -23.13 7 25 -76.58 -82.03 -23.27 8 77 -75.90 -80.54 -19.22 9 81 -76.38 -81.18 -20.30 10 42 -64.16 -73.36 -25.61 Hình 6. So sánh tổng chi phí giữa các giải thuật PSO, HPSO và HPSO* với chi phí truyền thông rất nhỏ Tuy nhiên khi chi phí truyền thông trở lên rất lớn (đặc trưng cho hạ tầng mạng rất kém) thì mức độ giảm tổng chi phí của hai giải thuật HPSO và HPSO* không thực sự cao so với giải thuật PSO (Bảng 5, Hình 8) vì chi phí truyền thông rất lớn kéo theo tỉ trọng chi phí truyền thông trong tổng chi phí của bài toán rất lớn (mức chi phí truyền thông gần như rất khó có thể giảm nhiều). 68
Bài toán lập lịch phân bổ tài nguyên trong môi trường điện toán đám mây Bảng 4. So sánh chi phí thử nghiệm giữa các giải thuật HPSO với PSO, HPSO* với PSO và HPSO trên các bộ dữ liệu (đơn vị %) với chi phí truyền thông trung bình Bộ Số HPSO HPSO* dữ tác (PSO) (PSO) (HPSO) liệu vụ 1 5 -56.37 -39.48 +38.72 2 8 -47.74 -63.26 -29.70 3 53 -73.16 -79.77 -24.61 4 44 -38.00 42.17 -6. 2 5 124 - .31 -18.79 -17. 1 6 16 -29.00 -24.81 5.90 7 25 -28.45 -48.21 -27.61 8 77 -48.65 -68.99 -39.60 9 81 -47.27 -46.36 +1.73 Hình 7. So sánh tổng chi phí giữa các giải thuật PSO, 10 42 -54.83 -54.54 +0.63 HPSO và HPSO* có chi phí truyền thông trung bình Bảng 5. So sánh chi phí thử nghiệm giữa các giải thuật HPSO với PSO, HPSO* với PSO và HPSO trên các bộ dữ liệu (đơn vị %) với chi phí truyền thông đáng kể Bộ Số HPSO HPSO* dữ tác (PSO) (PSO) (HPSO) liệu vụ - 1 5 13. 3 +4.47 +20.5 2 8 -1 22 -5. -4.42 3 53 -72.14 -73.80 -5.95 - 4 4 1 .54 -18.35 -5.57 5 124 +6.14 +8.83 +2.53 6 16 -7.96 -5.93 +2.21 7 25 +0.13 -9.45 -9.57 Hình 8. So sánh tổng chi phí giữa các giải thuật 8 77 -9.55 -7.04 +2.78 PSO, HPSO và HPSO* có chi phí 9 81 -60.10 -60.63 -1.33 truyền thông trung bình 10 42 -70.88 -67.92 +10.17 3. Kết luận Bài báo trình bày trình bày một giải thuật lập lịch động dựa trên phương pháp tối ưu bầy đàn (PSO) nhằm mục đích tối thiểu tổng chi phí thực thi của ứng dụng luồng công việc trong môi trường điện toán đám mây. Bài báo cũng trình bày một biến thể của giải thuật PSO là PSO* với cải tiến sử dụng trao đổi ngẫu nhiên các phần tử trong cá thể gbest với mong muốn tìm được gbest tốt hơn từ đó hội tụ nhanh hơn. Khi so sánh kết quả thực nghiệm giữa giải thuật PSO, HPSO và HPSO* với hai giải thuật phổ biến Random, RoundRobin bài báo đã chỉ rõ giải thuật lập lịch động dựa trên PSO đưa ra phương án với chi phí thực thi giảm rất nhiều. Tuy nhiên chúng tôi mới chỉ dừng lại ở mục tiêu tối thiểu tổng chi phí thực thi trong khi đó với các bài toán thực thế có rất nhiều mục tiêu khác nhau: tối thiểu tổng thời gian thực thi, tối thiểu tổng chi phí thực thi và thời gian thực thi hay cân bằng tải, chúng tôi sẽ tiếp tục nghiên cứu cải tiến theo hướng này. 69
Nguyễn Thị Thùy Liên và Đỗ Như Long TÀI LIỆU THAM KHẢO [1] Monte Zweben and Mark Fox, 1994. Intelligent scheduling. Morgan Kaufmann Publishers Inc. San Francisco, CA, USA, ISBN:1-55860-260-7. [2] Suraj Pandey, Linlin Wu, Siddeswara Mayura Guru, Rajkumar Buyya, A Particle Swarm Optimization – based Heuristic for Scheduling Workflow Applications in Cloud Computing Enviroments, 2010. Cloud Computing and Distributed Systems Laboratory Department of Computer Science and Software Engineering, The University of Melbourne, Autralia Suraj Pandey, Linlin Wu, Siddeswara Guru, and Rajkumar Buyya, A Particle Swarm Optimization (PSO)-based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments, Proceedings of the 24th IEEE International Conference on Advanced Information Networking and Applications (AINA 2010), Perth, Australia, Best Paper Award. [3] J. Kennedy and R. Eberhart, 1995. Particle Swarm Optimization, in IEEE International Conference on Neural Networks, Vol.4, pp. 1942-1948 [4] Sheng-Jun Xue, Wu Wu, 2012. Scheduling Workflow in Cloud Computing Based on Hybrid Partical Swarm Algorithm. Telkomnika, Vol. 10, No. 7, e-ISSN: 2087-278x. ABSTRACT Scheduling and resource allocation in a cloud computing environment Resources in cloud computing environments are stored in many different positions. Cloud computing provides the infrastructure for applications by providing virtualized resources automatically. An essential requirement when scheduling in a cloud computing environment is making plan mapped tasks that provide corresponding resource constraints. This paper presents a dynamic scheduling algorithm (HPSO*) based on PSO to make a plan for scheduling applications for resources, taking into account both the cost of computation and data transmission costs. At the same time this paper also presents the results of testing the algorithm on the data to show the effectiveness of the HPSO* algorithm. Keyword: Cloud computing environment, workflow, PSO, scheduling and resource allocation. 70

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.