Scan primitives for vector computers
- 4 December 2002
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The authors describe an optimized implementation of a set of scan (also called all-prefix-sums) primitives on a single processor of a CRAY Y-MP, and demonstrate that their use leads to greatly improved performance for several applications that cannot be vectorized with existing computer technology. The algorithm used to implement the scans is based on an algorithm for parallel computers. A set of segmented versions of these scans is only marginally more expensive than the unsegmented versions. The authors describe a radix sorting routine based on the scans that is 13 times faster than a Fortran version and within 20% of a highly optimized library sort routine, three operations on trees that are between 10 to 20 times faster than the corresponding C versions, and a connectionist learning algorithm that is 10 times faster than the corresponding C version for sparse and irregular networks.<>Keywords
This publication has 15 references indexed in Scilit:
- Parallel solutions to geometric problems in the scan model of computationJournal of Computer and System Sciences, 1994
- Compiling collection-oriented languages onto massively parallel computersJournal of Parallel and Distributed Computing, 1990
- Algorithmic techniques for computer vision on a fine-grained parallel machineIeee Transactions On Pattern Analysis and Machine Intelligence, 1989
- Parallel Programming and CompilersPublished by Springer Science and Business Media LLC ,1988
- Parallel Prefix ComputationJournal of the ACM, 1980
- Basic Linear Algebra Subprograms for Fortran UsageACM Transactions on Mathematical Software, 1979
- A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence EquationsIEEE Transactions on Computers, 1973
- Parallel Processing with the Perfect ShuffleIEEE Transactions on Computers, 1971
- A Fast Direct Solution of Poisson's Equation Using Fourier AnalysisJournal of the ACM, 1965
- A programming languagePublished by Association for Computing Machinery (ACM) ,1962