Powerlist: a structure for parallel recursion.
Many data-parallel algorithmsFast Fourier Transform, Batcher's sorting schemes, and the prefix-sumexhibit recursive structure. We propose a data structure called powerlist that permits succinct descriptions of such algorithms, highlighting the roles of both parallelism and recursion. Simple algebraic properties of this data structure can be explotied to derive properties of these algorithms and to establish equivalence of different algorithms that solve the same problem.
Program under Grant No. 003658-219 and by the National Science Foundation Award CCR-
9111912.
1 A notable exception is the recursive description of a prefix sum algorithm in Karp and
Ramachandran[12].
A data structure, powerlist, is proposed in this paper that highlights the role
of both parallelism and recursion. Many of the known parallel algorithms-
FFT, Batcher Merge, Prefix Sum, embedding arrays in hypercubes, etc.-have
surprisingly concise descriptions using powerlists. Simple algebraic properties of
powerlists permit us to deduce properties of these algorithms employing structural
induction.
Powerlist
The basic data structure on which recursion is employed (in LISP[16] or ML[17])
is a list. A list is either empty or it is constructed by concatenating an element
to a list. (We restrict ourselves to finite lists throughout this paper.) We call
such a list linear (because the list length grows by 1 as a result of applying
the basic constructor). Such a list structure seems unsuitable for expressing
parallel algorithms succinctly; an algorithm that processes the list elements has
to describe how successive elements of the list are processed.
We propose powerlist as a data structure that is more suitable for describing
parallel algorithms. The base-corresponding to the empty list for the linear
case-is a list of one element. (Clearly, there are many bases, depending on the
specific element in the list.) A larger powerlist is constructed from the elements
of two powerlists of the same length, as described below. Thus, a powerlist is
multiplicative in nature; its length doubles by applying the basic constructor.
There are two different ways in which powerlists are joined to create a larger
powerlist. If p; q are powerlists of the same length then
is the powerlist formed by concatenating p and q
./ q is the powerlist formed by successively taking alternate items from p and
q, starting with p.
Further, we restrict p; q to contain similar elements (defined in Section 2.1).
In the following examples the sequence of elements of a powerlist are enclosed
within angular brackets.
The operation j is called tie and ./ is zip.
2.1 Definitions
A data item from the linear list theory will be called a scalar. (Typical scalars
are the items of base types-integer, boolean, etc.-tuples of scalars, functions
from scalars to scalars and linear lists of scalars.) Scalars are uninterpreted in
our theory. We merely assume that scalars can be checked for type compatibility.
We will use several standard operations on scalars for purposes of illustration.
Notational Convention: Linear lists will be enclosed within square brackets,
A powerlist is a list of length 2 n , for some n, all of whose elements
are similar. We enclose powerlists within angular brackets, h i.
Two scalars are similar if they are of the same type. Two powerlists are
similar if they have the same length and any element of one is similar to any
element of the other. (Observe that similar is an equivalence relation.)
Let S denote an arbitrary scalar, P a powerlist and u; v similar powerlists.
A recursive definition of a powerlist is
hSi or hP i or u j v or u ./ v
Examples
h2i powerlist of length 1 containing a scalar
hh2ii powerlist of length 1 containing a powerlist of length 1 of scalar
h i not a powerlist
powerlist of length 1 containing the empty linear list
powerlist of length 2, each element of which is a powerlist of length
2, whose elements are linear lists of numbers
a representation of the matrix
where each column is
an element of the outer powerlist.
another representation of the above matrix where each row is an
element of the outer powerlist.
hhhai hbii hhci hdiii
representation of the tree in Figure 1. The powerlist contains two
elements, one each for the left and right subtrees.
2.2 Functions over Powerlists
Convention: We write function application without parantheses where no
confusion is possible. Thus, we write "f x" instead of "f(x)" and "g x y"
instead of "g(x; y)". The constructors j and ./ have the same binding power
and their binding power is lower than that of function application. Throughout
this paper, S denotes a scalar, P a powerlist and x; y either scalar or powerlist.
Typical names for powerlist variables are p; q;
hhci hdii
hhhai hbii hhci hdiii
hhai hbii

Figure

1: Representation of a complete binary tree where the data are at the
leaves. For leaf nodes, the powerlist has one element. For nonleaf nodes, the
powerlist has two elements, namely, the powerlists for the left and right subtrees.
Functions over linear lists are typically defined by case analysis-a function
is defined over the empty list, and, recursively over nonempty lists. Functions
over powerlists are defined analogously. For instance, the following function,
rev, reverses the order of the elements of the argument powerlist.
The case analysis, as for linear lists, is based on the length of the argument
powerlist. We adopt the pattern matching scheme of ML[17] and Miranda[24] 2
to deconstruct the argument list into its components, p and q, in the recursive
case. Deconstruction, in general, uses the operators j and ./ ; see Section 3.
In the definition of rev, we have used j for deconstruction; we could have used
./ instead and defined rev in the recursive case by
It can be shown, using the laws in Section 3, that the two proposed definitions
of rev are equivalent and that
for any powerlist P .
Scalar Functions
Operations on scalars are outside our theory. Some of the examples in this
paper, however, use scalar functions, particularly, addition and multiplication
(over complex numbers) and cons over linear lists. A scalar function, f , has zero
or more scalars as arguments and its value is a scalar. We coerce the application
of f to a powerlist by applying f "pointwise" to the elements of the powerlist.
For a scalar function f of one argument we define
2 Miranda is a trademark of Research Software Ltd.
It can be shown that
A scalar function that operates on two arguments will often be written as an
infix operator. For any such function \Phi, we have
(p ./ q) \Phi (u ./
Thus, scalar functions commute with both j and .
Note: Since a scalar function is applied recursively to each element of a pow-
erlist, its effect propagates through all "levels". Thus, + applied to matrices
forms their elementwise sum. 2
2.3 Discussion
The base case of a powerlist is a singleton list, not an empty list. Empty lists (or,
equivalent data structures) do not arise in the applications we have considered.
For instance, in matrix algorithms the base case is a 1 \Theta 1 matrix rather than an
empty matrix, Fourier Transform is defined for a singleton list (not the empty
list) and the smallest hypercube has one node.
The recursive definition of a powerlist says that a powerlist is either of the
form u ./ v or u j v. In fact, every nonsingleton powerlist can be written in
either form in a unique manner (see Laws in Section 3). A simple way to view
is that if the elements of L are indexed by n-bit strings in increasing
numerical order (where the length of L is is the sublist of elements
whose highest bit of the index is 0 and q is the sublist with 1 in the highest bit
of the index. Similarly, if u ./ then u is the sublist of elements whose
lowest bit of the index is 0 and v's elements have 1 as the lowest bit of the index.
At first, it may seem strange to allow two different ways for constructing the
same list-using tie or zip. As we see in this paper this causes no difficulty, and
further, this flexibility is essential because many parallel algorithms-the Fast
Fourier Transform being the most prominent-exploit both forms of construction

We have restricted u; v in u j v and u ./ v to be similar. This restriction
allows us to process a powerlist by recursive divide and conquer, where each
division yields two halves that can be processed in parallel, by employing the
same algorithm. (Square matrices, for instance, are often processed by quarter-
ing them. We will show how quartering, or quadrupling, can be expressed in
our theory.) The similarity restriction allows us to define complete binary trees,
hypercubes and square matrices that are not "free" structures.
The length of a powerlist is a power of 2. This restricts our theory somewhat.
It is possible to design a more general theory eliminating this constraint; we
sketch an outline in Section 6.
L0. For singleton powerlists, hxi; hyi
L1. (Dual Deconstruction)
For any non-singleton powerlist, P , there exist similar powerlists
s; u; v such that
L2. (Unique Deconstruction)
(p ./
L3. (Commutativity of j and ./ )
These laws can be derived by suitably defining tie and zip, using the standard
functions from the linear list theory. One possible strategy is to define tie as
the concatenation of two equal length lists and then, use the Laws L0 and L3
as the definition of zip; Laws L1, L2 can be derived next. Alternatively, these
laws may be regarded as axioms relating tie and zip.
Law L0 is often used in proving base cases of algebraic identities. Laws
L1, L2 allow us to uniquely deconstruct a nonsingleton powerlist using either
j or . Law L3 is crucial. It is the only law relating the two construction
operators, j and ./ , in the general case. Hence, it is invariably applied in
proofs by structural induction where both constructors play a role.
Inductive Proofs
Most proofs on powerlists are by induction on the length, depth or shape of the
list. The length, len, of a powerlist is the number of elements in it. Since the
length of a powerlist is a power of 2, the logarithmic length, lgl, is a more useful
measure. Formally,
The depth of a powerlist is the number of "levels" in it.
depth
depth
depth
(In the last case, since u; v are similar powerlists they have the same depth.)
Most inductive proofs on powerlists order them lexicographically on the pair
(depth, logarithmic length). For instance, to prove that a property \Pi holds for
all powerlists, it is sufficient to prove
\PihSi and,
The last proof step could be replaced by
The shape of a powerlist P is a sequence of natural numbers
d is the depth of P and
n 0 is the logarithmic length of P ,
1 is the logarithmic length of (any) element of P , say r
2 is the logarithmic length of any element of
A formal definition of shape is similar to that of depth. The shape is a linear
sequence because all elements, at any level, are similar. The shape and the
type of the scalar elements define the structure of a powerlist completely. For
inductive proofs, the powerlists may be ordered lexicographically by the pair
(depth, shape), where the shapes are compared lexicographically.
We show a few small algorithms on powerlists. These include such famous examples
as the Fast Fourier Transform and Batcher sorting networks. We restrict
the discussion in this section to simple (unnested) powerlists (where the depth
is 0); higher dimensional lists (and algorithms for matrices and hypercubes) are
taken up in a later section. Since the powerlists are unnested, induction based
on length is sufficient to prove properties of these algorithms.
4.1 Permutations
We define a few functions that permute the elements of powerlists. The function
rev, defined in Section 2.2, is a permutation function. These functions appear
as components of many parallel algorithms.
Rotate
Function rr rotates a powerlist to the right by one; thus, rrha b c di = hd a b ci.
Function rl rotates to the left: rlha b c di = hb c d ai.
There does not seem to be any simple definition of rr or rl using j as the
deconstruction operator. It is easy to show, using structural induction, that
rr,rl are inverses. An amusing identity is rev(rr(rev(rr P
A powerlist may be rotated through an arbitrary amount, k, by applying
successive rotations. A better scheme for rotating (u ./ v) by k is to rotate
both u, v by about k=2. More precisely, the function grr (given below) rotates
a powerlist to the right by k, where k - 0. It is straightforward to show that
for all k; k - 0, and all p, grr k is the k-fold application
of rr.
Rotate Index
A class of permutation functions can be defined by the transformations on the
element indices. Imagine that each element of a powerlist, having 2 n elements,
has associated with it an n-bit index, where the indices are in increasing numerical
order. (For a powerlist u j v, indices for the elements in u have "0" as
the highest bit and in v have "1" as the highest bit. In u ./ v, similar remarks
apply for the lowest bit.) Any bijection, h, mapping indices to indices defines
a permutation of the powerlist: The element with index i is moved to the position
where it has index (h i). Below, we consider two simple index mapping
functions; the corresponding permutations of powerlists are useful in describing
the shuffle-exchange network. Note that indices are not part of our theory.
A function that rotates an index to the right (by one position) has the
permutation function rs (for right shuffle) associated with it. The definition
of rs may be understood as follows. The effect of rotating an index to the
right is that the lowest bit of an index becomes the highest bit; therefore, if
rs is applied to u ./ v, the elements of u-those having 0 as the lowest bit-
will occupy the first half of the resulting powerlist (because their indices have
"0" as the highest bit, after rotation); similarly, v will occupy the second half.
Analogously, the function that rotates an index to the left (by one position)
induces the permutation defined by ls (for left shuffle), below. Figure 2 shows
the effects of index rotations on an 8-element list.
rs
ls

Figure

2: Permutation functions rs, ls defined in Section 4.1.
It is trivial to see that rs, ls are inverses.
Inversion
The function inv is defined by the following function on indices. An element
with index b in P has index b 0 in (inv P ), where b 0 is the reversal of the bit
string b. Thus,
000 001 010 011 100 101 110 111
inv h a b c d e f g h
h a e c g b f d h i
The definition of inv is
This function arises in a variety of contexts. In particular, inv is used to permute
the output of a Fast Fourier Transform network into the correct order.
The following proof shows a typical application of structural induction.
INV1. inv(p ./
structural induction on p and q.
Base
fFrom
fdefinition of invg
Applying Law L0g
Induction
fcommutativity of j , ./ g
fdefinition of invg
inv(r ./ u) ./ inv(s ./ v)
finductiong
(inv r ./ inv s) j (inv u ./ inv v)
fapply definition of inv to both sides of j g
Using INV1 and structural induction, it is easy to establish
and for any scalar operator \Phi
The last result holds for any permutation function in place of inv.
4.2 Reduction
In the linear list theory[4], reduction is a higher order function of two argu-
ments, an associative binary operator and a list. Reduction applied to \Phi and
[a 0 a an an ). This function over powerlists is defined
by
red \Phi
red \Phi (p j (red \Phi p) \Phi (red \Phi q)
4.3 Gray Code
Gray code sequence for n, is a sequence of 2 n n-bit strings where the
consecutive strings in the sequence differ in exactly one bit position. (The last
and the first strings in the sequence are considered consecutive.) Standard Gray
code sequences for are shown in Figure 3. We represent the n-bit

Figure

3: Standard Gray code sequence for n,
strings by linear lists of length n and a Gray code sequence by a powerlist
whose elements are these linear lists. The standard Gray code sequence may be
computed by function G, for any n.
Here, (0 :) is a scalar function that takes a linear list as an argument and
appends 0 as its prefix. According to the coercion rule, is the powerlist
obtained by prefixing every element of P by 0. Similarly,
where the function rev is from Section 2.2.
4.4 Polynomial
A polynomial with coefficients may be represented
by a powerlist p whose j th element is p j . The polynomial value at some point
! is
. For n ? 0 this quantity is
. The following function ep uses this
strategy to evaluate a polynomial p at a given point; here hwi is a singleton
powerlist and ep returns a singleton powerlist.
(p ./ q)
Note that w 2 is the pointwise squaring of w and \Theta has higher prioroty than +.
In anticipation of the Fast Fourier transform, we generalize ep to accept an
arbitrary powerlist as its second argument. For powerlists possibly,
unequal length) let p ep w be a powerlist of the same length as w, obtained
by evaluating p at each element of w. The definition of ep given above also
implements this generalization. Since ep applies pointwise to each element of
we have
4.5 Fast Fourier Transform
For a polynomial p with complex coeeficients, its Fourier Transform is obtained
by evaluating p at certain specific points. More precisely, the Fourier transform,
FT , of a powerlist p is a powerlist of the same length given by
where ep is the function defdined in Section 4.4, N is the logarithmic length of
w(N ) is the powerlist h! is the (2 N ) th principal root
of 1.
The straightforward computation of of p ep v for any p; v consists of evaluating
p at each element of v; this takes time
M . Since w(N ) is of a special form the Fourier Transform can be computed in
O(M log M ) steps, using the the Fast Fourier Transform algorithm[8]. This
algorithm also admits of an efficient implemntation, requiring O(log M ) steps
on O(M ) processors.
We derive the FFT algorithm below. We need the following two properties
of w(N ). For all N , N - 0, there is a powerlist u such that
The first equation follws from the fact that the right half of w(N + 1) is
its left half multiplied by ! 2 N
. Since ! is the (2 N+1 ) th principal root of 1,
\Gamma1. The second equation is straightforward since w(N ) is a powerlist
containing the successive powers of a number. Now,
fdefinition of FTg
fSince w(0) is a singleton, from the definition of epg
For the general case,
FT (p ./ q)
fLet N be the logarithmic length of p. From the definition of FTg
(p ./ q)
ffrom (1), let
fdistribute ep over the second argumentg
fdefinition of epg
fusing (2), replace u 2 by w(N )g
fdefinition of FTg
To get a formal definition of FFT , we write powers p for the powerlist h!
where M is the length of p and ! is the (2M ) th principal root of 1. Therefore,
u is powers p. The functions powers can be defined similarly to ep. Collecting
the definitions,
FFT (p ./
It is clear that FFT (p ./ q) can be computed from (FFT p) and (FFT q)
in O(M ) sequential steps or O(1) parallel steps using O(M ) processors (U can
be computed in parallel), where M is the length of p. Therefore, FFT (p ./ q)
can be computed in O(M log M ) sequential steps or O(log M ) parallel steps
using O(M ) processors.
The compactness of this description of FFT is in striking contrast to the
usual descriptions; see, for instance, Chandy and Misra[7, Section 6.13]. The
compactness can be attributed to the use of recursion and the avoidance of
explicit indexing (of the elements), by employing j and . FFT illustrates
the need for including both j and ./ as constructors for powerlists. (Another
function that employs both j and ./ is inv of Section 4.1.)
Inverse Fourier Transform
The inverse of the Fourier Transform, IFT, can be defined similarly to the FFT.
In fact, the definition of IFT can be derived from that of the FFT by pattern
matching.
For a singleton powerlist, hxi, we compute
IFT
fIFT, FFT are inversesg
For the general case, we have to compute IFT (p j q) from p; q. Let
in the unknowns u; v. These forms of deconstructions are chosen so that we
can easily solve the equations we generate, next. Taking FFT of both sides,
The left side is p j q because IFT, FFT are inverses. Replacing the right
side by the definition of FFT (u ./ v) yields the following equations.
These equations are easily solved for the unknowns U; V; W; u; v. (Note that the
law of unique deconstruction, L2, is used to deduce from the first equation that
.) The solutions of these equations yield the
following definition for IFT. Here, =2 divides each element of the given powerlist
by 2.
As before, ! is the N th principal root of 1 where N is the length of (p j q).
As in the FFT, the definition of IFT includes both constructors, j and .
It can be implemented efficiently on a Butterfly network. The complexity of
IFT is same as that of the FFT.
4.6 Batcher Sorting Networks
In this section, we develop some elementary results about sorting and discuss
two remarkable sorting methods due to Batcher[3]. We find it interesting that
is the preferred operator in discussing the principles of parallel
sorting. Henceforth, a list is sorted means that its elements are arranged in
ascending order.
A general method of sorting is given by
where merge (written as a binary infix operator) creates a single sorted powerlist
out of the elments of its two argument powerlists. In this section, we show two
different methods for implementing merge. One scheme is Batcher merge, given
by the operator bm. Another scheme is given by bitonic sort where the sorted
lists p; q are merged by applying the function bi to (p j (rev q)).
A comparison operator, l, is used in these algorithms. The operator is
applied to a pair of powerlists; it is defined by
That is, the 2i th and (2i th items of p l q are (p i min
respectively. The expression p l q can be computed in constant time using
O(len p) processors.
Bitonic Sort
A sequence of numbers, x there is an index i,
(ascending or descending) and
monotonic. The function bi, given below, applied to a bitonic pow-
erlist returns a sorted powerlist of the original items.
For two powerlists u; v that are sorted in ascending order the powerlist (u j (rev v))
is bitonic; thus u; v can be merged by applying bi to (u j (rev v)). The form of
the recursive definition suggests that bi can be implemented on O(N ) processors
in O(log N ) parallel steps, where N is the length of the argument powerlist.
Batcher Merge
Batcher has also proposed a scheme for merging two sorted lists. We define this
scheme, bm, as an infix operator below.
The function bm is well suited for parallel implementation. The recursive form
suggests that (r bm v) and (s bm u) can be computed in parallel. Since l can be
applied in O(1) parallel steps using O(N ) processors, where N is the length of
the argument powerlists, the function bm can be evaluated in O(log N ) parallel
steps. In the rest of this section, we develop certain elementary facts about
sorting and prove the correctness of bm.
Elementary Facts about Sorting
We consider only "compare and swap" type sorting methods. It is known (see
Knuth[13]) that such a sorting scheme is correct iff it sorts lists containing 0's
and 1's only. Therefore, we restrict our discussion to powerlists containing 0's
and 1's, only.
For a powerlist p, let z p be the number of 0's in it. To simplify notation,
we omit the space and write zp. Clearly,
Powerlists containing only 0's and 1's have the following properties.
Note: The condition analogous to (A2) under which p j q is sorted is,
The simplicity of (A2), compared with (A2 0 ), may suggest why ./ is the primary
operator in parallel sorting. 2
The following results, (B1, B2), are easy to prove. We prove (B3).
B2. z(p l
B3.
Proof: Since the statement of the theorem is symmetric in p; q, assume zp -
zq.
(p min q) ./ (p max q) sorted
fdefinition of p l qg
l q sorted 2
Correctness of Bitonic Sort
We show that the function bi applied to a bitonic powerlist returns a sorted
powerlist of the original elements: (B4) states that bi preserves the number
of zeroes of its argument list (i.e., it loses no data) and (B5) states that the
resulting list is sorted.
B4. z(bi
Proof: By structural induction, using B2. 2
B5.
Proof: By structural induction.
Base: Straightforward.
Induction: Let
) finduction on p and qg
ffrom B4: z(bi
fapply B3 with (bi p); (bi q) for
(bi p) l (bi q) sorted
fdefinition of big
Correctness of Batcher Merge
We can show that bm merges two sorted powerlists in a manner similar to the
proof of bi. Instead, we establish a simple relationship between the functions
bm and bi from which the correctness of the former is obvious. We show that
where rev reverses a powerlist (Section 2.2).
If p; q are sorted then p j (rev q) is bitonic (a fact that we don't prove here).
Then, from the correctness of bi it follows that bi(p j (rev q)) and, hence,
bm q is sorted (and it contains the elements of p and q).
Proof of (B6): By structural induction.
Base: Let
fdefinition of revg
fdefinition of big
fdefinition of bmg
Induction: Let
fexpanding
fdefinition of revg
fdefinition of big
finductiong
(r bm v) l (s bm u)
fdefinition of bmg
fusing the definitions of p; qg
The compactness of the description of Batcher's sorting schemes and the simplicity
of their correctness proofs demonstrate the importance of treating recursion
and parallelism simultaneously.
ffl7
ffl6
ffl5
ffl4
ffl3
ffl2
ffl1
ffl7
ffl6
ffl5
ffl4
ffl3
ffl2
ffl1
ffl7
ffl6
ffl5
ffl4
ffl3
ffl2
ffl1
ffl7
ffl6
ffl5
ffl4
ffl3
ffl2
ffl1
level 3
level 2
level 1
level 0
ffl0
ffl0
ffl0
ffl0

Figure

4: A network to compute the prefix sum of 8 elements.
4.7 Prefix Sum
Let L be a powerlist of scalars and \Phi be a binary, associative operator on that
scalar type. The prefix sum of L, with respect to \Phi, (ps L), is a list of the same
length as L given by
ps
that is, the i th element of (ps L) is obtained by applying \Phi to the first (i
elements of L in order. We will give a formal definition of prefix sum later in
this section.
Prefix sum is of fundamental importance in parallel computing. We show
that two known algorithms for this problem can be concisely represented and
proved in our theory. Again, zip turns out to be the primary operator for
describing these algorithms.
A particularly simple scheme for prefix sum of 8 elements is shown in Figure
4. In that figure, the numbered nodes represent processors, though the same
physical processors are used at all levels. Initially, processor i holds the list
element L i , for all i. The connections among the processors at different levels
depict data transmissions. In level 0, each processor, from 0 through 6, sends its
data to its right neighbor. In the i th level, processor i sends its data to (i
if such a processor exists (this means that for receives no
data in level i data transmission). Each processor updates its own data, d, to
r \Phi d where r is the data it receives; if it receives no data in some level then d is
unchanged. It can be shown that after completion of the computation at level
(log 2 (len L)), processor i holds the i th element of (ps L).
Another scheme, due to Ladner and Fischer[15], first applies \Phi to adjacent
elements to compute the list hx 0 \Phi x list
has half as many elements as the original list; its prefix sum is then computed
recursively. The resulting list is hx 0 \Phi x
This list contains half of the elements of the final list; the missing elements are
These elements can be computed by
appropriately to the elements of the already computed list.
Both schemes for prefix computation are inherently recursive. Our formulations
will highlight both parallelism and recursion.
Specification
As we did for the sorting networks (Section 4.6), we introduce an operator in
terms of which the prefix sum problem can be defined. First, we postulate
that 0 is the identity element of \Phi, i.e., 0 \Phi x. For a powerlist p, let
be the powerlist obtained by shifting p to the right by one. The effect of
shifting is to append a 0 to the left and discard the rightmost element of p;
thus, ha b c di
(p ./ q)
It is easy to show
S1. (r \Phi s)
S2. (p ./ q)
Consider the following equation in the powerlist variable z.
where L is some given powerlist. This equation has a unique solution in z,
because
For di which is exactly
(ps L). We define (ps L) to be the unique solution of (DE), and we call (DE)
the defining equation for (ps L).
Notes
1. The operator \Phi is not necessarily commutative. Therefore, the rhs of (DE)
may not be the same as L \Phi z   .
2. The operator \Phi is scalar; so, it commutes with .
3. The uniqueness of the solution of (DE) can be proved entirely within the
powerlist algebra, similar to the derivation of Ladner-Fischer scheme given
later in this section.
4. Adams[1] has specified the prefix-sum problem without postulating an
explicit "0" element. For any \Phi, he introduces a binary operator ~ \Phi over
two similar powerlists such that p ~ \Phi q. The operator ~
\Phi can be
defined without introducing a "0".
Computation of the Prefix Sum
The function sps (simple prefix sum) defines the scheme of Figure 4.
sps
sps
where
In the first level in Figure 4, L   \Phi L is computed. If
then this is hx This is the zip of the two sublists
Now prefix sums
of these two lists are computed (independently) and then zipped.
The Ladner-Fischer scheme is defined by the function lf .
lf (p ./
Correctness
We can prove the correctness of sps and lf by showing that the function ps
satisfies the equations defining each of these functions. It is more instructive to
see that both sps and lf can be derived easily from the specification (DE). We
carry out this derivation for the Fischer-Ladner scheme as an illustration of the
power of algebraic manipulations. First, we note
P1.
Proof: pshxi
ffrom the defining equation DE for pshxig
fdefinition of   g
f\Phi is a scalar operationg
f0 is the identity of \Phig
Derivation of Ladner-Fischer Scheme
Given a powerlist p ./ q, we derive an expression for ps(p ./ q). Let r ./ t, in
unknowns t, be ps(p ./ q). We solve for t.
ps (p ./ q). Using (DE)g
Applying law L2 (unique deconstruction) to the equation
we conclude that
LF1.
Now, we eliminate r from (LF2) using (LF1) to get Using
(DE) and this equation we get
Now we compute ps(p ./ q).
ps(p ./ q)
fby definitiong
Using (LF1) for rg
where t is defined by LF3. This is exactly the definition of the function lf for
a non-singleton powerlist. We also note that
r
eliminating t from (LF1) using (LF2) g
(r \Phi q)   \Phi p
definition of *g
r   \Phi q   \Phi p
Using (DE) and this equation
LF4.
This fact will be used in proving the correctness of sps, next.
Correctness of sps
We show that for a non-singleton powerlist L, ps
Proof: Let
ps L
ps(p ./ q)
t, where are given by (LF4,LF3)g
ps(q   \Phi p) ./ ps(p \Phi q)
fLetting
(ps u) ./ (ps v)
Now, we show that u ./
(q   \Phi p) ./ (p \Phi q)
(q   ./ p) \Phi (p ./ q)
fApply the definition of   to the first termg
(p ./ q)   \Phi (p ./ q)
Remarks
A more traditional way of describing a prefix sum algorithm, such as the simple
scheme of Figure 4, is to explicitly name the quantities that are being com-
puted, and establish relationships among them. Let y ij be computed by the i th
processor at the j th level. Then, for all
the logarithmic length of the list,
ae y i\Gamma2
oe
The correctness criterion is
y
This description is considerably more difficult to manipulate. The parallelism
in it is harder to see. The proof of correctness requires manipulations of indices:
for this example, we have to show that for all
The Ladner-Fischer scheme is even more difficult to specify in this manner.
Algebraic methods are to be preferred for describing uniform operations on
aggregates of data.
5 Higher Dimensional Arrays
A major part of parallel computing involves arrays of one or more dimensions.
An array of m dimensions (dimensions are numbered 0 through represented
by a powerlist of depth (m \Gamma 1). Conversely, since powerlist elements
are similar, a powerlist of depth may be regarded as an array of dimension
m. For instance, a matrix of r rows and c columns may be represented
as a powerlist of c elements, each element being a powerlist of length r storing
the items of a column; conversely, the same matrix may be represented by a
powerlist of r elements, each element being a powerlist of c elements.
In manipulating higher dimensional arrays we prefer to think in terms of
array operations rather than operations on nested powerlists. Therefore, we
introduce construction operators, analogous to j and ./ , for tie and zip along
any specified dimension. We use for the corresponding operators in dimension
for the dimension 2, etc. The definitions of these operators
are in Section 5.2; for the moment it is sufficient to regard j 0 as the pointwise
application of j to the argument powerlists (and similarly, ./ 0 ). Thus, for
similar (power) matrices A; B that are stored columnwise (i.e., each element is
a column), A j B is the concatenation of A; B by rows and A j 0 B is their
concatenation by columns. Figure 5 shows applications of these operators on
specific matrices.
Given these constructors we may define a matrix to be either



Figure

5: Applying matrices. Matrices are stored by columns.
Typical matrix format is used for display, though each matrix is to be regarded
as a powerlist of powerlists.
a singleton matrix hhxii, or
are (similar) matrices, or
are matrices.
Analogous definitions can be given for n-dimensional arrays. Observe that the
length of each dimension is a power of 2. As we had in the case of a pow-
erlist, the same matrix can be constructed in several different ways, say, first
by constructing the rows and then the columns, or vice versa. We will show, in
Section 5.2, that
Note: We could have defined a matrix using ./ and ./ 0 instead of j and
As j and ./ are duals in the sense that either can be used to construct
(or uniquely deconstruct) a powerlist, j 0 and ./ 0 are also duals, as we show in
Section 5.2. Therefore, we will freely use all four construction operators for
matrices. 2
Example: Matrix Transposition
Let - be a function that transposes matrices. From the definition of a matrix,
we have to consider three cases in defining - .
The description of function - , though straightforward, has introduced the possibility
of an inconsistent definition. For a 2 \Theta 2 matrix, for instance, either of
the last two deconstructions apply and, it is not obvious that the same result
is obtained independent of the order in which the rules are applied. We show
that - is a function.
We prove the result by structural induction. For a matrix of the form hhxii,
only the first deconstruction applies, and, hence, the claim holds. Next, consider
a matrix to which both of the last two deconstructions apply. Such a matrix is of
the form (p j
Applying one step of each of the last two rules in different order, we get
fapplying the last ruleg
fapplying the middle ruleg
And,
fapplying first the middle rule, then the last ruleg
From the induction hypothesis, (- p), (- q), etc., are well defined. Hence,
Crucial to the above proof is the fact that j and j 0 commute; this is reminiscent
of the "Church-Rosser Property" in term rewriting systems. Commutativity
is so important that we discuss it further in the next subsection.
It is easy to show that
Transposition of a square (power) matrix can be defined by deconstructing
the matrix into quarters, transposing them individually and rearranging them,
as shown in Figure 6. From the transposition function - for general matrices,
we get a function oe for transpositions of square matrices
Note the effectiveness of pattern matching in this definition.
oe q oe v
oe u
oe

Figure

Schematic of the transposition of a square powermatrix.
5.1 Pointwise Application
Let g be a function mapping items of type ff to type fi. Then g 0 maps a powerlist
of ff-items to a powerlist of fi-items.
Similarly, for a binary operator op
We have defined these two forms explicitly because we use one or the other
in all our examples; f 0 for a function f of arbitrary arity is similarly defined.
Observe that f 0 applied to a powerlist of length N yields a powerlist of length N .
The number of primes over f determines the dimension at which f is applied
(the outermost dimension is numbered 0; therefore writing ./ , for instance,
without primes, simply zips two lists). The operator for pointwise application
also appears in Backus[2] and in Steele and Hillis[23].
Common special cases for the binary operator, op, are j and ./ and their
pointwise application operators. In particular, writing ./ m to denote ./
z -
we define, ./
From the definition of f 0 , we conclude that f 0 and j commute. Below, we
prove that f 0 commutes with .
Theorem 1: f
Proof: We prove the result for unary f ; the general case is similar. Proof is
by structural induction.
Base: f 0 (hxi ./ hyi)
fdefinition of f 0 g
These are singleton listsg
Induction:
in the argument commuteg
finductiong
Theorem 2: For a scalar function f , f
Proof: Proof by structural induction is straightforward. 2
Theorem 3: If f; g commute then so do f
Proof: By structural induction. 2
The following results about commutativity can be derived from Theorems
1,2,3. In the following, m;n are natural numbers.
C1. For any f and m ? n
C2. For m 6= n,
C3. For all
C4. For any scalar function, f
C1 follows by applying induction on Theorems 1 and 3 (and the fact that f
commute). C2 follows from C1; C3 from C1, Law L3 and Theorem 3; C4 from
C1 and Theorem 2.
5.2 Deconstruction
In this section we show that any powerlist that can be written as
some p; q can also be written as u ./ m v for some u; v and vice versa; this is
analogous to Law L1, for dual deconstruction. Analogous to Law L2, we show
that such deconstructions are unique.
Theorem 4 (dual deconstruction): For any p; q and m - 0, if
defined then there exist u; v such that
Conversely, for any u; v and m - 0, if u ./ m v is defined then there exist some
q such that
We do not prove this theorem; its proof is similar to the theorem given below.
Theorem 5 (unique
Let\Omega be j or . For any natural
number m,
Proof: Proof is by induction on m.
The result follows from Law L2.
. The proof is similar
We prove
the result by structural induction on p.
Base:
fdefinition of j n+1 g
using Law L2g
a
j finduction on ng
fdefinition of j n+1 g
using Law L2g
j finduction on the length of
Theorems 4 and 5 allow a richer variety of pattern matching in function def-
initions, as we did for matrix transposition. We may employ
natural m;n to construct a pattern over which a function can be defined.
5.3 Embedding Arrays in Hypercubes
An n-dimensional hypercube is a graph of 2 n nodes, n - 0, where each node has
a unique n-bit label. Two nodes are neighbors, i.e., there is an edge between
them, exactly when their labels differ in a single bit. Therefore, every node
has n neighbors. We may represent a n-dimensional hypercube as a powerlist
of depth n; each level, except the innermost, consists of two powerlists. The
natural m;n can be used to access the nodes in any one
(or any combination of) dimensions.
We conclude with an example that shows how higher dimensional structures,
such as hypercubes, are easily handled in our theory. Given an array of size
we claim that its elements can be placed at the nodes of a
hypercube (of dimension m 0 +m 1 +::+m d ) such that two "adjacent" data items
in the array are placed at neighboring nodes in the hypercube. Here, two data
items of the array are adjacent if their indices differ in exactly one dimension,
and by 1 modulo N , where N is the size of that dimension. (This is called
"wrap around" adjacency.)
The embedding algorithm works as follows. If the array has only one dimension
then we create a gray code sequence, G m (see
Section 4.3). Abbreviate G m by g. We place the i th item of the array at the
node with label g i . Adjacent items, at positions i and
are placed at nodes g i and g i+1 which differ in exactly one bit, by the
construction.
This idea can be generalized to higher dimensional arrays as follows. Construct
gray code sequences for each dimension independently; store the item
with index (i at the node (g i 0
denotes the
concatenations of the bit strings. By definition, adjacent items differ by 1 in
exactly one dimension, k. Then, their gray code indices are identical in all
dimensions except k and they differ in exactly one bit in dimension k.
We describe a function, em, that embeds an array in a hypercube. Given an
array of size 2 m0 \Theta2 m1 \Theta::2 md it permutes its elements to an array 2 \Theta 2 \Theta
and the permutation preserves array adjacency as de-
scribed. The algorithm is inspired by the gray code function of Section 4.3. In
the following, S matches only with a scalar and P with a powerlist.
em P
The first line is the rule for embedding a single item in 0-dimensional hypercube.
The next line, simply, says that an array having length 1 in a dimension can be
embedded by ignoring that dimension. The last line says that a nonsingleton
array can be embedded by embedding the left half of dimension 0 and the reverse
of the right half in the two component hypercubes of a larger hypercube.
6 Remarks
Related Work
Applying uniform operations on aggregates of data have proved to be extremely
powerful in APL[9]; see Backus[2] and Bird[4] for algebras of such operators.
One of the earliest attempts at representing data parallel algorithms is in Preparata
and Vuillemin[21]. In their words, "an algorithm. performs a sequence of basic
operations on pairs of data that are successively 2
locations apart". An algorithm operating on 2 N pieces of data is described as a
sequence of N parallel steps of the above form where the k th step,
applies in parallel a binary operation, OPER, on pairs of data that are 2 (N \Gammak)
apart. They show that this paradigm can be used to describe a large number
of known parallel algorithms and, any such algorithm can be efficiently implemented
on the Cube Connected Cycle connection structure. Their style of
programming was imperative. It is not easy to apply algebraic manipulations to
such programs. Their programming paradigm fits in well within our notation.
Mou and Hudak[19] and Mou[20] propose a functional notation to describe divide
and conquer-type parallel algorithms. Their notation is a vast improvement
over Preparata and Vuillemin's in that changing from an imperative style to a
functional style of programming allows more succinct expressions and the possibility
of algebraic manipulations; the effectiveness of this programming style on
a scientific problem may be seen in [25]. They have constructs similar to tie and
zip, though they allow unbalanced decompositions of lists. An effective method
of programming with vectors has been proposed by Blelloch[5, 6]. He proposes a
small set of "vector-scan" instructions that may be used as primitives in describing
parallel algorithms. Unlike our method he is able to control the division of
the list and the number of iterations depending on the values of the data items,
a necessary ingredient in many scientific problems. Jones and Sheeran[10] have
developed a relational algebra for describing circuit components. A circuit component
is viewed as a relation and the operators for combining relations are given
appropriate interpretations in the circuit domain. Kapur and Subramaniam[11]
have implemented the powerlist notation and proved many of the alogrithms
in this paper using an inductive theorem prover, called RRL (Rewrite Rule
Laboratory), that is based on equality reasoning and rewrite rules. They are
now extending their theorem prover so that the similarity constraints on the
powerlist constructors do not have to be stated explicitly.
One of the fundamental problems with the powerlist notation is to devise
compilation strategies for mapping programs (written in the powerlist notation)
to specific architectures. The architecture that is the closest conceptually is the
hypercube. Kornerup[14] has developed certain strategies whereby each parallel
step in a program is mapped to a constant number of local operations and
communications at a hypercube node.
Combinational circuit verification is an area in which the powerlist notation
may be fruitfully employed. Adams[1] has proved the correctness of adder
circuits using this notation. A ripple-carry adder is typically easy to describe
and prove, whereas a carry-lookahead adder is much more difficult. Adams has
described both circuits in our notation and proved their equivalence in a remarkably
concise fashion. He obtains a succinct description of the carry-lookahead
circuit by employing the prefix-sum function (See Section 4.7).
Powerlists of Arbitrary Length
The lengths of the powerlists have been restricted to be of the form 2 n , n - 0,
because we could then develop a simple theory. For handling arbitrary length
lists, Steele [22] suggests padding enough "dummy" elements to a list to make
its length a power of 2. This scheme has the advantage that we still retain the
simple algebraic laws of powerlist. Another approach is based on the observation
that any positive integer is either 1 or 2 \Theta m or 2 \Theta m + 1, for some positive
integer m; therefore, we deconstruct a non-singleton list of odd length into two
lists p; q and an element e, where e is either the first or the middle or the last
element. For instance, the following function, rev, reverses a list.
The last line of this definition applies to a non-singleton list of odd length; the
list is deconstructed into two lists p; q of equal length and e, the middle element.
(We have abused the notation, applying j to three arguments). Similarly, the
function lf for prefix sum may be defined by
lf (p ./
In the last line, e is the first element of the argument list; the remaining
portion of the list (without the first item) is deconstructed into p; q. The right
side of that line denotes a list obtained by appending the element e, to the
list obtained by applying e\Phi to each element of lf(p ./ q); we have used the
convention that (e \Phi t) is the list obtained by applying e\Phi to each element of t.
The Interplay between Sequential and Parallel Computations
The notation proposed in this paper addresses only a small aspect of parallel
computing. Powerlists have proved to be surprisingly successful in expressing
those computations whose structures are independent of the specific data val-
ues; such is the case, for instance, in the Fast Fourier Transform, Batcher merge
and Prefix sum. Typically, however, parallel and sequential computations are
interleaved. While Fast Fourier Transform and Batcher merge represent highly
parallel computations, binary search is inherently sequential (there are other,
parallel search strategies). Gaussian elimination represents a mixture; the computation
consists of a sequence of pivoting steps where each step can be applied
in parallel. Thus parallel computations may have to be performed in a certain
sequence and the sequence may depend on the data values during a computa-
tion. More general methods, as in Blelloch[5], are then required.
The powerlist notation can be integrated into a language that supports sequential
computation. In particular, this notation blends well with ML[17] and
LISP[16, 23]. A mixture of linear lists and powerlists can exploit the various
combinations of sequential and parallel computing. A powerlist consisting of linear
lists as components admits of parallel processing in which each component
is processed sequentially. A linear list whose elements are powerlists suggests a
sequential computation where each step can be applied in parallel. Powerlists
of powerlists allow multidimensional parallel computations, whereas a linear list
of linear lists may represent a hierarchy of sequential computations.

Acknowledgement

This paper has been enriched by comments and suggestions
from Will Adams, Al Carruth (who suggested the term powerlist), Jorge
Cobb, Edsger W. Dijkstra, C.A.R. Hoare, Rajeev Joshi, Markus Kaltenbach,
Deepak Kapur, Jacob Kornerup, Scott Page, Vijaya Ramachandran, Guy Steele
Jr., Alex Tomlinson, and Evelyn Tumlin. Ernie Cohen was singularly helpful at
an early stage of this research. I am grateful to the Austin Tuesday Afternoon
which read and commented on a draft of this manuscript, and to Adams
and Kornerup, especially, for their comments on the second draft.



--R

Verifying adder circuits using powerlists.
Can programming be liberated from the von Neumann style?
Sorting networks and their applications.
Lectures on constructive functional programming.
Vector Models for Data-Parallel Computing
NESL: A nested data-parallel language
Parallel Program Design: A Foun- dation
An algorithm for the machine calculation of complex Fourier series.
A Programming Language.
Circuit design in Ruby.
Automated reasoning about parallel algorithms using powerlists.
Parallel algorithms for shared memory machines.
Sorting and Searching
Mapping Powerlists onto Hypercubes.
Parallel prefix computation.
The Definition of Standard ML.
A structure for parallel recursion (preliminary version).
An algebraic model for divide-and-conquer algorithms and its parallelism
Divacon: A parallel language for scientific computing based on divide-and-conquer
The cube-connected cycles: A versatile network for parallel computation
Steele Jr.
Steele Jr.
An overview of Miranda.
A divide-and-conquer method of solving tridiagonal systems on hypercube massively parallel computers
--TR
An overview of Miranda
Parallel program design: a foundation
The definition of Standard ML
Vector models for data-parallel computing
Parallel algorithms for shared-memory machines
Introduction to parallel algorithms and architectures
Powerlist
Connection Machine Lisp
Parallel Prefix Computation
The cube-connected cycles: a versatile network for parallel computation
Can programming be liberated from the von Neumann style?
NESL: A Nested Data-Parallel Language (Version 2.6)
Verifying Adder Circuits Using Powerlists

--CTR
Jayadev Misra, Derivation of a parallel string matching algorithm, Information Processing Letters, v.85 n.5, p.255-260, March
Georg Ch. Pflug , Ladislav Halada, A Note on the Recursive and Parallel Structure of the Birge and Qi Factorization for Tree Structured Linear Programs, Computational Optimization and Applications, v.24 n.2-3, p.251-265, February-March
Gorlatch, Programming with Divide-and-Conquer Skeletons: A Case Study of FFT, The Journal of Supercomputing, v.12 n.1-2, p.85-97, Jan./Feb., 1998
Ruben A. Gamboa, The Correctness of the Fast Fourier Transform: A Structured Proof in ACL2, Formal Methods in System Design, v.20 n.1, p.91-106, January 2002
Ross Paterson, A new notation for arrows, ACM SIGPLAN Notices, v.36 n.10, October 2001
Jean-Louis Giavitto , Olivier Michel, Declarative definition of group indexed data structures and approximation of their domains, Proceedings of the 3rd ACM SIGPLAN international conference on Principles and practice of declarative programming, p.150-161, September 05-07, 2001, Florence, Italy
Christoph A. Herrmann , Christian Lengauer, Parallelization of divide-and-conquer by translation to nested loops, Journal of Functional Programming, v.9 n.3, p.279-310, May 1999
Roberto Di Cosmo , Zheng Li , Susanna Pelagatti, A calculus for parallel computations over multidimensional dense arrays, Computer Languages, Systems and Structures, v.33 n.3-4, p.82-110, October, 2007
Gorlatch, SAT: a programming methodology with skeletons and collective operations, Patterns and skeletons for parallel and distributed computing, Springer-Verlag, London,
hypercube;algebra of parallel programs;prefix sum;batcher sort;parallel programs;recursion;Fast Fourier Transform