ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN

Bài thu hoạch môn học:TÍNH TOÁN LƯỚI

Đề tài:

SỬ DỤNG GIẢI THUẬT DI TRUYỀN
TRONG BÀI TOÁN ĐIỀU PHỐI CÔNG VIỆC
CHO ĐIỆN TOÁN ĐÁM MÂY Cán bộ giảng dạy: PGS TS NGUYỄN PHI KHỨ
Học viên: ĐỖ ĐÌNH THỦ
Mã số: CH1101140
Lớp CH06
Tp.HCM, 07-2013 Bài thu hoạch môn Tính Toán Lưới
Đỗ Đình Thủ _ CH1101140 Trang 2

Lời nói đầu
Ngày nay, trong thời đại bùng nổ internet, mô hình điện toán đám mây đang đáp
ứng ngày càng nhiều nhu cầu của con người đa dạng về ứng dụng và tần suất sử

2.1.1. Kiến trúc mô hình (Model architecture) 6
2.1.2. Xây dựng bài toán (Problem Formulation) 7
2.1.3. Hàm mục tiêu (Objective function) 8
2.1.4. Ràng buộc (Constraints) 8
2.2. Thuật toán phân lịch, điều phối di truyền đa mục tiêu (MO-GA Scheduling Algorithm) 8
2.2.1. Luật mã hóa (Encoding rule) 8
2.2.2. Khởi tạo quần thể (Population Initialization) 9
2.2.3. Thuật toán di truyền (Genetic Algorithm) 9
2.2.4. Chọn lọc tối ưu theo tiếp cận kho lưu trữ Pareto (Optimal Selection in Pareto Archive) 11
2.2.5. Các bước triển khai (mplementation Steps) 12
2.3. Giả lập và phân tích (Simulations and analysis) 12
2.3.1. Thiết lập thí nghiệm (Experimental Settings) 12
2.3.2. Đánh giá hiệu quả (Performance Evaluation) 13
3. THUẬT TOÁN DI TRUYỀN CHO BÀI TOÁN ĐIỀU PHỐI TÁC VỤ THEO HƯỚNG
TỐI ƯU SỰ HÀI LÒNG CỦA NGƯỜI DÙNG VÀ LỢI NHUẬN CỦA NHÀ CUNG CẤP 16
3.1. Điều phối công việc dựa trên giải thuật di truyền cho điện toán đám mây 16
3.1.1. Mã hóa và khởi tạo (Encoding and Initiation) 16
3.1.2. Hàm thích nghi và sự chọn lọc (Fitness Function and Selection 17
3.1.3. Trao đổi chéo và đột biến (Crossover and Mutation) 17
3.1.4. Điều kiện khởi tạo lại và dừng (Restart and Stop Condition) 18
3.2. Các kết quả giả lập 19
4. KẾT LUẬN 20 Bài thu hoạch môn Tính Toán Lưới
Đỗ Đình Thủ _ CH1101140 Trang 4

1. Giới thiệu
Với sự phát triển của hệ thống ảo và công nghệ Internet, điện toán đám mây
đã nổi lên như một nền tảng điện toán mới (new computing plaform). Điện toán đám


thuật toán dựa trên mô hình giá cả, sử dụng bộ xử lý chia sẻ để cân bằng giữa lợi
nhuận và sử dụng tài nguyên; Gang và cộng sự đề xuất một chương trình điều khiển
thuật toán di truyền tuyến tính, nhằm thiết lập lịch trình tốt nhất trong một tính năng
lưới bằng cách giảm thiểu chi phí kết hợp của tất cả người dùng trong một cách thích
hợp.Tất cả các phương pháp nêu trên xem xét lợi nhuận hoặc năng lượng trong
nghiên cứu của họ nhưng không có mối quan hệ giữa chúng.
Hiện nay có rất nhiều mô hình phân công tác vụ được phát triển bởi nhiều nhà
nghiên cứu để sử dụng tài nguyên tính toán trong môi trường điện toán phân bố,
nhưng các mô hình hiện tại không thích hợp cho điện toán đám mây. Bởi vì các mô
hình hiện tại chính vẫn là đang tập trung vào làm tăng hiệu quả của hệ thống. Hầu hết
các mô hình điều phối công việccho Cluster computing cố gắng vào việc tối thiểu
thời gian hoàn thành của các tác vụ batch. Các mô hình điều phối công việc cho điện
toán lưới, tổ tiên của điện toán đám mây, nhằm mục đích tăng cường số lượng hiệu
suất (performance metrics) giống như tốc độ tính toán và khả năng lưu trữ. Bên cạnh
đó, sự hài lòng của khách hàng và lợi ích của nhà cung cấp phải được xem xét đến để
giải quyết bài toán điều phối công việc trong điện toán đám mây. Nói cách khác, một
bộ phân lịch (scheduler) thực hiện các điều phối công việc đáp ứng các QoS đã đồng
ý trên SLA giữa người dùng dịch vụ điện toán đám mây với nhà cung cấp dịch vụ
điện toán đám mây làm tăng lợi ích cho họ.
Trong phần sau của bài thu hoạch sẽ giới thiệu một mô hình lập kế hoạch vĩ mô
với các thành phần nhận thức và quyết định cho điện toán đám mây, trong đó xem
xét cả các yêu cầu của công việc khác nhau và hoàn cảnh của cơ sở hạ tầng máy tính,
sau đó đưa ra một thuật toán dựa điều phối công việc dựa trên thuật toán di truyền
nhiều mục tiêu (MO-GA), có tính đến tiêu thụ năng lượng và lợi nhuận của các nhà
cung cấp dịch vụ, nhằm cung cấp một cơ chế lựa chọn động phù hợp nhất với các
chương trình điều phối cho người sử dụng theo yêu cầu thời gian thực. Phần cuối là
một thuật toán di truyền khác ứng dụng cho bài toán điều phối công việc cho điện
toán đám mây nhưng hướng tiếp cận là tăng mức hài lòng của người dùng cùng với
lợi nhuận của nhà cung cấp.

- “Request cognition component” phải nhận biết đầy đủ yêu cầu cụ thể cho tất cả
các công việc, trong đó có thể là tính toán, lưu trữ hay yêu cầu thông tin tính toán,
liên quan luật pháp và điều kiện đồng thời, bảo mật, các yêu cầu riêng, QoS, v.v.
- “Service decomposition component” phân rã các yêu cầu dịch vụ vào mức độ
khác nhau với bộ vi xử lý khác nhau thích hợp. Trong các thủ tục tiếp theo, “Task
manager” sẽ phân tích các yêu cầu tài nguyên của mỗi yêu cầu và ánh xạ vào những
bộ xử lý tối ưu để đạt được một giải pháp hiệu quả.
- “Task manager” chịu trách nhiệm quản lý trạng thái công việc (bắt đầu, dừng,
hủy…), xác định thứ tự phân lịch, tài nguyên liên kết và tài nguyên thích hợp cấp
phát cho mỗi yêu cầu dưới sự giúp đỡ của thuật toán điều phối tác vụ.
- “Resource cognition component” thực thi vai trò quản lý tài nguyên rảnh rỗi,
giám sát hiệu quả tài nguyên, tối ưu động theo chiến lược điều phối và thông báo lỗi.
2.1.2. Xây dựng bài toán (Problem Formulation)
Trong mô hình của chúng ta, một ứng dụng điện toán đám mây được xem như tập
hợp các mẫu công việc hay các công việc mang lại từ những tính toán phức tạp bằng
cách sử dụng tài nguyên của điện toán đám mây. Tập A = (a
1
, a
2
, a
3
,…, a
M
) là một
chuỗi ứng dụng đến theo thời gian. Trong suốt quá trình xử lý phân lịch, người dùng
gởi một yêu cầu ứng dụng a
i
(1≤ i ≤ M), với yêu cầu tài nguyên được miêu tả trong 1
bộ 3 thành phần là (t
i

được điều phối và thực thi trên đám mây C
j
, với p
j
là điện
năng cho mỗi máy ảo tại C
j
, như vậy điện năng tiêu thụ khi chạy a
i
cho bởi:
E
ij
= p
j
n
i
t
i
(tích của thời gian cung cấp, số máy ảo, và năng lượng 1 máy)
Lợi ích của nhà cung cấp dịch vụ là:
R
ij
= n
i
t
i
pr - co
ij

Vớ pr là giá đơn vị thu được của nhà cung cấp cho ứng dụng a

2.1.4. Ràng buộc (Constraints)
Các ràng buộc được liệt kê sau đây:
(1) Ứng dụng a
i
phải hoàn thành trước thời hạn d
i
, ngược lại thì điều phối này
xem như thất bại
(2) Mỗi ứng dụng chỉ có thể được phân phối vào chỉ một đám mây
2.2. Thuật toán phân lịch, điều phối di truyền đa mục tiêu
(MO-GA Scheduling Algorithm)
2.2.1. Luật mã hóa (Encoding rule)
Mỗi điều phối biểu diễn bằng ma trận 2 x M. Trong đó M là chiều dài của
chromosome (nhiễm sắc thể). Dòng đầu tiên là số ứng dụng yêu cầu, dòng thứ 2 là số
đám mây tương ứng nơi các ứng dụng được thực thi. Hình 2 là ví dụ của một kết quả
điều phối, trong đó ứng dụng 2 được liên kết với đám mây 0 và ứng dụng 5 được liên
kết với đám mây 1.
Bài thu hoạch môn Tính Toán Lưới
Đỗ Đình Thủ _ CH1101140 Trang 9 Hình 2. Ví dụ mã hóa kết quả điều phối
Theo luật trên ta thấy mỗi ứng dụng chỉ có thể liên kết với 1 đám mây, còn mỗi đám
mây có thể xử lý nhiều ứng dụng.
2.2.2. Khởi tạo quần thể (Population Initialization)
Quần thể khởi tạo có tác động tới các thế hệ tương lai, nó là bước quan trọng trong
toàn bộ thuật toán. Bước này được xây dựng bằng cách kết hợp ngẫu nhiên và các
phương pháp khởi tạo tham lam (greedy initialization). Với phương pháp khởi tạo
tham lam, bộ điều phối từ chối các ứng dụng không hợp ràng buộc về thời hạn, đó có
thể là nguyên nhân của toàn bộ việc điều phối sai. Loại này của phương thức khởi tạo

(3) Thao tác trao đổi chéo (Crossover Operation)
Thao tác trao đổi chéo sử dụng 2 cá thể s
1
và s
2
để tạo ra 2 cá thể s’
1
và s’
2
. Với cá
thể s
1
đầu tiên ta tạo ngẫu nhiên 2 số nguyên i,j với 1 ≤ i ≤ j ≤ N. Sau đó ta chép phần
s
i
trước i và sau j thành s’
1
. Ánh xạ các tác vụ giữa i và j thành cá thể trung gian s
1
m

tương ứng với kết quả phân bố tác vụ trong s
2
. Cuối cùng chép các tác vụ trong s
1
m

và vị trí tương ứng trong s’
1
. Cơ chế chung là từ 2 cá thể sau khi trao đổi phần phân

2
= (







) và v
3
= (1,0) đại diện cho
ba loại yêu cầu tương ứng. Ví dụ, chọn lựa tối ưu của véc tơ v
1,
v
2,
v
3
lần lượt là p
1,
p
3,

p
5

Hình 4. Sơ đồ ngữ nghĩa của chọn lọc tối ưu

Bài thu hoạch môn Tính Toán Lưới
Đỗ Đình Thủ _ CH1101140 Trang


Hình 5. Đặc trưng của máy ảo trong mỗi đám mây
2.3.2. Đánh giá hiệu quả (Performance Evaluation)
Tiến hành một số thí nghiệm và với các thông số khác nhau của thuật toán MO-
GA. So sánh kết quả với các thuật toán điều phối tối đa ứng dụng và thuật toán điều
phối ngẫu nhiên:
- Các thuật toán điều phối tối đa ứng dụng nhằm mục đích tối đa hóa số lượng các
ứng dụng theo lịch trình.
- Các thuật toán điều phối ngẫu nhiên giao ngẫu nhiên các ứng dụng điện toán
đám mây. Kết quả của mỗi thí nghiệm của MO-GA đã được rút ra từ 30 lần chạy độc
lập. Hình 6 cho thấy sự so sánh của MO-GA với vector lựa chọn v = (







) với hai
thuật toán khác, theo tỷ lệ đến khác nhau.
Bài thu hoạch môn Tính Toán Lưới
Đỗ Đình Thủ _ CH1101140 Trang
14 Hình 6. Thí nghiệm so sánh 3 thuật toaán khác nhau
Từ hình 6 ta có thể có kết luận như sau:
(1) So với các thuật toán khác, phương pháp điều phối MO-GA có thể có được lợi
nhuận cao hơn, trong khi tiêu thụ năng lượng thấp hơn. Khi tỷ lệ xuất hiện thấp,
phương pháp MO-GA tiêu thụ ít năng lượng hơn 44.46%, và có được lợi nhuận cao

Bài thu hoạch môn Tính Toán Lưới
Đỗ Đình Thủ _ CH1101140 Trang
16

3. Thuật toán di truyền cho bài toán điều phối tác vụ theo
hướng tối ưu sự hài lòng của người dùng và lợi nhuận của
nhà cung cấp
Phần này gồm có 2 phần:
- Mô hình điều phối công việc dựa trên thuật toán di truyền (GA) cho điện toán
đám mây và miêu tả làm sao thiết kế các thành phần chức năng điều phối tác vụ theo
giải thuật di truyền.
- Cấu hình giả lập và các kết quả ngắn gọn
3.1. Điều phối công việc dựa trên giải thuật di truyền cho điện
toán đám mây
3.1.1. Mã hóa và khởi tạo (Encoding and Initiation)
Một chromosome ch
k
đại diện cho thông tin cấp phát tác vụ, ví dụ: một phân
lịch tác vụ. k có giá trị từ 1 tới z là số ký hiệu của chromosome (nhiễm sắc thể) trong
một quần thể (population). Xét tính hài lòng của người sử dụng và lợi ích của nhà
cung cấp, bộ điều phối công việc xác định không gian nào để phân phối cho từng tác
vụ trong mỗi chu khì phân lịch. Mỗi chromosome ch
k
gồm có α[i] và β[i] chúng biểu
thị thông tin xử lý tác vụ và máy ảo cấp phát xử lý. Chiều dài của 1 chromosome
bằng với số tác vụ nhập vào.


3.1.3. Trao đổi chéo và đột biến (Crossover and Mutation)
Thao tác trao đổi chéo crossover là một cơ chế đơn giản nhằm hoán đổi 1 phần
của một chromosome cho một chromosome khác. Ở đây, có 2 điểm trao đổi chéo
được sử dụng để chuyển đổi vật liệu di truyền từ thế hệ cha mẹ cho thế hệ con.
Bài thu hoạch môn Tính Toán Lưới
Đỗ Đình Thủ _ CH1101140 Trang
18

Thao tác đột biến chính là việc mở rộng thông tin tìm kiếm bằng cách thay đổi một
phần của chromosome. Trong gian đoạn đầu của giải thuật di truyền, chất lượng của
các chromosome sinh ra không phải là đặc biệt tốt. Trải qua thời gian, chất lượng của
các chromosome được nâng lên cao hơn. Triển vọng trong việc nâng cao chất lượng
là các thao tác đột biến được thực thi sớm trong các bước đầu của giải thuật di truyền.
Nhưng thật khó khi nâng chất lượng của các chromosome bằng các thao tác đột biến
khi mà chất lượng đạt được tới 1 giá trị chuẩn. Trong trường hợp này, thao tác đột
biến sẽ làm tăng thời gian thực thi của giải thuật di truyền. Cho nên chúng tôi dùng
phương pháp, đột biến không đồng nhất, dần dần giảm tỷ lệ đột biến bằng số bản sao.
3.1.4. Điều kiện khởi tạo lại và dừng (Restart and Stop Condition)
Nếu giá trị thích nghi cao nhất của quần thể hiện tại không đạt ngưỡng thích
nghi tối thiểu, các chromosome với giá trị thích nghi cao trong quần thể hiện tại lọc
và cho ra một nữa của thế hệ tiếp, phần còn lại của quần thể sẽ được sinh ra một cách
ngẫu nhiên. Thao tác restart giúp cho hàm điều phối di truyền việc tối ưu cục bộ và
mở rộng không gian tìm kiếm khác. Thao tác khởi tạo lại:
Restart () //Restart operation
Input: a population po, a set of n tasks T, and a set of m processors P
Output: new population po′
{
1. find the chromosome b
ch
with the best fitness value in po;

| ≤ θ (f
t
≤ bf
c
) (1)
Nếu điều kiện dừng trên thỏa, hàm phân lịch di truyền dừng lại và xuất ra
chromosome với giá trị thích nghi cao nhất, ví dụ các điều phối, lịch trình công việc
Bài thu hoạch môn Tính Toán Lưới
Đỗ Đình Thủ _ CH1101140 Trang
19

tốt nhất. Nếu không, hàm phân lịch di truyền tiếp tục restart để phát sinh ra một quần
thể.
3.2. Các kết quả giả lập

Hình 9. Kết quả giả lập
Trong phần này trình bày giả lập mô hình điều phối công việc dựa trên thuật
toán di truyền (GATSM) trên mô hình hóa hệ thống các sự kiện rời rạc và môi trường
giả lập và đã xây dựng các thí nghiệm khác nhau để so sánh GATSM với mô hình
điều phối công việc Round Robin (Round Robin Task Scheduling Model (RRTSM)),
the Load Index-based Task Scheduling Model (LITSM) và the Activity Based
Costing-based Task Scheduling Model (ABCTSM). RRTSM phân phối vào các máy
ảo theo cách xem xét tuần tự thông tin của các tác vụ hay các máy ảo. LITSM sử
dụng một bộ chỉ mục (load index) của các máy ảo cho điều phối công việc. Trong
LITSM, một bộ phân lịch cấp phát các tác vụ vào máy ảo được nạp nhanh thông tin.
Và ABCTSM sử dụng chi phí yêu cầu để giải quyết tác vụ trên mỗi máy ảo và phân
Bài thu hoạch môn Tính Toán Lưới
Đỗ Đình Thủ _ CH1101140 Trang
20


Bài thu hoạch môn Tính Toán Lưới
Đỗ Đình Thủ _ CH1101140 Trang
21

Tài liệu tham khảo:
[1] Sung Ho Jang, Tae Young Kim, Jae Kwon Kim and Jong Sik Lee, “The Study
of Genetic Algorithm-based Task Scheduling for Cloud Computing”, International
Journal of Control and Automation, Vol. 5, No. 4, December, 2012,pp 157-162.
[2] Jing Liu, Xing-Guo Luo, Xing-Ming Zhang, Fan Zhang, Bai-Nan Li, “Job
Scheduling Model for Cloud Computing Based on MultiObjective Genetic
Algorithm”, IJCSI International Journal of Computer Science Issues, Vol. 10, Issue
1, No 3, January 2013, pp 134-139
[3] Nguyễn Phi Khứ, Bài giảng môn Tính toán lưới, Chương trình đào tạo thạc sĩ
CNTT qua mạng, tháng 6 2013