Printer Friendly

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

1. INTRODUCTION

Parallel 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
COPYRIGHT 2013 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.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

 
Article Details
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:

Terms of use | Privacy policy | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters