Parlists - a Generalization of Powerlists

. The powerlist notation has been very successful in specifying a number of parallel algorithms in a very elegant fashion. The major criticism of the notation was the restriction that input lengths were limited to powers of two. In this paper we present parlists, an extension of the powerlist notation to lists of arbitrary positive lengths. 1 Introduction The powerlist notation [10] has proven to be a major step forward in describing parallel algorithms succinctly. It allows the programmer to work at a high level of abstraction, by avoiding indexing notations, leading towards efficient implementations on parallel architectures [7]. The powerlist data structure is a list whose length is a power of two. In the powerlist notation it is possible to elegantly specify algorithms such as the Discrete Fast Fourier Transform without resorting to "index gymnastics" [10]. For such algorithms the restriction to lists of lengths a power of two is not serious; they are often presented this way in t..