Task Scheduling | Algorithms & Applications Group

Algorithms & Applications Group
Task Scheduling

supported by NSF, DOE
Olga Pearce, Marvin Adams, Nancy Amato
Project Alumni: Ping An

Task Scheduling | Scheduling Algorithms | STAPL Scheduler | ASCI Scheduler

Many parallel applications consist of multiple computational components. While the execution of some of these components or tasks depends on the completion of other tasks, others can be executed at the same time, which increases parallelism of the problem. The task scheduling problem is the problem of assigning the tasks in the system in a manner that will optimize the overall performance of the application, while assuring the correctness of the result.

The task scheduling problem can be modeled as a weighted directed acyclic graph (DAG). A vertex represents a task, and its weight the size of the task computation. An arc represents the communication among two tasks, and its weight represents the communication cost. The directed edge shows the dependency between two tasks.

Example Computation DAG

The primary goal of task scheduling is to schedule tasks on processors and minimize the makespan of the schedule, i.e., the completion time of the last task relative to the start time of the first task. The output of the problem is an assignment of tasks to processors.

Related Projects

Scheduling Algorithms
STAPL Scheduler
ASCI Scheduler

Papers

Task Scheduling and Parallel Mesh-Sweeps in Transport Computations, Nancy M. Amato, Ping An, Technical Report, TR00-009, Department of Computer Science, Texas A&M University, Jan 2000.
Technical Report(ps, pdf)

Department of Computer Science | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science Engineering TAMU