Algorithm mapping with parallel simulated annealing

Authors

B. Robič,
J. Šilc

Publication

Computers and Artificial Intelligence , 1995, 14(4): 339-351

Abstract

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 <i>N</i>/(deg(<i>G</i>)+1), where <i>N</i> is the number of task nodes in the mapped program graph G and deg(G) is the maximal degree of a node in <i>G</i>. 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.

BIBTEX copied to Clipboard