Evaluating Heuristics for Scheduling Dependent Jobs in Grid Computing Environments

Introduction

The past few years have witnessed a rapid development of grid computing systems and applications (Li & Baker, 2005). A grid is a heterogeneous computing environment in that resources may have various computing capacities. Job scheduling which is a process of mapping jobs to resources plays a crucial role in resource utilisation in grid environments. Jobs can be generally classified into two classes - independent jobs and dependent jobs. The problem of scheduling m jobs to n resources with an objective to minimise the total execution time (makespan) has been shown to be NP-complete requiring the development of heuristics (Ibarra & Kim, 1977). Braun et al (Braun et al., 2001) evaluated eleven heuristics for mapping independent tasks to heterogeneous computing environments which helps select the best heuristic to use in a given environment. Mapping dependent jobs to heterogeneous computing environments such as grids poses more challenges in that the dependencies of jobs have to be taken into account in the scheduling process.

Jobs with dependent tasks can be represented by Directed Acyclic Graphs (DAGs) in which each node represents an executable task and each directed edge represents data transfers between two tasks. We assume that DAGs always have a single entry node (i.e., a node with no parents) and a single exit node (i.e., a node with no children). To compute a schedule in grid environments, scheduling algorithms require the following information:

• ●

  Information on computing resources available in a grid environment.

• ●

  An Expected Completion Time (ECT) matrix in which the expected time to execute a task on each machine is provided.

• ●

  The network bandwidth of the communication link connecting any two computers.

This paper evaluates 12 heuristics for scheduling dependent jobs in grid environments. To facilitate performance evaluation, a DAG simulator is implemented which provides a set of tools for DAG job configuration, execution and monitoring. The following assumptions are made when scheduling a job with a number of dependent tasks:

• ●

  A computer can execute only one task at a time.

• ●

  Task execution can only start after all data required by the task is available.

• ●

  Data transfer can only begin when a task is completed.

• ●

  Data transfer is scheduled according to the order of the tasks requiring the data. This is referred to as in-order scheduling (Wang, Siegel, Roychowdhury, & Maciejewski, 1997).

• ●

  A computer can transfer only one set of data at a time. Data transfer and task execution can be performed in parallel.

• ●

  Task execution and data transfer are non-pre-emptive.

• ●

  Task execution is computed according to the order defined by a scheduler.

• ●

  An ECT matrix is provided. This can be generated by dividing the workload of a job by the MIPS rating of the processor where the job is executed.

• ●

  For list scheduling heuristics (Sih & Lee, 1993; Topcuoglu, Hariri, & Wu, 2002), partial makespan (the time required to execute the first n jobs in the workflow) is calculated by ignoring data transfer to jobs that are not yet scheduled.

The remainder of the paper is organised as follows. It briefly describes the twelve heuristics used in the evaluation, and presents the components of the DAG simulator for DAG jobs configuration, execution and monitoring. Then it evaluates the 12 heuristics and analyses the performance results. Finally it concludes the paper.