Abstract: The binary-forking model is a parallel computation model, formally defined by Blelloch et al., in which a thread can fork a concurrent child thread, recursively and asynchronously. The model incurs a cost of Ξ(log π) to spawn or synchronize π tasks or threads. The binary-forking model realistically captures the performance of parallel algorithms implemented using modern multithreaded programming languages on multicore shared-memory machines. In contrast, the widely studied theoretical PRAM model does not consider the cost of spawning and synchronizing threads, and as a result, algorithms achieving optimal performance bounds in the PRAM model may not be optimal in the binary-forking model. Often, algorithms need to be redesigned to achieve optimal performance bounds in the binary-forking model and the non-constant synchronization cost makes the task challenging. In this paper, we show that in the binary-forking model we can achieve optimal or near-optimal span with negligible or no asymptotic blowup in work for comparison-based sorting, Strassenβs matrix multiplication (MM), and the Fast Fourier Transform (FFT). Our major results are as follows: (1) A randomized comparison- based sorting algorithm with optimal π (log π) span and π (π log π) work, both w.h.p. in π. (2) An optimal π(logπ) span algorithm for Strassenβs matrix multiplication (MM) with only a Ξ (log log π)- factor blow-up in work as well as a near-optimal π (log π log log log π) span algorithm with no asymptotic blow-up in work. (3) A near- optimal π (log π log log log π) span Fast Fourier Transform (FFT) algorithm with less than a log π-factor blow-up in work for all prac- tical values of π (i.e., π β€ 10^10,000).
(Paper by Zafar Ahmad, Rezaul Chowdhury, Rathish Das, Pramod Ganapathi, Aaron Gregory, and Mohammad Mahdi Javanmard)