NPAC Technical Report SCCS-653

Parallel Remapping Algorithms for Adaptive Problems

Chao-Wei Ou, Sanjay Ranka

Submitted October 1 1994


Abstract

In this paper we present fast parallel algorithms for remapping a class of irregular and adaptive problems on coarse-grained distributed memory machines. We show that the remapping of these applications, using simple index-based mapping algorithm, can be reduced to sorting a nearly sorted list of integers or merging an unsorted list of integers with a sorted list of integers. By using the algorithms we have developed, the remapping of these problems can be achieved at a fraction of the cost of mapping from scratch. Experimental results are presented on the CM-5.


PostScript version of the paper