Recursive *-tree parallel data-structure
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 196-202
- https://doi.org/10.1109/sfcs.1989.63478
Abstract
The authors introduce a fundamentally novel parallel data structure, called recursive *-tree (star tree). For its definition, they use a generalization of this * functional and apply it to functions other than log. Using recursion in the spirit of the inverse-Akermann function, they derive recursive *-trees. The recursive *-tree data structure leads to a new design paradigm for parallel algorithms. The paradigm allows for unusually fast parallel computations that need only constant time, using an optimal number of processors under the assumption that a very small number of processors can write simultaneously, each into different bits of the same word.Keywords
This publication has 26 references indexed in Scilit:
- Computing on a free tree via complexity-preserving mappingsAlgorithmica, 1987
- Nonlinearity of davenport—Schinzel sequences and of generalized path compression schemesCombinatorica, 1986
- Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithmsPublished by Association for Computing Machinery (ACM) ,1986
- On efficient parallel strong orientationInformation Processing Letters, 1985
- Fast Algorithms for Finding Nearest Common AncestorsSIAM Journal on Computing, 1984
- Scaling and related techniques for geometry problemsPublished by Association for Computing Machinery (ACM) ,1984
- Searching, Merging, and Sorting in Parallel ComputationIEEE Transactions on Computers, 1983
- Parallel Generation of Postfix and Tree FormsACM Transactions on Programming Languages and Systems, 1983
- A complexity theory for unbounded fan-in parallelismPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- Parallel Prefix ComputationJournal of the ACM, 1980