Using Parallel Simulated Annealing in the Mapping Problem

This paper presents a parallel simulated annealing algorithm for solving the problem of mapping irregular parallel programs onto homogeneous processor arrays with regular topology. The algorithm constructs and uses joint transformations. These transformations guarantee a high degree of parallelism that is bounded below by d jNp j deg(Gp)+1 e, where jN p j is the number of task nodes in the mapped program graph G p and deg(G p ) is the maximal degree of a node in G p . The mapping algorithm provides good program mappings (in terms of program execution time and the number of processors used) in a reasonable number of steps