Date Added: Oct 2010
A multiprocessor environment consists of a number of processors that are connected through a communication network. The processors are generally identical and are fully connected with identical links. Multiprocessor environments are used to solve large-scale software applications. The availability of multiple processors helps in concurrent execution of processes. Task allocation algorithms try to exploit parallelism by dividing the software into modules, and allocating them to processors, so that the parallel execution time can be minimized. Modules may have data dependencies between them. Interdependencies between modules are represented as a weighted Directed Acyclic Graph (DAG) called the task graph. Vertices represent the modules having weight as the running time. Edges represent the dependency between modules having weight as the communication time.