A no-busy-wait balanced tree parallel algorithmic paradigm

TitleA no-busy-wait balanced tree parallel algorithmic paradigm
Publication TypeConference Papers
Year of Publication2000
AuthorsVishkin U
Conference NameProceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures
Date Published2000///
Conference LocationNew York, NY, USA
ISBN Number1-58113-185-2

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.