I.K. Pour, D.J. Krajnovich, et al.
SPIE Optical Materials for High Average Power Lasers 1992
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.
I.K. Pour, D.J. Krajnovich, et al.
SPIE Optical Materials for High Average Power Lasers 1992
Renu Tewari, Richard P. King, et al.
IS&T/SPIE Electronic Imaging 1996
George Markowsky
J. Math. Anal. Appl.
Fausto Bernardini, Holly Rushmeier
Proceedings of SPIE - The International Society for Optical Engineering