TY - CONF
T1 - A no-busy-wait balanced tree parallel algorithmic paradigm
T2 - Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures
Y1 - 2000
A1 - Vishkin, Uzi
AB - Suppose that a parallel algorithm can include any number of parallel threads. Each thread can proceed without ever having to busy wait to another thread. A thread can proceed till its termination, but no new threads can be formed. What kind of problems can such restrictive algorithms solve and still be competitive in the total number of operations they perform with the fastest serial algorithm for the same problem?Intrigued by this informal question, we considered one of the most elementary parallel algorithmic paradigms, that of balanced binary trees. The main contribution of this paper is a new balanced (not necessarily binary) tree no-busy-wait paradigm for parallel algorithms; applications of the basic paradigm to two problems are presented: building heaps, and executing parallel tree contraction (assuming a preparatory stage); the latter is known to be applicable to evaluating a family of general arithmetic expressions. For putting things in context, we also discuss our “PRAM-on-chip” vision (actually a small update to it), presented at SPAA98.
JA - Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures
T3 - SPAA '00
PB - ACM
CY - New York, NY, USA
SN - 1-58113-185-2
UR - http://doi.acm.org/10.1145/341800.341818
M3 - 10.1145/341800.341818
ER -