On the mapping problem using simulated annealing

Mapping a problem graph of communicating tasks onto a network graph of processing elements so that the communication distance is minimized and the problem graph is evenly distributed over the network, is an NP-complete problem. The authors demonstrate that an approximation technique called simulated annealing can be applied to find acceptable solutions to this problem. For this purpose, they first develop a distance-variance metric to estimate the goodness of a mapping. The authors then present evidence that, with a regular network topology, there are no significant local minima in the space of possible solutions. Hence, a faster form of simulated annealing called quenching becomes appropriate for the mapping problem.<>