STUDY AND ANALYSIS OF SCHEDULING TASK GRAPHS IN HETEROGENEOUS COMPUTING SYSTEM

Abstract

The progress in hardware technology and computer architecture has led to the design and construction of computer systems that exploit parallelism to improve the performance. In terms of hardware, this typically means providing multiple, simultaneously active processors. In terms of software, it means structuring a program as a set of largely independent subtasks. The structure of the program can be represented as Directed Acyclic Graphs (DAGs). The node in the graph denote the subtasks of a program and the link/edges between them represent the precedence data relation among the subtasks. A central problem in heterogeneous distributed computing system is efficiently scheduling the tasks of a parallel program. This problem is - complicated by the consideration that, in any heterogeneous distributed system, some processors and the links between them are bound to fail, which can have an adverse effect on an application executing in the system. A task scheduling algorithm is employed which minimizes not only the execution time but also the probability of failure of the application. The work reported in this dissertation, evaluates the performance of two static non-preemptive dynamic level based scheduling strategies for graph structured -programs on two network architectures, through simulation. Performance measure like failure probability and schedule length have been studied for different problem size and CCR. The simulation system, developed in this work, generates DAGs and simulates the fully connected and arbitrary networks. Two scheduling algorithms have been used to schedule the generated DAGs on to the target network. Performance measures are then obtained for each scheduling algorithm. A comparative study of the performance of heterogeneous distributed systems having different network topology is then carried out. These algorithms are coded in Turbo C++ on Windows 9x environment.