Nghiên cứu và ứng dụng các thuật toán lập lịch vào môi trường tính toán lưới
TÓM TẮT
Nhờ có nhiều tiến bộ trong công nghệ mạng và các nguồn tài nguyên máy tính phong phú, công
nghệ tính toán lưới đã ra đời và hiện nay là một lĩnh vực nghiên cứu khá hiệu quả. Một đặc điểm
nổi bật của tính toán lưới đó là có thể kết hợp các nguồn tài nguyên phân tán rộng khắp và cung
cấp số lượng dịch vụ không nhỏ cho người sử dụng. Để đạt được các mục tiêu đó, hệ thống lập
lịch hiệu quả là một phần thiết yếu của lưới. Bài báo nghiên cứu và ứng dụng thuật toán lập lịch
trong mô hình tính toán lưới với mục đích làm giảm thiểu thời gian hệ thống cần thiết để hoàn tất
các ứng dụng. Một số thuật toán được nghiên cứu đó là: OLB, MCT, Min-Min, Max-Min,
Sufferage; đồng thời trong bài báo này đưa ra kết quả so sánh về tính hiệu quả giữa các thuật toán
này khi được áp dụng vào mô hình cụ thể.
Tóm tắt nội dung tài liệu: Nghiên cứu và ứng dụng các thuật toán lập lịch vào môi trường tính toán lưới
![Nghiên cứu và ứng dụng các thuật toán lập lịch vào môi trường tính toán lưới Nghiên cứu và ứng dụng các thuật toán lập lịch vào môi trường tính toán lưới](https://s1.tailieuvn.net/xb70nb5jd4llaq8g/thumb/2021/12/03/nghien-cuu-va-ung-dung-cac-thuat-toan-lap-lich-vao-moi-truon_Tibr1zrJVZ.jpg)
Tăng Cẩm Nhung Tạp chí KHOA HỌC & CÔNG NGHỆ 65(03): 134 - 138 134 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên NGHIÊN CỨU VÀ ỨNG DỤNG CÁC THUẬT TOÁN LẬP LỊCH VÀO MÔI TRƯỜNG TÍNH TOÁN LƯỚI Tăng Cẩm Nhung Trường Đại học Kỹ thuật Công nghiệp – ĐH Thái Nguyên TÓM TẮT Nhờ có nhiều tiến bộ trong công nghệ mạng và các nguồn tài nguyên máy tính phong phú, công nghệ tính toán lưới đã ra đời và hiện nay là một lĩnh vực nghiên cứu khá hiệu quả. Một đặc điểm nổi bật của tính toán lưới đó là có thể kết hợp các nguồn tài nguyên phân tán rộng khắp và cung cấp số lượng dịch vụ không nhỏ cho người sử dụng. Để đạt được các mục tiêu đó, hệ thống lập lịch hiệu quả là một phần thiết yếu của lưới. Bài báo nghiên cứu và ứng dụng thuật toán lập lịch trong mô hình tính toán lưới với mục đích làm giảm thiểu thời gian hệ thống cần thiết để hoàn tất các ứng dụng. Một số thuật toán được nghiên cứu đó là: OLB, MCT, Min-Min, Max-Min, Sufferage; đồng thời trong bài báo này đưa ra kết quả so sánh về tính hiệu quả giữa các thuật toán này khi được áp dụng vào mô hình cụ thể. Từ khóa: Tính toán lưới, lập lịch,OLB, MET,MCT,Max-Min, Min – Min, Sufferage, xSufferage *ĐẶT VẤN ĐỀ Cũng như các công nghệ tính toán khác, tính toán lưới (Grid Computing) ra đời xuất phát từ nhu cầu tính toán của con người. Thực tế, càng ngày càng có nhiều bài toán lớn và phức tạp hơn được đặt ra và do đó các tổ chức cũng cần phải có những năng lực tính toán mạnh mẽ hơn. Có thể giải quyết vấn đề này bằng hai cách: Thứ nhất: Đầu tư thêm trang thiết bị, cơ sở hạ tầng tính toán (mua thêm máy chủ, máy trạm, siêu máy tính, cluster...). Rõ ràng là cách làm này hết sức tốn kém. Thứ hai: Một cách thực hiện hiệu quả hơn là phân bố lại hợp lý các nguồn tài nguyên trong tổ chức hoặc thuê thêm các nguồn tài nguyên từ bên ngoài (dĩ nhiên là với chi phí rẻ hơn nhiều so với việc đầu tư cho cơ sở hạ tầng tính toán). Đây là mục tiêu chính của tính toán lưới Môi trường lưới cho phép kết hợp các hệ thống xử lý lại với nhau để giải quyết một cách hiệu quả các nhu cầu ngày càng cao của con người [6]. Đặc biệt, đây là một công nghệ có khả năng kết hợp các nguồn tài nguyên từ những tổ chức khác nhau, phân tán trên phạm vi địa lý rộng và đặc biệt là không đòi hỏi các nguồn tài nguyên phải tương đồng về cấu trúc [7]. Bài toán lập lịch là một trong những vấn đề quan trọng được nghiên cứu trong các môi trường tính toán, đặc biệt là các môi trường * Tel: 0988724824; Email: tính toán phân tán như môi trường tính toán lưới. Do đặc thù của môi trường lưới như: số lượng công việc và các nguồn tài nguyên thường rất lớn. Mặt khác các tài nguyên này còn nằm phân tán và hỗn tạp, mỗi nguồn tài nguyên có thể do một tổ chức riêng biệt quản lý, có các chính sách và chi phí hoạt động khác nhau, bên cạnh đó tải (load) và tính sẵn sàng (availability) của các hệ thống cũng rất khác nhau; do đó vấn đề lập lịch (scheduling) trong hệ thống lưới có nhiều khó khăn và thách thức hơn so với môi trường khác, hiện tại vẫn còn đòi hỏi nhiều công sức nghiên cứu [3] GIỚI THIỆU BÀI TOÁN LẬP LỊCH TRONG MÔI TRƯỜNG LƯỚI[1] Bài toán lập lịch là một trong những vấn đề quan trọng được nghiên cứu trong các môi trường tính toán, đặc biệt là các môi trường tính toán phân tán như môi trường tính toán lưới. Quá trình lập lịch là quá trình quyết định sẽ thực thi công việc tại một nguồn tài nguyên cụ thể nào và vào thời điểm nào là thích hợp nhất do đó sẽ ảnh hưởng rất lớn đến hiệu năng hoạt động của hệ thống. Có khá nhiều vấn đề được đặt ra và cần giải quyết khi nghiên cứu về quá trình lập lịch trong môi trường tính toán lưới: Mối liên hệ và tác động lẫn nhau giữa các ứng dụng trong quá trình thực thi. Những đòi hỏi, yêu cầu khác nhau của từng ứng dụng trong hệ thống. Sự không đồng nhất và biến động của các nguồn tài nguyên trong môi trường. Tăng Cẩm Nhung Tạp chí KHOA HỌC & CÔNG NGHỆ 65(03): 134 - 138 135 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Mô hình hoạt động và các chính sách về truy xuất, bảo mật của hệ thống. CÁC THUẬT TOÁN ÁP DỤNG TRONG BÀI TOÁN LẬP LỊCH THEO HIỆU NĂNG CỦA HỆ THỐNG Mục đích của phương pháp này hướng đến mục đích giảm tối đa thời gian hệ thống cần thiết để hoàn tất các ứng dụng, thời gian này được gọi là makespan của hệ thống. Một số hướng tiếp cận được đề cập đến như OLB, MCT, Min-Min, Max-Min, Sufferage OLB (Opportunistic Load Balancing) Đây là chiến lược rất đơn giản, phân phối công việc cho tài nguyên có thời điểm sẵn sàng sớm nhất mà không quan tâm đến thời gian thực thi của công việc trên tài nguyên đó. MET (Minimum Execution Time)[3] Ngược lại với OLB, phân phối công việc vào các tài nguyên có khả năng thực thi công việc nhanh nhất, không quan tâm đến thời điểm bắt đầu và kết thúc của công việc trên tài nguyên đó. Giải thuật này thường có nhược điểm là không cân bằng tải vì hầu như các công việc đều được tập trung thực thi trên các tài nguyên có năng lực cao nhất Giả sử ta có 2 tác vụ cần thực thi là T1,T2. Các tác vụ lần lượt có kích thước T1=60, T2=120 [5]. Hệ thống có 2 máy tính cụm, mỗi máy tính cụm có 2 máy tính (host), năng lực lần lượt là: Cluster 1: H1=30, H2=60 Cluster 2: H3=45, H4=50 Gọi Eij = Ti/Hj là thời gian thực thi của tác vụ i trên host j, ta có: E11=T1/H1=2 E21=T2/H1=4 E12=T1/H2=1 (nhỏ nhất) E22=T2/H2=2 (nhỏ nhất) E13=T1/H3=1.3 E23=T2/H3=2.6 E14=T1/H4=1.2 E24=T2/H4=2.4 Như vậy cả 2 tác vụ đều thực thi trên host H2, makespan của hệ thống = 1 + 2 = 3 MCT (Minimum Completion Time) [3] Dựa trên khái niệm thời gian hoàn thành nhỏ nhất của tác vụ. Thời gian hoàn thành được tính bằng thời gian thực thi của tác vụ cộng với thời gian sẵn sàng của tài nguyên. Việc dựa trên thời gian hoàn thành nhỏ nhất sẽ giúp hệ thống cân bằng tải tốt hơn. Áp dụng với các số liệu tương tự như mục 3.2, ta định nghĩa Cij = Bj + Eij với Cij là thời gian hoàn thành của tác vụ i trên host j, Bj là thời gian sớm nhất host j có thể thực thi tác vụ (thời gian sẵn sàng). C11= B1 + E11 = 0 + 2 = 2 C21= B1 + E21 = 0 + 4 =4 C12= B2 + E12 = 0 + 1 = 1 C22= B2 + E22 = 0 + 2 =2 C13= B3 + E13 = 0 + 1.3 = 1.3 C23= B3 + E23 = 0 + 2.6 = 2.6 C14 =B4 + E14 = 0 + 1.2 = 1.2 C24 = B4 + E24 = 0 + 2.4 = 2.4 Tác vụ T1 theo thứ tự được chọn tài nguyên trước, sẽ chọn thực thi trên host H2 (thời gian hoàn thành thấp nhất). Thời gian bắt đầu B2 được cập nhật thành 1, vì chỉ sau thời điểm này H2 mới có thể thực thi các tác vụ khác. Giá trị E22 thay đổi: B2=1 C22 = B2 + E22= 1 + 2 = 3 > 2.4 Như vậy tác vụ T2 sẽ thực thi trên Host H4 vì có C24 nhỏ nhất. Thời gian thực thi toàn hệ thống makespan = 2.4 vì T1, T2 chạy song song trên 2 host khác nhau. Chúng ta có thể thấy, dựa vào giá trị MCT hệ thống sẽ cân bằng hơn dựa vào giá trị MET. Giải thuật Min – Min [2] Giải thuật Min – Min sẽ tính toán thời gian hoàn thành của tất cả các tác vụ trên tất cả các tài nguyên hiện có. Tác vụ nào có giá trị MCT nhỏ nhất sẽ được phép chọn tài nguyên trước. Sau đó cập nhật thời gian sẵn sàng cho tài nguyên được chọn, tính toán lại thông số với tất cả các tác vụ chưa được điều phối. Quá trình lặp lại cho đến khi tất cả các tác vụ đều đã chọn được tài nguyên thực thi. Ta định nghĩa một số khái niệm: T là tập các tác vụ, Hj,k là máy (host) thứ k của cluster j. C(Ti,Hj,k) là thời gian hoàn thành tác vụ Ti trên host Hj,k. Gọi f là một ánh xạ từ Rn vào R, toán tử argmin được định nghĩa: ))((min))(min(arg xfxff Rx n Rx n Chú thích: Giá trị C(Ti,Hj,k) là thời gian hoàn thành của tác vụ Ti trên host Hj,k. Lúc này Tăng Cẩm Nhung Tạp chí KHOA HỌC & CÔNG NGHỆ 65(03): 134 - 138 136 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên nếu argminj, k (C(Ti,Hj,k))gồm 2 thành phần( 11, ii hc ) thì giá trị ),( 11 , ii hci HTC là nhỏ nhất . Host 1 ih trên cluster 1 ic là host có khả năng hoàn tất tác vụ Ti sớm nhất. Giải thuật Min-Min: while(T≠ ) foreach ( TTi ) ( )),((minarg, ,, 11 kjikjii HTChc ) endfor s= )),((minarg 1,1 ihic ii HTC 1,1 shsc s HT T=T-{T} endwhile Áp dụng với các số liệu mục 2 C11= B1 + E11 = 0 + 2 = 2 C21= B1 + E21 = 0 + 4 =4 C12= B2 + E12 = 0 + 1 = 1 (min) C22= B2 + E22 = 0 + 2 =2 (min) C13= B3 + E13 = 0 + 1.3 = 1.3 C23= B3 + E23 = 0 + 2.6 = 2.6 C14 =B4 + E14 = 0 + 1.2 = 1.2 C24 = B4 + E24 = 0 + 2.4 = 2.4 Giá trị MCT(T1)= C12 =1 , MCT(T2)=C22=2 MCT(T1) nhỏ hơn, do đó tác vụ T1 được chọn host H1 để thực thi trước. Giá trị E22 thay đổi: B2=1, C22 = B2 + E22= 1 + 2 = 3 > 2.4 Như vậy tác vụ T2 sẽ thực thi trên Host H4 vì có C24 nhỏ nhất. Thời gian thực thi toàn hệ thống makespan = 2.4 vì T1, T2 chạy song song trên 2 host khác nhau. Giải thuật Max-Min [2] Tương tự như giải thuật Min-Min, tuy nhiên giải thuật Max-Min cho phép các tác vụ có MCT lớn hơn được ưu tiên chọn host để thực thi trước. Giải thuật này được đánh giá tốt và cân bằng hơn Min-Min vì trong khi các tác vụ dài hơn được ưu tiên chọn thiết bị tốt để thực thi trước, các tác vụ ngắn có thể luân phiên thực thi ở các thiết bị có năng lực yếu hơn. Các tác vụ dài không phải mất thời tác vụ ngắn hơn như ở giải thuật Min-Min. Toán tử argmax được định nghĩa tương tự toán tử argmin ))((max))(max(arg xfxff Rx n Rx n Giải thuật Max-Min: while(T≠ ) foreach( TTi ) ( )),((minarg, ,, 11 kjikjii HTChc ) endfor s= )),((maxarg 1,1 ihic ii HTC 1,1 shsc s HT T=T-{T} endwhile Áp dụng với các số liệu như mục 2 C11= B1 + E11 = 0 + 2 = 2 C21= B1 + E21 = 0 + 4 =4 C12= B2 + E12 = 0 + 1 = 1 (min) C22= B2 + E22 = 0 + 2 =2 (min) C13= B3 + E13 = 0 + 1.3 = 1.3 C23= B3 + E23 = 0 + 2.6 = 2.6 C14 =B4 + E14 = 0 + 1.2 = 1.2 C24 = B4 + E24 = 0 + 2.4 = 2.4 Giá trị MCT(T1)= C12 =1,MCT(T2)=C22=2 Lúc này tác vụ T2 có MCT lớn hơn nên được phép chọn host thực thi trước. T2 sẽ thực thi trên host H2. Giá trị B2 = 2, C12 = B2 + E12 = 2 + 1 =3 > 1.2 Như vậy, sau đó tác vụ T1 sẽ thực thi trên host H4 vì lúc này C14 =1.2 là nhỏ nhất Thời gian hoàn thành của hệ thống makespan = 2 vì T1, T2 chạy song song (nhỏ hơn với giải thuật Min-Min) Giải thuật Sufferage Suferage lấy ý tưởng từ giải thuật Min-Min và Max-Min đã đề ra trước đó[1]. Giải thuật Sufferage tính toán giá trị MCT thấp thứ nhất và thấp thứ hai đối với từng tác vụ trong hệ thống. Giá trị này được gọi là độ “thiệt hại” (suffering) của một tác vụ khi nó không được thực thi trên tài nguyên tốt nhất. Tác vụ có độ thiệt hại lớn nhất sẽ được ưu tiên chọn tài nguyên để thực thi trước. Giải thuật Suferage while(T≠ ) foreach ( TTi ) ( )),((minarg), ,, 11 kjikjii HTChc Tăng Cẩm Nhung Tạp chí KHOA HỌC & CÔNG NGHỆ 65(03): 134 - 138 137 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên )),((minarg),( ,1,1 22 kji ihkicj ii HTChc su fi= )),(),( 1,12,2 ihic i ihic i HTCHTC endfor S= )(maxarg ii suf 1,1 shsc s HT T=T-{T} endwhile Giải thuật này đặc biệt hiệu quả nếu tính đến vấn đề vận chuyển dữ liệu đến nơi thực thi Giải thuật này đặc biệt hiệu quả nếu tính đến vấn đề vận chuyển dữ liệu nơi thực thi tác vụ. Nếu một tài nguyên đã có sẵn dữ liệu của một tác vụ, tác vụ nếu thực thi trên tài nguyên này sẽ tiết kiệm được thời gian rất nhiều so với khi thực thi trên một tài nguyên khác. Tác vụ trong trường hợp này sẽ có giá trị Sufferage cao nên được Áp dụng với các số liệu như mục 2 Giá trị Suff (T1)= C14 – C12 = 0.2 Giá trị Suff (T2)= C24 – C22 = 0.4 Vì suff (T2) cao hơn nên tác vụ T2 được phép chọn host H2 để thực thi trước. Giá trị B2 = 2 C12 = B2 + E12 = 2 + 1 = 3 > 1.2 Như vậy, sau đó tác vụ T1 sẽ thực thi trên host H4 vì lúc này C14 = 1.2 là nhỏ nhất Thời gian hoàn thành của hệ thống makespan = 2 vì T1, T2 chạy song song. C11= B1 + E11 = 0 + 2 = 2 C21= B1 + E21 = 0 + 4 =4 C12= B2 + E12 = 0 + 1 = 1 (min) C22= B2 + E22 = 0 + 2 =2 (min) C13= B3 + E13 = 0 + 1.3 = 1.3 C23= B3 + E23 = 0 + 2.6 = 2.6 C14 =B4 + E14 = 0 + 1.2 = 1.2 C24 = B4 + E24 = 0 + 2.4 = 2.4 Ví dụ ở trên khá đơn giản, chỉ có chiều dài tác vụ ảnh hưởng đến thời gian thực thi của tác vụ nên trường hợp Sufferage khá giống Max – Min. Giải thuật XSufferage Do nhóm nghiên cứu Casanova đề ra, phát triển từ thuật toán Sufferage[1]. Các máy tính trong một Máy tính cụm thường có năng lực như nhau, do đó giá trị sufferage thường dần về 0. Điều này khiến một tác vụ Ti, khi rất cần chạy trên máy tính cụm j (ví dụ dữ liệu input của Ti đã nằm sẵn trên máy tính cụm j), nhưng trong trường hợp máy tính cụm này lại có 2 máy năng lực tương đương nhau khiến Suff(Ti) ≈ 0 nên Ti sẽ không có cơ hội chạy trên máy tính cụm j. Cải tiến ở đây là khái niệm Suf sẽ được tính ở mức cluster, không phải ở mức host. Giải thuật while(T≠ ) foreach ( TTi ) foreach clusterj hi,j= )),((minarg ,kjik HTC endforeach )),((minarg ,, 1 jihjiji HTCc )),((minarg ,,1 2 jihji icj i HTCc sufi= )),(),( 1,12,2 ihic i ihic i HTCHTC endforeach s= )(maxarg ii suf 1, ,1 scs hsc s HT T=T-{T} Endwhile KẾT LUẬN Bài báo đã nêu ra cái nhìn tổng quan nhất về vấn đề lập lịch trong môi trường lưới, và các thuật toán cụ thể được áp dụng cho lưới và các đặc điểm của giải thuật trên đó là: Phải duyệt tất cả các máy trong mọi máy tính cụm có thể dẫn đến độ phức tạp rất lớn. Ứng dụng rất lớn gồm nhiều tác vụ chạy song song, các tác vụ đóng vai trò như nhau. Một tác vụ có thể chạy trên host bất kỳ, không có sự ràng buộc về địa điểm thực thi. Từ cơ sở lý thuyết của các thuật toán đó đã được áp dụng vào hệ thống lưới gồm có hai máy tính cụm để chứng minh về tính hiệu quả của từng thuật toán đã được nêu ra. Tăng Cẩm Nhung Tạp chí KHOA HỌC & CÔNG NGHỆ 65(03): 134 - 138 138 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên TÀI LIỆU THAM KHẢO [1] Fangpeng Dong and Selim G. Akl, January 2006, Scheduling Algorithms for Grid Computing:State of the Art and Open Problems, Technical Report No. 2006-504, [3] Kousalya.K and Balasubramanie.P, April 2008, An Enhanced Ant Algorithm for Grid Scheduling Problem, IJCSNS International Journal of Computer Science and Network Security, VOL.8 No.4, [4] Saurabh Kumar Garg , Rajkumar Buyya and H. J. Siegel, 2009, Scheduling Parallel Applications on Utility Grids:Time and Cost Trade-off Management, Proc. 32nd Australasian Computer Science Conference (ACSC 2009), Wellington, New Zealand [5] Graham Ritchie and John Levine, A fast, effective local search for scheduling independent jobs in heterogeneous computing environments. [6] Ian Foster, C. Kesselman ,Computational Grids, Chapter 2 Of "The Grid:Blueprint For A New Computing Infrastructure", Morgan- Kaufman, 1999. RESEARCH AND APPLY SCHEDULE ALGORITHMS TO GRID COMPUTING ENVIRONMENTS Tang Cam Nhung 2 Thai Nguyen University of Tecnology Thanks to advances in wide-area network technologies and the low cost of computing resources, Grid computing came into being and is currently an active research area. One motivation of Grid computing is to aggregate the power of widely distributed resources, and provide non-trivial services to users. To achieve this goal, an efficient Grid scheduling system is an essential part of the Grid. This paper refers to the scheduling problem of grid system and some of scheduling algorithms applied to grid computing model so may reduce the maximum system time needed to complete the application. The algorithms are: OLB, MCT, Min-Min, Max-Min, Sufferage and in this paper is to compare the results of efficiency between algorithms when the applied to specific models. Keywords: grid computing, schedule, Opportunistic Load Balancing, Minimum Execution Time, Minimum Completion Time, Max-Min, Min – Min, Sufferage, xSufferage 2 Tel: 0988724824; Email:
File đính kèm:
nghien_cuu_va_ung_dung_cac_thuat_toan_lap_lich_vao_moi_truon.pdf