# A Critical-Path and Top-level attributes based task scheduling algorithm for DAG (CPTL).

1 INTRODUCTION

Task scheduling problem is mapping of tasks of an application program onto the processors and its primary objective is to minimize the execution time. It is an important area of research in parallel computing. Here, an application program is represented by a directed acyclic graph (DAG).

Task scheduling problem is an NP-hard [1,2]. There are three components [3] of tasks scheduling algorithm:(i) are performance of the processors, (ii) mapping of the tasks on to the processors, and (iii) execution order of the tasks on to the processors. Task scheduling algorithm can be either deterministic or non deterministic. In deterministic algorithm, number of tasks, number of processors, execution time of each task on the processors, and communication time between the tasks that are known at compiled time. But in case of nondeterministic algorithm, all the above information is known at run time. The proposed algorithm is based on deterministic model.

In this paper, we present a new approach for task scheduling algorithm in multiprocessor environment which is known as CPTL algorithms. It is based on CPT attribute which is difference of Critical Path (CP) [4], and Top level (t-level) [4]. We find the priority of the tasks of a given DAG using CPT attribute. Also, we present the comparison among proposed algorithm and three task scheduling heuristic algorithms: HLFET, MCP and DLS task scheduling algorithms.

We consider four performance metrics for comparison and performance analysis of the task scheduling algorithms.

The rest of the paper is organized as follows: Problem formulation have done in section 2. Section 3 consists of proposed algorithm and performance metrics are defined in section 4. The performance analysis and results of the task scheduling algorithms has been done in section 5. Finally, we come to conclusion part in section 6.

2 PROBLEM FORMULATIONS

2.1. Application Model

An application model is basically used for representing application programs. Here, task scheduling of an application program is represented by a directed acyclic graph (DAG). It consists of two tuples [G.sub.1]={T,L} where T is a finite set of nth tasks i.e T={[T.sub.1], [T.sub.2], ..., [T.sub.n]} and L is the communication link between the tasks [T.sub.i], and [T.sub.j]. Each task of a given DAG is associated with execution time and communication time between the tasks [T.sub.i], and [T.sub.j]. Layout of a DAG model with six tasks is given below in Figure 1.

When two tasks are allocated on a same processor, their communication time would be negligible. All the tasks should maintain the precedence constraints [6]. Here, an entry task is defined as a task which has not any predecessor task and an exit task is defined as a task which does not any successor task.

2.2 System Computing Model

Multiprocessor environment can be either homogenous or heterogeneous.

Homogenous processors work at same execution speed whereas heterogeneous processors work at different execution speed. In this paper, we consider homogeneous processors, and all processors are fully connected via identical link. A layout of fully connected processors [7] is shown in figure 2.

A major objective of task scheduling algorithm is to minimize the overall execution time i.e. to reduce the scheduling length.

3 PROPOSED ALGORITHM

The proposed algorithm is based on two attributes Critical Path (CP) [4], and Top-Level (T-Level) [4]. T-level of a task [T.sub.i] in a DAG is the longest path from entry task to [T.sub.i], and it does not include execution time of [T.sub.i], and CP is the longest path from entry task to exit task. We have abbreviated this algorithm as Critical Path and T-Level Attributes based Task Scheduling algorithm (CPTL). The CPTL scheduling algorithm uses CPT attribute which is the difference between CP and T-Level attributes. i.e.

CPT([T.sub.i]) = CP - [T.sub.Level(Ti)](i)

Where [T.sub.i] is number of tasks of a given DAG.

CPT attribute is used to computing the priority of the tasks. These tasks are sorted and allocated to the available processors. The tasks are allocated to the processors whose the earliest start time (EST) [8] is smaller.
```
CPTL Scheduling Algorithm:

given DAG

DAG.

Step2: Compute CP of given DAG.

Step3: Compute t-level of given DAG.

Step4: Compute CPT

Step5: Sorting the tasks of CPT in
decreasing order.

Step7:Remove tasks one by one from the
Queue

Step8 : Check Precedence Constraint (PC)
If PC is satisfied then
Allocate to the processor
Else

Removed task insert into end of
the Queue.

Step 9: When last a task of the Queue is
allocated to processor

Find the completion time of the last

Step 10: Stop.
```

3.1 Numerical Examples with Nine and Eleven Tasks.

We have taken two DAG1 and DAG2 with nine and eleven tasks respectively, and considered four homogeneous processor for allocation of the tasks. The communication and execution times are shown in the DAGs.

The scheduling length of proposed algorithm is given in the figure 6.

4 PERFORMANCE METRICS

This section discusses the performance metrics for evaluating the performance of proposed algorithm and heuristic algorithms. We discuss five performance metrics: Scheduling length, Speedup, Efficiency, Load Balancing, and Normalized Scheduling Length (NSL).

4.1 Scheduling length (SL)

Scheduling length is defined as the execution time taken by the last task executed on a processor.

4.2 Speedup (Sp)

Speedup [9] is the ratio of time taken by sequential and parallel execution. It is denoted by following:

Sp = Ts/Tp

Where Ts is the sequential execution time and Tp is the parallel execution time.

4.3 Efficiency (Eff.)

Efficiency [9] is the ratio of Speedup and total number of processors used. It is also called as processor utilization.

Eff = Sp/Pn

Where Sp is Speedup and Pn is the number of processors used.

Load Balancing [10] is the ratio of Scheduling length and mean of execution time of all processors.

LB = SL/Mean

Mean = [[SIGMA].sup.n.sub.i=1]/Pn

Where Pi is a sum of processing time of each processors and Pn is number of processors are used.

4.5 Normalized Scheduling Length (NSL)

Normalized Scheduling length (NSL) [11] of task scheduling algorithm is defined by following:

NSL = SL/max{Sum of computation costs along a path.}

5 PERFORMANCE ANALYSIS

This section presents comparisons among proposed algorithm: CPTL Scheduling algorithm and heuristic algorithms: HLFET, MCP, ETF, and DLS Scheduling algorithms.

CPTL scheduling algorithm gives minimum scheduling length as compared to heuristic scheduling algorithms. All comparisons have been done based on performance metrics in Section 4.

We have tested proposed algorithm on two DAG models with nine and eleven tasks. Also, we have taken four processors for allocation of the priority tasks of given DAGs. Table 3 shows comparison of the task scheduling algorithms. We have drawn graphs based on the results of Table 3.

Similarly, we can compute the performance metrics for DAG2 which is shown in Table 4.

6 CONCLUSIONS

We present new algorithm based on two attributes: Critical Path (CP) and Top level (T-level), called CPTL scheduling algorithm. It uses new attribute: CPT for computing priority of the tasks. It is a difference between a CP and a T-level attributes. Based on the priority attribute CPT, we allocated tasks on the given processors.

The CPTL scheduling algorithm gives lesser scheduling length as compared to heuristic algorithms: HLFET, MCP, ETF, and DLS. We have compared all task scheduling algorithms based on performance metrics illustrated in Section 4 considering two DAG models.

We achieved higher speedup, and efficiency for CPTL algorithms compared to heuristic algorithms.

Additionally, the proposed algorithm also gives less load balancing and NSL as compared to heuristic algorithms.

7 REFERENCES

[1.] M.R. Gary, D.S. Johnson, Computer and Intractability: A Guide to the Theory of NP-Completeness, W.H.Freeman,1979.

[2.] C.H. Papadimitrious, M. Yannakakis, Towards an architecture independent analysis of parallel algorithms, SIAM Journal of Computing 19(2),pp.322-328.1990

[3.] Jagbir Singh, "Improved Task Scheduling on Parallel System using Genetic Algorithm", International Journal of Computer Application. Vol.39 No.17, Feb. 2012.

[4.] Y.K. Kwok and I. Ahmad, "Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors," ACM Computing Survey, vol. 31. no 4,1999

[5.] Ranjit Rajak, "Comparison of BNP class of scheduling algorithms based on metrics", GESJ of Computer Science and Telecomunications, Vol. 34, No. 2, 2012.

[6.] Ranjit Rajak, "A Noval Approach for Task Scheduling in Multiprocessor System," International Journal of Computer Application. Vol. 44. No. 11, pp.12-16, April 2012.

[7.] Ranjit Rajak and C.P. Katti, "Task Scheduling in Multiprocessor System using Fork-Join Method(TSFJ)", International Journal of New Computer Architectures and Their Applications, Vol.3 No.3, pp.47-53, 2013.

[8.] Ali Fuat Alkaya and H.R. Topcuoglu, "A task scheduling algorithm for arbitrarily-connected processors with awareness of link contention", Cluster Computing. Vol. 9, pp. 417-431, 2006.

[9.] M.J. Quinn, "Parallel Programming in C with MPI and OpenMP", Tata McGraw-Hill, Edition 2003.

[10.] KwangSik Shin, MyongJin Cha, MunSuck Jang, "Task Scheduling Algorithm using Minimized Duplication in Homogeneous Systems", Journal of Parallel and Distributed Computing, Vol. 68, pp. 1146-1156, 2008.

[11.] Fatma A. Omara, Mona M. Arafa," Genetic Algorithm for Task scheduling Problem", Journal of Parallel and Distributed Computing Vol. 70, 13-22,2010.

Nidhi Rajak (1), Ranjit Rajak (2) and Anurag Dixit (3)

(1,3) School of Computing & Engineering Galgotias University: (U.P. India) (1) nidhi.bathre@gmail.com, (3) anuradixit@gmail.com (2) Department of Computer Science & Applications Dr. Harisingh Gour Central University Sagar: (M.P: India)

(2) ranjit.inu@gmail.com
```
Table 1. Computing CPT(Ti) Attribute for DAG1 with nine

T1            0          23
T2            6          17
T3            3          20
T4            3          20
T5            3          20
T6           10          13
T7           12          11
T8            8          15
T9           22           1

Table 2.Computing CPT(Ti) Attribute for DAG2

T1            0          34
T2            8          26
T3            4          30
T4            5          29
T5            6          28
T6           16          18
T7           10          24
T8           14          20
T9           13          21
T10          23          11
T11          32           2

Table3. Result of Task Scheduling Algorithms for
DAG1

Scheduling       Performance Metrics
Algorithms
SL    Sp      Eff.   LB     NSL

CPTL         17    1.77    0.44   1.89   0.730
HLFET[6]     19    1.57    0.39   1.58   0.826
MCP[6]       20    1.50    0.37   1.50   0.869
ETF[6]       19    1.57    0.39   1.42   0.732
DLS[6]       19    1.57    0.39   1.42   0.732

Table 4.Results of Task Scheduling Algorithms for
DAG2

Scheduling             Performance Metrics
Algorithms
SL      SP      Eff.      LB      NSL

CPTL          22    1.728    0.432    1.375    0.648
HLFET[5]      22    1.728    0.432    1.571    0.648
MCP[5]        24    1.583    0.395    1.655    0.706
ETF[5]        25    1.520    0.380    1.666    0.732
DLS[5]        24    1.583    0.395    1.846    0.706

Figure 4. Scheduling Length of Proposed
Algorithm is 17 units

P1    P2    P3    P4
0    T1
1    T1
2    T3
3    T3    T4    T5
4    T3    T4    T5
5    T2    T4    T5
6    T2    T4    T5
7    T2    T8    T5
8    T6    T8
9    T6    T8
10    T6    T8
11    T6
12    T7
13    T7
14    T7
15    T7
16    T9
17

Figure 6. Scheduling Length of Proposed Algorithm
is 22 units

P1    P2    P3    P4

0    T1
1    T1
2    T3
3    T3
4    T3
5    T3
6    T4    T5
7    T4    T5
8    T4    T5    T2    T7
9    T4    T5    T2    T7
10          T9    T2
11          T9    T2
12    T8    T9    T6
13    T8    T9    T6
14    T8    T9    T6
15    T8          T10
16    T8          T10
17                T10
18
19
20                T11
21                T11
22
```
COPYRIGHT 2014 The Society of Digital Information and Wireless Communications
No portion of this article can be reproduced without the express written permission from the copyright holder.