第一工業大学研究報告第27号（2015）pp.13－17

13

A Task Scheduling Method for Data Intensive Jobs in
A Task Scheduling Method for Data Intensive Jobs in
MulticoreMulticore Distributed
Distributed SystemSystem*1*2KazuoHajikano
Kanemitsu
Kazuo
Hajikano*1 Hidehiro
Hidehiro
Kanemitsu*2*1*3
3
MooMoo
WanWanKim*Kim

Department of Information Technology and Electronics, Daiichi Institute of Technology
1-10-2, Kokubu-Chuo, Kirishima, Kagoshgima, 899-4395, Japan*2 Global Education Center, Waseda University
1-104, Totsuka-Chou, Shinjuku, Tokyo, 169-8050, Japan*3

Department of Informatics, Tokyo University of Information Sciences
4-1, Onaridai, Wakaba, Chiba, 265-8501, Japan

Abstract: On task scheduling methods for a work-flow type job with precedence constraint among tasks overheterogeneous distributed environment, methods based on list scheduling are well known. These are considered
to not effective as expected about the response time in data intensive jobs. We propose a task scheduling method fordata intensive jobs in Multicore Distributed System, which can reduce the response time with keeping parallelism inexecution. We show advantage of proposed method against existing methods with experimental simulations.
Key word: task scheduling, multicore, heterogeneous, data intensive

1. Introduction
On task scheduling methods for a work-flow type job
with precedence constraint among tasks overheterogeneous distributed environment, methods basedon list scheduling, e.g., HEFT [1], PEFT(Predict EarliestFinish Time)[2], CEFT(Constrained Earliest FinishTime)[3] are well known. These methods are effective
for reducing the response time against computationallyintensive jobs. On the other hand, these are considered
to not to get improvement as expected about the responsetime in data intensive jobs such as MapReduce because
they try to insert each task in the idle time for eachprocessor without considering the actual data transfertime. We propose a task scheduling method for dataintensive jobs in Multicore Distributed System, which
can reduce the response time with keeping parallelism inexecution.
2. Assumed Model
2.1 Job Model
We assume a job to be executed among distributed
processor elements (PEs) is a Directed Acyclic Graph(DAG), which is one of task graphs. Let be the DAG,Gscls = (Vs, Es, Vscls), where s is the number of task
merging steps (described in 2.3), Vs is the set of tasks
after the s-th task merging step, Es is the set of edges(data communications among tasks) after the s-th task
merging step, and Vscls is the set of clusters which
consists of one or more tasks after the s-th task merging
step. An i-th task is denoted as nsi. Let W(nsi) be a sizeof nsi, i.e., W(nsi) is the sum of unit times taken for being
processed by the reference processor. We define data

dependency and direction of data transfer from nsi to nsj
as esij. And C(esij) is the sum of unit times taken fortransferring data from nsi to nsj over the reference
communication link. One constraint imposed by a DAG
is that a task cannot be started execution until all datafrom its predecessor tasks arrive. If a task does not have
any immediate predecessor, it is called START task, andif a task does not have any immediate successors, it iscalled END task.
2.2 System model
We assumed each computer is completely connectedto others, with heterogeneous processing speed andcommunication bandwidths. Each computer has one ormore PE, i.e., core, with heterogeneous processing speed.
Data transfer time within one computer is supposed to benegligible.
2.3 Definitions of a Cluster and Task Clustering
We denote the i-th cluster in Vscls as clss (i). If nsk isincluded in clss (i) by “the s + 1th task merging”, weclss (i) U
formulate one task merging as {clss+1 (i){nsk}. If any two tasks, i.e., nsi and nsj are included in thesame cluster, this means that they are assigned to thesame processing element. Then the communication
between nsi and nsj is localized, so that communication
time between those is zero. Task clustering is a set oftask merging steps, that is finished when a certain criteria
is satisfied.

3. Previous work
We proposed a method for efficient use ofcomputational resources each of which has a single

14

第一工業大学研究報告

processor in a heterogeneous distributed system [4]. The
method automatically derives the set of mapping
between each processor and each assignment unit (i.e.,the set of tasks in a DAG).

第27号（2015）

For each PE, we derivate the lower bound of a cluster
size to be assigned to the PE theoretically, considering
amount of data and load for a job , and processing
performance and bandwidth for each PE. With thoseHajikano and Kanemitsu and Kim：A Task Scheduling Method for Data Intensive Jobs in Multicore Distributed System

lower bounds, this method can keep parallelism even fordata intensive jobs with adequate number of PEs
involved in execution.
We also introduced WSL (Worst Scheduling Length)
as the index of lower bound and upper bound of theresponse time, which can be calculated before
scheduling. It is proved that WSL should be minimized
to minimize the response time.
3.1 WSL and level of task
WSL means the largest value that the response time cantake when every task is executed as late as possible.
When a task in a cluster is executed as late as possible
and a path including the task from START task to END
task is identified, the level of the task means the responsetime along the path, that is, summation of the maximum
start time of the task and the maximum elapsed time of
the task from its starting time to completion of the ENDtask. Largest value of the level in a cluster is defined as
the level of that cluster. Largest value of the level amongclusters is defined as WSL and we call the cluster with
the WSL as “the cluster dominating WSL” as well as callthe task with WSL as “the task dominating WSL”. Also,
the path that “the task dominating WSL” belongs to iscalled as “the path dominating WSL “In Fig.1, level of task F = tlevel(F) + blevel(F), wheretlevel(F) means elapsed time after execution of START
task until task F become ready to execute, whileblevel(F) means expected longest elapsed time afterexecuting task F until completion of END task . LV(j),i.e., the level of Cluster cls(j) is largest level among thoseof task E, F, G and H.

154. Proposal
To get more reduction of the response time for dataintensive jobs, we enhance the method proposed in [4] asfollows.
- Considering data transfer time, generated new cluster
is assigned to unassigned core belonging to thecomputer having already assigned other cores.
- Using WSL as priority for task scheduling.
Our proposal is consist of following 3 processes.
4.1 Process: Lower bound derivation for eachcluster execution time and PE selection
At first, we define δ is a lower bound of cluster
execution time. Fig. 2 (a) shows state after 4 task
mergings. There are unmerged tasks each of which is
assigned to the “virtual PE” with the maximum
processing speed and communication bandwidth,
respectively. On the other hand, other tasks are assigned
to actual PEs. In Fig. 2 (b), we temporarily assume thattasks on the path dominating WSL will be clustered andeach cluster is assigned to an identical PE (in (b), the PEis PP). From procedure 1) to 3) in (b), We get δopt for
selected PP to minimize upper bound for WSL(For moredetails about δopt derivation, refer to the literature[2].).
Once δopt is obtained, every cluster in (b) is restored toclusters in (a). We calculate δopt and WSL for every
candidate. Candidates are unassigned cores belonging tocomputers, one of whose cores have already been
assigned to the existing cluster at least. If there is no suchcore, unassigned cores belonging to any computers
would be candidates. Among candidates, the core withminimized WSL is selected to be assigned to newcluster in (c).
4.2 Process 2: Task clustering
We select the cluster with maximum level as pivot
and the succeeding cluster dominating level of pivot astarget. These two are merged into a new cluster. Thismerging step is repeated until the new cluster‘s execution
time exceeds the δopt. In (c), it is supposed that we get thenew cluster after six task mergings.
Process 1 and 2 are repeated until all tasks are merged
into clusters assigned to cores.
4.3 Process 3: Task scheduling.
At actual scheduling phase, the level for each readytask is recalculated with actual processor performanceand communication bandwidth, then the task with themaximum level is chosen to be executed next.
Fig. 3 shows state after completing all task mergings.
i.e., all tasks are merged into clusters assigned todifferent cores. Table 1 shows the level of each readytask. There are three ready tasks at 3rd row at Table 1,i.e., B, E and F. Task B belongs to the cluster assigned
to core P1,1 while task E and task F belong to the cluster
assigned to core P1,2. Therefore, task B can be executed

16

第一工業大学研究報告第27号（2015）

more data intensive case, proposed method shows betterperformance.

6. Conclusion
We presented a task scheduling method for dataintensive jobs in Multicore Distributed System. We
confirmed that advantage of proposed method against
existing methods with experimental simulations.

independently of task E and F. Because of task E and Fassigned to same core, we have to choose task E or F tobe executed next. Level of task E is 8.83 while that oftask F is 7.58 (middle of row), therefore Task E is chosen
to be executed next (3rd column).

5. Experiment
5.1 Objectives
We conducted the experimental simulation to confirm
advantages of our proposal against existing methods, i.e.,
HEFT and PEFT in term of response time.
5.2 Experimental Environment
In the simulation, a random DAG is a generated. Inthe DAG, each task size and data size are decided
randomly. Also CCR (Communication to ComputationRation) [5] is chosen as 1, 5 and 10. The max to min ratio
in term of data size is set to 2, 5 and 10. Also, the max tomin ratio in term of communication bandwidth is set to2, 5 and 10.
The simulation environment was developed by
JRE1.6.0_0, the operating system is Windows XP SP3,
the CPU architecture is Intel Core 2 Duo 2.66 GHz, andthe memory size is 2.0 GB.
5.3 Comparison about response time
Fig. 4 shows comparison results. In the Figures, αand β mean max to min ration of the processing speed
and communication bandwidth, respectively. In bothfigures, vertical axis show relative response time whereresponse time of proposed method is “1.00”.
From comparison result in Fig. 4, it is concluded that
response time of proposed method is better than that ofexisting method. Especially, As CCR is larger, that is, inReferences[1] H. Topcuoglu, et el., “Performance-Effective andLow-Complexity Task Scheduling for HeterogeneousComputing, ” IEEE Trans. on Parallel and DistributedSystems, Vol. 13, No. 3., pp. 260-274,2002.
[2] H. Arabnejad, et.el, “List Scheduling Algorithm for
Heterogeneous Systems by an Optimistic Cost Table”,
IEE Trans. on Parallel and distributed systems, vol. 25,
No. 3, pp. 682-694, March 2014[3] M. A. Khan, “Schedule for heterogeneous systems
using constrained critical paths”, Parallel Computing,vol. 38, pp 175-193, 2012[4] H. Kanemitsu, et el, “ A processor Mapping Strategy
for Processor Utilization in a Heterogeneous DistributedSystem”, Journal of Computing, Vol. 3, Issue 11, pp1-8,[5] O. Sinnen and l. A. “Sousa, Communication
Contention in Task Scheduling”, IEE Trans. on paralleland Distributed Systems, Vol. 16, No. 6, pp503-515,
2005

Hajikano and Kanemitsu and Kim：A Task Scheduling Method for Data Intensive Jobs in Multicore Distributed System17