Proc. 6th Int'l PARLE Conference, Athens, Greece, July 4-8, 1994.

This paper presents a parallel simulated annealing algorithm for solving the problem of mapping irregular parallel programs onto homogeneous processor array with regular topology. The algorithm constructs and uses joint transformations. These transformations guarantee a high degree of parallelism that is bounded below by |Np|/(deg(Gp) + 1), where |Np| is the number of task nodes in the mapped program graph Gp and deg(Gp) is the maximal degree of a node in Gp. 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.