Data reduction and fast routing: A strategy for efficient algorithms for message-passing parallel computers

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.