Abstract (Jacob Kornerup)

The field of parallel algorithm design has become a major area of research over the last decade. However, the field has yet to develop a standard language for expressing these algorithms. The Powerlist notation, introduced by Jayadev Misra, gives us a succinct representation of a certain class of parallel algorithms, amenable to algebraic proofs of correctness.

In this talk we will present several well known algorithms in the powerlist notation, focusing the prefix sum problem. We derive an efficient algorithm for hypercubic architectures and then derive a strategy for implementing most powerlist functions efficiently on the same class of architectures. The focus of this work is on correct and rigorous derivations; efficiency claims will only be backed by operational reasoning.


Last modified: March 8, 1995.
Kim Skak Larsen (kslarsen@imada.sdu.dk)