DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE ODENSE UNIVERSITY Data Structures for Parallel Programming Jacob Kornerup Department of Computer Science and Engineering Southern Methodist University Wednesday, June 10, 1998, at 2:15 PM The Seminar Room Parallel programming is still considered a difficult and error-prone activity. There are no universally accepted abstractions that both capture the essence of most parallel architectures, and are useful to the programmer in expressing parallel computations. In this talk we present three data structures: powerlist, parlist, and plist that can be used to describe parallel computations in a succinct manner. We define an algebra along with the inductive definition of each structure. Parallel computations are expressed as recursive functions over these definitions. The algebras facilitate equational reasoning allowing functions representing parallel computations to be derived from their specification. Powerlists were defined by Misra in 1994. A powerlist is a linear structure whose length is a power of two. We illustrate the formalism by presenting a prefix sum algorithm and the Fast Fourier Transform. The parlist structure is an extension to the powerlist structure that allows inputs of arbitrary lengths. We present the theory and show how functions and properties of powerlists can be extended to parlists. The powerlist structure is closely related to binary numbers. We generalize powerlists to plists by introducing basic constructors that take an arbitrary, positive number of similar plists and return a single plist. Plists can be used to reason algebraicly about manipulations on mixed-radix representation of natural numbers with minimal use of index notations. Using plists we describe four generalized interconnection networks and show that they are isomorphic. Kim Skak Larsen