Bài toán lập lịch Workflow trong môi trường điện toán đám mây

JOURNAL OF SCIENCE OF HNUE FIT., 2013, Vol. 58, pp. 140-149 This paper is available online at BÀI TOÁN LẬP LỊCH WORKFLOWTRONG MÔI TRƯỜNG ĐIỆN TOÁN ĐÁMMÂY Kiều Tuấn Dũng 1, Nguyễn Thế Lộc 1∗ và Phan Thanh Toàn 2 1 Khoa Công nghệ Thông tin, Trường Đại học Sư phạm Hà Nội, 2 Khoa Sư phạm Kĩ thuật, Trường Đại học Sư phạm Hà Nội, ∗Email: locnt@hnue.edu.vn Tóm tắt. Trong hoạt động của đám mây điện toán, việc tổ chức thực hiện những công việc workflow - loại công việc đòi hỏi nhiều công đoạn xử lí theo trình tự định trước - sẽ quyết định hiệu suất của cả hệ thống. Vấn đề nằm ở chỗ phải tìm ra phương án sử dụng nhiều dạng tài nguyên nằm ở những vị trí địa lí xa nhau được kết nối bởi các đường truyền tốc độ khác nhau sao cho chi phí tính toán và truyền thông là nhỏ nhất. Bài báo này trình bày một thuật toán giải quyết thông qua cách tiếp cận Bầy đàn và trình bày những kết quả thực nghiệm trên công cụ mô phỏng CloudSim chỉ rõ giải thuật đề xuất cho kết quả tốt hơn hai giải thuật Random và Round Robin. Từ khóa: Điện toán đám mây, mô hình luồng công việc, bài toán lập lịch. 1. Mở đầu Điện toán đám mây mở ra xu hướng mới trong việc cấp phát và quản lí tài nguyên điện toán ở tầm quốc gia và toàn cầu. Các tài nguyên mạng thay vì phân bố một cách riêng lẻ và không hiệu quả tại các cơ quan hay công ti thì nay được quản lí tập trung và phân phối một cách có hệ thống bởi công ti cung cấp các dịch vụ đám mây. Trong các dịch vụ đó phổ biến nhất là loại dịch vụ có mô hình Luồng công việc (từ đây gọi tắt là workflow). Chúng cấu thành từ chuỗi nhiều hoạt động kế tiếp nhau được biểu diễn và cấu trúc hóa bởi các luồng, ví dụ các thí nghiệm hóa, sinh học phân tử, phân tích dữ liệu khoa học thần kinh và phục hồi lại các thảm họa... Lập lịch workflow là một quy trình gắn kết và ánh xạ việc thực hiện các nhiệm vụ phụ thuộc lẫn nhau trên các tài nguyên phân tán và cũng như các bài toán lập lịch khác nó có độ phức tạp là NP-đủ. Giải thuật tối ưu bầy đàn (PSO - Paricle Swarm Optimization) là một trong những kỹ thuật tìm kiếm tối ưu toàn cục được giới thiệu bởi Kennedy và Eberhart [1]. Bài báo này sẽ trình bày các kết quả nghiên cứu giải thuật lập lịch tối ưu bầy đàn (PSO) cho các ứng dụng workflow trong môi trường điện toán đám mây (workflow cloud) để tối ưu hóa chi phí dịch vụ theo mô hình pay-per-use. Các kết quả chính của bài báo là: - Áp dụng cách tiếp cận PSO để phân phối công việc tới các tài nguyên đám mây nhằm tối thiểu hóa toàn bộ chi phí thực hiện. 140 Bài toán lập lịch Workflow trong môi trường điện toán đám mây - Tiến hành thực nghiệm trên môi trường mô phòng CloudSim để đánh giá kết quả và so sánh với giải thuật PSO heuristic, Random và Round Robin. 2. Nội dung nghiên cứu 2.1. Tối ưu bầy đàn Giải pháp tối ưu bày đàn PSO mô tả không gian giải pháp n chiều, mỗi cá thể Pi biểu diễn một lời giải của bài toán và có hành vi của một cá thể trong đàn, cá thể Pi có vị trí xki Bầy đàn P = {p1, p2, ..., pn} là một tập các cá thể. Mỗi cá thể có thể có thông tin về toàn bộ quần thể hoặc thông tin về một phần quần thể. Thông tin đó thường là thông tin về cá thể tốt nhất trong quần thể, nó được đánh giá qua giá trị của hàm mục tiêu. Vận tốc của cá thể xki = {u1, u2, ...un} là một vector n chiều làm thay đổi (di chuyển) vị trí của các cá thể Pi ở thế hệ k. Về mặt toán học, quan hệ vị trí - vận tốc là như sau: xk+1i = xki + v k+1 i (2.1). Vận tốc ảnh hưởng bởi tri thức của cá thể và kinh nghiệm của hàng xóm (các cá thể khác trong bầy đàn): vk+1i = ϕ1(individual_experience) + ϕ2(global_experience) (2.2) vk+1i = w.v k i + ϕ1(experiencei) + ϕ2(experienceg) (2.3) vk+1i = w.v k i + c1.rand1(pbesti)− x k i ) + c2.rand2(gbest − x k i ) (2.4) Hình 1 biểu diễn quan hệ vị trí - vận tốc trong không gian hai chiều với giá trị vk+1i được cập nhật theo kinh nghiệm bay tốt nhất của cá thể trong quá khứ và kinh nghiệm bay tốt nhất của cá thể tốt nhất trong quần thể. Nó sẽ tiến hành thay đổi (điều chỉnh hướng bay) tới vị trí mới vk+1i . Hình 1. Quan hệ vị trí - vận tốc trong không gian 2 chiều Mỗi cá thể có một vận tốc riêng để tính vị trí tiếp theo trong không gian lời giải, nó sẽ di chuyển trong đó để tìm ra lời giải tối ưu. Hàm mục tiêu F (x) mô tả yêu cầu của bài toán và được dùng để đánh giá các lời giải. Bằng cách so sánh lời giải hiện tại với lời giải tốt nhất, các cá thể sẽ xác định bước đi tiếp theo. Ba lời giải được sử dụng để xác định hướng đi tiếp theo là: tốt nhất cá nhân (pbest), tốt nhất toàn cục (gbest) và tốt nhất cục bộ (lbest). Quần thể ban đầu gồm n cá thể (mỗi cá thể là một lời giải), cá thể thứ i được biểu diễn bởi vector xi cóm chiều và vector vận tốc vi m chiều với i = 1, ..., n. Hàm mục tiêu của bài toán là f : Rm → R Mô tả thuật toán chi tiết như sau: B1: Khởi tạo quần thể với việc khởi tạo vector vị trí xi và vector vận tốc vi cho cá thể thứ i, i = 1, ..., n (cho mỗi cá thể Pi trong quần thể P (n)). B2: Khởi tạo các thông tin ban đầu về vị trí tốt nhất của các cá thể và cả quần thể: pbesti = xi (khởi tạo vị trí tốt nhất của cá thể thứ i bằng vị trí được khởi tạo hiện tại); 141 Kiều Tuấn Dũng, Nguyễn Thế Lộc, Phan Thanh Toàn gbest = min(f(xi)), i = 1, ...n (khởi tạo vị trí tốt nhất của cả quần thể bằng vị trí nhỏ nhất trong tất cả các vị trí của tất cả các cá thể được khởi tạo). B3: Bước lặp với điều kiện lặp xác định trước (sau một số lần lặp cho trước hoặc sau một số lần lặp mà không thu được kết quả tốt hơn): For 1 <= i <= n (với mỗi cá thể) vk+1i = w.v k i + c1.rand1.(pbesti − x k i ) + c2.rand2.(gbest − x k i ) (chỉnh lại chuyển động dựa theo chuyển động tốt nhất của mình và của cá thể tốt nhất trong đàn); xk+1i = x k i + v k+1 i (cập nhật lại vị trí theo hướng chuyển động mới nhất); If f(xi) < f(pbesti) then pbesti = xi (cập nhật lại vị trí tốt nhất của mỗi cá thể bằng việc so sánh với vị trí hiện tại); If f(xi) < f(gbest) then gbest = xi (cập nhật lại ví trí tốt nhất của quần thể bằng việc so sánh với cá thể tốt nhất hiện tại); Kiểm tra điều kiện kết thúc lặp, nếu thỏa mãn chuyển sang B4, còn không tiếp tục B3. B4: Kết thúc, trả về giá trị tốt nhất gbest. Ý nghĩa các tham số: w là hằng số quán tính; c1 và c2 là hệ số gia tốc, hằng số mô tả có bao nhiêu cá thể hướng về vị trí tốt, đặc trưng cho kinh nghiệm và tính xã hội; rand1 và rand2 là hai vector ngẫu nhiên, lấy giá trị trong đoạn [0, 1], nó được sinh ra tại mỗi bước lặp; pbesti là vị trí tốt nhất cho đến thời điểm hiện tại của cá thể thứ i trong quần thể; gbest là vị trí tốt nhất của cả quần thể tại thời điểm hiện tại. 2.2. Vấn đề tối thiểu chi phí Vấn đề phân phối các task của một ứng dụng workflow cho các tài nguyên phân tán xử lí có nhiều mục đích. Chúng tôi tập trung vào mục đích tối thiểu hóa tổng chi phí tính toán của một ứng dụng workflow đến khi hoàn thành trong điều kiện cho phép về thời gian (deadline) theo yêu cầu của người dùng[3]. Hình 2. Một workflow với các nút lưu trữ Si và các nút tính toán PCi Hình 2 chỉ ra một luồng gồm 5 công việc: T1, T2, T3, T4 và T5, mỗi công việc đều có 142 Bài toán lập lịch Workflow trong môi trường điện toán đám mây dữ liệu đầu vào và dữ liệu đầu ra: f.in, f.out, f12, f13, f14, f25, f35, f45. Luồng công việc được chia làm ba cấp độ khác nhau: cấp độ 1 gồm T1 , cấp độ 2 bao gồm: T2, T3, T4 chờ nhận dữ liệu từ T1 để xử lí và cung cấp dữ liệu cho T5 ở cấp độ 3. T5 phải chờ dữ liệu của T2, T3, T4 và khi T5 xong thì luồng công việc mới được coi là hoàn tất. Workflow được biểu diễn bằng đồ thị G = (V,E) trong đó: V = tập các task = {T1, T2, ..., Tn}, E = tập các cạnh biểu thị liên hệ dữ liệu giữa các task = {fj,k} trong đó cạnh fj,k cho biết dữ liệu sinh ra bởi task Tj (đầu ra của Tj) sẽ là đầu vào của task Tk. Tập các storage site (máy trạm lưu trữ - làm nhiệm vụ kho chứa) S = {S1, ...Si}. Tập các compute site (máy trạm tính toán) S = {PC1, ..., PCj}. Chi phí để PCj xử lí task Tk được cho trong bảng 1 (theo nhà cung cấp dịch vụ). Đơn giá truy cập dij = giá cước dành cho máy trạm i khi truy cập một đơn vị dữ liệu đặt trên máy trạm j , giá này do nhà cung cấp dịch vụ qui định và thỏa mãn: dij = dji ; dij + djk >= djk (Bảng 2). Mỗi task cha xuất ra output là một khối data và nó được dùng làm input cho task con. Kích thước của những khối data đó được gọi là trọng số cạnh ek1,k2 trong đó task k1 và k2 là cặp Cha-Con (Bảng 3). Bảng 1: Chi phí thực thi của mỗi Ti trên các PC 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 TP [i, j] = chi phí thực thi của Ti trên PCj; [Nguồn: Bảng giá sử dụng dịch vụ của Amazon EC2] Bảng 2: 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 PP [i, j] = chi phí truyền thông giữa hai PCi và PCj (giá trị theo đơn vị $/MB/giây) Bảng 3: Kích thước Input/Output của Taski DST2,T3,T4[2x2] Totaldata DST5[2x2] Totaldata Input 10 Input 30 Otput 10 Output 60 Input: Dữ liệu vào, Output: Kết quả ra của các công việc (đơn vị: MB) 143 Kiều Tuấn Dũng, Nguyễn Thế Lộc, Phan Thanh Toàn Bài toán có thể phát biểu như sau: “Tìm phương án mapping M sao cho giá trị cost lớn nhất trong số các PC là nhỏ nhất” Cexe(M)j = ∑ k wkj, ∀M(k) = j, (1) Ctx(M)j = ∑ k1∈k ∑ k2∈k dM(k1),M(k2)ek1,k2, ∀M(k2) 6= j , (2) Ctotal(M)j = Cexe(M)j + Ctx(M)j (3) Cost(M) = max(Ctotal(M)j), ∀j ∈ P (4) Minimize(Cost(M)j ), ∀M (5) với điều kiện: ek1,k2 > 0 txcostij = txcostji, ∀i, j ∈ N txcostik + txcostkj > txcostij , ∀i, j, k ∈ N Trong đó: Cexe(M)j : là tổng chi phí mà PCj phải trả theo sự phân phối của phương án mapping M. Nó bằng tổng các trọng số đỉnh, tức là chi phí thực thi của task k trên tài nguyên tính toán j (PCj), đại lượng trong ma trận TP trong bảng 1. Ctx(M)j : là tổng chi phí truy cập (access cost, bao gồm transfer cost- phí truyền thông) giữa các task thực hiện bởi PCj và những task khác, là cha hoặc con của những task kể trên. Gọi PC được M giao thực hiện task k1 là M(k1), PC được M giao thực hiện k2 là M(k2), như vậy trọng số cạnh (edge-weight) ek1,k2 sẽ cho biết kích thước file output mà task k1 sinh ra. Tất nhiên M(k1) là task cha, task M(k2) là task con. Access cost = ek1,k2 (kích thước file output mà task Cha k1 sinh ra cho task Con k2 dùng)× cước truyền thông giữa M(k1) và M(k2). Cước truyền thông của 1 đơn vị dữ liệu giữa 2 PC chính là dM(k1),M(k2) nêu trong mục trên. Nếu 2 task chạy trên cùng PC thì cước truyền = 0.txcosti,j là chi phí truy cập datacenter và chi phí truyền dữ liệu. 2.3. Lập lịch dựa tối ưu bầy đàn Trong phần này, chúng tôi trình bày giải thuật heuristic lập lịch động cho bài toán lập lịch ứng dụng workflow [2] nhằm tối thiểu hóa chi phí dựa trên giải thuật tối ưu bầy đàn. Quy trình tối ưu sử dụng giải thuật lập lịch heuristic (giải thuật 2) và các bước của giải thuật PSO (Giải thuật 1). Để giải quyết bài toán, chúng ta cần xác định không gian lời giải và phương pháp đánh giá, cập nhật giải pháp. Thuật bắt đầu với việc khởi tạo ngẫu nhiên vị trí và vận tốc của cá thể, dựa trên những giá trị này ta đánh giá hàm mục tiêu, cập nhật lại giá trị pbest và gbest. {(T2,PC1) (T3,PC2) (T4,PC3)} ↓ [1 2 3] T2 T3 T4 Hình 3: Ví dụ về biểu diễn các thể trong PSO Giải thuật 1: Giải thuật PSO 144 Bài toán lập lịch Workflow trong môi trường điện toán đám mây B1. Xây dựng kích thước cá thể bằng số các task sẵn sàng ∀ti ∈ T . B2. Khởi tạo vị trí các xi cá thể ngẫu nhiên từ các PC = 1, ..., j và vận tốc vi ngẫu nhiên. B3. Với mỗi cá thể, tính giá trị hàm mục tiêu theo công thức (4). B4. Nếu giá trị hàm mục tiêu tốt hơn Pbest trước đó, gán lại Pbest bằng giá trị mới. B5. Sau bước 3 và 4 cho tất cả các cá thể, chọn cá thể có giá trị tốt nhất coi là gbest. B6. Đối với tất cả các cá thể, tính toán vận tốc sử dụng công thức: vk+1i = w.v k i + c1.rand1.(pbesti − v k i ) + c2.rand2.(gbest − x k i ) và cập nhật lại vị trí các cá thể sử dụng công thức: xk+1i = x k i + v k+1 i B7. 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. Giải thuật 2: Giải thuật PSO_Heuristic B1. Tính chi phí tính toán trung bình của tất cả các task thực hiện trên tất cả các tài nguyên tính toán; B2. Tính toán chi phí truyền dữ liệu trung bình giữa các tài nguyên; B3. Thiết lập trọng số các node: weight wkj = (chi phí tính toán trung bình, chính là ma trận TP); B4. Thiết lập trọng số cạnh ek1,k2 bằng kích thước file chuyển giao giữa các task; B5. Repeat B6. For mọi task ở trạng thái “ready” 1 do B7. Gán mỗi {ti ∈ T} − pj theo giải thuật PSO; B8. End For; B9. Thực hiện mapping: gắn kết các task - resource; B10. Chờ xử lí công việc (phụ thuộc dữ liệu đầu vào và đầu ra giữa task cha-con); B11. Cập nhật lại các task ở trạng thái “ready”; B12. 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; B13. Tính toán PSO(ti); B14. Until không có task chưa được lập lịch. 2.4. CloudSim - công cụ mô phỏng môi trường điện toán đám mây CloudSim [4,5] là công cụ mô hình hóa và mô phỏng dịch vụ hạ tầng điện toán đám mây được phát triển tại đại học Melbourne ( Với CloudSim các nhà nghiên cứu có thể tập trung vào thiết kế hệ thống cụ thể mà không cần quan tâm đến chi tiết cơ sở hạ tầng của đám mây được cài đặt ra sao. 1Task Ready: các task mà có task cha thực thi xong và cung cấp dữ liệu output 145 Kiều Tuấn Dũng, Nguyễn Thế Lộc, Phan Thanh Toàn 2.5. Thực nghiệm 2.5.1. Dữ liệu và cách thực hiện Để 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 sử dụng gói thư viện JSwarm ( công cụ mô phỏng CloudSim và cài đặt giải thuật PSO heuristic bằng ngôn ngữ Java. Kết quả được thu thập để đánh giá và so sánh với giải thuật PSO Heuristic và 2 giải thuật lập lịch cơ bản: • Giải thuật Random [6,7]. • Giải thuật Round Robin [8]. 2.5.2. Kết quả và đánh giá So sánh kết quả thực nghiệm trên 3 giải thuật: PSO Heuristic, Random, RoundRobin với mô hình luồng công việc trên hình 2 với dữ liệu tính toán dưới đây. Bảng 4: 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 PC3 PC 0 0.1 0.1 PC 0.1 0 0.1 PC 0.1 0.1 0 DST2,T3,T4[2 × 2] DataSize (MB) DST5[2 × 2] DataSize (MB) Input 10 Input 30 Output 10 Output 60 Số cá thể = 25; Số thế hệ = 30; Số lần lặp = 30; Trọng số quán tính w=0.85; Hệ số gia tốc: C1=1.5 và C2=0.5. Bảng 5: Kết quả tính toán chi phí thực thi workflow sau 30 lần chạy Lần lặp PSO Random RoundRobin 1 12600.1 45500 40000 2 24600 52500 40000 3 16000.6 35500 40000 4 30600 58000 40000 5 12600.1 36500 40000 6 12600.1 46500 40000 7 12600.1 42000 40000 8 24600 64500 40000 9 28000.3 56500 40000 146 Bài toán lập lịch Workflow trong môi trường điện toán đám mây 10 24600 25000 40000 11 12600.1 53000 40000 12 43000 27000 40000 13 16000.4 35500 40000 14 18000.4 42500 40000 15 24600 36500 40000 16 24600 41500 40000 17 18500.5 40000 40000 18 12600 34000 40000 19 24600 21000 40000 20 34200 40000 40000 21 16000.4 47500 40000 22 24600 22000 40000 23 30600 40000 40000 24 24600 49500 40000 25 12600.1 36500 40000 26 24600 54500 40000 27 16000.6 36500 40000 28 24600 54500 40000 29 12600.1 57000 40000 30 35000.3 30500 40000 TB 21623.47 42066.67 40000 Hình 4. Biểu đồ so sánh kết quả thực nghiệm workflow sau 30 lần chạy Nhận xét: chi phí thực thi workflow trên giải thuật lập lịch dựa PSO tiết kiệm chi phí (giảm một nửa chi phí) so với các giải thuật Random và RoundRobin. b. Workflow Chimera Số cá thể = 25; Số lần lặp = 45; Số lần thử nghiệm = 30 147 Kiều Tuấn Dũng, Nguyễn Thế Lộc, Phan Thanh Toàn Hình 5. Mô hình workflow Chimera Hình 6. Biểu đồ so sánh kết quả thực nghiệm workflow Chimera 3. Kết luận Bài báo trình bày một giải thuật lập lịch theo chiến lược tối ưu bầy đàn nhằm tối thiểu hóa chi phí thực thi của ứng dụng workflow trong môi trường đám mây. So sánh kết quả thực nghiệm với hai giải thuật Random và RoundRobin ta nhận thấy giải thuật đề xuất đã giảm được chi phí thực thi. Hướng nghiên cứu tiếp theo sẽ giải quyết các yêu cầu đa dạng hơn như tối thiểu thời gian thực thi, cân bằng tải trong điều kiện ràng buộc về thời gian... 148 Bài toán lập lịch Workflow trong môi trường điện toán đám mây TÀI LIỆU THAM KHẢO [1] 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. [2] Suraj Pandey, Rajkumar Buyya 2009. Scheduling and Management Techniques for Data-Intensive Application Workflows. IGI Global, USA. [3] Suraj Pandey, Kapil Kumar Gupta, Adam Barker and Rajkumar Buyya, 2010. Minimizing Execution Cost when using Globally Distributed Cloud Services, AINA 2010, Australia. [4] 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. [5] 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 2009, IEEE Press, New York, USA. [6] Michael Mitzenmacher, Eli Upfal, 2005. Probabiliti and Computing:Randomized Algorithms and Probabilistic Analysis. Cambridge University Press. [7] Don Fallis, 2000. The Reliabiliti of Randomized Algorithms. British Journal for the Philosophy of Science 51:255-71. [8] Silberschatz, Abraham; Galvin, Peter B.; Gagne, Greg,2010. M odern Information Retrieval. Operating System Concepts (8th ed.). John_Wiley_&_Sons (Asia). pp. 194. ISBN 978-0-470-23399-3. ABSTRACT Workflow scheduling problems in a cloud computing evironment For companies or enterprises, managing data and solving problems effectively with large amount of data is first privilege. To deal with them, enterprises have to invest different kinds of expenses such as: hardware, software, network, maintenance, repair, upgrade, management, securiti control and etc. Cloud computing can help them the meet the demand and can be chosen to use popularly by different kinds of companies and enterprises. When using cloud computing, enterprises only need to pay for workflow applications used (i.e. the work that needs several processes in order). They don’t need to invest in infrastructure and care bout technology too much. Cloud computing, however, makes some problems to cope with: use current distracted resource, reduce computing and communicating cost... Consequently, scheduling problem of workflow applications comes out and it is the main content of the paper. 149