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.