Title

Scheduling task graphs in heterogeneous computing environments

Date of Award

1999

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Salim Hariri

Keywords

Processor allocation, Scheduling, Task graphs, Heterogeneous computing environments

Subject Categories

Computer Sciences | Physical Sciences and Mathematics

Abstract

Efficient application scheduling is critical for achieving high performance in heterogeneous computing environments. An application is represented by a directed acyclic graph (DAG) whose nodes represent tasks and whose edges represent communication messages and precedence constraints among the tasks. The general task-scheduling problem maps the tasks of an application on processors and orders their execution so that task precedence requirements are satisfied and a minimum schedule length is obtained. The task-scheduling problem has been shown to be NP-complete in general cases as well as in several Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance. cases. Although a large number of scheduling heuristics are presented in the literature, most of them target homogeneous processors. Existing algorithms for heterogeneous processors are not generally efficient because of their high complexity and the quality of their results. This thesis studies the scheduling of DAG-structured application tasks on heterogeneous domains. We develop two novel low-complexity and efficient scheduling algorithms for bounded number of heterogeneous processors, the Heterogeneous Earliest-Finish-Time (HEFT) algorithm and the Critical-Path-on-a-Processor (CPOP) algorithm. The experimental work presented in this thesis shows that these algorithms significantly surpass previous approaches in terms of performance (schedule length ratio, speed-up, and frequency of best results) and cost (running time and time complexity). Our experimental work includes randomly generated graphs and graphs deducted from real applications. As part of the comparison study, a parametric graph generator is introduced to generate graphs with various characteristics. We also present a further optimization of the HEFT Algorithm by introducing alternative methods for task prioritizing and processor selection phases. A novel processor selection policy based on the earliest finish time of the critical child task improves the performance of the HEFT algorithm. Several strategies for selecting the critical child task of a given task are presented. This thesis addresses embedding the task scheduling algorithms into an application-development environment for distributed resources. An analytical model is introduced for setting the computation costs of tasks and communication costs of edges of a graph. As part of the design framework of our application development environment, a novel, two-phase, distributed scheduling algorithm is presented for scheduling an application over wide-area distributed resources.

Access

Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance.

http://libezproxy.syr.edu/login?url=http://proquest.umi.com/pqdweb?did=730189511&sid=1&Fmt=2&clientId=3739&RQT=309&VName=PQD

Link to Full Text

Share

COinS