Classification of Parallel Implementations for Linearly Recursive Functions

Christoph Wedler

Broadcast, Reduction and Scan are popular functional skeletons which are used in distributed algorithms to distribute and gather data. We derive new parallel implementations of combinations of Broadcast, Reduction and Scan via a tabular classification of linearly recursive functions. The trick in the derivation is to not simply combine the individual parallel implementations of Broadcast, Reduction and Scan, but to transform these combinations to skeletons with a better performance. These skeletons are also linearly recursive. Our tabular classification exposes them, beside the skeletons Broadcast, Reduction and Scan.