I H C QU C GIA TP HCM I H C BÁCH KHOA Hu nh Nguyên L c NGHIÊN C U GI I THU T L P L CH CHO D NG TÍNH TỐN HI N Chun ngành : Khoa h c máy tính Mã s 604801 LU TP H CHÍ MINH, tháng 11 NG 2013 C HỒN THÀNH T I I H C BÁCH KHOA -HCM Cán b ng d n khoa h c : PGS TS Tho i Nam Cán b ch m nh n xét : TS Tr n Ng c Minh Cán b ch m nh n xét : TS Ph Lu c b o v t i Tr HCM ngày 25 tháng 12 2013 u ng i h c Bách Khoa, HQG Tp Thành ph n H i ng nh giá lu n v n th c s g m: (Ghi rõ h , tên, h c hàm, h c v c a H i ng ch m b o v lu n v n th c s ) PGS TS Tho i Nam TS Tr n Ng c Minh TS Ph u TS Ph m Tr TS Lê Thành Sách Xác nh n c a Ch t ch H i ng h giá LV ng Khoa qu n lý chuyên ngành sau lu n v n ã c s a ch a (n u có) CH T CH H NG NG KHOA IH C GIA TP.HCM I H C BÁCH KHOA C NG HÒA XÃ CH T NAM c l p - T - H nh phúc NHI M V LU MSHV: 11070458 30/11/1988 Chuyên ngành: I :604801 TÀI: NGHIÊN C U GI I THU T L P L CH CHO NG D NG TÍNH TỐN HI U II NHI M V VÀ N I DUNG: Nghiên c u th hi m c a h th nh th i hi n có h p cho ng d ng tính tốn xu t gi i thu t ánh x tác v c a ng d ng tính tốn hi vào m Hi n th i thu xu t so v i m t s gi i thu III NGÀY GIAO NHI M V :02/07/2012 IV NGÀY HOÀN THÀNH NHI M V :22/11/2013 V CÁN B NG D N:PGS TS Tho i Nam Tp HCM, ng CÁN B NG D N CH NHI M B NG KHOA KH & KT MT O u tiên, xin g i l i th Tho i Nam Trong su t trình th c hi n lu h tr Nh ng l ng d n c a PGS TS th ng d n t n tình c a th y ngu ng l c l n nh t cho tơi hồn thành lu Bên c il n b n h c viên cao h c khóa 2011, v nh ng h tr chia s su t q trình tơi th c hi n lu Và cu i cùng, xin g i l d a tinh th n v ng ch c, c n bè nh i t trình h c t p, nghiên c u TP H Chí Minh tháng 11/2013 Hu nh Nguyên L c I Trong nh cho vi xu t hi n c ng nhu c u tính tốn c a nhóm nghiên c u v a nh d c cho nhóm nghiên c u h th ng máy tính riêng l h tr cho ho ng nghiên c u c a mình, tài ngun tính tốn s t p trung t i m t ho c m c qu mây Các nhóm nghiên c u s c u cho ho c c cung c ng c a c n thi t Tuy nhiên, khác v i ng d ng ch v web v ct i , ng d ng có nhu c u s d ng l i ng d ng tính tốn hi thơng, b nh i nhi u tài nguyên, nhi u ràng bu tr t s có th tri n khai v i hi th Vì th , v có th th c thi ng d ng tính tốn hi Lu t cách hi u qu vi c thi t k , xây d ng gi i thu t l p l ch cho ng d ng tính tốn hi có th d dàng tri n khai n ng ti p c n c a lu tác v (máy ng d ng t ng qt v i mơ hình m ng gi a c cho theo m th , t th s d ng mơ hình m ts gi i quy t v ng d ng c này, lu xu t ba gi i thu t cho ba mơ hình m ng: mơ hình theo d ng hình sao, mơ hình d ng virtual cluster mơ hình d ng vòng ring d a gi i thu t tham lam gi i thu t quy ho ng Ba gi i thu t có th i gian th c thi th u cho k t qu t t K t qu th nghi m cho th y chi nguyên t c cl pl c l p l ch tham kh workload t i v t parallel workload archive [27], chi xu t có kh n d ng tài n Trong th nghi m v cl pl xu t có th nâng hi u su t t n d ng tài nguyên h th ng lên 25% so v i gi i thu t tham kh o II Abstract In recent years, the emerging of cloud computing has provided groups of researchers with access to compute resources in easier manners Instead of providing a whole system for each group , all resources are gathered into one or few places and can be monitored as a cloud computing model When a group requests, the system provides them exactly the same number of resources as desired However, most of common applications used in clouds such asweb-hosting services are optimized for cloud computing while several applications used by reseachers are of high performance computing (HPC) These applications require more resources and have more contrainsts of bandwidth, memory, latency, etc., , and currently are not ready to be deployed on clouds with high performance Therefore, the question of eve better performance for HPC applications on clouds is always a challenge In our work, we have designed and built a scheduler for deploying HPC applications on IaaS cloud systems We have analysed several general HPC applications with inter-communication tasks (or virtual machines) Then, we propose three algorithms for three models of inter-communication networks including star model, virtual cluster model and ring model All algorithms run in polynomial time and give optimal result Our scheduling strategies can achieve better resource utilization than the referenced ones In our experiments with workloads downloaded from the parallel workload archive [27], our strategy can improve upto 25% better resource utilization III ng, nh ng tài li u tham kh o tài li ng n u k t qu nghiên c u c a tơi tơi t so n th o N u có b t c sai ph m so v i l i cam k t, tơi xin ch u hình th c x lý nh Hu nh Nguyên L c IV M CL C L I TÓM T T LU II ABSTRACT III L IV M C L C V M C L C HÌNH VIII M C L C B NG X I THI U 1.1 TÍNH C 1.2 PHÁT BI 1.3 TÀI P THI T C UV ÓNG GÓP C A LU U TRÚC C A LU 1.4 C N TH C N N T NG 2.1 CÔNG NGH 2.2 O HÓA I 2.3 KI N TRÚC H TH 2.4 H T NG PH N C NG 11 2.5 H TH NH TH I C P PHÁP TÀI NGUYÊN 12 ÌNH NGHIÊN C 3.1 GI I THU T L P L 3.2 GI I THU T L P L CH CHO CÁC 3.3 GI I THU T L P L NG TI T KI NG D NG C TH NG T C 13 NG 13 14 TH NG 15 3.3.1 Gi i thu t l p l ch cho ng d ng thiên v truy xu t d li u 15 3.3.2 Gi i thu t l p l ch cho ng d ng thiên v giao ti p 16 3.3.2.1 B nh th chia s th ng gi a ng d ng khác 16 V 3.3.2.2 B nh th n giao ti p gi a máy o ch y m t ng d ng 16 NG QUAN BÀI TOÁN 19 4.1 19 NG D NG TÍNH TOÁN HI 4.2 TH C TI N H TH NG 19 4.3 BÀI TOÁN T NG QUÁT 22 I PHÁP CHO BÀI TOÁN T NG QUÁT S 5.1 L D NG ILP 24 P TRÌNH TUY N TÍNH 24 5.2 MƠ HÌNH HĨA TÀI NGUYÊN 25 5.2.1 Mơ hình hóa tài ngun h th ng 25 5.2.2 Mơ hình hóa tài ngun u c u c 5.3 GI I THU T S 5.4 KI M NGHI i dùng 25 D NG ILP CHO BÀI TOÁN T NG QUÁT 26 28 5.4.1 Coin-Or Symphony 28 5.4.2 H th ng th nghi m 28 5.4.3 K t qu th nghi m 29 5.4.3.1 S ng bi n 29 5.4.3.2 Th i gian th c thi 30 5.5 K T LU N 30 I THU XU T 32 6.1 M 32 6.2 G À HÌNH SAO 33 34 6.2.2 36 39 6.3 G À HÌNH SAO 40 ng ti p c n thi t k gi i thu t 41 6.3.2 Gi i thu t 46 6.3.2.1 Xây nh phân t h th ng 46 6.3.2.2 Gi i thu t quy ho xu t 48 6.3.3 Phân tích gi i thu t 51 VI 6.4 G 52 52 6.4.2 Gi i thu t 55 6.4.3 Phân tích gi i thu t 57 NGHI 58 7.1 T 58 59 59 60 7.2 T 61 62 63 64 7.2.4 V i workload t parallel workload archive 65 ng yêu c u có th ng liên t c 66 u su t s d ng h th ng 67 NG K T 71 8.1 K 8.2 T QU LU 71 NG PHÁT TRI N 71 VII CPU 10920 10669 10776 10748 11342 12802 10220 10765 10162 10385 27799 26940 26988 27703 27410 25638 26929 27399 26947 26997 1.4304 10.42 13.8 7.030 16.37 22.13 17.21 12.27 3.524 16.86 10.423 34.04 32.76 16.75 30.66 44.56 27.26 25.7 30.26 32.22 Utilization BW Utilization (Gbps) Increment (%) s Increment (%) B ng 7-8 B ng so sánh k t qu th c thi yêu c u gi a hai gi i thu t v i 10 -5000 Mbps Workload with bandwidth 1000-5000 Mbps 50 40 CPU Utilization Increment % 30 20 Bandwidth Utilization Increment 10 Hình 7-12 Bi 10 hi u d ng c a gi i thu xu t v i workload có u 1000-5000 Mbps i v i th nghi m v ng t n 5000 Mbps, chi n xu t cho hi u qu s d sánh, t n d i chi th ng t c so u h t workload th nghi m K tài th nghi m v i workload v thông th p (1000, 2000, 3000 Mbps) k Requests CPU 10 299 288 300 299 292 215 282 290 276 277 14996 16532 15343 14640 15046 18850 13212 15312 16083 16486 22430 27191 22186 22723 23226 27758 24212 24961 28073 28441 Utilization BW Utilization 68 (Gbps) Request CPU 300 300 300 300 300 201 300 300 300 292 15060 17892 15343 14768 16066 19097 15480 16584 18615 18754 22430 27191 22186 22723 23226 27758 24212 24961 28073 28441 0.42 8.22 0.87 6.77 1.31 17.1 8.30 15.7 13.7 0.57 10.5 1.13 9.62 24 23 11.3 20.6 19.7 Utilization Our BW Utilization (Gbps) Increment (%) Increment (%) B ng 7-9 B ng so sánh k t qu th c thi yêu c u gi a hai gi i thu t v i 10 -3000 Mbps Workload with bandwidth 1000-3000 Mbps 30 25 % 20 CPU Utilization Increment 15 Bandwidth Utilization Increment 10 5 Hình 7-13 Bi hi u d ng c a gi i thu xu t v i workload có u 1000-3000 Mbps i v i workload s d p (t qu c a chi n 3000 Mbps) hi u nhi u t l c a c hai gi i thu m 10 i v i gi i thu t ng h Cu ng yêu c u xu t, hi u su t s d ng -24% m t s workload (Hình 7-13) tài th nghi m v i workload v Mbps) k Requests CPU 10 147 88 127 144 138 52 161 121 77 94 4852 2658 3782 4614 3598 1906 4625 3508 2358 2738 Utilization 69 BW Utilization 21738 11728 16887 20442 16192 8385 20657 15635 10615 12062 134 132 143 138 156 87 151 150 128 138 5680 5631 5675 5771 5657 4258 5682 5688 5567 5695 25012 25012 25487 25710 25162 19265 25454 25354 25069 25330 17 111 50 25 57 123 22 62 136 107 15 113 50 25 55 129 23 62 136 109 (Gbps) Request CPU Utilization Our BW Utilization (Gbps) Increment (%) Increment (%) B ng 7-10 B ng so sánh k t qu th c thi yêu c u gi a hai gi i thu t v i 10 -5000 Mbps Workload with bandwidth 4000-5000 Mbps 150 100 % CPU Utilization Increment 50 Bandwidth Utilization Increment Hình 7-14 Bi 10 hi u d ng c a gi i thu xu t v i workload có u 4000-5000 Mbps iv chi ct ov xu link C th hi n 136% hi t k t qu n 5000 Mbps), n so v i chi d ng cpu c a h th ng t t 17% cao nh t lên nd workload th nghi m c cân b ng t i gi a n 136% 10 nghi m có hi u ch ng t , chi v i vi c cân b ng t i gi a link gi i thu t c xu t qu t ng yêu c u s d ng c 70 T NG K T 8.1 K t qu lu vòng ring - : - ) 2 - n) n) 8.2 ng phát tri n 71 72 Tài li u tham kh o [1] M Armbrust , A Fox , R Griffith , A D Joseph , R Katz , A Konwinski , G Lee , D Patterson , A Rabkin , I Stoica , M Zaharia, A view of cloud computing , Communications of the ACM, v.53 pp.50-59, 2010 [2] Greenberg, G Albert, "Networking the Cloud", International Conference on Distributed Computing Systems, 2009 [3] A Gupta , D Milojicic, Evaluation of HPC Applications on Cloud , Proceedings of the 2011 Sixth Open Cirrus Summit, pp.22-26, 2011 - aware vm allocation for infrastructure-as-a-service , Computing Research Repository, vol abs/1202.3683, 2012 [5] Gupta, Abhishek, Kalé, Laxmikant V., Milojicic, Dejan S., Faraboschi, Paolo, Balle, Susanne M., - Proceedings of the 2013 IEEE International Conference on Cloud Engineering, 2013 [6] T Agarwal , A Sharma , L V Kalé, Topology-aware task mapping for reducing communication contention on large parallel machines , Proceedings of the 20th international conference on Parallel and distributed processing, pp.145-145, 2006 [7] G Wei, A V Vasilakos, Y Zheng, N Xiong "A game-theoretic method of fair resource allocation for cloud computing services" The Journal of Supercomputing November 2010, v.54, pp.252-269, 2010 [8] A Stage and T Setzer, "Network-aware migration control and scheduling of differentiated virtual machine workloads", Proceedings of the 2009 ICSE Workshop on Software Engineering Challenges of Cloud Computing, International Conference on Software Engineering, pp.9-14, 2009 [9] Mo Australian Journal of Basic and Applied Sciences 5, pp.1549 1555, 2011 73 [10] Y Chawla and M Computing International Journal of Emerging Trends & Technology in Computer Science (IJETTCS), vol.1, Issue 3, pp.12-17, 2012 [11] A Beloglazov and R Buyya, "Energy Efficient Resource Management in Virtualized Cloud Data Centers", 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, 2010 [12] R Buyya and A Beloglazov, "Energy-Efficient management of data center resources for cloud computing: A vision, architectural elements, and open challenges", in Arxiv preprint arXiv:1006.0308, 2010 [14] M Zaharia, A Konwinski, A D Joseph, R H Katz, and I Stoica Proceedings ofSymposium on Operating Systems Design and Implementation, pp.29 42, 2008 [15] M Zaharia, D Borthakur, J Sen Sarma, K Elmeleegy, S Shenker, and I - Technical Report UCB/EECS-2009-55, EECS Department,University of California, Berkeley, 2009 [16] H Ballani, P Co SIGCOMM '11 Proceedings of the ACM SIGCOMM 2011 conference, pp.242-253, 2011 [17] M Wang, X Meng, and L Zhang, "Consolidating virtual machines with dynamic bandwidth demand in data centers", INFOCOM 2011 Proceedings IEEE, pp 71-75, 2011 [18] X Meng, V Pappas, and L Zhang, "Improving the scalability of data center networks with traffic-aware virtual machine placement," INFOCOM 2010 Proceedings IEEE, pp 1-9, 2010 [19] O Biran, A Corradi, M Fanelli, L Foschini, A Nus, D Raz, and E Silvera, "A stable network-aware vm placement for cloud systems," Cluster, Cloud 74 and Grid Computing (CCGrid), 2012 12th IEEE/ACM International Symposium, pp 498-506, 2012 [20] M Al-Fares, A Loukissas, and A Vahdat, "A scalable, commodity data center network architecture", Proceedings of the ACM SIGCOMM 2008 ACM, pp 63-74, 2008 -aware Global Information Infrastructure and Networking Symposium (GIIS), pp.1-8, 2012 [22] Cohen, R ; Lewin-Eytan, L ; Naor, INFOCOM, 2013 Proceedings IEEE, pp 355-359, 2013 [23] S Chaisiri, B.-S Lee, and D Niyato, "Optimal virtual machine placement across multiple cloud providers", Services Computing Conference, 2009 APSCC 2009 IEEE Asia-Pacific, pp.103-110, 2009 [24] Tziritas, N., Khan, S.U., Cheng-Zhong Xu, Distributed Algorithm to Minimize the Resource Consumption of Cloud Parallel and Distributed Systems (ICPADS), 2012 IEEE 18th International Conference, pp 61-68, 2012 [25] Fangzhe, C., Jennifer R., Ramesh, V., "Optimal Resource Allocation in Clouds", 2010 IEEE 3rd International Conference on Cloud Computing, pp.189196, 2010 [26] Irfan Habib, Virtualization with KVM , Linux Journal, v.2008 n.166, p.8, 2008 [27] LanL Origin 2000 Cluster Log , Internet: http://www.cs.huji.ac.il/labs/parallel/workload, Jun 2012 75 PUBLICATION Huynh Nguyen Loc for high performance communication- -aware virtual machines allocation , 5th International Conference on Ubiquitous and Future Networks (ICUFN), 2013, ISSN2165-8528, pp 822-826, Vietnam2-5 July 2013 76 PH N LÝ L CH TRÍCH NGANG H tên: Hu nh Nguyên L c 30/11/1988 a ch liên l c: 53/2a p H Tp H Chí Minh m huy n Hóc Mơn H Chí Minh O (B ut ih n nay) 9/2006 4/2011: Chuyên ngành K Thu t Máy Tính - Khoa Khoa h c & K thu t Máy ih Q TRÌNH CƠNG TÁC (B ut n nay) 4/2011 - nay: Nghiên c u viên - Khoa Khoa h c & K thu i h c Bách 77 Bandwidth-aware virtual machines allocation for high performance communication-intensive applications Loc N Huynh #1 , Nam Thoai ∗2 Hochiminh city Univeristy of Technology - Vietnam National University Vietnam {hnloc,nam}@cse.hcmut.edu.vn Abstract—Cloud computing has become a step up in computing whereby shared computation resources are provided on demand As Infrastructure-as-a-Service (IaaS) providers provide more and more services to users, they also have to balance between the user’s Service Level Agreement (SLAs) and the cost of resource usage To optimize resource usage as low as possible while keeping user’s SLA guaranteed is one of the most significant tasks For those who use IaaS system to run their high performance applications such as communication-intensive applications, congestion of network becomes a critical problem Sending a numerous requests to network-unaware scheduler maybe not processed due to network bottleneck while resource usage is very low In this paper, to solve this problem, we propose a scheme of minimizing the required bandwidth consumption between every pair of virtual machines while keeping an introduced SLA to users We show that our scheduler takes advantage of serving heavy communication-intensive applications with a lot of requested virtual machines I I NTRODUCTION Cloud computing becomes one of the most significant technology in computing and data storage due to its flexibility and cost saving Cloud computing breaks down the system into many isolated domains ranging from one single machine to thousands of computing machines and gives them to users with full access power to whatever they want IaaS providers such as Amazon, RackSpace, GoGrid, etc provide many services to their customers These services come with guaranteed computation processing, disk space and charge based on usage but not with network performance guarantee For those who use these systems to run their high performance communication-intensive applications, network will become a bottleneck These applications require significant guarantees of bandwidth, delay or jitter And it’s important to improve Quality of Service (QoS) for network guarantee to achieve user’s requirements for the next generation of cloud computing In this paper, we focus on allocation of high performance communication-intensive application onto existed IaaS system We consider a request model in which a user can ask for a virtual cluster [1] with k is given number of virtual machines connect to a virtual switch and B is bandwidth of link connects from each virtual machine to virtual switch This simply leads us to find the applicable allocation to satisfy 978-1-4673-5990-0/13/$31.00 ©2013 IEEE virtual cluster request’s characteristics as well as to keep the network cost in system as low as possible In real world, Cloud computing system is not like a virtual cluster whose every nodes connect to a switch but a combination of a lot of zones and physical nodes connected to each other by high speed network Embedding a virtual network request into real system requires us to know the network topology precisely And it has been shown that embedding a virtual cluster request into arbitrary network topology is the NP-hard problem [2] However, with the specific topology like tree, there exists an algorithm that solve the problem of embedding virtual cluster request into tree topology in polynomial time [1] Furthermore, as the arising of multiprocessors computers, a numerous virtual machines can be allocated on a single physical node These allocated virtual machines can communicate with each others via a low latency, high speed virtual network inside a physical machine without consuming any network resources We take this into account to reduce the external network cost for allocation of large virtual cluster requests Our goal is to propose a new scheduling algorithm for high performance communication-intensive applications for Cloud computing by mapping a constrained virtual cluster request onto a known tree network topology We leverage the internal network bandwidth of the local physical machine and reduce the external communication cost to achive best resource usage while keeping user’s SLA In our experiments, we show that our algorithm achieves better resource usage than original algorithm proposed by Dutta [1] This paper is organized as follows In Section 2, we review previous resource allocation problem We present some preliminaries and our method in Section Our algorithm is proposed in Section And we validate our algorithm’s performance by experiments in Section Finally, we conclude our study and point to the future work in Section II R ELATED W ORK The scheduling problem for high performance communication-intensive has been well studied for a long time The general problem is the assignment of a set of n dependent jobs on p processors while reducing the 822 ICUFN 2013 ... L c I Trong nh cho vi xu t hi n c ng nhu c u tính tốn c a nhóm nghiên c u v a nh d c cho nhóm nghiên c u h th ng máy tính riêng l h tr cho ho ng nghiên c u c a mình, tài nguyên tính tốn s t p... tính tốn song song v i m c tl gi i quy t m t toán m t ng yêu c u v th i gian th toán hi cg i ng tính - HPC) Nhi u mơ hình máy tính c nghiên c u phát tri n nh m ph c v cho vi c x m nhi u máy tính. .. NGHIÊN C U GI I THU T L P L CH CHO NG D NG TÍNH TỐN HI U II NHI M V VÀ N I DUNG: Nghiên c u th hi m c a h th nh th i hi n có h p cho ng d ng tính tốn xu t gi i thu t ánh x tác v c a ng d ng tính