Design and performance evaluation of a flexible clustering and allocation scheme for parallel processing.

Abstract

Parallel processing is an important and popular aspect of computing and has been developed to meet the demands of high-performance computing applications. In terms of hardware, a large number of processors connected with high speed networks are put together to solve large scale computationally intensive applications. The computer performance improvements made so far have been based on technological developments. In terms of software, many algorithms are developed for application problem execution on parallel systems to achieve required performance. Clustering and scheduling of tasks for parallel implementation is a well researched problem. Several techniques have been studied to improve performance and reduce problem execution times. In this thesis, a new clustering and scheduling scheme, called flexible clustering and scheduling (FCS) algorithm is proposed. It is a novel approach where clustering and scheduling of tasks can be tuned to achieve maximal speedup or efficiency. The proposed scheme is based on the relation between the costs of computation and communication of task clusters. Vital system parameters such as processor speed, number of processors, and communication bandwidth affect speedup and efficiency. Processor speed and communication bandwidth vary from system to system. Most clustering and scheduling strategies do not take into account the system parameters. The low complexity FCS algorithm can adapt itself to suit different parallel computing platforms and it can also be tuned to suit bounded or unbounded number of processors. The analytical, simulation and experimental studies presented in this thesis validate the claims.