A STUDY OF TASK ALLOCATION STRATEGIES FOR BUS CONNECTED MULTIPROCESSORS

Abstract

Multiprocessor systems are dominating in the new era of computation for their faster computations. A multiprocessor system consists of two or more processors which operate concurrently in a cooperative manner during the execution of a job. When a job is submitted to a multiprocessor system two issues will come into picture. The first one is partitioning of job into set of modules or tasks which can be executed concurrently. And the second is assignment of these tasks to set of processors. A task graph results when a job is partitioned. The task graph consists of a set of nodes which correspond to estimated execution time of a module and the edges which correspond to the amount of data flow among the corresponding tasks. The assignment of tasks to processors. plays a very vital role as the completion time of a ,job mainly depends on It. Here finding of optimal assignments is found to be time consuming which is not a desirable feature. Hence an assignment process should be faster and lead to near optimal assignments, if not optimal . For this purpose a kind of heuristic approach is employed. This dissertation work deals with few task allocation strategies based on heuristic approach. Algorithms for allocating independent tasks and allocating communicating tasks are discussed separately. If there is no data flow between tasks then they are said to be independent tasks, otherwise they are called communicating tasks.The algorithms discussed here are implemented and tested for various problems . From results it can be seen that the proposed heuristics are fast and leading to optimal or near optimal solutions in most of the cases. The proposed heuristic for allocation of independent tasks performs very much better when number of tasks increase, (signal processing example).