Simulated annealing and the mapping problem: A computational study

Abstract

Given an array of processors, the mapping problem requires assignment of program modules to processors such that the communication time between modules is minimized. Typically, this requires assignment of modules which intercommunicate to adjacent processors. Although polynomial solutions to certain instances of the mapping problem exist, an efficient, exact algorithm for the general-case problem has not been found. Consequently, researchers have concentrated on development of efficient heuristic solutions. This study explores the application of simulated annealing to the mapping problem. Performance of the annealing model will be compared with that of an existing heuristic procedure, and experimentation with various parameters of the annealing algorithm will be employed in determination of the most significant factors affecting the efficiency of the simulated annealing solution.