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 + 750.8 = 235 (W) và
khoảng thời gian [1, 100] là: 175 + 750.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à: 2351 +
212.599 = 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 + 750.6 = 220 (W) và ở khoảng thời gian [1, 100]
là: 175 + 750.5 = 212.5 (W) và năng lượng tiêu thụ là: 2201 + 212.599
= 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 = 100250 + (175 + 750.2)1 + (175 + 750.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à (nm), 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
- Xem thêm -