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

1 INTRODUCTIONTask 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: Step 1: Read DAG ([t.sub.n] number of tasks) Entry Task: first task or starting task of given DAG Exit Task: last task or end task of given 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. Step6: Add the tasks to a Queue. 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 task. 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.

4.4 Load Balancing(LB)

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 tasks Tasks(Ti) T-Level(Ti) CPT(Ti) 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 with eleven tasks Tasks(Ti) T-Level(Ti) CPT(Ti) 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

Printer friendly Cite/link Email Feedback | |

Title Annotation: | directed acyclic graph |
---|---|

Author: | Rajak, Nidhi; Rajak, Ranjit; Dixit, Anurag |

Publication: | International Journal of New Computer Architectures and Their Applications |

Article Type: | Report |

Date: | Jul 1, 2014 |

Words: | 2018 |

Previous Article: | Data center architectures: challenges and opportunities. |

Next Article: | Modeling and utilization of an IPMC muscle. |

Topics: |