%AAhmad, Zafar%AChowdhury, Rezaul%ADas, Rathish%AGanapathi, Pramod%AGregory, Aaron%AJavanmard, Mohammad%Anull Ed.%BJournal Name: Proc. 33st ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA)
%D2021%I
%JJournal Name: Proc. 33st ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA)
%K
%MOSTI ID: 10298539
%PMedium: X; Size: 22 to 34
%TLow-Span Parallel Algorithms for the Binary-Forking Model
%XThe 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 Theta(log n) to spawn or synchronize n 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 O(log n) span and O(nlog n) work, both w.h.p. in n. (2) An optimal O(log n) span algorithm for Strassen's matrix multiplication (MM) with only a loglog n - factor blow-up in work as well as a near-optimal O(log n loglog log n) span algorithm with no asymptotic blow-up in work. (3) A near-optimal O(log n logloglog n) span Fast Fourier Transform (FFT) algorithm with less than a log n-factor blow-up in work for all practical values of n (i.e., n le 10 ^10,000 ).
%0Journal Article
Country unknown/Code not availablehttps://doi.org/10.1145/3409964.3461802OSTI-MSA