Optimal Parallel Algorithms in the Binary-Forking Model
share
In this paper we develop optimal algorithms in the binary-forking model for a variety of fundamental problems, including sorting, semisorting, list ranking, tree contraction, range minima, and set union, intersection and difference. In the binary-forking model, tasks can only fork into two child tasks, but can do so recursively and asynchronously, and join up later. The tasks share memory, and costs are measured in terms of work (total number of instructions), and span (longest dependence chain). Due to the asynchronous nature of the model, and a variety schedulers that are efficient in both theory and practice, variants of the model are widely used in practice in languages such as Cilk and Java Fork-Join. PRAM algorithms can be simulated in the model but at a loss of a factor of Ω( n) so most PRAM algorithms are not optimal in the model even if optimal on the PRAM. All algorithms we describe are optimal in work and span (logarithmic in span). Several are randomized. Beyond being the first optimal algorithms for their problems in the model, most are very simple.
READ FULL TEXT