Heuristic algorithm for dynamic remapping of real time applications in multiprocessor machines

A parallel program is a set of inter-communicating tasks, linked one to another by rules of precedence. A task is a sequential program involving communication routines: SEND and RECEIVE messages. The task allocation problem, (known as mapping problem), on a parallel machine amounts to searching all applications T→P, T being the set of tasks and P the set of processors. Algorithms used to solve the task allocation problem are basically divided into two sets: enumerative (exact) and heuristic (empiric). This paper presents a bibliographical synthesis of the different enumerative and heuristic methods. A heuristic algorithm for task allocation problem is proposed. This algorithm takes into account both temporal and spatial constraints of the program. Finally, a conception of a dynamic task allocation tool is discussed. It involves simulating the execution of the parallel program to determine its characteristics, which in turn allows scanning potential allocations to increase the system´s performances. A heuristic policy, which decides when to invoke a global load remapping, is proposed