ASSIGNMENT OF LINEAR AND RANDOM TASK 'GRAPHS IN DISTRIBUTED SYSTEMS

Abstract

This thesis presents two algorithms for task assignment in distributed systems with homogeneous processors. First one is for assigning a chain-structured task graph on a distributed system having chain-structured interconnection structure. In this algorithm the objective is to minimize the bottleneck cost which is the measure of quality of assignment. The algorithm presented here is based on the probing approach, as used by Bokhari, Iqbal, and Nicol and O'Hallaron. Our algorithm does optimal assignment as Iqbal's does, but is n times faster than that of his, where n is the number of processors. The second algorithm is for assigning random task graph with m tasks to n processors. Here no particular interconnection , structure is assumed. The communication cost between any two processors is assumed the same provided the amount of data transfer is same. The objective of this assignment is to reduce the load imbalance and the IPC cost. The algorithms have been compared with the existing algorithms to show that algorithms proposed here perform reasonably good.