Powerlist: a structure for parallel recursion
- 1 November 1994
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 16 (6) , 1737-1767
- https://doi.org/10.1145/197320.197356
Abstract
Many data-parallel algorithms—Fast Fourier Transform, Batcher's sorting schemes, and the prefix-sum—exhibit recursive structure. We propose a data structure called powerlist that permits succinct descriptions of such algorithms, highlighting the roles of both parallelism and recursion. Simple algebraic properties of this data structure can be explotied to derive properties of these algorithms and to establish equivalence of different algorithms that solve the same problem.Keywords
This publication has 11 references indexed in Scilit:
- Computer programming as an artPublished by Association for Computing Machinery (ACM) ,2007
- A divide-and-conquer method of solving tridiagonal systems on hypercube massively parallel computersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Automated reasoning about parallel algorithms using powerlistsPublished by Springer Nature ,1995
- An overview of MirandaACM SIGPLAN Notices, 1986
- The cube-connected cycles: a versatile network for parallel computationCommunications of the ACM, 1981
- Parallel Prefix ComputationJournal of the ACM, 1980
- Can programming be liberated from the von Neumann style?Communications of the ACM, 1978
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965
- LISP 1.5 PROGRAMMER'S MANUALPublished by Defense Technical Information Center (DTIC) ,1962
- A programming languagePublished by Association for Computing Machinery (ACM) ,1962