Tài liệu Quản lý tài nguyên hướng tiết kiệm năng lượng trên môi trường điện toán đám mây

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA NGUYỄN QUANG HÙNG QUẢN LÝ TÀI NGUYÊN HƯỚNG TIẾT KIỆM NĂNG LƯỢNG TRÊN MÔI TRƯỜNG ĐIỆN TOÁN ĐÁM MÂY LUẬN ÁN TIẾN SĨ KỸ THUẬT TP. HỒ CHÍ MINH NĂM 2019 ĐẠI HỌC QUỐC GIA TP. HCM TRƯỜNG ĐẠI HỌC BÁCH KHOA NGUYỄN QUANG HÙNG QUẢN LÝ TÀI NGUYÊN HƯỚNG TIẾT KIỆM NĂNG LƯỢNG TRÊN MÔI TRƯỜNG ĐIỆN TOÁN ĐÁM MÂY Chuyên ngành: Mã số chuyên ngành: KHOA HỌC MÁY TÍNH 62.48.01.01 Phản biện độc lập 1: Phản biện độc lập 2: PGS. TS. Nguyễn Tấn Khôi TS. Nguyễn Đình Minh Phản biện 1: Phản biện 2: Phản biện 3: PGS. TS. Trần Công Hùng PGS. TS. Lê Trung Quân PGS. TS. Huỳnh Xuân Hiệp NGƯỜI HƯỚNG DẪN KHOA HỌC 1. PGS. TS. Thoại Nam 2. TS. Nguyễn Thanh Sơn LỜI CAM ĐOAN Tác giả xin cam đoan đây là công trình nghiên cứu của bản thân tác giả. Các kết quả nghiên cứu và các kết luận trong luận án này là trung thực, và không sao chép từ bất kỳ một nguồn nào và dưới bất kỳ hình thức nào. Việc tham khảo các nguồn tài liệu (nếu có) đã được thực hiện trích dẫn và ghi nguồn tài liệu tham khảo đúng quy định. Tác giả luận án Chữ ký i TÓM TẮT LUẬN ÁN Điện toán đám mây (ĐTĐM), một mô hình tính toán phân bố cỡ lớn, đang trở thành một mô hình điện toán tiện ích (utility computing) được định hướng bởi tính kinh tế. Các đám mây hạ-tầng-như-một-dịch-vụ (IaaS Cloud) cung cấp tài nguyên cho người dùng (đám mây) dưới dạng máy ảo ngày càng phổ biến tại các trung tâm dữ liệu (TTDL) đám mây. Một nghiên cứu ước tính công suất tiêu thụ và chi phí điện năng tiêu thụ cho một trung tâm dữ liệu ở Mỹ khoảng 50 MW và hơn 15 triệu đô-la mỗi năm, một nghiên cứu khác chỉ ra chi phí phải trả cho điện năng tiêu thụ tại các trung tâm dữ liệu ảo hóa ngày càng tăng và xu thế là chi phí về năng lượng tiêu thụ này tiếp tục tăng trong khi chi phí cho phần cứng không đổi. Bài toán lập lịch máy ảo hướng tiết kiệm năng lượng là một hướng giải quyết cần thiết trong các trung tâm dữ liệu ảo hóa đám mây đối với các nhà cung cấp dịch vụ ĐTĐM để giảm chi phí hoạt động. Một trong những thách thức của bài toán giảm tổng điện năng tiêu thụ của các máy vật lý là bài toán lập lịch máy ảo tiết kiệm năng lượng tiêu thụ của các máy vật lý trong các TTDL ảo hóa đám mây (tiếng Anh: Energy-aware scheduling/placement of virtual machines in Cloud virtualized data centers). Luận án này nghiên cứu bài toán lập lịch máy ảo hướng hiệu quả năng lượng trong đám mây hạtầng-như-một-dịch-vụ hoặc đám mây tính toán hiệu năng cao, trong đó các máy vật lý có tài nguyên giới hạn (mỗi máy vật lý chỉ đặt được tối đa một số giới hạn là g ≥ 1 máy ảo đồng thời) và các máy ảo yêu cầu nhiều loại tài nguyên trong các khoảng thời gian (bắt đầu, kết thúc), không di dời và không nhường trong thời gian thực thi của các máy ảo. Bài toán lập lịch máy ảo hướng hiệu quả năng lượng này là NP-hard và cũng là một chủ đề nghiên cứu được quan tâm hiện nay. Các đóng góp chính của luận án gồm: 1. Bài toán lập lịch máy ảo hướng tiết kiệm năng lượng tiêu thụ nêu trong luận án này có tính mới là chiều thời gian sử dụng của các máy ảo và mỗi máy ảo yêu cầu nhiều loại tài nguyên đồng thời. 2. Luận án khai thác khoảng thời gian thực thi của mỗi máy ảo (thời gian bắt đầu và thời gian kết thúc của mỗi máy ảo) để từ đó tìm ra mục tiêu lập lịch mới tương đương là: “Tối thiểu tổng thời gian bận rộn của các máy vật lý”; đồng thời sử dụng dữ liệu về tải sử dụng trên các chiều tài nguyên của mỗi máy vật lý và yêu ii cầu mỗi máy ảo. Thay vì tối thiểu số máy vật lý được dùng, luận án đã đề xuất hai nhóm giải thuật: i. Sử dụng chiều thời gian trong giải pháp lập lịch hướng tiết kiệm năng lượng luận án đề xuất nhóm giải thuật lập lịch thứ nhất MinDFT (bao gồm các giải thuật MinDFT-ST, MinDFT-FT, MinDFT-LDTF và MinDFT-LFT ở chương 5). Các giải thuật MinDFT-ST, MinDFT-FT, MinDFT-LDTF, MinDFT-LFT khác nhau về cách sắp xếp danh sách máy ảo (đầu vào) trước khi gán máy ảo lên máy vật lý bằng giải thuật MinDFT. Giải thuật MinDFT là một heuristic dạng Best-Fit Decreasing (BFD) gán máy ảo lên máy vật lý có thời gian hoàn thành của máy vật lý tăng thêm nhỏ nhất để tối thiểu tổng năng lượng tiêu thụ của các máy vật lý. Giải thuật MinDFT có độ phức tạp về thời gian là O(n.m) với n là số máy ảo cần lập lịch và m là số máy vật lý. ii. Giải pháp lập lịch hướng tiết kiệm năng lượng dựa trên yếu tố thời gian và độ dài của vector các tài nguyên còn dư (sau khi cấp cho các máy ảo) của các máy vật lý, luận án đề xuất nhóm giải thuật thứ hai EMinTRE với các giải thuật gồm: EMinTRE-ST, EMinTRE-FT, EMinTRE-LDTF và EMinTRELFT (ở chương 6). Giải thuật EMinTRE đề xuất sử dụng độ đo mới (ký hiệu: TRE – different Time and Resource Efficiency) để gán máy ảo mới. Độ đo TRE là bao gồm cả tỉ lệ độ chênh lệch về thời gian bận rộn của máy vật lý (có nhân với trọng số thời gian) và độ dài của vector các tài nguyên còn dư của máy vật lý (mỗi tài nguyên đều nhân tỉ lệ phần trăm tài nguyên còn dư với trọng số). Máy vật lý nào có giá trị TRE nhỏ nhất sẽ được chọn để gán máy ảo. Giải thuật EMinTRE là một heuristic dạng Best-Fit Decreasing nhằm tối thiểu tổng thời gian bận rộn của các máy vật lý dẫn đến rút giảm tổng năng lượng tiêu thụ của các máy vật lý. Các giải thuật EMinTRE-ST, EMinTRE-FT, EMinTRE-LDTF và EMinTRE-LFT khác nhau về cách sắp xếp danh sách máy ảo (đầu vào) trước khi gán máy ảo lên máy vật lý bằng giải thuật EMinTRE. Giải thuật EMinTRE có độ phức tạp về thời gian là O(n.m) với n là số máy ảo cần lập lịch và m là số máy vật lý (giả sử m ≥ logn). 3. Luận án thực hiện đánh giá hiệu quả của các giải thuật lập lịch đề xuất bằng mô phỏng dựa trên phần mềm CloudSim. (Phần mềm CloudSim là một trong những phần mềm mô phỏng các giải thuật cấp phát tài nguyên trên môi trường điện toán iii đám mây phổ biến nhất). Nhiều đánh giá dựa trên mô phỏng được thực hiện sử dụng các mô hình tải song song (parallel workload models) trong Parallel Workload Archive (PWA) cho thấy rằng: “Các giải thuật lập lịch đề xuất (trong luận án) đều giảm tổng điện năng tiêu thụ hơn so với các giải thuật lập lịch phổ biến khác như: giải thuật Power-Aware Best-Fit Decreasing (ký hiệu: PABFD) của A. Beloglazov, giải thuật Modified First-fit Decreasing Earliest (ký hiệu: Tian-MFFDE) của W. Tian, các heuristic đóng thùng dạng Norm-based Greedy (ký hiệu: VBP-Norm-L1, VBP-Norm-L2),…”. iv ABSTRACT Cloud computing, which is a large-scale distributed computing paradigm, has been becoming an utility computing model and is driven by economies of scale. Infrastructure-as-a-Service (IaaS) cloud provides cloud users with computing resources in terms of virtual machines (VMs) to run their applications in cloud virtualized data centers. A study has estimated the energy cost of a single data center is more than $15M per year. The power consumption is increased with the increasing scale of these data centers. Therefore, advanced scheduling techniques for reducing energy consumption of these cloud systems are highly concerned for any cloud providers to reduce energy cost. This thesis investigates the energy-efficient virtual machine scheduling problems in IaaS clouds where users request multiple resources in fixed intervals and nonpreemption for processing their virtual machines and physical machines have bounded capacity resources. Many previous works are based on migration techniques to move on-line VMs from low utilization hosts and turn these hosts off to reduce energy consumption. However, the techniques for migration of VMs could not use in our research. The scheduling problem is NP-hard and is one of the hot topic research. The key contributions are: 1. Thesis proposes new approach to the problem of energy-aware virtual machine scheduling with the execution time of virtual machines and each virtual machine requires multiple computing resources simultaneously. 2. Thesis exploits the execution time of each virtual machine (between the start time and end time of each virtual machine) to find out the equivalent scheduling goal is "Minimizing total busy time of the physical machines". Instead of minimizing the number used physical machines, the thesis propose scheduling algorithms to minimize the sum of total busy time of all physical machines that is equivalent to minimize total energy consumption. The thesis proposes two approaches: i. Using the execution time of each virtual machine the thesis proposes the Minimizing Differential Finishing Time (MinDFT) algorithms, which is denoted as MinDFT-ST, MinDFT-FT, MinDFT-LDTF and MinDFT-LFT (in the chapter 5). All of MinDFT-ST, MinDFT-FT, MinDFT-LDTF and MinDFT-LFT algorithms differ in sorting of list of virtual machines to be v allocated by core MinDFT algorithm. The MinDFT algorithm is a BestFit Decreasing heuristic to allocate a virtual machine to a physical machine that has enough available resources and minimum of the increasingly finishing time of the physical machine. The time complexity of MinDFT algorithm is O(n.m) where n is the number of virtual machines to be scheduled, m is the number of physical machines. ii. The energy-aware virtual machine scheduling algorithms based on both the time and length (Euclidean norm) of multiple dimensional vector where each dimension of the vector is the residual resource utilization (after allocation for placed virtual machines) of a physical machine. The thesis proposed the Energy-aware Minimizing Differential Time and Resource Efficiency algorithms, which are denoted as EMinTRE-ST, EMinTRE-FT, EMinTRE-LDTF and EMinTRE-LFT (in Chapter 6). The EMinTRE-ST, EMinTRE-FT, EMinTRE-LDTF and EMinTRE-LFT algorithms are proposed using a new metric (denoted as TRE – different Time and Resource Efficiency) to allocate virtual machines to physical machines. The TRE metric is sum of squared of ratio of increasing finishing time of a physical machine (multiplied by the time weight) and length of the residual resources vector of the physical machine (each resource multiplied by percentage of residual resources with weight). A physical machine that has enough available resources and minimum of the TRE value will be selected to allocate a virtual machine. Core EMinTRE algorithm is Best-Fit Decreasing on the TRE. The EMinTRE-ST, EMinTRE-FT, EMinTRE-LDTF and EMinTRE-LFT algorithms differ in sorting of list of virtual machines to be allocated by the core EMinTRE algorithm. The EMinTRE algorithm has the time complexity is O(n.m) where n is the number of virtual machines to be scheduled, m is the number of physical machines (assume that m ≥ log n). 3. Thesis evaluates performance of these proposed scheduling algorithms by simulations. Thesis chooses CloudSim, which is a popular Cloud data centers and virtual machine allocation algorithms simulation software. There are many extensive simulations using parallel workload models in Parallel Workload vi Archive show that the proposed algorithm has the least total energy consumption compared to the state-of-the-art algorithms include Beloglazov’s Power-Aware Best-Fit Decreasing (denoted as PABFD), Tian’s Modified First-fit Decreasing Earliest (denoted as Tian-MFFDE), vector bin-packing heuristics (denoted as VBP-Norm-L1, VBP-Norm-L2). vii LỜI CÁM ƠN Tôi xin trân trọng cám ơn PGS. TS Thoại Nam và TS. Nguyễn Thanh Sơn đã tận tình hướng dẫn tôi thực hiện nghiên cứu. Tôi cũng xin cảm ơn các đồng nghiệp tại bộ môn Hệ Thống & Mạng Máy Tính, khoa Khoa Học & Kỹ Thuật Máy Tính, phòng Đào tạo Sau đại học trường Đại học Bách Khoa – Đại học Quốc Gia Tp. Hồ Chí Minh, các thầy cô và các nhà khoa học phản biện đã đóng góp ý kiến cho Luận án Tiến sĩ này. Tôi xin cảm ơn đến GS. TS. Josef Küng trường Johannes Kepler University of Linz/JKU, Austria đã giúp đỡ rất nhiều trong thời gian tôi đi nghiên cứu tại trường bằng học bổng Erasmus Mundus GATE project. Con chân thành gửi đến cha: Nguyễn Văn Nghiệm và mẹ: Nguyễn Thị Thu Đông sự biết ơn sinh thành, dưỡng dục. Tôi cũng gửi lời cảm ơn đến vợ: Hồ Kim Oanh và hai con Nguyễn Kim Anh và Nguyễn Ngọc Vân Anh đã đồng hành tôi trong thời gian qua. viii MỤC LỤC LỜI CAM ĐOAN ............................................................................................................ i TÓM TẮT LUẬN ÁN .................................................................................................... ii ABSTRACT ............................................................................................................. v LỜI CÁM ƠN .......................................................................................................... viii MỤC LỤC ............................................................................................................ ix DANH MỤC CÁC HÌNH ẢNH ................................................................................... xii DANH MỤC BẢNG BIỂU ......................................................................................... xiii DANH MỤC CÁC TỪ VIẾT TẮT ............................................................................. xiii DANH MỤC CÁC KÝ HIỆU ..................................................................................... xvi CHƯƠNG 1 GIỚI THIỆU ........................................................................................ 1 Đặt vấn đề ......................................................................................................... 1 Tầm vực nghiên cứu .......................................................................................... 5 Đóng góp chính của luận án .............................................................................. 6 Bố cục của luận án ............................................................................................ 8 CHƯƠNG 2 CƠ SỞ LÝ THUYẾT ........................................................................ 10 Điện toán đám mây (Cloud computing) .......................................................... 10 Quản lý máy ảo trong Trung tâm dữ liệu đám mây ........................................ 12 Bài toán lập lịch công việc song song ............................................................. 13 Kết luận ........................................................................................................... 15 CHƯƠNG 3 TỔNG QUAN VỀ CÁC GIẢI PHÁP LẬP LỊCH/PHÂN BỔ MÁY ẢO TIẾT KIỆM NĂNG LƯỢNG TRÊN HẠ TẦNG TÍNH TOÁN CỦA TRUNG TÂM DỮ LIỆU ........................................................................................................... 16 Tổng quan các phương pháp luận tiết kiệm năng lượng ................................. 16 Mô hình công suất tiêu thụ và năng lượng tiêu thụ ......................................... 17 Ưu và khuyết điểm của các giải pháp dựa trên phần cứng (bộ xử lý) hỗ trợ DVFS để tối thiểu tổng năng lượng tiêu thụ của các máy vật lý .............................. 19 Khảo sát các giải pháp dồn máy ảo (virtual machine consolidation) để tối thiểu tổng năng lượng tiêu thụ của các máy vật lý ................................................... 19 Khảo sát các phương pháp phân bổ/lập lịch máy ảo theo hướng năng lượng hiệu quả trong các trung tâm dữ liệu ........................................................................ 20 Kết luận ........................................................................................................... 26 ix CHƯƠNG 4 KIẾN TRÚC HỆ THỐNG VÀ BÀI TOÁN LẬP LỊCH MÁY ẢO CÓ THỜI GIAN BẮT ĐẦU VÀ KẾT THÚC CỐ ĐỊNH TIẾT KIỆM NĂNG LƯỢNG . 27 Kiến trúc hệ thống đám mây tính toán hiệu năng cao hiệu quả năng lượng ... 27 Các ký hiệu ...................................................................................................... 29 Mô hình công suất và điện năng tiêu thụ của máy vật lý ................................ 30 Một số định nghĩa............................................................................................ 30 Bài toán lập lịch máy ảo có thời gian bắt đầu và kết thúc cố định trên các máy vật lý đồng nhất tiết kiệm năng lượng ...................................................................... 32 Các định lý ...................................................................................................... 34 Kết luận ........................................................................................................... 36 CHƯƠNG 5 GIẢI THUẬT MinDFT TỐI THIỂU TỔNG THỜI GIAN HOÀN THÀNH TĂNG THÊM ĐỂ TIẾT KIỆM ĐIỆN NĂNG TIÊU THỤ CỦA CÁC MÁY VẬT LÝ ........................................................................................................... 37 Giới thiệu......................................................................................................... 37 Giải thuật MinDFT-ST và MinDFT-FT .......................................................... 38 Đánh giá hiệu suất của hai giải thuật MinDFT-ST và MinDFT-FT ............... 42 Giải thuật lập lịch MinDFT-LDTF và MinDFT-LFT ..................................... 48 Kết luận ........................................................................................................... 52 CHƯƠNG 6 GIẢI THUẬT EMinTRE TỐI THIỂU TỔNG THỜI GIAN BẬN RỘN - ỨNG DỤNG VÀO TIẾT KIỆM ĐIỆN NĂNG TIÊU THỤ CỦA CÁC MÁY VẬT LÝ ........................................................................................................... 53 Giới thiệu......................................................................................................... 53 Giải thuật lập lịch EMinTRE .......................................................................... 57 Giải thuật lập lịch EMinTRE-ST, EMinTRE-FT, EMinTRE-LDTF, EMinTRE-LFT ......................................................................................................... 62 Đánh giá các giải thuật đề xuất ....................................................................... 64 Đánh giá về giải thuật MinDFT và EMinTRE ................................................ 73 Kết luận ........................................................................................................... 75 CHƯƠNG 7 PHÂN TÍCH ĐỘ HIỆU QUẢ TRÊN LÝ THUYẾT CỦA CÁC GIẢI THUẬT LẬP LỊCH ĐỀ XUẤT ................................................................................... 77 Phân tích độ hiệu quả của các giải thuật lập lịch ............................................ 77 Kết luận ........................................................................................................... 83 CHƯƠNG 8 TỔNG KẾT ....................................................................................... 84 Tóm tắt ............................................................................................................ 84 x Hướng nghiên cứu mở rộng ............................................................................ 87 DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ ............................................................. 88 TÀI LIỆU THAM KHẢO ............................................................................................ 89 xi DANH MỤC CÁC HÌNH ẢNH Hình 2.1: Mô hình của điện toán đám mây [44]. .......................................................... 11 Hình 2.2: Mô hình phân lớp kiến trúc ảo hóa gồm ba (03) tầng [44]. .......................... 12 Hình 3.1 Công suất tiêu thụ (Watt) của một máy chủ theo tải CPU (nguồn [12]) ....... 17 Hình 3.2 Các đặc tính dùng để phân loại các tiếp cận mức trung tâm dữ liệu ............. 22 Hình 4.1 Kiến trúc phần mềm hệ thống đám mây tính toán hiệu năng cao (HPCCloud) hiệu quả năng lượng [34]. ............................................................................................. 27 Hình 5.1 Tổng điện năng tiêu thụ. ................................................................................ 46 Hình 5.2 Tổng điện năng tiêu thụ ................................................................................. 48 Hình 5.3: Tổng điện năng tiêu thụ được chuẩn hóa...................................................... 51 Hình 6.1 Ví dụ đặt hai máy ảo trên một máy vật lý...................................................... 54 Hình 6.2: Tổng điện năng tiêu thụ chuẩn hóa theo PABFD. Kết quả mô phỏng của các giải thuật lập lịch cho bài toán lập lịch hệ thống gồm 5000 máy vật lý và 10246 máy ảo có thông tin của các máy ảo được tạo ra từ mô hình workload của Feitelson. ........ 69 Hình 6.3: Tổng điện năng tiêu thụ chuẩn hóa theo PABFD. Kết quả mô phỏng của các giải thuật lập lịch cho bài toán lập lịch hệ thống gồm 5000 máy vật lý và 6583 máy ảo có thông tin của các máy ảo được tạo ra từ mô hình workload song song Lublin99 của Lublin. ........................................................................................................................... 70 Hình 6.4: Tổng điện năng tiêu thụ chuẩn hóa theo PABFD. Kết quả mô phỏng của các giải thuật lập lịch cho bài toán lập lịch hệ thống gồm 5000 máy vật lý và 3677 máy ảo có thông tin của các máy ảo được tạo ra từ mô hình workload song song Downey97 của Downey. ................................................................................................................. 72 Hình 6.5: Tổng điện năng tiêu thụ chuẩn hóa theo PABFD. Kết quả mô phỏng của các giải thuật lập lịch cho bài toán lập lịch hệ thống gồm 5000 máy vật lý và 2223 máy ảo có thông tin của các máy ảo được tạo ra từ mô hình workload song song Lublin99. .. 73 Hình 6.6: Thời gian bắt đầu (start time) và thời gian kết thúc (finish time) của các máy ảo trong mô hình workload song song Lublin99. ......................................................... 74 xii DANH MỤC BẢNG BIỂU Bảng 1.1: Ví dụ thông số của năm (5) máy ảo. Dữ liệu về CPU, RAM, băng thông mạng của các máy ảo được chuẩn hóa theo tổng khả năng của máy vật lý.................... 2 Bảng 3.1: Công suất tiêu thụ (W) của từng thành phần trong một máy chủ ................ 18 Bảng 3.2: Tóm tắt các nghiên cứu về lập lịch/phân bổ máy ảo trên các trung tâm dữ liệu ................................................................................................................................ 25 Bảng 5.1: Cấu hình bốn (4) loại máy ảo dùng trong mô phỏng. .................................. 43 Bảng 5.2: Mô hình công suất tiêu thụ (W) với tải sử dụng CPU (phần trăm %) của một máy chủ IBM Server x3250 (1 x [Xeon X3470 2933 MHz, 4 cores], 8GB)................ 44 Bảng 5.3: Kết quả mô phỏng các giải thuật lập lịch trên hệ thống ĐTĐM gồm 5.000 máy vật lý (hosts) và 10.000 máy ảo (VMs). ............................................................... 45 Bảng 5.4: Kết quả mô phỏng các giải thuật lập lịch sắp xếp theo thời gian bắt đầu sớm nhất trước. ..................................................................................................................... 47 Bảng 5.5: Tám (8) kiểu máy ảo dùng cho mô phỏng ................................................... 50 Bảng 5.6: Thông tin về loại máy vật lý được dùng trong mô phỏng. ........................... 50 Bảng 5.7: Kết quả mô phỏng các giải thuật lập lịch trên SDSC-BLUE-2000-4.2-cln của Parallel Workload Archives [39]. .......................................................................... 51 Bảng 6.1 Ví dụ về sáu (6) máy ảo với nhu cầu tài nguyên, thời gian bắt đầu và thời gian kết thúc (đvtg.). ..................................................................................................... 54 Bảng 6.2: Tám (8) kiểu máy ảo dùng cho mô phỏng ................................................... 67 Bảng 6.3: Thông tin về loại máy vật lý được dùng trong mô phỏng. ........................... 67 Bảng 6.4: Kết quả mô phỏng của các giải thuật lập lịch cho bài toán lập lịch với hệ thống gồm 5000 máy vật lý và 10246 máy ảo có thông tin của các máy ảo được tạo ra từ mô hình workload của Feitelson. ............................................................................. 68 Bảng 6.5: Kết quả mô phỏng của các giải thuật lập lịch cho bài toán lập lịch với hệ thống gồm 5000 máy vật lý và 8847 máy ảo có thông tin của các máy ảo được tạo ra từ mô hình workload của Lublin. ...................................................................................... 70 Bảng 6.6: Kết quả mô phỏng của các giải thuật lập lịch cho bài toán lập lịch với hệ thống gồm 5000 máy vật lý và 3677 máy ảo có thông tin của các máy ảo được tạo ra từ mô hình workload của Downey. ................................................................................... 71 Bảng 6.7: Kết quả mô phỏng của các giải thuật lập lịch cho bài toán lập lịch với hệ thống gồm 5000 máy vật lý và 2223 máy ảo có thông tin của các máy ảo được tạo ra từ mô hình workload song song Lublin99. ....................................................................... 74 DANH MỤC CÁC TỪ VIẾT TẮT Thuật ngữ Viết tắt xiii Tiếng Anh/Việt/Giải thích Central Processing Unit Cloud Cloud computing Cloud Virtualized Data Center CPU Cloud ĐTĐM CVDC Cluster of workstations Cluster, COW IT CNTT Data center DC Data centers DCs Dynamic Voltage and Frequency DVFS Scaling Floating-Point Operations Per FLOPS Second Genetic Algorithm GA High Performance Computing HPC High Performance Computing HPC Cloud Cloud High Throughput Computing HTC Host Infrastructure-as-a-Service IaaS Infrastructure-as-a-Service IaaS Cloud Cloud Millions of Instructions Per MIPS Second Physical machine PM Platform-as-a-Service PaaS Portable Batch System PBS Power-Aware Job Scheduling PASS Service Level Agreement Software-as-a-Service SuperNode SLA SaaS SuperNode-V User VM-based lease Lease Virtual machine VM xiv Bộ xử lý Đám mây Điện toán đám mây Trung tâm dữ liệu ảo hóa đám mây Máy tính cụm Công nghệ thông tin Trung tâm dữ liệu Các trung tâm dữ liệu (số nhiều) Công nghệ thay đổi tần số và điện thế cung cấp cho bộ xử lý (CPU) Số phép toán dấu chấm động thực hiện trong một giây Giải thuật di truyền Tính toán hiệu năng cao Điện toán đám mây tính toán hiệu năng cao Tính toán thông năng cao Một máy vật lý Hạ-tầng-như-một-dịch-vụ Đám mây hạ-tầng-như-một-dịchvụ Hàng triệu lệnh máy mỗi giây Máy vật lý Nền tảng như một dịch vụ Tên của một phần mềm quản lý máy tính cụm Bài toán lập lịch công việc hướng đến mục tiêu tối thiểu năng lượng Thỏa hiệp mức dịch vụ Phần mềm như một dịch vụ Tên của một dạng máy tính cụm được phát triển tại Trường Đại học Bách Khoa ĐHQG-HCM Tên của một dạng máy tính cụm ảo hỗ trợ thực thi các máy ảo được phát triển tại Trường Đại học Bách Khoa ĐHQG-HCM Hợp đồng thuê bao các máy ảo của người dùng Máy ảo Virtual machines VMs Các máy ảo (số nhiều) xv DANH MỤC CÁC KÝ HIỆU Ký hiệu Ý nghĩa ký hiệu Vi - Máy ảo thứ i sẽ được lập lịch. Mj - Máy vật lý thứ j. S - Một lập lịch khả thi. Pidle - Công suất tiêu thụ lúc không tải (0% tải CPU) của một máy vật lý. Pmax - Công suất tiêu thụ cực đại của một máy vật lý. Pj(t) - Công suất tiêu thụ của máy vật lý Mj ở thời điểm t. si - Thời gian bắt đầu yêu cầu (cố định) của máy ảo Vi. fi - Thời gian kết thúc của máy ảo Vi. duri - Thời gian thực thi yêu cầu (không đổi) của máy ảo Vi. 𝑈!"#$ (𝑡) - Tải sử dụng CPU của máy vật lý Mj ở thời điểm t. T - Thời gian tối đa của bài toán lập lịch. Lj - Tập các máy ảo được gán lên máy vật lý Mj bởi một lập lịch. ei - Năng lượng tiêu thụ (Wh) của việc chạy máy ảo Vi trên một máy vật lý mà máy ảo Vi được gán đến trong thời gian từ si đến (si + duri). ViÎMj - Quan hệ Î xác định máy ảo Vi được gán lên máy vật lý Mj. ℒj - Tập các máy ảo được lập lịch lên máy vật lý thứ j. Uj,r - Tải sử dụng (utilization) của một tài nguyên thứ r. ℤ+ - Tập số nguyên dương. Vir - Tổng số tài nguyên thứ r được yêu cầu của máy ảo thứ i. si - Thời gian bắt đầu của máy ảo thứ i. xvi duri - Khoảng thời gian thực thi của máy ảo thứ i. Mjr - Tổng khả năng tối đa của một tài nguyên thứ r mà máy vật lý thứ j có thể cung cấp. wr - Trọng số của tài nguyên thứ r trong máy vật lý thứ j. Tj - Tổng thời gian bận rộn của một máy vật lý thứ j. xvii CHƯƠNG 1 GIỚI THIỆU Đặt vấn đề Điện toán đám mây (ĐTĐM) [1], [2] đang trở thành một mô hình điện toán tiện ích (utility computing) [2] và được định hướng bởi tính kinh tế [3], [4]. Các đám mây hạ-tầng-như-một-dịch-vụ (IaaS Clouds) cung cấp tài nguyên cho người dùng (đám mây) dưới dạng máy ảo (virtual machine, viết tắt: VM) ngày càng phổ biến tại các trung tâm dữ liệu (TTDL) ảo hóa đám mây (cloud virtualized data center) [4]–[11]. Công suất của các trung tâm dữ liệu cỡ lớn này yêu cầu từ vài chục Mega-Watts (MW) để hoạt động [9], [12]. Nghiên cứu [44] ước tính công suất tiêu thụ và chi phí điện năng tiêu thụ cho một trung tâm dữ liệu ở Mỹ khoảng 50 MW và hơn 15 triệu đô-la mỗi năm. Nghiên cứu [12] chỉ ra chi phí phải trả cho điện năng tiêu thụ tại các trung tâm dữ liệu ngày càng tăng, và xu thế là chi phí về năng lượng tiêu thụ này tiếp tục tăng trong khi chi phí cho phần cứng không đổi. Bài toán lập lịch máy ảo trong các trung tâm dữ liệu ảo hóa đám mây mục tiêu tiết kiệm năng lượng là một vấn đề quan trọng đối với các nhà cung cấp dịch vụ ĐTĐM để giảm chi phí hoạt động. Một trong những thách thức của bài toán giảm tổng điện năng tiêu thụ của các máy vật lý là bài toán lập lịch/phân bổ máy ảo tiết kiệm năng lượng tiêu thụ của các máy vật lý trong các trung tâm dữ liệu ảo hóa đám mây (Energy-aware scheduling/placement of virtual machines in Cloud virtualized data centers) [9], [13]– [16]. Mặc dù bài toán lập lịch/phân bổ các máy ảo hướng tiết kiệm điện năng trong các trung tâm dữ liệu ảo hóa đám mây được nghiên cứu nhiều [6], [9], [17], [18] nhưng vẫn còn nhiều thách thức. Bài toán lập lịch máy ảo hướng tiết kiệm năng lượng với các ràng buộc về các khoảng thời gian thực thi cố định và không di dời (non-migration) của các máy ảo đang được quan tâm và có nhiều vấn đề cần nghiên cứu sâu hơn [19]–[23]. Luận án này nghiên cứu bài toán lập lịch máy ảo mục tiêu tiết kiệm năng lượng trong ĐTĐM với các đặc điểm: nhiều tài nguyên (gồm CPU, bộ nhớ, băng thông mạng, v.v…) yêu cầu được sử dụng đồng thời trong các khoảng thời gian cố định (fixed intervals), không nhường (non-preemption) và không di dời (non-migrating). Một số công trình khác như [13], [23]–[25] giải bài toán này theo hướng tối thiểu số máy vật lý 1