Recursive *-Tree Parallel Data-Structure (Extended 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. >

Authors

• Omer Berkman
• Uzi Vishkin

Keywords

• Parallel algorithms
• Concurrent computing
• Algorithm design and analysis
• Phase change random access memory
• Binary trees
• Computational modeling
• Complexity theory
• Computer science
• Computational geometry
• Pattern matching
• Computational Model
• Paradigm Shift
• Time Constant
• Parallelization
• Linear Time
• Input Size
• Leaf Node
• Algorithm For Problem
• Sequential Algorithm
• Binary Tree
• Parallel Algorithm
• Induction Step
• Single Processor
• Number Of Processors
• Balanced Tree
• Pre-processing Algorithm
• Lowest Common Ancestor Algorithm