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 (energy aware resource management in cloud computing) tt

CHƯƠNG 1 1.1 GIỚI THIỆU Giới thiệu Điện toán đám mây (ĐTĐM) đang trở thành một mô hình điện toán tiện ích (utility computing) và đượ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 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). 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. 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. 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 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). 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 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. 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ớ, 1 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 (nonpreemption) và không di dời (non-migrating). Một số công trình khác như giải bài toán này theo hướng tối thiểu số máy vật lý sử dụng (và tắt các máy khác không dùng). Tuy nhiê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ý trong bài toán lập lịch máy ảo được nghiên cứu trong luận án này. 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 mạng Thời gian bắt đầu 1 2 3 4 5 0,5 0,5 0,1 0,1 0,2 0,1 0,1 0,5 0,5 0,2 0,1 0,5 0,1 0,1 0,2 0 0 0 0 0 Khoảng thời gian (Đ.vị: Giờ) 100 100 1 1 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.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.Ucpu. Giả sử các máy ảo 2 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à: 𝑡2 𝐸 = ∫𝑡1 𝑃(𝑡)𝑑𝑡 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ý. 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 (M 2) 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.8 = 235 (W) và khoảng thời gian [1, 100] là: 175 + 750.5 = 212.5 (W), tổng năng lượng tiêu thụ của máy vật lý M1 trong khoảng thời gian [0, 100] là: 2351 + 212.599 = 21272.5 (Wh). 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.6 = 220 (W) và ở khoảng thời gian [1, 100] là: 175 + 750.5 = 212.5 (W) và năng lượng tiêu thụ là: 2201 + 212.599 = 21257.5 (Wh). 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: 𝐸𝑆1 ) là: 𝐸𝑆1 = 21272.5 + 21257.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: 𝐸𝑆2 ) là: 𝐸𝑆2 = 100250 + (175 + 750.2)1 + (175 + 750.2)1 𝐸𝑆2 = 𝟐𝟓𝟑𝟖𝟎 (Wh). 3 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ụ. 1.2 Vấn đề tồn tại cần giải quyết Bài toán phân bổ máy ảo tiết kiệm năng lượng là bài toán NP-hard. Xuất phát từ bài toán đóng thùng (bin-packing problem) các nghiên cứu đề 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. Các giải pháp 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 là triết lý để tiết kiệm năng lượng ở các công trình. Tuy nhiên có một công trình chỉ ra phương pháp di dời các máy ảo như các nghiên cứu trước có những hạn chế với các ứng dụng tính toán hiệu năng cao và tổng thời gian bận rộn của các máy vật lý quyết định tổng năng lượng tiêu thụ của các máy vật lý khi lập lịch các công việc có thời gian thực thi cố định. Do đó các phương pháp tối thiểu tổng số máy vật lý dùng không dẫn đến tối thiểu tổng năng lượng sử dụng của các máy vật lý, thay vì vậy nghiên cứu nên tối thiểu tổng thời gian bận rộn (total busy time) của các máy vật lý. Bài toán lập lịch mục tiêu tối thiểu tổng thời gian bận rộn cũng là bài toán NP-hard nên cần có giải thuật hiệu quả. 1.3 Mục tiêu của luận án Mục tiêu của luận án là nghiên cứu bài toán lập lịch máy ảo hướng hiệu quả năng lượng (energy-efficient scheduling of virtual machines) trong môi trường điện toán đám mây với các đặc điểm: (i) môi trường điện toán đám mây dạng hạ-tầng-như-một-dịch-vụ (IaaS cloud), đám mây riêng (private cloud) hay đám mây tính toán hiệu năng cao (High Performance Computing Cloud) cho phép các tài nguyên cung cấp dưới dạng máy ảo; (ii) các máy ảo yêu cầu nhiều loại tài nguyên đồng thời được sử dụng trong các khoảng thời gian bắt đầu và kết thúc cố định; và (iii) các máy ảo không 4 bị di dời (non-migration) và không nhường (non-preemption) trong suốt thời gian thực thi. Dựa trên yếu tố thời gian bắt đầu và kết thúc của máy ảo, mục tiêu chính của luận án là đề xuất các giải thuật lập lịch hướng hiệu quả năng lượng khi đặt tất cả các máy ảo (với yêu cầu tài nguyên của máy ảo biết trước) lên các máy vật lý sao cho tổng năng lượng tiêu thụ của các máy vật lý sử dụng là nhỏ nhất (xét trong toàn bộ thời gian lập lịch). Thay vì đi tìm số máy vật lý nhỏ nhất, luận án sẽ tìm tổng thời gian bận rộn các máy vật lý nhỏ nhất để đạt được tổng năng lượng tiêu thụ của các máy vật lý nhỏ nhất. Luận án đi chứng minh trong môi trường các máy vật lý đồng nhất, công suất của mỗi máy vật lý tuyến tính theo tải sử dụng CPU của máy vật lý và mỗi máy ảo yêu cầu tài nguyên thực thi trong khoảng thời gian cố định, mục tiêu tổng thời gian bận rộn các máy vật lý nhỏ nhất tương đương mục tiêu tổng năng lượng tiêu thụ của các máy vật lý nhỏ nhất. Luận án đánh giá các giải thuật lập lịch đề xuất cho bài toán lập lịch máy ảo bằng mô phỏng (dùng phần mềm CloudSim) và so sánh chúng với các giải thuật lập lịch máy ảo của các công trình khác. Độ phức tạp của các giải thuật lập lịch cũng được tính toán. 1.4 Đóng góp của luận án Những đóng góp chính của luận án bao gồm: 1. Mô tả bài toán lập lịch máy ảo hướng hiệu quả năng lượng. Cho n máy ảo được lập lịch lên m máy vật lý, mục tiêu là hiệu quả năng lượng với các đặc điểm: d tài nguyên (CPU, bộ nhớ, băng thông mạng, v.v…), d – số loại tài nguyên đồng thời được sử dụng 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). 2. 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, 5 MinDFT-LDTF và MinDFT-LFT ở chương 5). Tất cả các giải thuật nhóm thứ nhất đều dựa trên giải thuật chính là MinDFT gán máy ảo lên máy vật lý có tổng thời gian hoàn thành tăng thêm nhỏ nhất. Các giải thuật MinDFT-ST, MinDFT-FT, MinDFT-LDTF và MinDFT-LFT này khác nhau ở cách sắp xếp danh sách máy ảo trước khi gán. MinDFT-ST sắp danh sách máy ảo theo thời gian bắt đầu tăng dần, MinDFT-FT sắp danh sách máy ảo theo thời gian kết thúc tăng dần, MinDFT-LDTF sắp danh sách máy ảo theo thời gian thực thi dài nhất trước và MinDFT-LFT sắp danh sách máy ảo theo thời gian kết thúc sau cùng trước. Hai giải thuật MinDFTST và MinDFT-FT được trình bày ở công trình và hai giải thuật MinDFT-LDTF và MinDFT-LFT được nêu ở công trình. 3. 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à EMinTRE-LFT (ở chương 6). Tất cả các giải thuật nhóm thứ hai EMinTRE này (bao gồm EMinTRE-ST, EMinTRE-FT, EMinTRE-LDTF và EMinTRELFT (ở chương 6)) đều dựa trên giải thuật chính là EMinTRE để tối thiểu tổng thời gian bận rộn của các máy vật lý trong khi vẫn quan tâm đến việc tài nguyên hiệu quả khi gán máy ảo lên máy vật lý. Luận án đề xuất độ đo mới TRE (Time increasing – Resource Efficency) dựa trên độ dài của vector tài nguyên còn trống và thời gian bận rộn tăng thêm trên mỗi máy vật lý. Ý nghĩa của độ đo TRE là khi gán máy ảo lên máy vật lý sẽ quan tâm thêm các chiều tài nguyên khác (như CPU, bộ nhớ, băng thông mạng,…) đang dùng. Nếu các máy có thời gian bận rộn tăng thêm bằng nhau thì giải thuật sẽ gán máy ảo lên máy vật lý nào có độ dài của vector tài nguyên trống còn lại nhỏ nhất. Tất cả các giải thuật EMinTRE6 ST, EMinTRE-FT, EMinTRE-LDTF và EMinTRE-LFT gán máy ảo lên một máy vật lý có giá trị TRE nhỏ nhất, các giải thuật này khác nhau ở cách sắp xếp danh sách máy ảo trước khi gán đến máy vật lý bằng giải thuật EMinTRE. Giải thuật EMinTRE-ST sắp xếp danh sách máy ảo theo thời gian bắt đầu tăng dần, giải thuật EMinTRE-FT sắp xếp danh sách máy ảo theo thời gian kết thúc tăng dần, giải thuật EMinTRE-LDTF sắp xếp danh sách máy ảo theo thời gian thực thi yêu cầu của máy ảo dài nhất trước, còn giải thuật EMinTRE-LFT sắp xếp danh sách máy ảo theo thời gian kết thúc sau cùng trước. 4. Luận án đánh giá các giải thuật lập lịch đề xuất trên và các giải thuật lập lịch so sánh khác bằng mô phỏng các giải thuật lập lịch trên phần mềm CloudSim sử dụng các workload thực (trong các file log-trace) trong Parallel Workload Archive (PWA), hoặc các workload được tạo ra từ mô hình tải của Parallel Workload Models. Kết quả cho thấy các giải thuật MinDFT-ST, MinDFTFT, MinDFT-LDTF, MinDFT-LFT, EMinTRE-ST, EMinTREFT, EMinTRE-LDTF và EMinTRE-LFT đề xuất hiệu quả hơn các giải thuật phổ biến hiện nay trong lập lịch máy ảo. Đặc biệt, giải thuật EMinTRE được đề xuất để giải quyết cho bài toán lập lịch máy ảo với thời gian bắt đầu và kết thúc vì giải thuật EMinTRE cho kết quả tổng năng lượng tiêu thụ nhỏ hơn các giải thuật được so sánh khác gồm: Power-Aware Best-Fit Decreasing (PABFD) của A. Beloglazov, heuristic đóng thùng Norm-based Greedy (VBP-Norm-L2) của R. Panigrahy, Modified First-Fit Decreasing Earliest (Tian-MFFDE) của W. Tian. 5. Luận án phân tích đánh giá độ hiệu quả (lý thuyết) của các giải thuật lập lịch đề xuất. Các giải thuật đề xuất có độ xấp xỉ (approximation) về lý thuyết không lớn hơn g lần so với giải thuật tối ưu (g là số máy ảo lớn nhất có thể gán lên một máy vật lý bất 7 kỳ) trong trường hợp tổng quát và luận án cũng trình bày độ xấp xỉ của giải thuật đề xuất trong một số trường hợp đặc biệt. 1.5 Bố cục của luận án Luận án bao gồm 8 chương: chương 1 sẽ giới thiệu động cơ thực hiện nghiên cứu và các thách thức tồn tại Chương 2 sẽ trình bày nền tảng lý thuyết. Chương 3 sẽ thực hiện phân loại và đánh giá ưu và khuyết điểm của các nghiên cứu trong và ngoài nước đã có và liên quan đến đề tài của luận án đang nghiên cứu. Chương 4 mô tả bài toán, cơ sở của luận án để từ đó đề xuất giải thuật lập lịch máy ảo. Chương 5 và chương 6 luận án trình bày các giải thuật lập lịch đề xuất là MinDFT-ST, MinDFT-FT, MinDFT-LDTF, MinDFT-LFT, EMinTRE-ST, EMinTRE-FT, EMinTRE-LDTF và EMinTRE-LFT cho bài toán lập lịch máy ảo tối ưu tổng điện năng tiêu thụ được nêu ra trong chương 4. Chương 7 phân tích độ xấp xỉ của các giải thuật lập lịch đề xuất trong luận văn ở chương 5 và chương 6. Chương 8 tổng kết và các công việc trong tương lai. CHƯƠNG 2 CƠ SỞ KIẾN THỨC Chương 2 trình bày về cơ sở kiến thức liên quan khái niệm điện toán đám mây (tiếng Anh: cloud computing, viết tắt: ĐTĐM), mô hình hạ tầng như một dịch vụ (IaaS), máy ảo (virtual machine), các công trình quản lý máy ảo trong trung tâm dữ liệu ảo hóa đám mây, bài toán lập lịch công việc song song. Theo các công trình nghiên cứu lý thuyết, tối thiểu tổng thời gian bận rộn (total busy time) của các máy vật lý trong bài toán lập lịch song song có nhiều ứng dụng trong nhiều lĩnh vực như: bài toán truyền tín hiệu qua mạng cáp quang (optical networks), bài toán lập lịch tiết kiệm năng lượng, bài toán thiết kế mạng quang (optimal network design) và bài toán gán wavelengh. Cho bài toán lập lịch trong đó số công việc được xử lý đồng thời bởi một máy có giới hạn. Đầu vào của bài toán là tập n công việc, mỗi 8 công việc kết hợp với một khoảng thời gian bắt đầu và kết thúc cố định. Cho một tham số g ≥1 (g là một số tự nhiên lớn hơn 0) là số lượng công việc tối đa được xử lý đồng thời bởi một máy bất kỳ. Mỗi máy hoạt động liên tục trong các khoảng thời gian này gọi là khoảng thời gian bận rộn (busy interval) mà hợp của tất cả các khoảng thời gian của các công việc được máy xử lý. Mục tiêu là gán các công việc lên các máy sao cho tổng thời gian bận rộn của các máy là nhỏ nhất. Bài toán lập lịch tối thiểu tổng thời gian bận rộn (gọi là MINBUSY) của các máy là NP-hard với g ≥ 2. 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 Chương 3 trình bày các phương pháp luận tiết kiệm năng lượng, mô hình công suất và năng lượng tiêu thụ của một máy vật lý. 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ý, 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 và chỉ ra các đóng góp và giới hạn của các công trình liên quan. Luận án cũng đưa thêm một tiêu chí mới vào cây phân loại các công trình có các kỹ thuật hiệu quả năng lượng mức trung tâm dữ liệu/đám mây dựa trên tối thiểu tổng thời gian thực thi. 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 Chương 4 trình bày 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 được hướng đến của luận án, mô hình công suất và điện năng tiêu thụ của máy vật lý, 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. 9 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Ý 5.1 Giới thiệu Chương này sẽ dựa vào hai định lý 4.1 và 4.2 ở chương 4 - phát hiện của chúng tôi về bài toán phân bổ máy ảo với mỗi máy ảo yêu cầu nhiều tài nguyên, có thời gian bắt đầu và kết thúc xác định trước. Đồng thời chương này cũng trình bày hai giải thuật phân bổ máy ảo tiết kiệm năng lượng của nghiên cứu sinh (ký hiệu MinDFT-ST, MinDFT-FT) trong hệ thống điện toán đám mây với các máy vật lý đồng nhất. Cả hai MinDFT-ST và MinDFT-FT đề xuất nhằm giảm tổng điện năng tiêu thụ cho các máy vật lý theo các định lý nêu trong chương 4. 5.2 Giải thuật MinDFT-ST và MinDFT-FT Hai giải thuật lập lịch tiết kiệm năng lượng: MinDFT-ST và MinDFT-FT tối thiểu thời gian tăng thêm nhỏ nhất để giảm điện năng tiêu thụ của các máy vật lý trong bài toán lập lịch máy ảo. (Giải thuật 5.1 trình bày mã giả cho hai giải thuật MinDFT-ST và MinDFT-FT.) Hai giải thuật MinDFTST và MinDFT-FT khác nhau cách sắp xếp của danh sách máy ảo. Giải thuật MinDFT-ST đề xuất cách sắp xếp danh sách các máy ảo để phân bổ theo thời gian bắt đầu của các máy ảo sớm nhất trước; còn giải thuật MinDFT-FT đề xuất cách sắp xếp danh sách các máy ảo để phân bổ theo thời gian kết thúc (thời gian kết thúc là tổng của thời gian bắt đầu (si) và thời gian thực thi (duri) của từng máy ảo) của các máy ảo sớm nhất trước. Cả hai giải thuật MinDFT-ST và MinDFT-FT đều gọi giải thuật chính MinDFT. MinDFT là một heuristic dạng Best-Fit Decreasing (BFD) để phân bổ một máy ảo mới lên một máy vật lý sao cho thời gian tăng thêm của tổng thời gian hoàn tất của tất cả các máy vật lý (sau khi gán máy ảo này) là nhỏ nhất. Mục đích của hai giải thuật MinDFT-ST và MinDFT-FT đều nhằm tối thiểu tổng thời gian hoàn tất của tất cả các máy vật lý, cũng 10 là tối thiểu tổng năng lượng tiêu thụ (KWh) của các máy vật lý trên một tập các máy ảo đã cho. Thời gian chạy tệ nhất của giải thuật MinDFTST/FT là O(n.m + n log n). Trong các hệ thống điện toán đám mây thường số lượng máy vật lý m khá lớn so với log(n), nên độ phức tạp của giải thuật MinDFT-ST/FT là O(n.m). Hình 5.1 Tổng điện năng tiêu thụ (đơn vị: KWh). Trục hoành biểu diễn Energy (Unit: KWh) 6,000 5,000 4,000 3,000 2,000 1,000 0 các giải thuật phân bổ máy ảo cần so sánh, trục tung biểu diễn tổng điện năng tiêu thụ. 5.3 Giải thuật lập lịch MinDFT-LDTF và MinDFT-LFT Hai giải thuật MinDFT-LDTF và MinDFT-LFT dựa trên giải thuật chính là MinDFT (Giải thuật 5.2) được đề xuất là vì với các cách sắp xếp danh sách máy ảo theo thứ tự khoảng thời gian thực thi yêu cầu dài nhất trước (hoặc thời gian kết thúc muộn nhất trước) vẫn có trường hợp tốt. Giải thuật 5.3 trình bày mã giả của hai giải thuật MinDFT-LDTF và MinDFT-LFT. Khác với giải thuật MinDFT-ST/FT (Giải thuật 5.1). Hai giải thuật MinDFT-LDTF (MinDFT-LFT) sẽ sắp xếp danh sách máy ảo theo thứ tự khoảng thời gian thực thi yêu cầu dài nhất trước (thời gian kết thúc muộn nhất trước), thay vì sắp danh sách máy ảo theo thời gian bắt đầu sớm nhất 11 trước như MinDFT-ST. Thời gian kết thúc của máy ảo tính là tổng của thời gian bắt đầu và khoảng thời gian chạy liên tục và không nhường (nonpreemption) của máy ảo. 5.4 Kết luận Chương 5 của luận án đã trình bày hai giải thuật phân bổ máy ảo là MinDFT-ST, MinDFT-FT, MinDFT-LDTF, MinDFT-LFT cho bài toán lập lịch máy ảo mục tiêu tối thiểu tổng năng lượng tiêu thụ của các máy vật lý (được phát biểu trong chương 4). Hai giải thuật MinDFT-ST, MinDFT-FT được trình bày trong công trình quốc tế có phản biện. 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Ý Chương này đề xuất giải thuật EMinTRE và các cách sắp xếp danh sách máy ảo để phân bổ tạo thành các giải thuật lập lịch gồm: EMinTRE-ST, EMinTRE-FT, EMinTRE-LDTF và EMinTRE-LFT. Giải thuật EMinTRE sử dụng chỉ số TRE lựa chọn máy vật lý có chỉ số TRE nhỏ nhất để gán máy ảo. Chỉ số TRE tính theo thời gian tăng thêm và độ đo về tài nguyên hiệu quả trên từng tài nguyên của máy vật lý (tính theo giá trị chuẩn của vector đường chéo còn trống của các tài nguyên). 6.1 Giới thiệu Nhiều nghiên cứu cho thấy rằng bài toán phân bổ máy ảo (virtual machine allocation) hướng tiết kiệm năng lượng là NP-hard. Có vài nghiên cứu đã thực hiện trên bài toán phân bổ máy ảo tiết kiệm năng lượng. Nhiều nghiên cứu đề xuất giải thuật dồn các máy ảo lên một số ít các máy vật lý bằng cách sử dụng các heuristic của đóng thùng (bin-packing), ví dụ: First-Fit Decreasing, hay Best-Fit Decreasing có sửa đổi. Các phương pháp dùng heuristic đóng thùng sẽ cố gắng dùng số máy vật lý nhỏ nhất để thực thi 12 các máy ảo và tắt các máy rảnh (không có gán bất cứ máy ảo nào trên nó) khác nhiều nhất có thể. Với bài toán lập lịch được mô tả trong chương 4 của luận án này, việc sử dụng số máy vật lý nhỏ nhất không đồng nghĩa với tổng năng lượng tiêu thụ ở tất cả các máy vật lý nhỏ nhất. Trong hệ thống điện toán đám mây (ĐTĐM) với các máy vật lý đồng nhất, và công suất tiêu thụ của các máy vật lý giống nhau và tuyến tính theo tải sử dụng bộ xử lý (CPU utilization), quan sát thấy rằng việc sử dụng số máy vật lý tối thiểu không tương đương tổng năng lượng tiêu thụ ở tất cả các máy vật lý nhỏ nhất. Nghĩa là một lập lịch với thời gian làm việc dài hơn sẽ tiêu thụ nhiều năng lượng hơn lập lịch ngắn hơn. 6.2 Giải thuật lập lịch EMinTRE Trong phần này, nghiên cứu sinh trình bày một giải thuật lập lịch đề xuất tên là: EMinTRE. Luận án đề xuất một độ đo mới (đặt tên là TRE – Time increasing and Resource Efficiency) gồm hai tham số: tỉ lệ thời gian tăng thêm trên tổng thời gian bận rộn và tài nguyên hiệu quả trên các chiều tài nguyên (được ước lượng khi gán một máy ảo đến một máy vật lý). EMinTRE gán một máy ảo lên một máy vật lý sao cho giá trị TRE của máy vật lý là nhỏ nhất. Lặp lại cho đến khi gán hết tất cả các máy ảo trong danh sách. 13 Hình 6.1 Ví dụ đặt hai máy ảo trên một máy vật lý. Giải thuật EMinTRE khác với giải thuật MinDFT (chương 5) là: MinDFT chỉ quan tâm tối thiểu thời gian hoàn thành tăng thêm nhỏ nhất khi gán máy ảo lên một máy vật lý, còn EMinTRE ngoài tỉ lệ tổng thời gian bận rộn tăng thêm còn quan tâm cả tài nguyên hiệu quả trên các chiều tài nguyên là nhỏ nhất khi gán máy ảo lên một máy vật lý. Giải thuật EMinTRE cũng khác giải thuật EMinRET ở điểm: công thức tính độ đo TRE (của EMinTRE) khác với RET (của EMinRET). Giải thuật EMinTRE khác với giải thuật MinDFT (chương 5) là: MinDFT chỉ quan tâm tối thiểu thời gian hoàn thành tăng thêm nhỏ nhất khi gán máy ảo lên một máy vật lý, còn EMinTRE ngoài tỉ lệ tổng thời gian bận rộn tăng thêm còn quan tâm cả tài nguyên hiệu quả trên các chiều tài nguyên là nhỏ nhất khi gán máy ảo lên một máy vật lý. Giải thuật EMinTRE cũng khác giải thuật EMinRET ở điểm: công thức tính độ đo TRE (của EMinTRE) khác với RET (của EMinRET). 14 Tải sử dụng (utilization) của một tài nguyên thứ r (tài nguyên r có thể là tổng số MIPS trên các core (ký hiệu là cpu), dung lượng bộ nhớ vật lý (ký hiệu ram), băng thông mạng (ký hiệu netbw), dung lượng hệ thống file (ký hiệu disk), v.v…) của máy vật lý thứ j (ký hiệu Mj), ký hiệu Uj,r, được tính theo công thức (6.1) sau. Gọi K là tập các tài nguyên đang xét, ℒj là tập các máy ảo được lập lịch lên máy vật lý thứ j. Giả sử có d  ℤ+ loại tài nguyên đang xét trong bài toán lập lịch, ví dụ cho K={1, 2, 3, 4} (với 1 là CPU, 2 là RAM, 3 là băng thông mạng, 4 là đĩa cứng) thì d = 4. Ta có: 𝑈𝑗,𝑟 (𝑡) = 1 ( 𝑀𝑗𝑟 𝑉𝑖𝑟 ) , r ∈ 𝐾, ∀𝑗 ∈ [1, 𝑚] (6.1) ∑ 𝑉𝑖 ∈ℒj ∧𝑠𝑖 ≤𝑡≤𝑠𝑖 +𝑑𝑢𝑟𝑖 trong đó: Vir  ℤ+ là tổng số tài nguyên thứ r được yêu cầu của máy ảo thứ i (ký hiệu Vi), si  ℤ+ và duri  ℤ+ là thời gian bắt đầu và khoảng thời gian thực thi của máy ảo Vi, Mjr  ℤ+ là 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. Tất cả Vir, si và duri đều là không đổi và giả sử cho biết trước lúc yêu cầu các máy ảo. Biểu diễn vector tải sử dụng tài nguyên trên máy vật lý thứ j ở một thời điểm xác định là: Uj = (Uj,1, Uj,2, …, Uj,d). Gọi Dj là độ dài của vector các chiều tài nguyên còn trống của một máy vật lý thứ j (vector tải sử dụng tài nguyên trên máy vật lý thứ j là (Uj,1, Uj,2, …, Uj,d) với các Uj,1, Uj,2 ,…, Uj,d được chuẩn hóa theo giá trị tài nguyên tương ứng trên máy vật lý thứ j đó), Dj được định nghĩa như sau: 𝑑 2 𝐷𝑗 = √ ∑ ((1 − 𝑈𝑗,𝑟 ). 𝑤𝑟 ) , ∀𝑗 ∈ [1, 𝑚] (6.2) 𝑟=1 trong đó ký hiệu wr là trọng số của tài nguyên thứ r trong máy vật lý thứ j. 15 Chỉ số TRE (Time increasing - Resource Efficiency) được đề xuất tính theo công thức (6.3) sau. Giá trị của TRE trên mỗi máy vật lý thứ j sẽ được ký hiệu là TREj, với ∀j∈{1,2,…,m} giá trị TREj được mô tả là: 2 𝑑𝑖𝑓𝑓 𝑡𝑗 𝑇𝑅𝐸𝑗 = ( × 𝑤𝑡𝑖𝑚𝑒 ) + 𝐷𝑗 2 𝑇𝑗 (6.3) trong đó tjdiff là thời gian tăng thêm khi gán một máy ảo đến máy vật lý thứ j, wtime là trọng số của thành phần thời gian trong công thức TREj và Tj là tổng thời gian bận rộn của một máy vật lý Mj. Giải thuật 6.1 trình bày mã giả của giải thuật lõi EMinTRE cho các giải thuật như: EMinTRE-ST, EMinTRE-FT, EMinTRE-LDTF và EMinTRELFT. Giải thuật EMinTRE gán lần lượt từng máy ảo thứ i (i=1, 2, 3,…, n) trong danh sách có thứ tự (đã được sắp xếp theo một thứ tự trước nào đó như: thời gian bắt đầu tăng dần, thời gian dài nhất trước,…) lên một máy vật lý thứ j (1 ≤ j ≤ m) sao cho có giá trị TRE j tính theo công thức (6.3) của máy vật lý này là nhỏ nhất. Giải thuật EMinTRE-LFT là heuristic dạng best-fit có độ phức tạp là (nm), trong đó: n - là số máy ảo cần lập lịch, m - là số máy vật lý trong hệ thống. 6.3 Giải thuật lập lịch EMinTRE-ST, EMinTRE-FT, EMinTRELDTF, EMinTRE-LFT Các giải thuật này gồm hai bước chính là: (i) Bước 1: Sắp xếp danh sách máy ảo cần gán theo một thứ tự nhất định như thời gian bắt đầu tăng dần, hoặc thời gian kết thúc tăng dần, hoặc thời gian thực thi máy ảo dài nhất trước, hoặc thời gian kết thúc của các máy ảo sau cùng trước; (ii) Bước 2: Gọi giải thuật EMinTRE để gán một máy ảo lên một máy vật lý sao cho giá trị TRE của máy vật lý là nhỏ nhất. Lặp lại bước 2 cho đến khi gán hết tất cả các máy ảo trong danh sách. 16 Trong phần này sẽ đánh giá hiệu quả của các giải thuật đề xuất gồm MinDFT-LDTF, MinDFT-LFT, EMinTRE-LDTF và EMinTRE-LFT so sánh với các giải thuật phân bổ máy ảo khác được liệt kê bên dưới: - Giải thuật lập lịch Tian-MFFDE (Modified First-Fit Decreasing Earliest) [27] được chọn làm giải thuật cơ sở để so sánh. Giải thuật TianMFFDE sắp danh sách máy ảo theo thứ tự khoảng thời gian thực thi dài nhất trước và sau đó gán lần lượt từng máy ảo đến một máy vật lý bất kỳ mà tài nguyên trống còn đủ thỏa mãn yêu cầu tài nguyên của máy ảo. - Giải thuật lập lịch PABFD (Power-Aware and Best-Fit Decreasing) là một bin-packing heuristic dạng Best-fit được cải tiến. PABFD sắp danh sách máy ảo theo chiều giảm dần của tổng tải sử dụng CPU được yêu cầu và PABFD sẽ gán một máy ảo mới đến bất cứ máy vật lý nào mà có mức tăng thêm của công suất tiêu thụ là nhỏ nhất. Giải thuật PABFD được chọn để so sánh với các giải thuật mà luận án đề xuất bởi vì PABFD là một heuristic tiết kiệm năng lượng được biết đến rộng rãi trong cộng đồng nghiên cứu các giải thuật đặt máy ảo hướng tiết kiệm năng lượng. - Giải thuật lập lịch VBP-Norm-L2, là heuristic tham lam dựa trên lp-norm bậc 2 (p=2) (Norm-based Greedy) được đề xuất bởi nhóm nghiên cứu thuộc Microsoft Research cho bài toán vector bin-packing (ứng dụng cho bài toán phân bổ máy ảo). VBP-Norm-L2 gán một máy ảo mới đến một máy vật lý mà tối thiểu khoảng cách norm trên phần tài nguyên còn dư (sau khi đặt máy ảo này) của máy vật lý. - Giải thuật lập lịch MinDFT-ST đã được trình bày trong chương 5. Các giải thuật lập lịch trên sẽ được đánh giá dựa trên mô phỏng sử dụng phần mềm CloudSim. Trong mô phỏng, giả sử các ứng dụng có mô hình tải luôn sử dụng các tài nguyên đạt 100% tải của mỗi máy ảo (đã được yêu cầu). Các workload để thử nghiệm các giải thuật được được tạo ra từ hai mô hình workload công việc song song của Feitelson và của Lublin99 trong Parallel Workload Archive (PWA). Thông tin về thời gian đến, thời 17 gian bắt đầu (nếu thời gian bắt đầu không có thì tính bằng tổng của thời gian đến cộng với thời gian đợi trong hàng đợi công việc), thời gian chạy (running time) và số lượng bộ xử lý của mỗi công việc trong log-trace sẽ được chuyển thành thời gian đến, thời gian bắt đầu, thời gian thực thi cho mỗi máy ảo và số lượng máy ảo tương ứng. Khi máy ảo kết thúc thì tất cả các ứng dụng đang chạy trên máy ảo đó cũng kết thúc theo tương ứng. Trên mỗi số lượng máy ảo cần, mỗi máy ảo được tạo xoay vòng trong tám (08) kiểu máy ảo. Tất cả các máy vật lý đều giống nhau và mỗi máy vật lý là một loại máy chủ thông dụng với CPU có tổng cộng 16 core (3250 MIPS/core), bộ nhớ vật lý là 136,8 Gbytes, tổng băng thông mạng là 10 Gb/s, dung lượng đĩa còn trống là 10 Tbytes. Mô hình năng lượng của mỗi máy vật lý: công suất tiêu thụ lúc tải rảnh là 175 W (khi tải của CPU là 0%) – giả định là không có máy ảo nào được thực thi trên máy vật lý, và công suất tiêu thụ cực đại là 250 W (công suất tiêu thụ lúc tải rảnh bằng 70% công suất cực đại). 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. 18 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. 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. 19 6.4 Kết luận Chương 6 của luận án trình bày giải thuật chính EMinTRE bao gồm bốn giải thuật lập lịch gồm EMinTRE-ST, EMinTRE-FT, EMinTRE-LDTF và EMinTRE-LFT (tương ứng bốn cách sắp xếp danh sách máy ảo trước khi gán) cho bài toán lập lịch máy ảo hướng tiết kiệm năng lượng (nêu trong chương 4). Kết quả mô phỏng cho thấy so sánh với các giải thuật khác như Tian-MFFDE, PABFD, VBP-Norm-L2, MinDFT-LDTF thì bốn giải thuật đề xuất gồm EMinTRE-ST, EMinTRE-FT, EMinTRE-LDTF và EMinTRE-LFT đều có tổng năng lượng tiêu thụ nhỏ hơn (tốt hơn các giải thuật đang có của các nghiên cứu khác) trên các mô hình tải công việc song song của Parallel Workload Models. Giải thuật EMinTRE-LDTF tốt nhất với tải của mô hình Feitelson, giải thuật EMinTRE-LFT tốt tốt nhất với tải của mô hình Downey, giải thuật EMinTRE-FT tốt nhất với tải của mô hình Lublin. 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 Chương này phân tích độ hiệu quả trên lý thuyết của các giải thuật lập lịch được đề xuất ở chương 5 và chương 6 trên. CHƯƠNG 8 8.1 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Kết luận Luận án này giải quyết bài toán lập lịch máy ảo trên các máy vật lý mục tiêu tiết kiệm năng lượng tiêu thụ của các máy vật lý. Thách thức của bài toán lập lịch này là NP-hard. Luận án đã phân tích bài toán lập lịch máy ảo với mỗi máy ảo yêu cầu nhiều loại tài nguyên và thực thi trong các khoảng cố định và mỗi máy vật lý có tài nguyên giới hạn. Mặc dù các giải thuật First-fit Decreasing hay Best-fit Decreasing của bài toán đóng thùng (bin-packing problem) tối thiểu số máy vật lý dùng, nhưng luận án chỉ ra rằng phương pháp tối thiểu số máy vật lý không đồng nghĩa với việc tối 20