Parallel algorithms, Programming paradigms, Generic algorithms, Divide and conquer, Quicksort, Fast Fourier transform, Tree machine
We develop a generic divide and conquer algorithm for a parallel tree machine. From the generic algorithm we derive balanced, parallel versions of quicksort and the fast Fourier transform by substitution of data types, variables and statements. The performance of these algorithms is analyzed and measured on a Computing Surface configured as a tree machine with distributed memory.
Hansen, Per Brinch, "Parallel Divide and Conquer" (1991). Electrical Engineering and Computer Science Technical Reports. 131.