Powerlist: A Structure for Parallel Recursion

Many important synchronous parallel algorithms -- Fast Fourier transform, routing and permutation, Batcher merge, solving tridiagonal linear systems by odd-even reduction, prefix-sum algorithms -- are best formulated in a recursive fashion. The network structures on which parallel algorithms are typically implemented -- Butterfly, Sorting networks, hypercube, complete binary tree -- are also recursive in nature. However, parallelism as an implementation technique is awkward to combine with recursion. Therefore parallel recursive algorithms are typically described iteratively, one parallel step at a time. Similarly, the connection structures are often explained pictorially, by displaying the connections between one "level" and the next. The mathematical properties of the algorithms and connection structures are rarely evident from these descriptions.

A proposed data structure, the powerlist, admits of succinct descriptions of such algorithms and connection networks. It highlights the roles of both parallelism and recursion. Algebraic properties of powerlists permit proofs by structural induction. The proposal promises to be useful in describing parallel algorithms in a machine-independent fashion, and implementing them efficiently on specific connection structures. It has already proved to be useful in verifying certain arithmetic circuits.