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.
