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)