Thuật toán lập lịch luồng công việc theo phương pháp tối ưu bày đàn trong môi trường điện toán đám mây - Phan Thanh Toàn

Công nghệ thông tin & Khoa học máy tính P.T.Toàn, N.T.Lộc, N.D.Cường, Đ.N.Long, “Thuật toán lập lịch ... điện toán đám mây.” 132 THUẬT TOÁN LẬP LỊCH LUỒNG CÔNG VIỆC THEO PHƯƠNG PHÁP TỐI ƯU BÀY ĐÀN TRONG MÔI TRƯỜNG ĐIỆN TOÁN ĐÁM MÂY Phan Thanh Toàn1*, Nguyễn Thế Lộc1, Nguyễn Doãn Cường2, Đỗ Như Long2 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 phải 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 đạt hiệu quả tốt nhất, đây chính là bài toán quan trọng nhất tại các trung tâm điện toán đám mây. Bài báo này đề xuất 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 thuật toán PSO để 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 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. ĐẶT VẤN ĐỀ Điện toán đám mây là sự tích hợp của nhiều công nghệ thuộc lĩnh vực công nghệ thông tin và truyền thông nhằm cho phép người dùng truy cập đến những dịch vụ từ các nhà cung cấp. Đám mây gồm nhiều máy chủ, các tác vụ (task - khối công việc tương đối độc lập) sẽ được xếp lịch thực hiện tại các máy chủ sao cho hiệu quả đạt được là cao nhất. Lập lịch thực thi luồng công việc (workflow) là vấn đề quan trọng nhất của trung tâm điều khiể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. Bài toán lập lịch workflow từ lâu đã được chứng minh là thuộc lớp NP-Complete [4] do vậy nó thường được giải quyết 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. Nội dung của bài báo gồm:1. Giới thiệu bối cảnh thực tế tại trung tâm điện toán đám mây, 2. Phát biểu bài toán và xây dựng mô hình toán học cho vấn đề thực thi luồng công việc trong môi trường đám mây, 3. Giới thiệu tóm tắt về chiến lược tối ưu bày đàn PSO [1], và đề xuất một thuật toán lập lịch mới gọi là PSO-WS để giải quyết bài toán. Để kiểm chứng hiệu năng của thuật toán đề xuất, 4. Trình bày các thực nghiệm tiến hành trên môi trường mô phỏng thông qua công cụ CloudSim. [4,5,10]. Các kết quả được phân tích để so sánh PSO-WS với giải thuật PSO Heuristic và 2 giải thuật lập lịch cơ bản là Random [6][7] và Round Robin [8]. 2. BÀI TOÁN TỐI THIỂU HÓA CHI PHÍ 2.1. Phát biểu bài toán Giả sử chúng ta cần phải sắp xếp lịch biểu cho một luồng công việc gồm n tác vụ trong một môi trường điện toán đám mây với các yêu cầu và giả thiết 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 tác vụ gốc (tác vụ vào) và một tác vụ ra (output) + Đám mây có N máy chủ tính toán và K máy chủ lưu trữ sẵn sàng hoạt động. Mỗi tác vụ được thực thi trên một và chỉ một máy chủ + Chi phí vận hành mỗi máy chủ do nhà cung cấp dịch vụ cung cấp theo một đơn giá 2.2. Mô hình toán học của bài toán Tối thiểu chi phí thực thi luồng công việc Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 133 Chúng ta ký hiệu: 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 tác vụ, E là tập cạnh của đồ thị thể hiện mối quan hệ giữa các tác vụ. 3) Tập các tác vụ V ={T1, T2,,TM}. 4) Cạnh e =(Ti, Tj)  E cho biết tác vụ cha Ti thực hiện trước và sẽ chuyển cho tác vụ con Tj một khối lượng dữ liệu xác định. 5) Khối lượng tính toán của Ti kí hiệu là Wi đo bằng đơn vị flop (floating point operations). 6) Năng lực xử lý của một máy chủ được biểu diễn bởi 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 flop trên máy chủ (excution cost) được biểu diễn thông qua 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 với băng thông biểu diễn thông qua hàm số B () : SxS  R+ ;(Si, Sj)  B(Si, Sj) Giả sử hàm B( ) thỏa mãn các điều kiện sau: - B(Si, Si) =  (băng thông tại chỗ lớn 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) Giá trị của hàm băng thông B( ) được cung cấp bởi nhà cung cấp dịch vụ 9) Khối lượng dữ liệu giữa Ti và Tk (kí hiệu là Dik) là hằng số cho biết trước 10) Đơn giá cước truyền giữa 2 máy chủ (Communication Cost), đơn vị là dolar/bit, được biểu diễn thông qua hàm số C: SxS  R+; (Si, Sk)  C(Si, Sk) Giả sử hàm C( ) có tính đối xứng: C(Si, Sk) = C(Sk, Si) 11) Mỗi phương án xếp lịch là một ánh xạ f( ) : T  S; Ti  f(Ti); Trong đó f(Ti) là máy chủ chịu trách nhiệm thực thi tác vụ Ti Từ đó suy ra:  Thời gian tính toán của tác vụ Ti là: Wi / P(f(Ti) ) (i=1,2, ... M)  Chi phí tính toán của tác vụ Ti là: Wi E(f(Ti))  Thời gian truyền dữ liệu giữa tác vụ Ti và tác vụ con Tk là: Dik / B(f(Ti),f(Tk))  Chi phí truyền thông giữa tác vụ Ti và tác vụ con Tk là: DikC(f(Ti),f(Tk)) 12) Chi phí thực thi Ti trên máy chủ f(Ti) là phí tính toán cộng với phí truyền thông giữa Ti với các tác vụ con Tj. 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 tác vụ trong luồng. Hàm mục tiêu được xác định như sau:           MinTfTfCDTfEW M i M k kiik M i ii     1 11 , (1) Hình 1: Đồ thị luồng công việc với 15 task. Công nghệ thông tin & Khoa học máy tính P.T.Toàn, N.T.Lộc, N.D.Cường, Đ.N.Long, “Thuật toán lập lịch ... điện toán đám mây.” 134 3. THUẬT TOÁN ĐỀ XUẤT PSO (Particle Swarm Optimization) là thuật toán tiến hóa được đề xuất bởi R. Eberhart và J. Kennedy năm 1995 [1,2] lấy ý tưởng từ 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 PSO sẽ tạo ra một quần thể gồm nhiều cá thể ở những vị trí ngẫu nhiên, mỗi cá thể tượng trưng cho một phương án của bài toán. Các cá thể sẽ đi tìm mồi, tức là di chuyển trong không gian lời giải để tìm kiếm lời giải tối ưu. Trong quá trình tìm kiếm mỗi các thể sẽ di chuyển theo hướng tổng hợp từ ba thành phần là hướng đi hiện tại, hướng đi tốt nhất của cả bầy và hướng đi tốt nhất của chính mình cho tới thời điểm hiện tại. Dựa trên tư tưởng tối ưu bày đàn và mô hình bài toán đã trình bày ở phần 3, chúng tôi đề xuất một giải thuật với tên gọi PSO- WS gồm những bước như dưới đây. 3.1. Mã hóa cá thể Mỗi cá thể trong quần thể được biểu diễn bởi 2 thành phần cơ bản là vector vị trí (positon) và vector chuyển động (velocity). Vector vị trí có số chiều bằng số tác vụ. Cả 2 vector được mô tả thông qua một cấu trúc dữ liệu bảng băm Hashtable position Hashtable velocity Ví dụ : Luồng công việc gồm 5 tác vụ T1, T2, T3, T4, T5 và 3 máy chủ S1, S2, S3. Một cá thể được mã hóa như sau: T1 T2 T3 T4 T5 S1 S2 S1 S3 S2 Nghĩa là T1, T3 được thực hiện trên S1; T2 và T5 trên S2 còn T4 được thực hiện trên S3 3.2. Mã hóa tác vụ Mỗi tác vụ được xác định bởi 3 đại lượng là (i) khối lượng tính toán cần thực hiện, (ii) kích thước dữ liệu xuất ra của tác vụ và (iii) danh sách các tác vụ phụ thuộc. 3.3. Biểu diễn dữ liệu 3.3.1. Chi phí thực thi tác vụ trên máy chủ Chi phí này được biểu diễn dưới dạng bảng và ta sử dụng cấu trúc bảng băm như sau Hashtable> TH_matrix; Bảng 1. Chi phí thực thi của các tác vụ Ti trên các máy chủ Si. TP[5x3] S1 S2 S3 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 3.3.2. Chi phí truyền thông giữa các máy chủ Chi phí này cũng được biểu diễn thông qua cấu trúc bảng băm tương tự Hashtable> HH_matrix; Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 135 Bảng 2. Chi phí truyền thông giữa các PC. PP[3x3] S1 S2 S3 S1 0 0.17 0.21 S2 0.17 0 0.22 S3 0.21 0.22 0 Trong đó PP[i,j] là chi phí truyền thông giữa Si và Sj (giá trị theo đơn vị $/MB/giây). 3.3.3. Dữ liệu vào/ra giữa các tác vụ 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 bảng băm như sau để lưu trữ: Hashtable> edge_weight Bảng 3. Kích thước input/output của tác vụ i. DT2,T3,T4 [2x2] total data DT5 [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). 3.4. Thuật toán PSO-WS 1. Tính ma trận chi phí thực thi các tác vụ trên các host, ma trận chi phí truyền thông giữa các host và ma trận khối lượng dữ liệu vào/ra giữa các tác vụ 2. Khởi tạo danh sách tác vụ sẵn sàng gồm tất cả tác vụ, danh sách tác vụ chưa lập lịch gồm tất cả tác vụ 3. Repeat 4. for each Ti in readyTask do 5. Gán Ti cho thực hiện trên máy chủ Sj theo chiến lược PSO 6. end for 7. Chờ xử lý công việc (phụ thuộc dữ liệu đầu vào và đầu ra giữa tác vụ cha-con). 8. Cập nhật lại readyTask ,các tác vụ ở trạng thái “ready”, và phí giao tiếp giữa các tài nguyên 9. Tính toán PSO({Tj}). 10. Until <không còn tác vụ nào chưa được lập lịch> end procedure Bắt đầu: Tính ma trận chi phí thực thi task trên host Tính ma trận chi phí truyền thông giữa các host Tính ma trận khối lượng dữ liệu vào/ra giữa các task Khởi tạo các task sẵn sàng Tìm kiếm PSO_Algorithm(readyTasks) Còn task chưa lập lịch? Xử lý công việc(phụ thuộc dữ liệu vào/ra giữa các task cha-con) Cập nhật các task ở trạng thái ready Cập nhật lại các chi phí đúng sai KẾT THÚC Công nghệ thông tin & Khoa học máy tính P.T.Toàn, N.T.Lộc, N.D.Cường, Đ.N.Long, “Thuật toán lập lịch ... điện toán đám mây.” 136 4. 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 PSO-WS bằng ngôn ngữ Java với sự trợ giúp của gói thư viện JSwarm [9] và công cụ mô phỏng CloudSim [4,5,10]. Hình 2 cho thấy kết quả thực nghiệm được so sánh giữa giải thuật PSO-WS với 3 giải thuật khác là: PSO_Heuristic, Random [6,7], RoundRobin [8] 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] S1 S2 S3 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] S1 S2 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 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 = 0.85 và 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- WS PSO_ Heuristic Random Round Robin Lần lặp PSO- WS PSO_ Heuristic Rand om Round Robin 1 12.500 12.500 45500 40000 16 12.500 12.500 2700 0 40000 2 12.500 12.500 52500 40000 17 16.500 12.500 355 0 40000 3 18.500 25.000 35500 40000 18 12.500 18.500 425 0 40000 4 16.000 12.500 58000 40000 19 12.500 25.000 365 0 40000 5 12.500 12.500 36500 40000 20 12.500 12.500 465 40000 6 12.500 12.500 46500 40000 21 12.500 12.500 4200 40000 7 12.500 12.500 42000 40000 22 12.500 12.500 6450 0 40000 8 16.500 18.500 64500 40000 23 16.000 12.500 565 0 40000 9 12.500 12.500 56500 40000 24 12.500 12.500 250 0 40000 10 12.500 12.500 25000 40000 25 16.000 18.500 455 0 40000 11 12.500 12.500 53000 40000 26 12.500 25.000 525 40000 12 16.500 12.500 27000 40000 27 12.500 12.500 3550 40000 13 12.500 18.500 35500 40000 28 12.500 12.500 5800 0 40000 14 12.500 12.500 42500 40000 29 12.500 12.500 365 0 40000 15 12.500 12.500 36500 40000 30 12.500 18.500 465 0 40000 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 37, 06 - 2015 137 Nhận xét: giải thuật lập lịch PSO-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 đã sử dụng các trọng số quán tính w = 0.85, hệ số gia tốc C1 = 1.5 và C2 = 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 PSO-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 toán PSO-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 PSO-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 PSO-WS sẽ cho kết quả nhỏ nhất. 5. 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. TÀI LIỆU THAM KHẢO [1]. Suraj Pandey, Linlin Wu, Siddeswara Guru, and Rajkumar Buyya, A Particle Swarm Optimization (PSO)-based Heuristic for Scheduling Workflow Applications in Cloud Computing Environments, AINA 2010, Australia, April, 2010. [2]. Suraj Pandey, Rajkumar Buyya. Scheduling and Management Techniques for Data- Intensive Application Workflows, IGI Global, USA, 2009. [3]. Suraj Pandey, Kapil Kumar Gupta, Adam Barker and Rajkumar Buyya, Minimizing Execution Cost when using Globally Distributed Cloud Services, AINA 2010, Australia, April 2010. [4]. Rodrigo N. Calheiros, Rajiv Ranjan, Anton Beloglazov, Cesar A. F. De Rose, and Rajkumar Buyya, 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, January, 2011. [5]. Rajkumar Buyya, Rajiv Ranjan and Rodrigo N. Calheiros, 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. Probability and Computing:Randomized Algorithms and Probabilistic Analysis, April 2005. Cambridge University Press. [7]. Don Fallis. 2000. The Reliability of Randomized Algorithms. British Journal for the Philosophy of Science 51:255–71. [8]. 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. [9]. Thư viện JSwarm [10]. Công cụ mô phỏng CloudSim Công nghệ thông tin & Khoa học máy tính P.T.Toàn, N.T.Lộc, N.D.Cường, Đ.N.Long, “Thuật toán lập lịch ... điện toán đám mây.” 138 [11]. Phan Thanh Toàn, Kiều Tuấn Dũng, Nguyễn Thế Lộc, Nguyễn Doãn Cường, Sắp xếp lịch biểu thực thi luồng công việc tại Đám mây điện toán, Kỷ yếu hội thảo quốc gia lần thứ XVI: Một số vấn đề chọn lọc của Công nghệ thông tin và truyền thông, Đà Nẵng, 2013. [12]. V. Krishna Reddy, B. Thirumala Rao, Dr. L.S.S. Reddy, P. Sai Kiran, Research Issues in Cloud Computing, Global Journal of Computer Science and Technology, Volume 11 Issue 11, 7/2011, Global Journals Inc. (USA), ISSN: 0975-4350. [13]. Kennedy, J.; Eberhart, R. Particle Swarm Optimization. Kỷ yếu hội thảo IEEE International Conference on Neural Networks, ICNN, (1995). ABSTRACT A PARTICLE SWARM OPTIMIZATION-BASED WORKFLOW SCHEDULING ALGORITHM IN THE CLOUD ENVERONMENT Workflow is the series of tasks that are necessary to complete a goal. Workflow scheduling, the most important problem which the cloud controllers deal with, focuses on mapping and managing the execution of tasks on servers so that the expenses is the minimum. In this paper, we build a workflow scheduling framework which run on the cloud computing environments. In order to solve the mentioned problem, we propose a PSO-based algorithm for scheduling workflow tasks in the cloud environments so that the total cost is minimized. Keywords: Workflow scheduling, Workflow applications, Cloud computing. Nhận bài ngày 29 tháng 12 năm 2014 Hoàn thiện ngày 30 tháng 3 năm 2015 Chấp nhận đăng ngày 12 tháng 06 năm 2015 Địa chỉ : 1Đại học Sư phạm Hà Nội; *Email : pttoan@hnue.edu.vn; 2Viện Công nghệ Thông tin- Viện Khoa học và Công nghệ quân sự.