# A modified task scheduling algorithm of task graph without communication time.

1. INTRODUCTIONParallel computing is a technique that can solve many complex problems. It can be used for scientific and engineering problems. A parallel program can be a collection of tasks and these tasks are assigned to the processor for concurrent execution. Task scheduling is an important area in parallel processing. It is an application program that is represented by a directed acyclic graph (DAG). The objective of task scheduling is to minimize the overall task scheduling length or execution time of task on processors. Task scheduling on a multiprocessor system is also known as an NP-complete problem except for in some cases [2]. It can be done either on heterogeneous or homogeneous multiprocessors systems. We are considering only homogeneous multiprocessor system for task scheduling. It has three components [3]: processor performance, task mapping and order of execution of tasks on processors. Task scheduling can be classified into two parts: static scheduling and dynamic scheduling [5]. Static scheduling is a scheduling in which assignment of tasks on the processors of task graph are done at compile time. Sometime, it is also known as compile time scheduling because the information of tasks execution time, communication time and their precedence constraint are known in advance. Dynamic Scheduling is a scheduling in which assignment of tasks on the processors of the task graph is done at run time. It is also known as run time scheduling. The tasks information in dynamic scheduling is not known in advance.

In this paper, we present a modified algorithm of Task scheduling based on breath first search (TSB) [1] and call this algorithm MTSB. MTSB is also based on the concepts of Breath First Search (BFS) graph traversal algorithm [4] which is used to find the execution order of tasks. The main difference of TSB and MTSB is the assignment of tasks on processors. In TSB algorithm, we have considered communication time between tasks but in MTSB algorithm the communication time is not considered during allocation of tasks on the processors

There are four BNP class of scheduling algorithms: Highest Level First with Estimate Time (HLFET) algorithm, Modified Critical Path (MCP) algorithm, Earliest Time First (ETF) algorithm and Dynamic Level Scheduling (DLS) algorithm. We will discuss MTSB algorithm with the help of DAG program and performance analysis of algorithms will be based on five matrices: scheduling length, speedup, efficiency, load balancing and normalized scheduling length (NSL).

The rest of this paper is organized as follows: Section 2 gives brief discussion of model of task scheduling in multiprocessors system. BNP class scheduling algorithms are presented in Section 3. The proposed algorithm will be discussed in Section 4 and the performance analysis based on matrices in Section 5 and performance evolution in section 6. Finally, come to the conclusion in Section 7.

2 TASK SCHEDULING MODEL

We are considering the mapping of tasks onto a multiprocessor system and it consists of n identical processors P. i.e. P={[P.sub.1,[P.sub.2,]] ... [P.sub.n}] We assume that the processors are connected with each other via identical links. Task scheduling of an application program is represented by directed acyclic graph G={V,E,W,C} of m tasks. Where V is finite set of tasks i.e. V={[T.sub.1,[T.sub.2,]] ... [T.sub.n]},E is directed edges from task [T.sub.i] to [T.sub.j,] W is execution time of task [T.sub.i] and C is communication time between the task [T.sub.i] and [T.sub.j.]

If there is a direct link from [T.sub.i] to [T.sub.j] then [T.sub.i] is a predecessor of [T.sub.j] and [T.sub.j] is a successor of [T.sub.i.] There is a precedence constraint which exists during allocation of tasks onto the processors. That is task [T.sub.i] will execute only if it gets all the information from its predecessors [T.sub.j].

The layout of the DAG model [1] is given in figure 1.

3 BNP CLASS OF SCHEDULING ALGOTIHMS

BNP class of scheduling algorithms is developed for a bounded number of processors (BNP) and the processors are identical as well as completely connected. It is a part of list tasks scheduling algorithms [13]. It is further divided into four parts: Highest Level First with Estimated Time (HLEFT), Modified Critical Path (MCP), Earliest Time First (ETF) and Dynamic Level Scheduling (DLS) algorithms. All these four BNP class of scheduling uses the priority attributes for scheduling: t-level, b-level [6], static level and ALAP (as late as possible) [7, 8].

4 PROPOSED ALGORITHM

We are proposing an algorithm for task scheduling in multiprocessor system without communication time. This algorithm is a modified algorithm of task scheduling algorithm using breath first search (TSB) [1] which is proposed by us in previous papers. The new algorithm is called modified task scheduling algorithm using breath first search (MTBS). The basic difference between them is their communication time of the tasks. In TSB algorithm, we considered communication time between the tasks while assigning it onto the processors but MTSB does not consider the communication time between the tasks during assign onto the processors. We have changed only a few steps in the previous algorithm and found that MTSB gives better results as compared to TSB. We will test this algorithm on given DAG with nine tasks.

4.1 MTSB Algorithm

The details of MTSB algorithm:

DAG: Directed Acyclic Graph, NRTQ: Not Ready Task Queue, RTQ: Ready Task Queue Step 1: Read a DAG that consist n number of tasks. Step 2: Insert first task into NRTQ Step 3: while (NRTQ! = Null) do Delete a task from NRTQ Step 4: Generate successors of a deleted task Step 5: For each successor of deleted task do If a successor task is not present either in NRTQ or RTQ then Insert successor task into NRTQ. // end for Step 6: If deleted task is not present in RTQ then Insert deleted task into RTQ Step 7: Check predecessor of a deleted task is present or not in RTQ If present then Insert deleted task into RTQ Else Insert deleted task into NRTQ //end while Step 8: Now we have RTQ that consists all the task of a given DAG. : For i=1 to nth tasks Remove a task Ti from RTQ For j=1 to mth processors Compute the earliest start time of a removed task on each processor(Pj) without communication time then schedule a removed task on processor. Before allocated on a processor, check precedence constraint of the task. Step 9: Calculate scheduling length based on execution time of the last tasks on the processor.

5 PERFORMANCE MATRICES

To evaluate the performance of the MTSB, TSB and BNP class of scheduling algorithms are based on five matrices: Scheduling Length, Speedup, Efficiency, Normalized Scheduling Length (NSL) and Load Balancing.

5.1 Scheduling Length (SL)

It is also called makespan and defined by a following equation [16]:

Scheduling Length = max[FT(Ti,P)}

Here FT is finishing time of a last task Ti on a processor P.

5.2 Speedup (SP)

Speedup [14] is the ration of sequential execution time (Ts) and parallel execution time (Tp). It is defined by following:

Speedup = [Ts/Tp]

5.3 Efficiency (EFF)

Efficiency [14] of a parallel program is the ratio of speedup and number of processors used. It is defined by following:

Speedup

Efficiency = Speedup/Number of Processors used x 100

5.4 Normalized Scheduling length (NSL)

NSL [15] of a list task scheduling algorithm is defined by following:

NSL = Scheduling Length/Max[Sum of exexcution time along a path}

5.5 Load Balancing (LB)

Load balancing [16] is the ratio of scheduling length and average execution time over all the processors. It is defined by following:

Load Balancing = Scheduling Length/Average

Where Average is the ratio of sum of processing time of each processor and number of processors.

6 PERFORMANCE EVALUATIONS

We have run MTSP, TSP and BNP class of

scheduling algorithms on a DAG with nine tasks. In our simulation, we consider the numbers of homogenous processors as four and they are completely connected.

6.1 MTSB Algorithm implementation

By considering above DAG of an application program, we have to compute NRTQ and RTQ of the tasks of given DAG

6.1.1 Numerical analysis for DAG

Now, we are computing RTQ for given DAG.

After processing NRTQ and RTQ as per proposed algorithm, we have RTQ of task order: T1, T2, T7, T3, T4, T5, T6, T8, T9. Using these tasks order, we draw Gantt. Chart for scheduling of tasks. According to MTSB algorithm, no communication time is considered during allocation of task on the processors.

The proposed algorithm MTSB gives better result in compared to TSB and BNP class of scheduling algorithms. All the comparison has been done based above five matrices in table 4.

7 CONCLUSION

In this paper, we have proposed an algorithm MTSB which is a modified of TSB algorithm. The MTSB algorithm is not considered communication time while mapping of tasks on the processors. Also, we have done comparative study between MTSB, TSB and BNP class of scheduling algorithms. MTSB algorithm had provided shorter scheduling length. The comparative study has done based on five matrices: scheduling length, speedup, efficiency, normalized scheduling length and load balancing. Similarly, MTSB algorithm is also satisfied better results like load balancing, speedup, efficiency and normalized scheduling length. Here, the future work can be applied in heterogeneous environment of the system where processors have different speed.

8 REFERENCES

[1.] Rajak, Ranjit. :A Novel Approach for Task Scheduling in Multiprocessor System. International Journal of Computer Application, vol. 44, no.11, pp: 12-16, (2012)

[2.] Zomaya A. Y. Parallel and Distributed Computing Handbook. McGraw-Hill,(1996).

[3.] Singh Jagbir. : Improved Task Scheduling on Parallel System using Genetic Algorithm. International Journal of Computer Applications Vol 39- No. 17, (2012)

[4.] Kanetkar Yashwant. : Data Structure Using C.BPB Publications, (2003)

[5.] Rajaraman V. & Murthy C.Siva Ram. :Parallel Computers Architectures and Programming. PHI Publication, (2012).

[6.] Rahman, Amir Masoud, Vahedi, Mohammad Ali.: A Noval Task Scheduling in Multiprocessors System with Genetic Algorithm by Using Elistism Stepping Method. Science and Research Branch, Tehran, Iran, (2008.).

[7.] Kwok, Y. K., Ahmad., I.: Dynamic Critical Path Scheduling : An Effective Techniques for Allocating Tasks Graph onto Multiprocessor. IEEE Transaction on Parallel and Distributed System, vol. 7, no 5, pp 506-621, (1996)

[8.] Wu, M. Y., Gajski,. D. D.: Hyperpool: A programming Aid for Message Passing. IEEE Transaction on Parallel and Distributed System.vol.3, pp 330-343, (1990)

[9.] Adam., T. L., Candy, K. M., Dickson, J.: A Comparison of list scheduling for parallel processing system. Communication ACM,vol.17,no.12, pp 685-690, (1974).

[10.] Hwang., J. J, Chow., Y. C, Anger., F. D., Lee., C. Y. Lee .: Scheduling precedence graph in systems wit interprocessor communication times. SIAM Journal of Computing. vol. 18, no. 2, pp244-257,(1989.)

[11.] Sih, G, C. Lee, E. A. :Compile time scheduling heuristic for interconnection -constrained heterogeneous processor architecture. IEEE Transaction on Parallel and Distributed System, vol. no 2,pp-75-87, (1993)

[12.] Rajak Ranjit,: Comparison of BNP Class of Scheduling Algorithms Based On Matrices. GESJ: Computer Science and Telecommunications, vol. 2, no. 34,.(2012)

[13.] Kwok, Yu-Kwong and Ahmad, Ishfaq.: Static Scheduling Algorithms for Allocating Directed Task Graphs to Mulitprocessors. ACM Computing Surveys, vol. 31, no.4, (1999).

[14.] Quinn M. J.: Parallel Programming in C with MPI and Open MP. Tata McGraw-Hill, Edition, (2003)

[15.] Kwang Sik Shin, Myong Jin Cha, MunSuck Jang.: Task Scheduling Algorithm using Minimized Duplication in Homogeneous Systems. Journal of Parallel and Distributed Computing, vol. no, 68, pp.1146-1156, (2008)

[16.] Fatma A. Omara, Mona M. Arafa.: Genetic Algorithm for Task scheduling Problem. Journal of Parallel and Distributed Computing, vol. no 70, pp13-22, (2010)

Ranjit Rajak (1), C. P. Katti (2) & Nidhi Rajak (3)

(1) Department of Computer Science & Application Dr.HariSingh Gour Central University, Sagar-470003(MP-India)

(2) School of Computer & System Sciences Jawaharlal Nehru University (JNU), New Delhi-110067(India)

(3) School of Computing Science & Engineering Galgotias University, Greater Noida (UP-India)

ranjit.jnu@gmail.com (1), cpkatti@yahoo.com (2), nidhi.mtech2014@gmail.com (3)

Table 2. BNP class of scheduling algorithms with Priority Attributes S. No Algorithms Priority Attribute 1 HLFET [9] Static Level 2 MCP [8] ALAP 3 ETF [10] Static Level 4 DLS [11] Dynamic Level Table 3. Processing of NRTQ and RTQ [1] Not Ready Task Queue Ready Task Queue (RTQ) (NRTQ) T1 ... T2T7T3T4T5 T1 T7T3T4T5T6 T1T2 T3T4T5T6T9 T1T2T7 T4T5T6T9T8 T1T2T7T3 T5T6T9T8 T1T2T7T3T4 T6T9T8 T1T2T7T3T4T5 T9T8 T1T2T7T3T4T5T6 T8T9 T1T2T7T3T4T5T6 T9 T1T2T7T3T4T5T6T8 ... T1T2T7T3T4T5T6T8T9 Table 4. Comparison of MTSP, TSB and BNP class of scheduling algorithms. Algorithms SL SP EFF LB NSL MTSB 11 2.727 68.18% 1.189 0.478 TSB[1] 16 1.875 46.87% 1.560 0.695 HLEFT[1] 19 1.578 39.47% 1.583 0.826 MCP[1] 20 1.500 37.50% 1.509 0.869 ETF[1] 19 1.578 39.47% 1.425 0.732 DLS[1] 19 1.578 39.47% 1.425 0.732

Printer friendly Cite/link Email Feedback | |

Author: | Rajak, Ranjit; Katti, C.P.; Rajak, Nidhi |
---|---|

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

Article Type: | Technical report |

Geographic Code: | 1USA |

Date: | Oct 1, 2013 |

Words: | 2185 |

Previous Article: | New windowing technique detection of sags and swells based on continuous S-transform (CST). |

Next Article: | Spectrum analysis of the suspension dynamics measured by MEMS inertial system. |

Topics: |