Parallel placement of parallel processes
Chrisila C. Pettey, Michael R. Leuze · 1988
The problem of placing the individual processes of a logically partitioned problem on the nodes of a multiprocessor in such a manner as to minimize the communication and memory utilization costs is known as the process placement problem. This problem is, in general, NP-complete. A number of algorithms for finding approximate solutions to the process placement problem have been investigated. Some of these algorithms rely on heuristics to initially place the processes. This approach is sometimes followed by iterative refinement, where pairs of processes are swapped in a search for better approximations. For other algorithms which rely almost solely on iterative refinement, initial placement is of much less importance. Recently simulated annealing, a more sophisticated adaptive search technique, has been applied to the process placement problem. All of these process placement algorithms are sequential. (Although simulated annealing has recently been implemented in parallel on a hypercube architecture, no work has been done in applying the parallel version to the process placement problem.)