第一工業大学研究報告第28号（2016）pp.19－30

19

A Task Scheduling Method after Clustering for Data Intensive

AA
Task
Clusteringfor
for Data
DataIntensive
Intensive
TaskScheduling
Scheduling Method
Method after
after Clustering
Jobs in Heterogeneous Distributed Systems
Jobs in Heterogeneous
Distributed Systems
Jobs in Heterogeneous
Distributed Systems*1*3*4*1 Kanemitsu*2, Moo Wan*3
Kazuo Kazuo
Hajikano, Hidehiro, and Kim
Hee-Dong
Hajikano, Hidehiro Kanemitsu*2, Kim
Moo Wan, andKim
Hee-Dong Kim*4
*1
*2
*4
Kazuo
Hajikanoof,Information
Hidehiro Kanemitsu, Moo
Wan Kim*3, Daiichi
and Hee-Dong*1 Department
Technology
and Electronics,
InstituteKimof Technology.

*1 Department
of Information Technology and Electronics, Daiichi Institute of Technology.
k-hajikano@daiichi-koudai.ac.jp
k-hajikano@daiichi-koudai.ac.jp*2 Global
Education Center, Waseda University, Tokyo Japan. kanemih@ruri.waseda.jp*2 Global
Education
Center, Waseda
Tokyo
Japan. Sciences,
kanemih@ruri.waseda.jp*3
Department
of Informatics,
Tokyo University,
University ofInformation
Chiba Japan.
*3 Department
of Informatics, Tokyo University of Information Sciences, Chiba Japan.
mwkim@rsch.tuis.ac.jp
mwkim@rsch.tuis.ac.jp*4 Hankuk
University of Foreign Studies, Yongin Korea.
*4 Hankuk University of Foreign Studies, Yongin Korea.

kimhd@hufs.ac.kr
kimhd@hufs.ac.kr

Abstract
SeveralAbstracttask clustering heuristics are proposed for allocating tasks in heterogeneous systems to achieve a good
responsetask
timeclusteringin data intensive
jobs.
hasallocating
been one tasksof challenging
problemssystems
that howtoeachtask ashould
Severalheuristics
areHowever,proposeditforin heterogeneousachievegoodbescheduled
after
a
task
allocation
by
a
task
clustering.
We
proposeataskschedulingmethodafter
task
clustering,
response time in data intensive jobs. However, it has been one of challenging problems that how each task should
leveraging
Worst
Lengthby(WSL)
an upperWe
boundof thea taskschedule
length.method
In our after
proposedmethod, abescheduledafter Schedulea task allocationa taskasclustering.
proposeschedulingtask clustering,task in a WSL
sequence
is Lengthscheduled
preferentiallyto boundmake WSL
by simulation
leveraging
Worst
Schedule(WSL)
as an upperof thesmaller.
scheduleExperimental
length. In ourresults
proposedmethod, a
show
that
the
response
time
isimproved
inseveraltask
clustering
heuristics.
In
particular,
ourproposedschedulingtask in a WSL sequence is scheduled preferentially to make WSL smaller. Experimental results by simulation
methodthe task timeclustering
we proposed
previously
outperforms
conventional
list-basedtask schedulingshow
thatwiththe response
is improvedin several
task clustering
heuristics.
In particular,
our proposed
methods.
method with the task clustering we proposed previously outperforms conventional list-based task schedulingmethods.
Category: Task Scheduling
Keywords:
TaskSchedulingclustering, Task scheduling, Heterogeneous, Data intensive
Category: Task
Keywords: Task clustering, Task scheduling, Heterogeneous, Data intensive

I. INTRODUCTION
I. INTRODUCTION

task scheduling methods for data-intensive jobs areimportantto get methods
efficient useof resources and
quick
task
schedulingfor data-intensive
jobs
areresponsetime(hereinafter,
we
call
it
"schedule
length")important to get efficient use of resources and quick
for real time
responsetimeapplication.
(hereinafter, we call it "schedule length")Ontaskschedulingmethods for a work-flow typefor real time application.
jobOnwithconstraintforamong
tasks overtask precedence
scheduling methods
a work-flow
type
heterogeneous
distributed
environment,
methodsjobwith precedence
constraint
among tasks
over
based
on
list
scheduling,
e.g.,
HEFT
[1],
PEFT
[2],
heterogeneous distributed environment, methods
CEFT on[3]list are
well known.
These[1],methodsarebasedscheduling,e.g., HEFTPEFT [2],effectivefor
reducingtheschedule
lengthagainstCEFT [3] are well known. These methods arecomputationallyintensiveOn theotheragainst
hand,effective
for reducing
thejobs.
schedule
lengththese are considered
notjobs.
to getascomputationallyintensive
On improvement
the other hand,
expectedabout
theschedule
lengthindataintensivethese are considered not to get improvement asjobs suchabout
as MapReduce
becausetry intensive
to insert
expected
the schedule
lengththey
in data
each
task
in
the
idle
time
for
each
processor
jobs such as MapReduce because they try towithout
insertTherefore, computational resource allocations andeach task in the idle time for each processor without

Recently, task execution models are becoming
morediverse,taske.g., execution
grid computing,cloud
Recently,modelsare computing.
becoming
Especially,
wee.g.,
are entering,so called,“Bigcomputing.
Data” eramorediverse,grid computing,
cloud
where
massiveununiformeddata
aregathered
Especially, we are entering, so called, “Big Data”fromera
the real
worldununiformed
and webpages
throughinternet,
where
massive
data aregatheredfromsearched
analyzed
real time manner.
data
thereal andworld
and inwebpages
throughThese
internet,areprocessedinparallelbyheterogamous
systems,i.e.,searched and analyzed in real time manner. These datamany
computational
withvariousareprocessedin parallel byresourcesheterogamous
systems,i.e.,
processing
speed
and
communication
bandwidth,many computational resources with various
connected over
the andnetwork.
Jobs runningbandwidth,
over suchprocessing
speedcommunication
environmentarecalleddata-intensivejobsuchsuchasconnected over the network. Jobs running over
MapReduce, indata traveljob
oversuchtasks.
environment
arewhichcalledlarge
data-intensiveasTherefore, computational
resource
allocations
andMapReduce,in which large
data travel
over tasks.

第一工業大学研究報告

20

considering the actual data transfer time.
On the other hand, considering data communication
time among tasks, many task clustering heuristics
have been proposed for heterogeneous systems withdata communications localized in a cluster, e.g., RAC[4], FCS [5], CHP [6], Triplet [7]. These areconsidered to be effective for data intensive jobs.
These do not use the actual processing time andcommunication bandwidth of each processor, do notalways achieve a good schedule length in all types ofapplications and systems, and do not specify taskscheduling after clustering. Other task schedulingmethods considering data communication time, havebeen proposed, e.g., [8], [9]. These duplicate tasks tolocalize communications among tasks.
We propose a task scheduling method after
completion of task clustering and processor
assignment to the clusters, leveraging WSL (Worst
Schedule Length) [10], [11] affecting schedule length.
It works with conventional clustering heuristics andimprove their schedule length, using the actual
processor time and the communication bandwidth of
the assigned processer.

II. Assumed Mode
A. System ModelIn this paper, we supposed off-line schedulinginstead of on-line scheduling where tasks are assigned
to processer after becoming ready to be executed, e.g.,
the method proposed in [12]. We assumed that a job isexpressed as a Directed Acyclic Graph (DAG), which
is known as a work-flow type job. Let Gs = (V, E, Vscls)
be the DAG, where V is the set of tasks, E is the set ofedges (data communications among tasks), and Vscls is
the set of task clusters including one or more tasks bys task clustering steps. This means that Gs has (|V| - s)
unclustered tasks and |V| = |Vscls | for s = 0. The i-thtask is denoted as ni, and let w(ni) be the size of ni, i.e.,w(ni) is the sum of unit time for processing by thereference processor. We define data dependency anddirection of data transfer from ni to nj as ei,j, c(ei,j) is
the sum of unit time for transferring data from ni to nj
over the reference communication link. One constraint
imposed by a DAG is that a task cannot be started
execution until all data from its predecessor tasks

第28号（2016）

arrive. pred(ni) is the set of immediate predecessors ofni, and suc(ni) is the set of immediate successors of ni.
If pred(ni) =∅, ni is called START task, and if suc(ni)=∅, ni is called END task. If there are one or more pathform ni to nj, we denote such a relation as ni ≺ nj.
We assume that each processor is completely
connected to others over the network, withheterogeneous processing speeds and communication
bandwidths. The set of processor is expressed as P
= {p1, p2, ・・・pn}, and the processing speed of pi
is denoted as αi when that of the reference processor isset to 1. The execution time in the case that nk isprocessed on pi is expressed as tp(nk, αi) = w(nk) /αi.
Let the set of communication bandwidths be β ={β1, β2, ・・・・βn} , where that of the reference
communication link is set 1, and if c(ei,j) is sent frompk to pl, the communication time is defined as thecommunication speed Lk,l is defined as Lk,l = min{βk,βl}, then let the communication time be tc(ei,j , Lk,l) =c(ei,j)/ Lk,l .

B. Task Clustering
A task cluster is a set of tasks explicitly grouped
together before scheduling every task. As a result,every task in a task cluster comes to be assigned to thesame processor. Let the i-th task cluster in Vscls beclss(i). If nsk is included in clss(i) by the (s + 1)th taskclustering, it is expressed by clss+1(i) ← clss(i) U {nsk}.
If any two tasks, i.e., ni and nj are included in the samecluster, they are assigned to the same processor. In thiscase the communication time between nsi and nsj
becomes zero.
The total task size in a task cluster is called the taskcluster size, and let call the value of the task cluster
size divided by the processing time the task cluster
processing time, or T(clss(i), αp).

C. Schedule Length
In a DAG application, a task can start for execution
if every data from its immediate predecessors havearrived. Let the start time of ni on pp be ts(ni, pp), let
the completion time of nj on pp be tf(nj, pp). Then tf(nj ,pp) is defined as follows.
tf(nj , pp) = ts(nj , pp) + tp(w(nj), αp).
(1)
When all the data from pred(nj) has arrived at nj , njHajikano, Kanemitsu, Moo Wan Kim and Hee-Dong Kim：A Task Scheduling Method after Clustering for Data Intensive Jobs in Heterogeneous Distributed Systems

can start for execution immediately. However, even if
every data from pred(nj) has arrived at nj , nj cannot be
started until the execution of another task in the sameprocessor is finished. The time when all the data fromevery immediate predecessor tasks has arrived at nj iscalled as Data Ready Time (DRT) [10]. If we define
DRT of nj on pp when every task in pred(ni) is
schedule as tdr(ni, pq), it is derived as follow.
��� ��� � �� �=max�� �������� ���� ����� ��� � �� � � �� ������� �� ���� ���� (2)From (2), tdr(nj) is derived from the completion timeof tasks in pred(nj) assigned to the same processor andthe data arrival time from tasks in pred(nj) assigned toother processors. In the former case, p = q and tc(c(ei,j),Lp,q) = 0. On the other hand, the latter case requires
data transfer time. The start time of ni , i.e., ts(nj , pp)
is derived using DRT as follows.
ts(nj, pq) = max { tf(ni , pq), tdr(nj , pq)},(3)
where ni has been scheduled. In (3), the choice oftf(ni , pq) affects the completion time of nj. If ts(nj ,pq) is derived by tf(ni , pq), there must be an idle timeslot which can accommodate tp(nj , αq) and starts at
tf(ni , pq) in case of an insertion–based policy. On theother hand, if ts(nj , pq) is derived by tdr(ni, pq), there isdata waiting time for data arrival from otherprocessors. If we define such a data waiting time astw(nj, pp), it can be expressed as follows.
��������� ��� � �� � � ��� ��� � �� ��� ��� � �� � = ���� ��� � �� � � �� ��� � �� �� ����������

(4)
During the time slot derived by (4), some tasks
come to be inserted by an insertion-based policy inorder to minimize their completion time. The schedule
length is expressed by��������������� =max������ ������ ����� ��� � �� ��. (5)D. Task Scheduling in Clusters

�� is 23. In (c), the schedule length in the order of��� → �� → �� is 24, because the data arrival time of���� at �� is delayed by the increase of the start timeof �� . In (d), the schedule length is larger than thatof (b) and (c) by scheduling �� in ����1� at thelatest execution order.
It can be concluded that the schedule length isvaried depending on the execution order for each task
in clusters, even though the set of tasks belonging to
the cluster is same among (b), (c), and (d).

III. PREVIOUS WORK
In our previous work [10], [11], we presented aprocessor assignment strategy for processor utilization.
The number of processors is limited by imposing thelower bound for each cluster size. Under the constraint,
we theoretically showed that which processor should
be assigned the cluster (assignment unit). The
processor to be assigned is the one which has good
impact on minimizing indicative value for theschedule length.

A. Related Results
Our previous works[10], [11] focus on how todecide the lower bound of each assignment unit size
(sum of task size in the task cluster divided by theprocessing speed) in order to find a subset of given
processors. Contributions of the literature [10], [11]are: (i) Worst Schedule Length (WSL) was defined
2
2

6

4

2
4

1

2

1
3

2

3

5

(a) Initial State

2
4

6

3
10

3
5

4
5

6

2

(b) Task scheduling (SL=23)
2
4

1

1

2

10

6

2

4

1

3

5

4

10

6

4

2

Fig.1 shows an example of a task clustering andscheduling tasks. In this figure, (a) represents theinitial state of the DAG, and (b), (c), and (d) represent
the state after a task clustering has been finished.
Execution orders of tasks is different among (b), (c)and (d).
In (b), schedule length in the order of ��� → �� →

21

2

1

4

3

2
5
2

6

(c) Task scheduling (SL=24)

10

4

1

3

5

4

6

1
3

2

5

4
5
2

6

(d) Task scheduling (SL=29)

Fig. 1. Task Scheduling after Task Clustering

22

第一工業大学研究報告

and its effect on the schedule length was proposed, (ii)the lower bound of the assignment unit size for aprocessor was derived. From the following sections,
we briefly describe those two factors.

B. Worst Schedule Length (WSL)
WSL is the maximum execution path length in casethat each task is executed as late as possible in aprocessor, provided that there is no data waiting timefor each task once the processor starts execution.
Since WSL derivation requires the assignment andclustering state M(Gs), at first we present the definitionof M(Gs). At the initial clustering state G0 , each task
belongs to a task cluster and suppose that it is assigned
to the virtual processor pivt ∈ Pvt having the
maximum processing speed and maximum
communication bandwidth, i.e.,
Let M : Gs → P be the assignment state after aprocessor assignment is performed to Gs. M(G0)corresponds to {(cls0(1), p1vt), (cls0(2), p2vt), ….,(cls0(|V|), p|V|vt)}, where pivt is a virtual processor
having the maximum processing speed and the
maximum communication bandwidth. From the initialassignment state, each virtual processor is replacedwith an actual processor and the number of taskclusters is reduced by a processor assignment and atask clustering, i.e., | M(Gs)| ≤ | M(G0)| for s � 0.
Table 1 shows notations for deriving WSL.
WSL(M(� � )) is the maximum of LV(���� ���), which
Table 1. Notation for WSL(M(Gs))(Here, note nk ∈ clss(i)).

第28号（2016）

corresponds to the maximum of �������� �, where�� ∈ � ���� ���� . �������� � is the maximum time
duration from the START task to the END task in casethat �� is scheduled as late as possible. That is,
WSL(M(� � )) is the maximum of level value in all task
at the clustering state of M(� � ). For a task cluster
clss(i), top(clss(i)) is the set of tasks which can start
execution first in clss(i), and in(clss(i)) is the set oftasks having incoming edges from other task clusters
and out(clss(i)) is the set of tasks having outgoingedges to other task clusters. btm(clss(i)) is the set oftasks having no immediate successor tasks in clss(i),and dc(nk , clss(i)) is the set of tasks being one ofdescendant tasks of nk in clss(i). S(nk , clss(i)) is thetime span from the start time of the task in top(clss(i))
to the start time of nk in case that tw(nk , pp) = 0 andevery task having no dependencies with nk is executed
before nk . TL(clss(i)) is the latest start time of the task
in top(clss(i)), and tlevel(nk) is the latest start time ofnk without data waiting time if nk ∉ top(clss(i)).
tlevel(nk) is derived by S(nk , clss(i)) if nk ∉top(clss(i)), otherwise it is the latest data ready time.
blevel(nk) is the longest path length from nk to the
END task, and BL(clss(i)) is the maximum execution
path length including S(nk , clss(i)) and blevel(nk). If
LV(clss(i)) is defined as the sum of TL(clss(i)) andBL(clss(i)), WSL at M(Gs), i.e., WSL(M(Gs)) is definedas the maximum value of LV(clss(i)) where clss(i) ∈Vscls .
EXAMPLE 3.1. Fig. 2 presents an example of
WSL derivation. (a) is the DAG at M(G0), and (b) is
the DAG at M(G4), i.e., four tasks have been included
cls 0 (A) A
4 1
cls0 (B) 2|0.5

2|0.5

D

41

8 2

2 0.5

cls 0 (G) 6 1.5
6|1.5

2|0.5

41
2|1

8|2

(a )The state of M(G ).

pi

w( X)

c(e X ,Y ) | t c (e X , Y , Li , j )

F

2 1
2|0.5

H

8|2

cls4(H)( b)The stete of M(G 4 ).

pj
Task ID

8 4

2 0.5
0

X

6|1.5

6|1.5

H

4|0

E

G
cls 4 ( G ) 6 1.5

2 0.5 cls 0 (H)assign

6 3
2|0

D

F

cls 4 (C)

2|1

C

8|0

2 0.5

6|1.5

G

A

4 1

B

6 1.5

cls 0 (E) 2|0.5
cls 0 (F) 4|1
E
cls0 (D)

2|0.5

2|0

C

B

2 0.5
8|2

cls 4 ( A)cls0 (C)assignYt p ( X , i )Meanings of assigned values.

Task
Cluster

Processor( pi , i ,  i )cls 4 ( A)
cls 4 ( C)( p1 , 4 , 2)

cls 4 (G )cls 4 ( H )( p7vt , 4, 4)( p 2 , 2 , 4)
( p8vt , 4, 4)Processor Assignment at (b).

Fig. 2 Example of WSL derivation

Hajikano, Kanemitsu, Moo Wan Kim and Hee-Dong Kim：A Task Scheduling Method after Clustering for Data Intensive Jobs in Heterogeneous Distributed Systems

in task clusters. In both cases, bold arrows mean theexecution sequence dominating WSL. Suppose there
are three processors (pi, αi, βi) = (p1, 4, 2), (p2, 2, 4),(p3, 4, 4). At (a), each task belongs to a task cluster
denoted by dashed box and assigned to a virtual
processor having the maximum processing speed
being 4 and the maximum communication bandwidth
being 4. As for cls0(A), we have the following result.
top(cls0(A)) = out(cls0(A)) = btm(cls0(A)) = {A}.
From this state, WSL(M(G0)) = 9.5 is decided by thepath, A, C, E, G, and H, which is the same as thecritical path length at M(G0). On the other hand, at (b)there are four task clusters. At cls4(A), suppose cls4(A),cls4(C), cls4(G), and cls4(H) are assigned to p1, p2, p7vt,
and p8vt , respectively. Then we have the following
result.
top(cls4(A)) = {A}. in(cls4(A)) = ∅.
out(cls4(A)) = {A, D}, btm(cls4(A)) ={D}.
At cls4(C), we havetop(cls4(C)) = {C}. in(cls4(C)) = {C}.
out(cls4(C)) = btm(cls4(C)) = {E, F}.
Since we have the following results as:dc(C, cls4(C)) = {C, E, F}. dc(E, cls4(C)) = {E}.
dc(F, cls4(C)) = {F}.
We obtain the following values:
TL(cls4(C)) = tlevel(C) = 2.
S(E, cls4(C)) = 8 – 4 = 4.
S(F, cls4(C)) = 8 – 1 = 7.
blevel(E) = 9. blevel(F) = 3.5.
BL(cls4(C)) = max {4 + 9, 7 + 3.5} = 13.
Then we have LV(cls4(C)) = 2 + 13 = 15. At the DAG
of (b), cls4(C) has two execution orders, i.e., C, E, F
and C, F, E. LV(cls4(C)) is taken when the execution
order is the former case (the dashed arrow means that
E starts execution after F is finished.). We obtain
LV(cls4(A)) = 14, LV(cls4(G)) = LV(cls4(H)) = 15. Then
we have WSL(M(G4)) = 15.

scheduling method. According to the literature [11], itis proved that both the upper bound and the lower
bound of the schedule length can be made smaller if
WSL is small. Thus, minimizing WSL by a task
allocation can lead to the reduction of the schedule
length.

D. Lower Bound of Assignment Unit Size
In the literature [10], ΔWSLup(M(Gs)) is defined as
an upper bound of WSL(M(GS)) - WSL(M(G0)). Thatis, a small value of ΔWSLup(M(Gs)) means that WSL
can be made smaller by the s-th clustering step.
According to the literature [10], ΔWSLup(M(Gs)) is afunction of the lower bound, the processing speed, andthe communication bandwidth.
At ΔWSL(M(Gs)), there are a number of taskclusters exceeding the lower bound, i.e., δ(αp, βp, Gs)
on a path belonging to the set of tasks dominating
WSL(M(Gs-1)), where αp and βp are variables that must
be determined. Thus,�� �

The task clustering heuristic proposed in theliterature [10] performs to minimize WSL instead ofschedule length because the schedule length cannot be
decided until every task is scheduled by a task������� � ��������� ���� � ��,����� ����� ��

��

(6)

ΔWSLup(M(Gs)) assumes the local minimum value
when δ(αp, βp, Gs) equals to the following value.

cls 4 ( A)

A

A

4 1

2|0
2 0.5

C

6 3
2|0

D

8 4

6|1.5

2|0

E

F

6|1.5

2 1
2|0.5

G
cls 4 ( G ) 6 1.5
6|1.5

6 3
4|0

E

41

2|1

C

8|0

2|1

4 1

cls 4 ( C)

2|1

B

8 4

opt (3 , 3 ,G 5 )

G

8|2

6 1.5
6|1.5

H

2 0.5 cls4(H)26  8 8     9.3
2  2 3


H

2 0.5

(a )The stete of M(G 4 ).

( b) opt ( 3 ,  3 , G 5 ) derivation withthe path (A-C-E-G-H)

cls5 ( A)
2|0being a part of A,C,F,E,G,H

A

4 1

2|1

2|0

D

E

6|2

G

cls5 ( G )

6 3
6|0

8 4

4|0

F

2 1
2|0.67

which dominates WSL(M(G 4 )).
Task
Cluster

6 3

8|0

2|1

cls5 ( C)
C

B

2 0.5

41

C. WSL Properties

23

8|2.67cls5 ( A )cls5 (C)cls5 ( G )Processor( p i , i ,  i )( p1 , 4, 2)( p 2 , 2 , 4)
( p3 , 2, 3)

Processor Assignment at (c).

H

2 1(c)The stete of M(G 5 ).

Fig. 3. Lower Bound Derivation at M(G5)第一工業大学研究報告24���� ��� , �� , � � �max����� �� max �����,� ��∑� �������
≺ ���� � � ����,� ��
=� �
� �
+
�,
��
��
��

(7)
≺
is a path where each task belongs towhere ������
the set of tasks dominating WSL(M(Gs-1)). In (7),
δopt(αp, βp, Gs) is derived by tracing the path in the setof tasks and edges dominating WSL(M(Gs-1)).
EXAMPLE 3.2 Fig. 3 shows an example of thelower bound derivation presented in [10]. At (a), G
and H are un-clustered at M(G4). The path, A, C, E, G,
H is the path in which every task belongs to the set oftasks {E, C, F, G, H} dominating M(G4). From thispath, δopt(αp, βp, G5) is derived as 9.3 by assuming thenext assigned processor is p3. Then cls5(G) includes
one of unclustered tasks, H. However, the total
execution time at cls5(G) at (c) is 3 + 1 = 4 < 9.3 andthen cls5(G) will be clustered into one of cls5(A) orcls5(C) in the next task clustering step.

D. Existing Clustering

Heuristics

Many task clustering heuristics have been proposed
for homogeneous system [14], [15], [16], [17]. In
homogenous systems, task assignment is not required.
As a result, a clustering priority in a task clustering
heuristic for homogeneous system directory affects
the schedule length. However, in heterogeneous
systems, system information, such as the processing
speed and communication bandwidth, is required forderiving a clustering priority. Conventional taskclustering heuristics for heterogeneous systems do not
use actual processing time or communication time forthe clustering priority [4], [5], [6], [7]. The objectiveof a clustering is to localize data communications, and
it is known that DAGs with larger data size have betterschedule length. Even though RAC [4] and FCS [5]define the lower bound of task clusters, they can’t get
good schedule length for all DAG.
On the other hand, in literature [10], we proposed
the task clustering heuristic which derivate the lower
bound for each task cluster automatically and get goodschedule length for all DAGs. Proposed taskclustering heuristic consists of three phases based onminimizing WSL. (i)Derive the lower bound for thecluster size as (7), (ii) decide the processor to be

第28号（2016）assigned, which minimize ΔWSL. Then (iii) merge
several tasks into a cluster until its size exceeds thelower bound derived in (i). In other words, theproposed method manages to generate the linear
cluster to minimize WSL.

IV. PROPOSAL
A. Basic Idea
In this section we propose a task scheduling methodthat is performed after each task has been assigned
to a processor by a task allocation. If task allocationis performed by a task clustering, each task is assigned
to a task cluster, i.e., a task cluster is an assignment
unit for each processor. Followings are features of our
proposal.
- Our proposal minimizes the WSL (Worstschedule Length) to lower the upper and lower
bound of the schedule length.
- We use the actual processing speed and thecommunication bandwidths of each processor
assigned to each task cluster for deriving thescheduling. In the conventional list-based taskscheduling such as HEFT, CEFT and PEFT
adopt average processing time and the averagecommunication time for deriving the schedulingpriority.

B. Proposed Task scheduling
We present how the scheduling priority is derived
for each task. We call a task as a free task, whose every
immediate predecessor tasks have been scheduled.
The objective of the proposed scheduling is tominimize WSL by choosing a task having the
maximum ����� value from the free task list. By
choosing such a task, we obtain the fact that WSL canbe made smaller as follows.
THEOREM 4.1.
Let WSL after m tasks have been scheduled be���� .
If a task �� � ��������� �� ��,�������� � =max ��������� ��,�� ����������

is selected at the m-th task selection phase, then we
have

25

Hajikano, Kanemitsu, Moo Wan Kim and Hee-Dong Kim：A Task Scheduling Method after Clustering for Data Intensive Jobs in Heterogeneous Distributed Systems���� ≤ ������ .

(8)

Proof4.1.
First we define the two set of tasks as follow,����� = ��� ��� � ��������� � ������� � ∩������� � ≠ ∅�.
������� = � ��� � ��������� � ������� � ∩������� � = ∅�.(9)Without loss of generality, suppose that ��
belongs to a task cluster ������ and the level of������ is defined as LV(K).
(i) Level of tasks in����� ,For each task �� � ����� , there can be two cases,

i.e., whether �� belongs to ������ or not.
(i-i) The case of �� � ������.
If we have LV(K) = �������� � before the m-thtask selection, we obtain LV(K) after �� is selected
as follows.
������� ��� �� ≤����� =
max�� ����������� ������ ��� ��� �, (10)where ������ ��� � is �������� � after m tasks
have been scheduled.
(i-ii) The case of �� � ������.
In this case, �������� � is not affected by ��
selection. Thus, WSL is not increased.
(ii) Level of tasks in ����� .
For each task �� � ����� , �������� � is not

INPUT: Clustered DAG G.
OUTPUT: Schedule of G.
Define the task cluster to which ni belongs by C(ni);Define the processor to which ni is assigned by proc(ni);Define USCHED to be set of unscheduled tasks;
Define FREEsched to be the set of tasks whose all immediate
predecessor tasks have been scheduled;
1: WHILE USCHED ≠ ∅ DO
2:
Find ni having a maximum of level(ni) in FREEsched.
If two or more tasks have the same maximum value,
the task ni having maximum blevel value is selected;
3:
FREEsched ← FREEsched - {ni};4:
USCHED ← FREEsched - {ni};5:Insert ni into an idle time slot of proc(ni) s.t,tf(ni, proc(ni)) is minimized by an insertion-based
policy.
6:
Set tf(ni, proc(ni));
7:
FOR nj ∊ suc(ni) DO
8:
IF nk ∉ USCHED for∀nk pred(nj) THEN
9:
FREEsched ← FREEsched ∪ {nj};10:
END IF
11:
END FOR
12: END WHILE

Fig. 4. Procedure for the Schedulingaffected by �� selection. Thus, WSL is notincreased.
From (i) and (ii), it leads that WSL is not increased
by choosing the task having the maximum ����� in��������� . □As described in section III.C, minimizing WSL
contributes to lower the upper bound and the lower
bound of the schedule length. To minimize the WSL,
the strategy of our proposal is to reduce WSL for eachscheduling step. However, how to minimize WSL is
NP-complete problem as with the schedule length
minimization. That is, our proposal is based on aCls(H)A

Cls(E)

4 1.3

2|0.7

3|0

C

B

6 2

8 2.7
16|0

1|0

D

12|0

2|0.7
8 2.7

6|0

2|0

F

4|0

E

4 1.3

2|0.7

6|0

H

G

2 0.7

6 2

6 2

8|0

6|0

J

4 1.3

I

2 0.7

10|0

2|0.7

K

2 0.7

(a) Before Scheduling Tasks
cls(E)Step1

cls(H)FREE
task

Level of FREE
task

Selectedtask & FT

Step

FREE
task

Level of FREE
task

Selectedtask & FT

1

A

level(A)=12.8

FT(A)=1.3

2

Clevel(C)=83

Flevel(F)=84

Hlevel(H)=85Jlevel(J)=8

FT(J)=9.4

6

Klevel(I)=12.8

FT(K)=12.8

level(A)=12.8

B

FT(B)=4.7
2D, E

level(D)=12.8,
blevel(D)=5.4
level(E)=12.8,
blevel(E)=6.8

FT(E)=7.4

3

Dlevel(D)=12.8

FT(D)=8.7

4

Glevel(G)=12.8

FT(G)=10.7

5Ilevel(I)=12.8

FT(I)=11.4

(b)
1.3

p2

A

Scheduling
6.0

3.3 4.0

Cp7

F

12.1 12.8

J

K

H
E

B
2.0

8.1 9.4

4.7

G

D
7.4

8.7

I
10.7 11.4(c) Gantt Chart
Fig. 5. Example of the Scheduling

FT(C)=3.3
FT(F)=4
FT(E)=6

第一工業大学研究報告

26

warranty for WSL reduction. Moreover, our proposal
has a practical time complexity (see Section IV.D) andthus is said to be a cost-effective approach for
reducing both the upper bound and the lower bound of
the schedule length.

C. Procedure and Example
Figure 4 presents the procedures for proposedscheduling. First, ��������� includes all of the
START tasks and USCED includes all of the tasks.
This procedure finishes when USCED becomes empty.
At line 2, the task to be scheduled is selected by the�����. After the completion of task clusterings andprocessor assignments to clusters, �������� � can bederived with the actual processer speed and thecommunication bandwidth of the processer which ��
has been assigned to. That is, we can derivate WSL.
In the scheduling phase, the task having the
maximum ����� in ��������� is scheduled byinserting it into an idle time of the processor. The task
is assigned to an idle time of ������� � at line 5. Afterthe task is scheduled, each task in ������ � becomesa part of ��������� if all of its predecessor tasks
have been scheduled.
Example 4.1 Figure 5 shows an example ofscheduling tasks. Figure 5(a), (b) and (c) present theDAG before scheduling each task, the task scheduling
result, and Gantt chart, respectively. In Fig. 5(a), theDAG has two task clusters and each cluster is assigned
to each processor. Since there is only one START task
in Fig. 5(a), A is included in ��������� , and it isselected for scheduling. Then, B in cls(E) and C incls(E) become free, and their �����s are 12.8 and 8,
respectively; moreover, �� ��� �� � = 1.3. At step 2 ofcls(E) in Fig. 5(b), D and E are assigned to �� , but
their ����� s are same. In this case, their ������
values are compared at line 2 in Fig. 4.
Since ��������� = �.� � ��������� = 6.8 , E isselected. At step3 of cls(E) in Fig. 5(b), D is selected
and its finish time is calculated. There is no idle time
between B and E according to Fig. 5(c), and D is
added after E. As a result, the finish time of D is 8.7.
Similarly, at step 4 of cls(E) in Fig. 5(c), there is no
idle time in B-E or E-D. Thus, G is added after D. At
step 5 of cls(E), step 5 of cls(H) and step 6 of cls(H),I, J, and K are added, and the schedule time is 12.8.

第28号（2016）

D. Complexity of the Proposed Method
In this section, we analyze the complexity of the
proposed scheduling algorithm. At line 2 in Fig. 4, wehave |��������� | ≤ |�| and every task in��������� is ordered according to nonincreasingorder of �����. Thus, one task is put in ���������
by log|��������� | steps. As a whole, this operation
takes ��|�| log|�|�.
At line 5 in Fig. 4, an idle slot can be found by atmost the number of tasks assigned to the processer.
This takes |�|� .
At
line
7
to
11,
this
requires|������ �| log|������ �| steps. As a whole, it takes
��|�| log|�|�.
Therefore, the complexity of the proposedscheduling is �|�|� , which is not higher than those ofexisting scheduling [1], [2], [3].

V. Experiment
A. Objectives
We conducted the experimental simulations toconfirm advantages of our proposal against existing
methods in term of Schedule Length. Actually, theSchedule Length Ratio (SLR) [1], [2] metric was used
to measure the performance of each schedulingmethods. The SLR is defined as follows;
��� =

��

,

∑� ��� �� ��� ������� ��
�

(11)

�� ��

B. Comparison with Existing Scheduling
Methods.
Here, we conducted the experimental simulations toconfirm advantages of the proposed schedulingmethod against existing methods in term of Schedule
Length Ratio (SLR).
1) Existing Scheduling Methods: Any taskclustering heuristics doesn’t specify the taskscheduling method after task clustering. Here, we
picked up following task scheduling methods afterclustering for comparison.
-Method 1: The proposed scheduling method.
-Method 2: The task with minimum rank_down (theHajikano, Kanemitsu, Moo Wan Kim and Hee-Dong Kim：A Task Scheduling Method after Clustering for Data Intensive Jobs in Heterogeneous Distributed Systems

longest path length from START task to the task)
is scheduled. [1]-Method 3: The task with minimum value of sumof rank_down and rank_up (the longest path lengthfrom the task to the END task) is scheduled. [1]-Method 4: The task with maximum rank_up isscheduled. [1]We supposed that Triplet [7] and RAC [4] areclustering heuristics working under task schedulingmethods.
2) Experimental Environment: In the simulation,
two types of DAGs, i.e., random DAGs and Gaussian
Elimination DAGs were generated. We present eachcondition as follow.
a) Random DAGs: In the simulation, 100
DAGs were generated under following conditions andaverage of schedule lengths of DAGs were calculated
after scheduling tasks. For each DAG, the number oftasks in the DAG was chosen from {50, 100, 300, 500,
1000} randomly, the max to min ratio in term of task
size was 100, the max to min ratio in term of data size
was 100, and the Communication to Computation
Ratio (CCR) [13], defined as the averagecommunication bandwidth divided by the average
processing speed, was chosen from {0.1, 0.5, 1, 3, 5,10}. The maximum number of tasks on a path, i.e., thedepth, is defined by the Parallelism Factor (PF), which
Table 2. Comparison of SLR among schedulingmethod for random DAGs (1/2)
CCR
0.1
0.5
1
3
5
10

Triplet w/
method 1
1.438
2.013
2.511
4.014
4.616
8.319

Triplet w/
method 2
1.483
2.211
2.475
4.213
4.672
8.467

Triplet w/
method 3
1.44
2.108
2.497
4.159
4.702
8.513

Triplet w/
method 4
1.421
2.093
2.602
4.186
4.815
8.344

Table 4. Comparison of SLR among schedulingmethods for Gaussian elimination DAGs (1/2)
CCR
0.1
0.5
1
3
5
10

Triplet w/
method 1
3.724
6.132
7.375
9.412
13.85815.729Triplet w/
method 2
3.778
6.391
7.668
9.815
14.19416.512

Triplet w/
method 3
3.781
6.218
7.423
9.915
14.011
16.228Triplet w/
method 4
3.517
6.191
7.402
9.529
14.03315.994is denoted by �|�|⁄� ; in our experiments, α waschosen from {0.5, 1.0, 2.0}. For each task, out degree
was randomly chosen from 1 to 5.
For theheterogeneity of the system, processing speed of a
CPU was chosen as normal distribution where the max
to min ratio were set to 2, 5 and 10, andcommunication bandwidth were chosen as normal
distribution where the max to min ratio was set to 2, 5
and 10.
b) Gaussian elimination DAGs:
In thesimulation, 100 DAGs were generated in case thatmatrix size were 10, 30 and 50, and average ofschedule lengths of DAGs were calculated afterscheduling tasks. For each DAG, the max to min ratio
in term of task size was 100, the max to min ratio interm of data size was 100, and the CCR was chosenfrom {0.1, 0.5, 1, 3, 5, 10}. For the heterogeneity ofthe system, processing speed of a CPU was chosen as
normal distribution where the max to min ratio were
set to 2, 5 and 10, and communication bandwidth werechosen as normal distribution where the max to min
ratio was set to 2, 5 and 10.
The simulation environment was developed by
JRE1.6.0_0, the operating system was Windows XP
SP3, the CPU architecture was Intel Core 2 Duo 2.66
GHz, and the memory size is 2.0 GB.
3) Experimental Result for Each Clustering: Table
Table 3. Comparison of SLR among schedulingmethod for random DAGs (2/2)
CCR
0.1
0.5
1
3
5
10

RAC w/
method 1
2.017
2.736
3.813
7.298
9.371
12.732

RAC w/
method 2
2.271
2.994
4.017
7.419
9.667
13.044

RAC w/
method 3
1.938
2.866
3.905
7.498
9.891
13.318

RAC w/
method 4
1.998
2.831
3.982
7.418
9.776
13.417

Table 5. Comparison of SLR among schedulingmethods for Gaussian elimination DAGs (2/2)
CCR
0.1
0.5
1
3
5
10

RAC w/
method 1
2.017
3.248
4.395
9.155
16.28918.642

RAC w/
method 2
2.133
3.372
4.571
9.372
16.83519.325

RAC w/
method 3
2.317
3.174
4.618
9.779
17.03719.492

RAC w/
method 4
1.983
3.711
4.498
9.227
16.79318.881

27

第一工業大学研究報告

28

2 and 3 show comparison results for random DAGs in
terms of SLR. Table 2 and 3 are cases of Triplet and
RAC, respectively. For each value of CCR, SLRs forRadom DAGs are derived with different schedulingmethods. Table 4 and 5 show the comparison results
for Gaussian Elimination DAGs in terms of SLR.
Table 4 and 5 are cases of Triplet and RAC,
respectively. For each value of CCR, SLRs for
Gaussian Elimination DAGs are derived with different
scheduling methods.
In any case, the proposed scheduling method get
better SLR than that of other scheduling methods if
CCR is equal to or larger than 0.5. That is, theproposed method is suitable for data-intensive jobs
with larger CCR.

第28号（2016）

In this experiment, we compared the SLR by
method 1 in the task clustering in [10], Triplet and
RAC with conventional list-based task schedulingheuristics (HEFT, PEFT, and PEFT). We used same
experimental environment described in section V.B.2).
We call the proposed clustering heuristic in [10] asclustering 1 in this section.
1) Experimental Results: Fig. 6 shows thecomparison results for SLR. For each value of CCR,
SLRs for Radom DAGs are derived with the proposedscheduling methods working above clustering 1,
Triplet and RAC and with HEFT, PEFT and CEFT.
We can see that the proposed clustering heuristic [10]with the proposed scheduling method has better SLRs,
if CCR is larger than 1.0. Fig. 7 shows experimental
results for SLRs on Gaussian elimination DAGs. We
can see that the clustering heuristic in [10] with the

C. Comparison of Clustering Heuristics
14
12

SLR

10
8
6
4
2
0
0.1

0.5

Clustering 1 w/ method 1

1

CCR

Triplet w/ method 1

3

5

RAC w/ method 1

10
HEFT

PEFT

CEFT

Fig. 6. Comparison of SLR among clustering methods for random DAG
20
18
16
14

SLR

12
10
8
6
4
2
0
0.1

0.5

1

3

5

10

CCR
Clustering 1 w/ method 1

Triplet w/ method 1

RAC w/ method 1

HEFT

PEFT

CEFT

Fig. 7. Comparison of SLR among clustering methods for Gaussian elimination

Hajikano, Kanemitsu, Moo Wan Kim and Hee-Dong Kim：A Task Scheduling Method after Clustering for Data Intensive Jobs in Heterogeneous Distributed Systems

proposed scheduling method has better SLRs, if CCR
is equal to and larger than 3. That is, the proposedscheduling method with the clustering heuristic
proposed in [10] is suitable for data intensive jobs withlarger CCR.

D. Discussion
For both of Gaussian elimination DAGs andRandom DAGs, clustering 1 and xEFT (i.e., CEFT,
PEFT, HEFT) doesn’t make big difference in terms of
SLR in case that CCR is less than 3, becausedelays caused by data-waiting time at each task affect
SLR a little.
On the other hand, clustering 1 shows
better SLRs remarkably in case that CCR is equal toand larger than 3. That is, bigger data-transferring
time makes bigger data-waiting time at each processer
and it is considered to contribute to make SLR worse
remarkably. The combination of clustering 1
minimizing WSL and proposed scheduling method,i.e., method 1, which makes WSL smaller was proved
to be effective for larger CCR.
Therefore, the proposed scheduling method
working over the clustering heuristic in [10] is suitablefor work-flow type jobs handling massive data.

XI. CONCLUSION
In this paper, we proposed the task schedulingmethod after completion of task clustering inheterogeneous system. At the proposed method, tasks
on the path dominating WSL, i.e., with maximum
value of level, are preferred to be scheduled. As aresult, the Schedule Length Ratio (SLR) can be madesmaller than that of several existing method, if the
CCR is equal to or greater than 0.5.
Furthermore, the proposed scheduling method withthe task clustering heuristic proposed in [10] has been
confirmed to get smaller SLR than that of well-known
list scheduling method such as HEFT, CEFT and
PEFT, if CCR is equal to or bigger than 3 through theexperiment. In conclusion the proposed schedulingmethod can be applied to execute data-intensive jobsin heterogeneous systems.

REFERENCES

29

1. H. Topcuoglu, et el., “Performance-Effective and
Low-Complexity
Task
Schedulingfor
Heterogeneous Computing,” IEEE Trans. on
Parallel and Distributed Systems, Vol. 13, No. 3.,
pp. 260-274,2002.
2. H. Arabnejad, et.el, “List Scheduling Algorithm for
Heterogeneous Systems by an Optimistic Cost
Table,” IEEE Trans. on Parallel and distributed
systems, vol. 25, No. 3, March 2014.
3. M. A.
Khan, “Schedule for heterogeneous
systems using constrained critical paths,” Parallel
Computing, Vol 38, pp 175-193, 2012.
4. B. Jedari and M. Dehghan, “Efficient DAG
Scheduling with Resource-Aware Clustering for
Heterogeneous Systems,” Computer andInformation Science, Springer, Vol. 208, pp.249261, 2009.
5. S. Chingchit. M. Kumar, and L. N. Bhuyan, “A
Flexible Clustering and Scheduling Scheme for
efficient Parallel Computation, “ Proc. of the 13th
International and 10th Symposium on Paralleland Distributed Processing, pp. 500-505, 1999.
6. C. Boeres, J. V. Filho, and V. E. F. Rebello, “A
Cluster-based Strategy for Scheduling task on
Heterogeneous Processors,” Proc. of the 16th
Symposium on Computer Architecture and Highperformance Computing (SBAC-PAD’04), pp.
214-221, 2004.
7. B. Cirou and E. Jeannot, “Triplet: a Clustering
Scheduling Algorithm for Heterogeneous
Systems,” Proc. of 2001 International Conference
on Parallel Workshops (ICPPW’01), pp. 231-236,
2001.
8. S. G. Ahmad et al., "Data-Intensive Workflow
Optimization based on Application Task Graph
Partitioning in Heterogeneous Computing
Systems," Proc. of IEEE 4th International
Conference on Big Data and Cloud Computing, pp.
129-136, 2014.
9. Aida A. Nasr et al., “Task Scheduling Algorithm forHigh Performance Heterogeneous Distributed
Computing Systems,” International Journal ofComputer Applications (0975 – 8887), Volume 110– No. 16, pp. 23-29, Jan’ 2015
10. H. Kanemitsu et al., “A Processor Mapping
Strategy for Processor Utilization in a
Heterogeneous Distributed System,” Journal of

30

第一工業大学研究報告

Computing, Vol. 3, Issue 11, pp. 1-8, 2011.
11. H. Kanemitsu et al., “On the Effect of Applying
the Task Clustering for Identical processor
Utilization to Heterogeneous Systems,” Grid
Computing – Technologies and Applications,Widespread Converge and new Horizon, Intech(ISBN: 978-953-51-0604-3), pp. 29 – 46, March,
2012.
12. W, Aheng and L. Tang, "A Priority-Based
Scheduling Heuristic to Maximize Parallelism of
Ready Tasks for DAG Applications," Proc. of the
15th IEEE/ACM International Symposium on
Cluster,
Cloud
and
Grid
Computing(CCGrid2015), pp. 596-605, 2015.
13. O, Sinnen “Task scheduling for Parallel systems,”
Willey, 2007.
14. A. Gerasoulis and T. yang, “A Comparison ofClustering Heuristics for Scheduling Directed
Acyclic Graphs on Multiprocessors,” Journal of
Parallel and Distributed Computing, Vol. 16, pp.
276-291, 1992.
15. V. Sarkar, “Partitioning and Scheduling Parallel
programs for Execution on Multiprocessors,”
Cambridge, MA: MIT Press, 1989.
16. M. Y. Wu and D. D. Gajski, “Hypertool: A
programming aid for message-passing systems,”
IEEE Trans. on Parallel and Distributed Systems,
Vol. 1, No. 3, pp. 330-343, 1990.
17. T. Yang and A. Gerasoulis, “DSC: Scheduling
Parallel Tasks on an Unbounded Number ofProcessors,” IEEE Trans. on Parallel andDistributed Systems,” Vol. 5, No. 9, pp. 951-967,
1994.

第28号（2016）