PARALLEL REMAPPING OF ADAPTIVE PROBLEMS

In this paper we present fast parallel algorithms for remapping a clas s of irregular and adaptive problems on coarse-grained distributed mem ory machines. We show that the remapping of these applications, using simple index-based mapping algorithm, can be reduced to sorting a near ly sorted list of integers or merging an unsorted list of integers wit h 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. (C) 1997 Academic Press.