I H C QU C GIA TP. HCM
I H C BÁCH KHOA
--------------------

NG PH M

L P L CH H

TR
HI

QU N LÝ CÁC TÍNH TỐN

Chun ngành: Khoa H c Máy Tính
Mã s : 60.48.01

LU

TP. H CHÍ MINH, tháng 11


C HOÀN THÀNH T I
I H C BÁCH KHOA
-HCM

Cán b

ng d n khoa h c: ........................................................................................

Cán b ch m nh n xét 1: ..............................................................................................

Cán b ch m nh n xét 2: ..............................................................................................

Lu

cb ov t

ngày ..25.. tháng ..12..

iH

TP. HCM

.2013..

Thành ph n H

m:

1. TS. Nguy

c Thái...............................................

2. TS. Nguy

n.....................................

3. TS. Tô Bá Lâm.........................................................
4. TS. Hu

ng Nguyên.......................................


5. TS. Tr

...................................................

Xác nh n c a Ch t ch H
ngành sau khi lu
CH T CH H

ng Khoa qu n lý chuyên
c s a ch a (n u có).

NG


I H C QU C GIA TP.HCM
I H C BÁCH KHOA

C NG HÒA XÃ H I CH
c l p -T do -H nh phúc

T NAM

NHI M V LU

H và tên h c viên:

NG PH

............... MSHV: 11070488.................


10/08/1985 .......................................

TP. HCM .............

Chuyên ngành: KHOA H C MÁY TÍNH .......................... Mã s : 604801 ......................

TÀI: L P L CH H TR QU N LÝ CÁC TÍNH TỐN HI
CAO.........................................................................................................................................
..................................................................................................................................................
NHI M V

VÀ N I DUNG: i) Nghiên c u bài toán l p l
n toán
xu t các mơ hình quy ho ch tuy
làm rõ b n ch t toán h c
c a bài toán; iii) xây d ng gi i thu t heuristic MMgi i quy t bài toán l p l
workflow................................................................................................................................ ..
..................................................................................................................................................
..................................................................................................................................................
II. NGÀY GIAO NHI M V : 21/01/2013

..

III. NGÀY HOÀN THÀNH NHI M V : 22/11/2013.
IV. CÁN B
NGUYÊN.

..............................................
.


............................

NG D N: TS. TR

NG

TP
CÁN B

NG D N

13
NG KHOA


L IC
Xin chân thành c

hai Th y

ng Nguyên. Trong su t
c hoàn thành lu

m

ng d n, TS. Tr

nh


hai Th y
il ic

n tình ch d n tơi t ng
n Cơ, TS. Lê Thành Vân,

cùng các Th y, các b n trong nhóm nghiên c u v nh ng ý ki
giúp

tài

quý báu

c hồn thi

Xin chân thành bi
ih
Thu t Máy tính.

t n tình gi ng d y và
c a t t c quý Th y/Cô t i
c bi t là các Th y/Cô trong khoa Khoa h c và K


TĨM T T

vì

mơ hình tốn
tài ngun cloud.



ABSTRACT
Many large scale scientific applications require computational ability that is beyond
the capabilities of a single computer. The computing requirements and data
intensive of these applications demand a high performance computing platform
such as a cluster, grid or cloud to solve in acceptable executing time. Workflow is
structured as a common model for describing a wide range of scientific applications.
In order to execute workflow applications efficiently and utilize the allocated
resources in an appropriate way, a scheduling policy should be in place.
The scheduling strategies are developed for different objectives such as
minimization of total execution time, minimization of total execution cost,
minimization of execution cost while meeting a user-defined deadline, or
combination of these and so forth. In this study, we focus on building some integer
linear programs for workflow scheduling problem, and developing an algorithm to
address minimizing the total execution time of workflow applications which are
assigned to execute on computational virtual resources provided by cloud.


L
ng, ngo i tr các k t qu tham kh o t các cơng
i dung trình bày trong lu
n n i dung nào c a lu

th c hi
m

cn

l y b ng c p


ng khác.
TP.HCM, 22 tháng 11
ng Ph


PH N LÝ L CH TRÍCH NGANG
H

NG PH
/08/1985
TP. H Chí Minh
a ch : 7/5 Nguy

,P

ng

n, Qu n 12, TP. HCM.

Email:
O
2003 2008: Sinh viên
Công Ngh Thông Tin.
2011

ng

iH c


2013: H c viên cao h

m K Thu t TP. HCM, khoa
i H c Bách Khoa

-HCM,

chun ngành Khoa H c Máy Tính.
Q TRÌNH CƠNG TÁC
2008 2009: K

p trình nhúng t i cơng ty Renesas Design Vietnam.

2009 2011: Gi ng viên t
Công Ngh Thông Tin.
2009 nay: K

iH

m K Thu t TP. HCM, khoa

n m m t i công ty TMA Solutions Vietnam.


Mục lục
Mục lục

i

Danh sách hình vẽ

1 MỞ
1.1
1.2
1.3
1.4

iii

ĐẦU
Động cơ nghiên cứu . . . . . . .
Mục tiêu và phạm vi nghiên cứu
Phương pháp nghiên cứu . . . .
Bố cục luận văn . . . . . . . . .

.
.
.
.

1
1
2
3
3

.
.
.
.
.

.
.
.
.
.

5
5
6
6
7
7
8
9
9
10
11

3 MƠ HÌNH TỐN HỌC
3.1 Phát biểu bài tốn . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Thuật ngữ, ký hiệu . . . . . . . . . . . . . . . . . . . . . .

13
13
13

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.


.
.
.
.

.
.
.
.

.
.
.
.

2 TỔNG QUAN LÝ THUYẾT
2.1 Giới thiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Lập lịch các công việc độc lập (Independent task scheduling)
2.2.1 MET (Minimum Excecution Time) . . . . . . . . . .
2.2.2 MCT (Minimum Completion Time) . . . . . . . . . .
2.2.3 Min-Min, Max-Min . . . . . . . . . . . . . . . . . . .
2.3 Lập lịch workflow (Dependent task scheduling) . . . . . . . .
2.3.1 Lập lịch best-effort . . . . . . . . . . . . . . . . . . .
2.3.1.1 HEFT (Heterogeneous Earliest-Finish-Time)
2.3.1.2 Hybrid.BMCT (Hybrid heuristic) . . . . . .
2.3.2 Lập lịch QoS constraint . . . . . . . . . . . . . . . .

i


.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.

.
.
.
.
.
.
.
.
.

.


MỤC LỤC

.
.
.
.
.
.

15
15
16
16
18
21

.
.
.
.
.
.
.
.
.
.
.

.
.
.

24
24
24
25
27
27
29
32
33
33
33
35
35
36
37

5 TỔNG KẾT
5.1 Đóng góp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Hướng phát triển . . . . . . . . . . . . . . . . . . . . . . . . . . .

41
41
42

Tài liệu tham khảo


43

Các cơng trình đã cơng bố

46

3.2

3.3

3.1.2 Bài tốn quyết định .
Mơ hình quy hoạch tuyến tính
3.2.1 Các ràng buộc . . . . .
3.2.2 Mơ hình 1 . . . . . . .
3.2.3 Mơ hình 2 . . . . . . .
Mô phỏng và so sánh . . . . .

. . . . .
nguyên
. . . . .
. . . . .
. . . . .
. . . . .

.
.
.
.
.
.


.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.

.
.
.
.
.

4 LẬP LỊCH NHIỀU ỨNG DỤNG WORKFLOW
4.1 Phân tích yêu cầu và hướng tiếp cận . . . . . . .
4.1.1 Phân tích yêu cầu . . . . . . . . . . . . . .
4.1.2 Hướng tiếp cận . . . . . . . . . . . . . . .
4.2 Giải thuật MM-HEFT . . . . . . . . . . . . . . .
4.2.1 Các định nghĩa dùng trong giải thuật . . .
4.2.2 Chi tiết giải thuật . . . . . . . . . . . . . .
4.2.3 Phân tích độ phức tạp . . . . . . . . . . .
4.2.4 Ví dụ minh họa . . . . . . . . . . . . . . .
4.2.4.1 Dữ liệu đầu vào . . . . . . . . . .
4.2.4.2 Xuất kết quả . . . . . . . . . . .
4.3 Thực nghiệm và đánh giá . . . . . . . . . . . . .
4.3.1 Thiết lập dữ liệu mô phỏng . . . . . . . .
4.3.2 Phương pháp đánh giá . . . . . . . . . . .
4.3.3 Các kết quả và phân tích . . . . . . . . . .

ii

.
.
.
.
.
.


.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.


.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.

.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.

.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.


Danh sách hình vẽ
3.1
3.2
3.3

Ví dụ về một ứng dụng workflow đơn giản. . . . . . . . . . . . . .
Cấu trúc thu nhỏ của năm loại workflow khoa học. . . . . . . . .
Kết quả chạy được với năm loại workflow với 20 task. . . . . . . .


14
21
23

4.1
4.2
4.3

Hai workflow DAG A và B được hợp nhất thành một workflow. .
Biểu đồ Gantt biểu diễn phép gán các task của các workflow. . . .
Biểu đồ kết quả thời gian hồn thành thực thi trung bình của các
workflow. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Biểu đồ kết quả thời gian chạy trung bình của giải thuật. . . . . .
Biểu đồ kết quả tỷ số trung bình giữa thời gian thực thi tuần tự
và thời gian thực thi song song. . . . . . . . . . . . . . . . . . . .

26
34

4.4
4.5

iii

40
40
40


Chương 1

MỞ ĐẦU
Ngày nay, việc nghiên cứu khoa học ngày càng phụ thuộc vào công nghệ thông
tin, nơi mà các hệ thống máy tính với quy mơ lớn và có hiệu năng tính tốn cao
(ví dụ như clusters, grids và supercomputers) được sử dụng bởi các cộng đồng các
nhà nghiên cứu để thực thi các ứng dụng khoa học của họ. Ứng dụng khoa học
thường địi hỏi nhu cầu tính tốn phức tạp cần sức mạnh tính tốn vượt q khả
năng của một máy tính duy nhất, mất nhiều thời gian để thực thi và các bộ dữ
liệu (datasets) được tạo ra thường có kích thước hàng terabytes hoặc petabytes.
Lưu trữ, truyền dẫn các bộ dữ liệu khoa học với kích thước lớn và việc giải quyết
vấn đề thực hiện tính tốn với tốc độ nhanh đang trở thành một thách thức lớn.

1.1

Động cơ nghiên cứu

Workflow được dùng như cấu trúc chung để mơ hình cho các ứng dụng khoa học
thực thi trên hệ thống phân bố [9]. Các workflow khoa học này xử lý khối lượng
dữ liệu có kích thước và nhu cầu tính tốn rất lớn. Chúng được biểu diễn bởi đồ
thị có hướng và khơng có chu trình, trong đó mỗi cơng việc tính tốn được đại
diện bởi các nút trên đồ thị, và mỗi sự phụ thuộc dữ liệu giữa hai công việc được
biểu diễn bởi cạnh có hướng giữa hai nút. Bởi vì sự quan trọng của các workflow
khoa học, nên có nhiều nghiên cứu xem xét những lợi ích của việc sử dụng điện
tốn đám mây (cloud computing 1 ) nhằm thực thi các workflow khoa học [6-8].
1

/>
1


Những đặc tính điện tốn đám mây đáp ứng được nhu cầu thực thi các workflow

khoa học, điện toán đám mây khơng chỉ cung cấp tài ngun tính tốn hiệu năng
cao, mà cịn kiến trúc hạ tầng có khả năng mở rộng đáp ứng nhu cầu cho các ứng
dụng khoa học thực thi.
Bên cạnh những ưu điểm mà điện toán đám mây mang lại thì những thách
thức mới sẽ phải đối mặt, lập lịch workflow là một trong những thách thức ấy.
Lập lịch workflow là vấn đề của việc phân bổ các cơng việc của workflow có sự
phụ thuộc dữ liệu lẫn nhau đến các tài nguyên phân tán. Trong q trình thực
thi một ứng dụng workflow, các cơng việc và tập tin dữ liệu của workflow cần
được gán và phân phối đến các tài nguyên phân tán trong môi trường cloud.
Những tập tin dữ liệu này cần phải có chiến lược sắp xếp phù hợp, vì khi một
cơng việc được gán cho một tài ngun tính tốn, một số tập tin dữ liệu đầu vào
(input data) cần thiết cho việc thực thi cơng việc đó có thể khơng có sẵn trên tài
ngun tính tốn này. Do đó, để có thể bắt đầu việc thực thi tác vụ sẽ đòi hỏi
việc di chuyển các tập tin dữ liệu đầu vào cần thiết. Tổng số kích thước của các
tập tin trong các workflow khoa học có từ hàng terabytes đến petabytes, việc di
chuyển tập tin như vậy có thể làm tăng tổng thời gian thực thi (makespan) của
workflow, đặc biệt là đối với các workflow có kích thước dữ liệu lớn.

1.2

Mục tiêu và phạm vi nghiên cứu

Workflow là chủ đề nghiên cứu trong nhiều năm nay, trong khi điện toán đám
mây mới nổi lên như một mơ hình điện tốn mới (computing paradigm) mà có
thể sử dụng nó cho việc thực thi các workflow khoa học. Do vậy, để thực thi có
hiệu quả workflow và tận dụng các nguồn tài nguyên được phân phối trên cloud
một cách thích hợp thì một chính sách cho việc lập lịch cần phải được áp dụng
một cách hợp lý.
Các chiến lược lập lịch workflow được phát triển nhằm vào nhiều mục tiêu
khác nhau như giảm thiểu tổng thời gian thực thi, giảm thiểu tổng chi phí cho

việc thực thi, giảm thiểu tổng chi phí thực thi khi vẫn đáp ứng được yêu cầu về
thời gian thực thi, tối đa việc tận dụng các tài nguyên sẵn có (nhằm cân bằng
tải việc sử dụng), hoặc kết hợp các mục tiêu này. Nội dung của đề tài nghiên cứu
này tập trung vào mục tiêu giảm thiểu tổng thời gian thực thi (makespan) các

2


cơng việc của workflow trong mơi trường điện tốn đám mây. Cụ thể:
• Đề tài đưa ra hai mơ hình quy hoạch tuyến tính nguyên (integer linear
program (ILP)) cho bài tốn lập lịch workflow tối ưu. Việc xác định mơ
hình tốn học có thể giúp giải quyết bài tốn bằng cách sử dụng các solver
phổ biến. Độ hiệu quả giữa hai mơ hình tốn học này được phân tích và so
sánh thơng qua một số kết quả mơ phỏng.
• Đề tài đề xuất giải thuật heuristic cho việc lập lịch đồng thời nhiều ứng
dụng workflow trên các cụm tài nguyên phân bố trên cloud. Giải thuật đề
xuất được so sánh, phân tích và đánh giá với các giải thuật đề xuất bởi các
cơng trình nghiên cứu liên quan.
Hai mơ hình toán học và giải thuật heuristic đề xuất trong đề tài được xây dựng
và tiến hành kiểm nghiệm độ hiệu quả trên tập dữ liệu của dự án Pegasus 1 . Do
đó, kết quả thực nghiệm sẽ đặc trưng cho loại dữ liệu này.

1.3

Phương pháp nghiên cứu

Đề tài sẽ vận dụng phương pháp bàn giấy để nghiên cứu bài toán quy hoạch
tuyến tính, các giải thuật lập lịch, chiến lược phân bổ cơng việc-tài ngun trên
hệ phân bố. Từ đó kết hợp với mục tiêu đã đề ra để tiến hành xây dựng mơ hình
tốn học, và giải thuật lập lịch.

Bên cạnh đó, sử dụng thêm phương pháp thực nghiệm để tiến hành thử
nghiệm các mơ hình tốn học, giải thuật lập lịch đã đề xuất dựa trên tập dữ liệu
khách quan và ghi nhận kết quả. Sau đó phân tích đánh giá kết quả dựa trên
mục tiêu tối ưu đã xác định cho bài toán và rút ra kết luận.

1.4

Bố cục luận văn

Nội dung của đề cương luận văn này sẽ được trình bày trong năm chương:
1

/>
3


Chương 1: Mở đầu
Chương này trình bày động cơ nghiên cứu của đề tài, từ đó đặt ra mục tiêu,
phạm vi của đề tài, và phương pháp nghiên cứu.
Chương 2: Tổng quan lý thuyết
Trình bày tổng quan lý thuyết (literature review) về các giải thuật lập lịch workflow, giới thiệu các cơng trình nghiên cứu liên quan.
Chương 3: Mơ hình toán học
Phát biểu mục tiêu tối ưu của bài toán nghiên cứu, đề xuất hai mơ hình quy
hoạch tuyến tính nguyên cho việc giải bài toán.
Chương 4: Lập lịch nhiều ứng dụng workflow
Phân tích u cầu của bài tốn lập lịch đồng thời nhiều ứng dụng workflow trên
các cụm tài nguyên có sự giới hạn về tốc độ truyền dẫn và đề xuất giải thuật
heuristic cho bài toán này.
Chương 5: Tổng kết
Tổng kết những vấn đề đã làm được trong phạm vi luận văn, những đóng góp và

hướng phát triển của luận văn.

4


Chương 2
TỔNG QUAN LÝ THUYẾT
Trong chương này sẽ giới thiệu về nền tảng của vấn đề nghiên cứu, tổng quan
về các giải thuật lập lịch các công việc độc lập, lập lịch workflow, giới thiệu bài
toán và hướng tiếp cận ở những cơng trình nghiên cứu liên quan. Những nghiên
cứu này là nền tảng để xây dựng mơ hình cho bài tốn lập lịch workflow sẽ trình
bày ở Chương 3, và thiết kế giải thuật heuristic trong Chương 4.

2.1

Giới thiệu

Việc tìm hiểu một số giải thuật định thời để có một cái nhìn tổng quan hơn về
các phương pháp tiếp cận giải bài tốn. Từ đó, đề tài đề xuất giải pháp tốt hơn
cho bài toán cụ thể cần giải quyết và cũng từ góc nhìn tổng quan này làm cơ sở
để so sánh, đánh giá với giải pháp mà đề tài đề xuất. Nhìn chung, các giải thuật
này đều dựa trên các bước chính như sau:
• Đầu tiên, tất cả các cơng việc đều được xếp có thứ tự vào trong hàng đợi
cơng việc.
• Khi có tài ngun sẵn sàng, cơng việc có độ ưu tiên cao nhất sẽ được lấy
ra khỏi hàng đợi để gán việc thực thi vào tài ngun này.
• Khi có nhiều tài ngun sẵn sàng cùng lúc thì tùy từng giải thuật sẽ chọn
tài nguyên thích hợp.

5



• Quá trình này được lặp cho đến khi tất cả các cơng việc trong hàng đợi đều
được hồn thành.
Sự khác biệt giữa các giải thuật này là cách tính tốn độ ưu tiên cho cơng
việc và cách chọn nguồn tài nguyên để gán.

2.2

Lập lịch các công việc độc lập (Independent
task scheduling)

2.2.1

MET (Minimum Excecution Time)

Giải thuật MET [15, 18] dựa trên ý tưởng tính ước lượng thời gian thực thi của
mỗi tác vụ (task) trên các tài nguyên khác nhau, sau đó gán mỗi tác vụ vào tài
nguyên mà nó cho là tốt nhất để thực hiện tác vụ đó, khơng quan tâm tại thời
điểm đó tài ngun này có sẵn sàng hay chưa. Giải thuật này có nhược điểm là
khơng cân bằng tải sử dụng vì nhiều khả năng tất cả các tác vụ sẽ chỉ được gán
vào một tài ngun có khả năng tính tốn mạnh.
Ví dụ: Giả sử có hai task cần thực hiện, task thứ nhất có kích thước t1 = 120,
task thứ hai có kích thước t2 = 240. Hai tài nguyên có khả năng lần lượt là
m1 = 60 và m2 = 80. Giả sử thời gian thực hiện của task i trên tài nguyên j là
Eij = ti /mj . Tính thời gian thực hiện các tác vụ trên các tài nguyên tương ứng,
ta được:
E11 = t1 /m1 = 120/60 = 2.0, E21 = t2 /m1 = 240/60 = 4.0,
E12 = t2 /m2 = 120/80 = 1.5, E22 = t2 /m2 = 240/80 = 3.0,
=⇒ E12 có giá trị nhỏ nhất nên t1 được gán vào m2 .

Thực hiện tương tự cho các task còn lại:
E21 = t2 /m1 = 240/60 = 4.0, E22 = t2 /m2 = 240/80 = 3.0,
=⇒ E22 có giá trị nhỏ nhất nên t2 được gán vào m2 .
Vậy cả hai task t1 , t2 đều được gán lần lượt trên m2 nên thời gian hoàn thành
của chúng là makespan = 1.5 + 3.0 = 4.5.

6


2.2.2

MCT (Minimum Completion Time)

MCT là giải thuật kết hợp MET và cân bằng tải, giải thuật [15, 18] thực hiện gán
các công việc cho tài nguyên sao cho công việc đó được hồn thành sớm nhất.
Như vậy, giải thuật này dựa vào thời gian hồn thành chứ khơng dựa vào thời
gian thực thi, khi đó tài nguyên tốt chưa chắc được chọn vì nó đang bận thực thi
một tác vụ nào đó (có xét đến thời điểm để một task có thể bắt đầu thực thi).
Ví dụ: Cũng với các giả sử có các task và tài nguyên giống trong ví dụ ở phần
2.2.1. Giả sử thời gian hồn thành của task i trên tài nguyên j là Fij = Sj + Eij
với Sj là thời điểm có thể bắt đầu thực hiện một task trên tài nguyên j và
Eij = ti /mj là thời gian thực hiện task i trên tài ngun j. Tính thời gian hồn
thành các tác vụ trên các tài nguyên tương ứng, giả sử ban đầu tất cả các tài
nguyên đều sẵn sàng ở thời điểm bắt đầu là 0:
F11 = S1 + E11 = 0 + t1 /m1 = 120/60 = 2.0,
F21 = S1 + E21 = 0 + t2 /m1 = 240/60 = 4.0,
F12 = S2 + E12 = 0 + t1 /m2 = 120/80 = 1.5,
F22 = S2 + E22 = 0 + t2 /m2 = 240/80 = 3.0,
=⇒ F12 có giá trị nhỏ nhất nên t1 được gán vào m2 , đồng thời cập nhật
S2 = 1.5.

Lặp lại các bước thực hiện với các task còn lại:
F21 = S1 + E21 = 0 + t2 /m1 = 240/60 = 4.0,
F22 = S2 + E22 = 1.5 + t2 /m2 = 1.5 + 240/80 = 4.5,
=⇒ F21 có giá trị nhỏ nhất nên t2 được gán vào m1 , cập nhật S1 = 4.0.
Vậy thời gian hoàn thành của hai task t1 , t2 là makespan = max {1.5, 4.0} =
4.0.

2.2.3

Min-Min, Max-Min

Thuật giải Min-Min [15, 18] sử dụng ma trận Minimum Completion Time. Ở mỗi
bước tính, giải thuật ước lượng thời gian hoàn thành của tất cả các task trên tất
cả các tài nguyên hiện có. Task nào được gán việc thực thi vào tài ngun tương
ứng có thời gian hồn thành sớm nhất sẽ được chọn. Sau đó xét lại từ đầu các
task và tiếp tục như vậy cho đến khi hồn thành gán tất cả các task.
Ví dụ: Cũng với giả sử giống ví dụ ở phần 2.2.2, giải thuật Min-Min sẽ thực

7


hiện các bước như sau:
Tính thời gian hồn thành của task t1 trên các tài nguyên khác nhau:
F11 = S1 + E11 = 0 + t1 /m1 = 120/60 = 2.0,
F12 = S2 + E12 = 0 + t1 /m2 = 120/80 = 1.5,
Tính thời gian hồn thành của task t2 trên các tài nguyên khác nhau:
F21 = S1 + E21 = 0 + t2 /m1 = 240/60 = 4.0,
F22 = S2 + E22 = 0 + t2 /m2 = 240/80 = 3.0,
=⇒ Trong số các thời gian hoàn thành nhỏ nhất của các tác vụ, chọn nhỏ
nhất một lần nữa: min {min {F11 , F12 }, min {F21 , F22 }} = min {1.5, 3.0} = 1.5.

Do đó chọn task t1 gán trên m2 , cập nhật giá trị S2 = 1.5.
Lặp lại các bước trên cho các task chưa gán còn lại:
F21 = S1 + E21 = 0 + t2 /m1 = 240/60 = 4.0,
F22 = S2 + E22 = 1.5 + t2 /m2 = 1.5 + 240/80 = 4.5,
Vì chỉ cịn một task t2 nên t2 được gán trên tài ngun m1 , do có thời gian
hồn thành thực thi nhỏ nhất.
Vậy thời gian hoàn thành hai task t1 , t2 : makespan = max {1.5, 4.0} = 4.0.
Tương tự như thuật giải Min-Min nhưng Max-Min ưu tiên gán những task có
thời gian thực hiện lớn. Trong những task có thời gian hồn thành nhỏ, task nào
có thời gian thực hiện lớn mà hồn thành sớm thì ưu tiên được chọn.

2.3

Lập lịch workflow (Dependent task scheduling)

Lập lịch workflow là một quá trình phân bổ việc thực thi của các cơng việc có sự
phụ thuộc lẫn nhau lên các tài nguyên phân tán. Phân phối các tài nguyên phù
hợp cho các công việc của workflow sao cho việc thực thi được hoàn thành nhằm
đáp ứng hàm mục tiêu nào đó được đặt ra bởi người dùng.
Về cơ bản, có hai lớp lập lịch workflow: best-effort và QoS constraint [17].
Chiến lược lập lịch best-effort cố gắng tối thiểu hóa thời gian thực thi workflow,
bỏ qua các yếu tố khác như chi phí thuê tài nguyên, thỏa mãn yêu cầu về dịch
vụ của người dùng (users’ QoS satisfaction). Ngược lại, lập lịch QoS contraint
thì cố gắng tối đa hóa độ hiệu quả dựa theo các ràng buộc về yêu cầu dịch vụ

8


của người dùng, ví dụ như hồn thành thực thi trong thời hạn cho phép nhưng
tối thiểu được chi phí thuê tài nguyên. Mục sau sẽ trình bày các giải thuật ở các

cơng trình nghiên cứu liên quan đến hai lớp lập lịch workflow này.

2.3.1

Lập lịch best-effort

2.3.1.1

HEFT (Heterogeneous Earliest-Finish-Time)

Giải thuật HEFT [11] bao gồm hai giai đoạn (phase) chính: (1) tính tốn độ ưu
tiên của các task (task prioritizing), (2) chọn lựa tài nguyên để thực thi task
(selection processor), sắp xếp theo thứ tự về độ ưu tiên của các task và gán từng
task đến tài nguyên tốt nhất để thực thi task ấy với thời gian hoàn thành được
nhỏ nhất.
Ở giai đoạn tính tốn độ ưu tiên của task được tiến hành bằng cách tính giá
trị rank của task trên workflow DAG được duyệt theo chiều hướng lên (bắt đầu
tính giá trị rank của task kết thúc), task của giá trị rank cao nghĩa là có độ ưu
tiên cao. Giá trị rank của task được tính dựa trên thời gian trung bình để thực
thi task trên tất cả tài nguyên và thời gian trung bình để truyền dẫn dữ liệu sinh
ra giữa hai task trên tất cả kết nối của tài nguyên. Cụ thể giá trị rank của một
task được tính theo cơng thức đệ qui truy hồi như sau:
(2.1a)

rank(uexit ) = wexit
rank(ui ) = wi +

max

∀uj ∈succ(ui )


{ci,j + rank(uj )}

(2.1b)

Trong đó, wexit là thời gian trung bình để thực thi task trên tất cả tài nguyên,
ci,j là thời gian trung bình để truyền dẫn dữ liệu sinh ra giữa hai task trên tất cả
kết nối của tài nguyên.
Trong giai đoạn chọn lựa tài nguyên, các task được định thời theo thứ tự về
độ ưu tiên của chúng và mỗi task được gán vào tài nguyên có khả năng hoàn
thành thực thi trong thời gian ước lượng là sớm nhất. Algorithm 1 là mã giả của
giải thuật HEFT.

9


Algorithm 1 HEFT algorithm
Input: A workflow DAG G = (U, E).
Output: A schedule.
1:
2:
3:
4:
5:
6:
7:
8:

Compute the average execution time for each task u ∈ U .
Compute the average data transfer time between tasks and their successors.

Compute rank value for each task.
Sort the tasks in a scheduling list Q by decreasing order of task rank value.
while Q = ∅ do
u ← remove the first task from Q.
r ← find a resource which can complete u at earliest time.
end while

2.3.1.2

Hybrid.BMCT (Hybrid heuristic)

Giải thuật hybrid heuristic [12] được đề xuất cho việc lập lịch các task của workflow DAG trên hệ phân bố. Giải thuật heuristic này kết hợp với giải thuật lập
lịch các task độc lập sau khi đã nhóm các task khơng có phụ thuộc dữ liệu với
nhau. Tương tự HEFT, hybrid heuristic cũng tiến hành tính tốn độ ưu tiên của
từng task, sắp xếp các task theo thứ tự độ ưu tiên giảm dần, và sau đó gom các
task khơng có sự phụ thuộc dữ liệu thành các nhóm. Trong giai đoạn gom các
task độc lập thành các nhóm, giải thuật phân nhóm các task theo thứ tự độ ưu
tiên của chúng và thêm task vào nhóm hiện tại. Khi nhận thấy một task có sự
phụ thuộc dữ liệu với task khác trong cùng nhóm, thì sẽ tạo nhóm mới và thêm
task này vào nhóm đó. Số của nhóm được gán dựa vào thứ tự giá trị rank của
các task trong cùng nhóm. Sau cùng sẽ áp dụng các giải thuật lập lịch các task
độc lập cho từng nhóm (ví dụ như giải thuật MCT, Min-Min, Max-Min,...). Mã
giả của giải thuật Hybrid heuristic được trình bày ở Algorithm 2.

10


Algorithm 2 Hybrid heuristic
Input: A workflow DAG G = (U, E).
Output: A schedule.

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

Compute the average execution time for each task u ∈ U .
Compute the average data transfer time between tasks and their successors.
Compute rank value for each task.
Sort the tasks in a scheduling list Q by decreasing order of task rank value.
Create a new group Ci and i = 0.
while Q = ∅ do
u ← remove the first task from Q.
if t has dependence with a task in Ci then
i++; create a new group Ci
Add u to Ci
end if
end while

j=0
while j <= i do
Schedule tasks in Ci by using independent task scheduling algorithm.
j++
end while

2.3.2

Lập lịch QoS constraint

Abrishami et al. [4] đề xuất hai giải thuật lập lịch workflow trong môi trường
IaaS cloud: IaaS Cloud Partital Critical Paths (IC-PCP), và IaaS Cloud Partial
Critical Paths with Deadline Distribution (IC-PCPD2). Mục tiêu chính của hai
giải thuật này là tìm một cách phân phối giữa các công việc của workflow và
các VMs của các dịch vụ tính tốn, việc lập lịch sao cho chi phí thuê tài nguyên
phải trả cho việc thực thi workflow là tối thiểu trong khi tổng thời gian thực thi
workflow hoàn thành sớm hơn hoặc bằng với thời hạn cuối (deadline) yêu cầu từ
người dùng. Ý tưởng cơ bản của hai giải thuật này dựa trên chiến lược quay lui
(backtracking), duyệt các task (các node) trên đồ thị công việc bằng kỹ thuật
duyệt theo chiều sâu DFS, lời giải tìm được của giải thuật là một cách định thời

11


khả dĩ (feasible solution). Kết quả thực nghiệm cho thấy giải thuật đề xuất có
thời gian tính tốn rất chậm khi sử dụng workflow có kích thước lớn (khoảng
1000 task).
Cũng với mục tiêu tơi ưu chi phí th tài ngun, Pandey et al. [6] đề xuất giải
thuật meta-heuristics dựa trên phương pháp particle swarm optimization (PSO)
để cho ra một kết quả lập lịch ứng dụng workflow trên tài nguyên của cloud, giải

thuật giải quyết cả hai loại chi phí: chí phí tính tốn và chi phí truyền dẫn dữ
liệu. Kết quả thực nghiệm cho thấy giải thuật heuristic dựa trên PSO đạt được
kết quả tiết kiệm chi phí phải thuê, và đưa ra cách phân bổ tốt workload trên tài
nguyên, tuy nhiên dữ liệu cho việc thực nghiệm giải thuật là chưa đủ lớn.
Trong bài báo của tác giả Genez et al. [5] vấn đề lập lịch workflow được biểu
diễn bằng cơng thức quy hoạch tuyến tính ngun, xem xét việc thuê tài nguyên
theo nhu cầu (on-demand) và để dành (reserved) từ nhiều nhà cung cấp IaaS
cloud. Chiến lược lập lịch đưa ra cách gán giữa các công việc của workflow và
các nhà cung cấp tài nguyên IaaS, sao cho tổng chi phí phải thuê là tối thiểu và
đồng thời thỏa mãn yều cầu về deadline của người dùng. Mô phỏng việc tìm lời
giải của bài tốn lập lịch bằng kết quả chạy được từ solver IBM CPLEX.

12


Chương 3
MƠ HÌNH TỐN HỌC
Việc xây dựng các mơ hình tốn học mang lại một góc nhìn tồn diện hơn về
phương diện toán học của bài toán lập lịch workflow đang xét. Với hai mơ hình
được trình bày trong chương này, chúng ta có thể thấy được sự ảnh hưởng của
việc đặt biến ra quyết định đối với từng mô hình. Các biến quyết định khác nhau
sẽ mang lại hiệu quả tính tốn khác nhau cho từng mơ hình của chúng.
Nội dung trình bày trong chương này dựa trên nghiên cứu của chúng tôi được
công bố tại [16]. Chương này trình bày về hai mơ hình tốn học cho bài tốn lập
lịch workflow, so sánh hai mơ hình dựa vào kết quả thực nghiệm. Cụ thể, phần
3.1 phát biểu bài toán, giới thiệu các thuật ngữ, ký hiệu. Phần 3.2 giới thiệu chi
tiết việc xây dựng hai mơ hình quy hoạch tuyến tính bao gồm phát biểu các ràng
buộc, hàm mục tiêu. Sau cùng, phần 3.3 đưa ra những phân tích, đánh giá về độ
hiệu quả giữa hai mơ hình bằng kết quả mơ phỏng có được từ solver.


3.1
3.1.1

Phát biểu bài toán
Thuật ngữ, ký hiệu

Những ký hiệu sẽ được sử dụng xuyên suốt luận văn được định nghĩa như sau:
• DAG G = (U, E), mỗi nút ui ∈ U đại diện cho một tác vụ (task) của
workflow, và mỗi cạnh ei,j ∈ E đại diện cho sự phụ thuộc dữ liệu giữa hai
task ui và uj . ei,j là dữ liệu được sinh bởi task ui , và được sử dụng bởi task

13


Hình 3.1: Ví dụ về một ứng dụng workflow đơn giản.

uj . Nhãn ở mỗi nút của đồ thị DAG đại diện cho chi phí tính tốn của task,
và nhãn ở mỗi cạnh đại diện cho chi phí truyền dẫn dữ liệu giữa hai nút (ví
dụ như kích thước của tập tin dữ liệu cần được truyền). Hình 3.1 là ví dụ
về một ứng dụng workflow đơn giản.
• n: số task của đồ thị DAG G (n ∈ N);
• U = {u1 , . . . , un }: tập hợp các task của workflow. Một task khơng có bất
kỳ task cha nào gọi là task bắt đầu u1 và một task khơng có bất kỳ task
con nào gọi task kết thúc un ;
• W = {w1 , . . . , wn }: tập hợp các yêu cầu tính tốn của mỗi task u ∈ U ;
• V : tập hợp tất cả máy ảo (VM) (tài nguyên bất đồng nhất) được cấp phát
bởi các máy vật lý trong cloud cá nhân. Số lượng máy ảo m = |V |;
• fi,j : kích thước của tập tin dữ liệu cần được truyền dẫn giữa hai task ui và
uj ;
• H(j): tập hợp tất cả task cha trực tiếp của task uj ∈ U ;

• K(j): tập hợp tất cả task con trực tiếp của task uj ∈ U ;

14