STUDIES ON THE PERFORMANCE EVALUATION OF A LINEARLY EXTENSIBLE MULTIPROCESSOR NETWORK

Abstract

Exploiting parallelism is now a necessity to improve the throughput of the computer systems. 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 structuring of a program is usually represented by a problem graph. The nodes of the graph denote the subtasks of a program and the links/arcs between them represent the precedence data relations among the subtasks. Research is active in the direction of developing new multiprocessor architectures and schedule the partitioned program onto it in order to achieve higher execution speeds and/or increased programming comfort. The present work, reported in this thesis, is concerned with the development of a new multiprocessor network, called a Linearly Extensible Tree (LET) network and a dynamic scheduling scheme, named as Minimum Distance Scheduling (MDS) scheme, for parallel execution of tree-structured problems. In addition to this, simulation studies are carried out to compare the performance of LET multiprocessor network and the proposed scheduling scheme MDS with other similar multiprocessor networks and related scheduling schemes available in literature, on different types of problem graphs- general and tree-structured in particular. The model proposed is a linearly extensible tree (LET) multiprocessor network, which exhibits the desirable properties of similar types of multiproceesor networks. The LET network combines linear extensibility with small number of processing elements per extension. The network has lower diameter, hence reduces the average path-length travelled by all messages and contains a constant degree per node. A dynamic scheduling scheme MDS has been developed, which forces minimum distance constraint, based upon only the adjacency matrix information of the LET network, and with relatively small overhead, it oversees that the task arrives at the proper processor maintaining the

task relations even for grossly unbalanced problem graphs or In the presence of failing nodes or links. This scheduling scheme is compared with other available static and dynamic scheduling schemes in the literature for implementation on LET network and other similar multiprocessor networks for graph problems in general and tree-structured problems in particular. The superiority of the developed organisation i.e. LET network and MDS scheme on other existing organisation such as Binary deBruijn Multiprocessor (BDM) network and Round-Robin (R-R) scheme, BDM network and Minimum Load (ML) scheduling, hypercube and Dimension Exchange Method (DEM) scheme, hypercube network and Gradient Model (GM) scheme, and hypercube network and Hierarchical Balance Method (HBM) has been established. Performance of LET network has also been studied for problems having an Acyclic Precedence Graph (APG) structures. In this connection a static Latest Precedence Scheduling (LPS) algorithm has been developed which runs faster compared to a similar other algorithm. The LPS algorithm preserves minimum distance. Performance of LET under this algorithm for APG'S has been tested and compared to other networks.