Fast Mapping And Remapping Algorithms For Irregular And Adaptive Problems
Chao Wei Ou, Sanjay Ranka, Geoffrey Fox · Syracuse University Libraries (Syracuse University) · 1993
This paper describes the performance of localitybased mapping and remapping partitioners for unstructured grids. We show that the algorithm produces good mappings at a relatively low cost and can be easily parallelized. Further, the algorithm can provide remapping for incremental problems at a fraction of the total cost. 1 Introduction Load-balancing and reduction of communication are two important issues for achieving good performance distributed-memory parallel computers. It is important to map the program such that the total execution time is minimized; the mapping can typically be performed statically or dynamically. For a large class of scientific problems that are irregular in nature, achieving a good mapping is difficult [1]. The nature of the irregularities is unknown at the time of compilation and can be derived only at runtime. The handling of such irregular problems requires runtime information in order to partition the computation in such a fashion that each processor rec...