Đặ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 sử dụng (và tắt các máy khác không dùng). Tuy nhiên với bài toán lập lịch máy ảo được nghiên cứu trong luận án, việc tối thiểu số máy vật lý sử dụng chưa phải là một giải pháp tốt nhất để tối thiểu tổng điện năng tiêu thụ của các máy vật lý.
Xét một ví dụ sau: 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ý. VM ID CPU RAM Băng thông Thời gian Khoảng thời gian mạng bắt đầu (Đơn vị: Giờ) 1 0,5 0,1 0,1 0 100 2 0,5 0,1 0,5 0 100 3 0,1 0,5 0,1 0 1 4 0,1 0,5 0,1 0 1 5 0,2 0,2 0,2 0 1 Giả sử cho năm (5) công việc có thông tin và nhu cầu tài nguyên (như CPU, dung lượng bộ nhớ (RAM), băng thông mạng) của từng loại máy ảo (tính theo tỉ lệ phần trăm tổng khả năng tài nguyên CPU, dung lượng bộ nhớ và băng thông mạng của máy vật lý, ví dụ 0,1 là 10%, tối đa là 1,0 tức 100%) được liệt kê trong Bảng 1. Giả sử tất cả các máy vật lý trong hệ thống đều đồng nhất, công suất tiêu thụ cũng như nhau và có mối quan hệ tuyến tính với tải CPU.
Các ràng buộc gán là (i) tổng tài nguyên yêu cầu trên từng loại của các máy ảo được gán đều nhỏ hơn hoặc bằng 1; (ii) mỗi máy ảo đều phải được gán tại thời điểm bắt đầu; (iii) các máy ảo khi đã được gán thì không di dời và không nhường. Giả sử công suất (đơn vị: Watt) của một máy vật lý tính bởi phương trình: P = Pidle + (Pmax - Pidle).Ucpu trong đó P là công suất của máy vật lý, Ucpu là tải CPU của máy vật lý với 0 ≤ Ucpu ≤ 1, Pmax là công suất cực đại với 100% tải CPU của máy vật lý, Pidle là công suất chạy không tải với 0% tải CPU. Cho Pidle = 175 (W), Pmax = 250 (W), công suất máy vật lý là: P = 175 + 75. Giả sử các máy ảo sử dụng CPU không đổi và bằng đúng CPU yêu cầu trong suốt thời gian nó đang thực thi.
Năng lượng tiêu %& thụ của một máy vật lý (ký hiệu E) là: 𝐸 = ∫%' 𝑃(𝑡 )𝑑𝑡 trong đó P(t) là công suất của máy vật lý theo thời gian tÎ[t1, t2], t1 và t2 là thời gian bắt đầu và kết thúc thực thi của máy vật lý. 2 Nếu dùng giải pháp số máy nhỏ nhất thì một lịch S1 thực thi các máy ảo có VM ID là 1, 4, 5 gán lên máy vật lý thứ nhất (M1) tại thời điểm bắt đầu là 0 và các máy ảo có VM ID là 2, 3 gán lên máy vật lý thứ hai (M2) tại thời điểm bắt đầu là 0 thì chỉ cần hai (02) máy vật lý với tổng thời gian bận rộn của cả hai máy vật lý là: (100 + 100) = 200 giờ, công suất tiêu thụ của máy vật lý M1 ở khoảng thời gian [0,1] là: 175 + 75´0. Công suất của máy vật lý thứ hai M2 ở khoảng thời gian [0, 1] là: 175 + 75´0.5 (W) và năng lượng tiêu thụ là: 220´1 + 212. Tổng năng lượng tiêu thụ của cả hai máy vật lý M1 và M2 của lịch S1 (ký hiệu: 𝐸(! ) là: 𝐸(! = 21272.5 = 𝟒𝟐𝟓𝟑𝟎 (Wh) Còn nếu một giải pháp khác tối thiểu tổng thời gian bận rộn của các máy vật lý thì một lịch S2 thực thi các máy ảo có VM ID là 1, 2 gán lên máy vật lý thứ nhất ở thời điểm bắt đầu là 0, các máy ảo có VM ID là 3, 4 gán lên máy vật lý thứ hai ở thời điểm bắt đầu là 0 và máy ảo có VM ID là 5 được gán lên máy vật lý thứ ba ở thời điểm bắt đầu là 0.
Lịch S2 cần ba máy vật lý nhưng tổng thời gian bận rộn của cả ba máy vật lý chỉ là (100 + 1 + 1) = 102 giờ và tổng năng lượng tiêu thụ (ký hiệu: 𝐸(" ) là: 𝐸(" = 100´250 + (175 + 75´0. Năng lượng tiêu thụ của lịch S2 (25380 Wh) giảm so với năng lượng tiêu thụ của lịch S1 (42530 Wh) là: 40,3%. Qua ví dụ phản chứng này cho thấy việc sử dụng số máy vật lý nhỏ nhất không đạt được mục tiêu tối ưu về năng lượng tiêu thụ trong bài toán lập lịch máy ảo hướng tiết kiệm năng lượng tiêu thụ. Bài toán lập lịch máy ảo tiết kiệm năng lượng là NP-hard [26].
Bài toán gán máy ảo tiết kiệm năng lượng (power-aware virtual machine placement problem) [13], [25], [27] có thể xem như bài toán đóng thùng véc-tơ d chiều (d-dimensional Vector Bin Packing Problem [27], [28]), mỗi thùng (bin) có thể xem như là một máy vật lý, mỗi vật 3 (item) là một máy ảo cần phải đặt vào thùng, giới hạn các chiều của thùng xem như là giới hạn của các tài nguyên như CPU, bộ nhớ, dung lượng đĩa, băng thông mạng,… trên máy vật lý và chi phí mỗi thùng [29] như là công suất tiêu thụ ở mỗi máy vật lý. Một phép đặt tất cả vật (bin) vào các thùng (bin) là một lời giải cho bài toán gán máy ảo lên các máy vật lý. Bài toán đóng thùng véc-tơ d chiều được biết là NP-hard [26] với mọi d lớn hơn hay bằng 1 [27], [28]. Tồn tại một giải thuật thời gian đa thức để rút giảm bài toán đóng thùng véc-tơ d chiều về bài toán gán máy ảo.
Bài toán gán máy ảo là NP-hard. Quản lý máy ảo [14], [24], [30] với mục tiêu năng lượng hiệu quả là bao gồm đặt máy ảo và di dời. Xuất phát từ bài toán đóng thùng [27] các nghiên cứu [13][31] đề xuất các giải thuật tiết kiệm năng lượng dựa trên tối ưu số máy vật lý nhỏ nhất. Triết lý để tiết kiệm năng lượng ở các nghiên cứu như [13], [24], [25] dùng các kỹ thuật di dời sẽ cho phép dồn tải lên một số nhỏ các máy vật lý và tắt các máy khác không dùng.
Nghiên cứu [31] liên quan bài toán dồn máy ảo nhận biết năng lượng bằng cách tối ưu cân bằng năng lượng – hiệu năng dựa trên giả thuyết về điểm tối ưu hoạt động tồn tại (trong ứng dụng Web, cơ sở dữ liệu) trên từng máy vật lý. Các công việc dùng heuristic đóng thùng sẽ thử tối thiểu số các máy vật lý đang hoạt động và tắt các máy vật lý rảnh (là những máy vật lý không được gán máy ảo nào) nhiều nhất có thể để tiết kiệm điện năng tiêu thụ. Tuy nhiên nhiều nghiên cứu như Tian [23][34] chỉ ra phương pháp di dời các máy ảo có những hạn chế với các ứng dụng tính toán hiệu năng cao. Bài toán lập lịch của luận án này cũng không di dời các máy ảo đang hoạt động để tiết kiệm năng lượng.
Trong luận án này, nghiên cứu sinh cho rằng nếu các máy vật lý là đồng nhất và năng lượng tiêu thụ của máy vật lý tuyến tính theo tải sử dụng, gán máy ảo (cho bài toán lập lịch máy ảo tiết kiệm năng lượng được phát biểu ở trên) để tối thiểu tổng điện năng tiêu thụ của các máy vật lý tương đương với gán máy ảo để tối thiểu tổng thời gian bận rộn của các máy vật lý. Tại bất cứ thời điểm nào, một máy vật lý gọi là bận rộn (busy) nếu có ít nhất một máy ảo được lập lịch thực thi trên máy vật lý này, nếu khác thì máy 4 vật lý này đang rảnh (idle). Tổng thời gian bận rộn (total busy time) [19], [23], [35] của một máy vật lý được hiểu là tổng các khoảng thời gian mà máy vật lý bận rộn. Một nghiên cứu của W.
Bài toán của luận án này khác với bài toán của Tian [23] ở một số điểm: (i) W. Tian [23] có tổng điện năng tiêu thụ cao hơn các giải thuật MinDFT-LDTF, EMinTRE-ST, EMinTRE-FT, EMinTRE-LDTF và EMinTRE-LFT được phát triển trong luận án thông qua đánh giá giải thuật bằng mô phỏng.
