PERFORMANCE STUDY OF CRITICAL PATH SCHEDULING FOR MULTIPROCESSOR NETWORKS

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 mglans providing multiple, simultaneously active processors. In terms of 'oftware, it means structuring a program as a set of largely independe,~ (t subtasks. The structure of the program can be represented as Directed / Acyclic Graphs (DAGs). The nodes in the graph denote the subtasks of a program and the links/edges between then represent the precedence data rela scions among the subtasks. The ` work reported in this dissertation, evaluates the performance of three-static, non-preemptive critical-path based scheduling strategies for graph structured programs on two network architectures, through simulation. Performance measures like speed up, load imbalance factor and number of processors used have been studied for different problem sizes. The simulation system, developed in this work, generates DAGs and simulates the Linearly Extensible Tree and Hypercube networks. Three 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 multiprocessor networks is then carried out.