Naga Ayachitula, Melissa Buco, et al.
SCC 2007
This paper presents several algorithms for solving problems using massively parallel SIMD hypercube and shuffle-exchange computers. The algorithms solve a wide variety of problems, but they are related because they all use a common strategy. Specifically, all of the algorithms use a divide-and-conquer approach to solve a problem with N inputs using a parallel computer with P processors. The structural properties of the problem are exploited to assure that fewer than N data items are communicated during the division and combination steps of the divide-and-conquer algorithm. This reduction in the amount of data that must be communicated is central to the efficiency of the algorithm. This paper addresses four problems, namely the multiple-prefix, data-dependent parallel-prefix, image-component-labeling, and closest-pair problems. The algorithms presented for the data-dependent parallel-prefix and closest-pair problems are the fastest known when N ≥P and the algorithms for the multiple-prefix and image-component-labeling problems are the fastest known when N is sufficiently large with respect to P. © 1992 Springer-Verlag New York Inc.
Naga Ayachitula, Melissa Buco, et al.
SCC 2007
Amir Ali Ahmadi, Raphaël M. Jungers, et al.
SICON
L Auslander, E Feig, et al.
Advances in Applied Mathematics
Martin C. Gutzwiller
Physica D: Nonlinear Phenomena