ON TASK ALLOCATION METHODS FOR DISTRIBUTED COMPUTER SYSTEMS

Abstract

This thesis addresses the problem of static task allocation in distributed computer systems. Task allocation is the problem of assigning a set of interdependent tasks, which address a common goal, to the set of processors of a distributed computer system, subject to certain performance oriented cost functions and constraints. In case of static allocation, a task assigned to a processor resides on the processor until the execution of the task is completed. For this the task execution costs and intertask communication costs are to be known a priori. The task allocation problem to find optimal assignments for an arbitrary number of processors (more than two) is known to be NP-complete. Hence, it is desirable to develop heuristic algorithms which provide good sub-optimal assignments. The present work is an endeavour in this direction. When the processors are dissimilar, an optimal allocation will exploit the specific capabilities of the processors and avoid excessive interprocessor communication. With this performance goal a search method is presented for the task allocation problem. Network flow graph model and array representation for task execution costs and intertask communication costs are used to obtain task assignments in this search method.

When the processsors are identical or similar the objective for task allocation problem is to assign each processor with equal load and minimum interprocessor communication cost. With this objective a clustering method is suggested for random program graphs and constrained program graphs. A heuristic algorithm is also presented with the constraint of precedence order among the tasks besides assigning equal load to processors. Finally, closely related problem of job scheduling is attempted to enhance system performance from the point of view of reducing the average response. A simple, dynamic, decentralized job scheduling algorithm which tries to keep all the processors busy all the time with minimum communication overhead is suggested.