The Strict Time Lower Bound and Optimal Schedules for Parallel Prefix with Resource Constraints.
AbstractPrefix computation is a basic operation at the core of many important applications, e.g., some of the Grand Challenge problems, circuit design, digital signal processing, graph optimizations, and computational geometry.1 In this paper, we present new and strict time-optimal parallel schedules for prefix computation with resource constraints under the concurrent-read-exclusive-write (CREW) parallel random access machine (PRAM) model. For prefix of N elements on p processors (p independent of N) when N > p(p + 1)/2, we derive Harmonic Schedules that achieve the strict optimal time (steps), $\left\lceil {{{2\left( {N-1} \right)} \mathord{\left/ {\vphantom {{2\left( {N-1} \right)} {\left( {p+1} \right)}}} \right. \kern-\nulldelimiterspace} {\left( {p+1} \right)}}} \right\rceil $. We also derive Pipelined Schedules that have better program-space efficiency than the Harmonic Schedule, yet only require a small constant number of steps more than the optimal time achieved by the Harmonic Schedule. Both the Harmonic Schedules and the Pipelined Schedules are simple and easy to implement. For prefix of N elements on p processors (p independent of N) where Np(p + 1)/2, the Harmonic Schedules are not time-optimal. For these cases, we establish an optimization method for determining key parameters of time-optimal schedules, based on connections between the structure of parallel prefix and Pascal's triangle. Using the derived parameters, we devise an algorithm to construct such schedules. For a restricted class of values of N and p, we prove that the constructed schedules are strictly time-optimal. We also give strong empirical evidence that our algorithm constructs strict time-optimal schedules for all cases where Np(p
Introduction
Given a computation evaluates a 0 ffi a associative operation ffi.
Prefix sum (or first-order linear recurrence with coefficients 1) is a special case of prefix computation that can
be stated as a simple loop:
We refer to our problem interchangeably as recurrence, prefix sums, or prefix computation, since the results on
prefix sum can be readily applied to prefix computation with other associative operations.
Prefix computation is a fundamental operation at the core of many key applications such as the
Grand Challenge problems, circuit design, digital signal processing, graph optimizations, and computational
geometry[1, 8, 15]. In addition, it is also an important tool in loop parallelization. Traditional automatic loop
parallelization techniques[4] respect loop-carried dependences, and are thus unable to generate scalable parallel
code from loops containing loop-carried dependences. To understand how to parallelize loops with loop-carried
dependences beyond these techniques, it is essential to understand the simplest case of loops with loop-carried
dependence, namely prefix sums. The optimal schedules and the technique used to derive them in this paper
could be applied-with some extensions- to parallelizing many sequential algorithms containing loop carried
dependences.
Since in practical applications the amount of resources (i.e., functional units, processors) is fixed a priori and
independent of the problem size, it is desirable to devise a scheme which performs prefix computation in optimal
time with a given set of resource constraints. Since we are interested in extending the technique to handle more
general forms of loops with loop-carried true dependence, we are also concerned with other properties of these
optimal schedules, such as clarity, simplicity of implementation, and extendibility.
For a prefix of N elements on p processors (p independent of N ) in N ? p(p 1)=2, we derive Harmonic
Schedules that achieve the strict optimal time (steps), 1)e. We also derive Pipelined Schedules
that have better program-space efficiency than the Harmonic Schedule, yet take a small constant number of
steps more than the optimal time achieved by the Harmonic Schedule. Both the Harmonic Schedules and the
Pipelined Schedules are simple and thus are easy to implement.
For a prefix of N elements on p processors (p independent of N ) in N - p(p + 1)=2, there does not exist the
kind of structure of parallel prefix computation as for those in N ! p(p 1)=2. We establish an optimization
method for determining key parameters of time-optimal schedules, based on connections between structures of
parallel prefix and Pascal's triangle. Using the parameters, we devise an algorithm to construct schedules. For a
restricted class of cases in terms of N and p, we derive strict time-optimal schedules subject to an optimization
condition. For other cases, we give strong empirical evidence that the same algorithm constructs strict time-optimal
schedules. We conjecture that our schedules for N - p(p achieve the strict optimal time.
The paper is organized as follows. Section 2 presents our assumptions and definitions. Section 3 reviews
related work. Section 4 presents the Harmonic Schedule for N ? p(p shows the strict time-
optimality of the Harmonic Schedule and its properties. Section 6 gives the Pipelined Schedule, Section 7
establishes an optimization method for determining key parameters of time-optimal schedules for N - p(p
gives an algorithm to construct schedules for N - p(p strict time-optimal
schedules within our optimization for a restricted class of cases in terms of N and p, and provides
strong empirical evidence that our algorithm constructs the strict time-optimal schedules for all cases where
our results.
We assume the parallel random access machine (PRAM) concurrent-read-concurrent-read (CREW) model [15]
in our analysis. A PRAM consists of p autonomous processors, executing synchronously, all having access to a
globally shared memory. Each processor computes an operation in one time step (or unit). Our schedules are
time-optimal in terms of the number of parallel time steps for which all results are computed. In the CREW
model: multiple processors may read simultaneously from a memory location (i.e., broadcasting data) but
exclusive access is required for writing to the same memory location. To facilitate the study of the computational
complexity and its comparison with previous work in the area, as in most previous results on PRAM CREW,
we assume memory access, data transfer, and other communication take zero time steps.
We now define the terms frequently used in this paper. A schedule A is used to perform a computation 1 . We
denote the time (i.e., the number of time steps) to run schedule A on our machine as T p (A), or T p and T when
unambiguous, where p refers to the number of processors in the machine. We refer to T p and T interchangeably
as time, time steps or steps. The time to compute A sequentially is denoted by T 1 (A). The speedup of a machine
with p processors over a uniprocessor, for schedule A, is denoted or simply S
when unambiguous. Let O p be the number of operations executed in some computation using p processors. We
define operation redundancy to be R since operations are assumed to take
one time step each, the number of operations in the sequential program O 1 defines its run time). Finally, we
define utilization as U is the maximum number of operations that p processors can
perform in T p steps.
There are three types of data-dependences defined in the literature [11]. For our purposes we need only
concern ourselves with true, or flow dependences defined as follows. If an operation uses the result of another
operation is said to be true or flow dependent on simply dependent on unambiguous.
A loop-carried dependence is a type of true dependence in a loop where an operation in an iteration uses a value
produced in a previous iteration.
A dependence of operation can be represented as a directed arc from dependence graph
consists of a set of nodes representing operations or input values and the dependence arcs connecting them. A
binary dependence graph is a dependence graph in which all operations take two operands. An operand may
either be an input value or a value output by an operation. A dependence graph for a prefix computation
scheduled using tree-height reduction (THR) [11] is referred to as a THR graph.
The final values of prefix sums are the values computed by the definition of prefix sums. The final operations
of prefix sums are operations that assign the final values. The redundant operations (or auxiliary or intermediate
operations) are operations that compute auxiliary values in an effort to speed up the final value computation. The
redundant values (or auxiliary or intermediate values) refer to those auxiliary values computed by redundant
operations. Figure 1 shows dependence graphs for a sequential schedule and a parallel schedule for a prefix
computation with eight inputs. As illustrated in those two graphs, nodes for final operations are on the top
fringe, nodes for redundant operations are the inner ones (identified with a square inside), and nodes for given
values are the ones without incoming arcs (placed at the bottom). Note that a dependence graph for a sequential
schedule for prefix sums is a tree but one for a parallel schedule is not.
We define
for any i - j where In particular, ah0; is the prefix sum of the first j elements. Note
We distinguish between our algorithm and schedule -our algorithm is used to produce a schedule(for the given
prefix computation) which, when run on the PRAM, will execute the actual prefix computation.
3 Related Work
The results in parallel prefix computation can be divided in two categories: with no resource constraints, where
usually the number of processor p is a function of the problem size N , and with resource constraints where p is
independent of N . A comprehensive survey of parallel computing using the prefix problem is given in [14].
Special forms of prefix circuits have been previously known to Ofman as early as 1963, whose carry circuit[18]
is a form of the carry circuits later discussed by Ladner and Fischer [13]. Muraoka[16] showed that this simplest
linear recurrence can be computed in log N with N=2 processors, and used the name tree-height reduction for this
technique. Kogge and Stone's recursive doubling[12], for first-order linear recurrences, is essentially equivalent
to tree-height reduction when applied to the prefix problem . Chen and Kuck[11] showed that linear recurrences
can be computed in 1 log N with p - N=2. Ladner and Fischer[13] found a class of circuits for a prefix of
size assuming enough processors are available.
With unlimited resources, Fich[9] gave upper bounds and lower bounds on the circuit size (i.e., the number
of gates or operations) for prefix circuits with N inputs with depth log N d, where d - dlog Ne is an extra
depth, for most cases of unbounded and bounded fan-out. Fich constructed the circuits using a more complex
recursive procedure than Ladner and Fischer's. With unbounded fan-out, the lower bounds for prefix circuits
of input N were Upper bounds with
fan-out bound f - 2 were also obtained. Finally, lower bounds with fan-out two were k2
1. Bilgory and Gajski[5] gave a different algorithm
that generates suffix(the term they used) solutions with minimum cost for a given length n, depth d, initial
value availability e, and fanout f . The cost is defined as the minimum number of operation nodes along a pair
of corresponding input and output. A lower bound on the cost is therefore the maximum number of nodes on
a path from an input to its corresponding output. Instead of circuit size, they chose cost as the measurement
because it fit better with their consideration for silicon layout.
Cole and Vishkin[6] gave an algorithm that solves the prefix sums problem in O(log N= log log N using
log log N= log N processors, provided that each a[i] is represented by O(log N ) bits, which is different from
the problem we address.
With resource constraints, a well-known algorithm described in [3], computes the prefix problem in 2N=p+
log p time. Given p processors, the algorithm divides the problem into p partitions, and "conquers" the local
computation in each partitions with one processor, and "combines" the results. This algorithm takes 2N=(p(p+
more steps than the optimal time.
Snir [19] gave an algorithm for dynamically constructing parallel prefix circuits with a fixed number of
processors for CREW machines such that the depth of the resulting circuit for p processors is 2N=(p+ 1) +O(1)
for which is very close to strict time-optimal in depth. For a given problem size N , Snir's
algorithm works to find the right partition of the problem so as to minimize the depth of the resulting schedule,
and must recompute the partition each time a new N is given. This is an overhead associated with problem
size N at either compile time or run time. If N is known only at run time as it frequently is, then the overhead
incurred by finding the right partition will have an impact on performance.
Parallel prefix computation has also been studied in the EREW PRAM model. In Kruskal, Rudolph, and
Snir [10], it was shown that the prefixes of n elements can be computed using p processors and 2n=p
steps. Egecioglu and Koc [7] studied the tradeoffs between parallel arithmetic steps (required to perform
associative operations) and parallel routing steps (required to transfer operands from one processor to another)
for prefix computation, and presented a prefix algorithm using (2(p
routing steps.
4 The Harmonic Schedule
a3 a4 a5 a6 a7
x3
x2 x3
Sequential Full THR
for (i=1; i<N; i++)

Figure

1: The sequential schedule vs. full tree-height reduction (THR) of prefix sums.
Given a prefix problem of size N as shown in Figure 1, the number of operations in the sequential schedule is
cannot be reduced - by the definition of the required outputs. The left drawing of Figure 1 gives
the computation tree of the sequential schedule for prefix sums of size 8. The tree height, i.e., the dependence
distance on the critical path of the tree for the sequential schedule, equals N \Gamma 1, the minimum number of time
steps to compute the problem sequentially.
The way to parallelize this computation is to use the associativity of the operator and to reduce tree height
(time). The drawing on the right of Figure 1 gives a full tree-height reduction (THR) schedule for prefix sums
of size 8. As shown, we use associativity to compute redundant values ahead of the final value computation,
and then to compute multiple final values in parallel.
Thus we trade multiple processors and redundant operations for speedup, or parallelism. The speed of a
prefix schedule can be thought of as (measured by) the average number of final values produced in a step. Given a
fixed number of processors, we do not want to introduce too many redundant operations, because that will reduce
the average number of results produced per step. For example, with a fixed number of processors, full THR as
shown in Figure 1 slows down the computation farther away from optimal as the problem size N increases. In
order to produce as many final results as possible, given a fixed number of processors, a schedule should do as
few redundant operations as possible. However, one cannot reduce the number of redundant operations below a
certain threshold, because that would leave some processors idle and slow down the computation. For example,
removing all redundant operations, the schedule would degenerate to the sequential schedule as shown in Figure
1 and all but one processor would stay idle.
Therefore, the fastest parallel schedules for a fixed number of processors would use the minimum number of
redundant operations while simultaneously achieving full processor utilization. This is the idea of the Harmonic
Schedule. In the remainder of this section, we describe in detail the derivation and properties of Harmonic
Schedules. We shall prove in the next section that the Harmonic schedule is indeed time-optimal.
Example 4.1

Figure

2 illustrates an iteration of the Harmonic Schedule for processors. The nodes on the top fringe
in

Figure

represent the final values of the prefix computed by the final operations. The inner nodes represent
the redundant values computed by the redundant operations . The bottom ends of the vertical lines represent
the given elements of the prefix sums. The first step of the iteration has one final operation and
operations, the second step has two final operations and redundant operations, and the k-th step has k final
operations and redundant operations. Each step does one more final operation and one fewer redundant
operation than the immediate preceding step. All p processors are in full utilization in all p steps in iterations
(i.e.,loop body). Final and redundant computations "meet" at the end of each iteration. At the end of each
iteration all redundant values are used in computing final values. Another nice property is that the number of
operations in an iteration is the sum of final operations and redundant operations, s(p) Hence
we called our schedule "Harmonic Schedule". 2
The numbers correspond to steps in the loop body.
computed by redundant operations.
The top nodes are final values computed by final operations.
The inner nodes output redundant values

Figure

2: An Iteration of Schedule H for processors.
Schedule 4.1 Harmonic Schedule
Let a multiple of s(p) (all the other cases will be discussed
shortly). The Harmonic Schedule that computes prefix sums of N elements on p processors, denoted H, is
decribed below. Recall ahi; ji represents partial sum of elements a[i] throught a[j] (refer to Section 2). We can
translate the schedule into one using array a[N \Gamma 1] straightforwardly as shown in Figure 3.
I: for
K: for do
f
li
gThe inner loop (K) of the Harmonic Schedule consists of p iterations. Each iteration of the inner loop is executed
in a single parallel step. Each parallel step consists of p operations as shown in the inner loop body that are
executed by the p processors in parallel. The first group of (p \Gamma operations compute the "look ahead"
redundant values or "prefix values", and the second group of k operations compute final values. We refer to the
inner loop as a period of computation by the Harmonic Schedule. We can also easily verify that in schedule H,
no memory location is written into by multiple operations simultaneously.
Schedule 4.1 can be instantiated for a given number of processors during compilation in negligible time.
Note that (unlike in [19]) there is no run-time scheduling overhead, since the full instantiation of the schedule
depends on p and does not depend on N . The array subscript calculation in an instantiated H schedule (i.e.,
for an actual value of p) becomes very simple and can be reduced to addition using strength reduction[2].
do each step in parallel with 7 processors
2. a[28i
3.
4. a[28i
5. a[28i
7.

Figure

3: An instantiated schedule H for processors.
As an illustration, we instantiate a Harmonic Schedule for processors in Figure 3. We have
28 and 21. The inner nodes of height l in Figure 2 are computed by operations in the
l-th step of the instantiated schedule in Figure 3. Note that all operations in each step execute in parallel. We
use array t to store redundant values to distinguish redundant values from final values and given elements. The
size of array t can be reduced to s(p \Gamma 1) since the contents of t produced in an iteration are only used in that
same iteration and thus t can be reused in each iteration.
Theorem 4.1 For prefix sums of size processors, the Harmonic Schedule
computes the given prefix sums. It computes final values in yielding
a speedup S p 1)=2 with a processor utilization U p
Proof:
To prove the correctness of the Harmonic Schedule, it suffices to show it produces the correst results,
for the first period of s(p) elements plus the starting element a 0 , since all periods
have identical computation structures. Note that a period of the Harmonic Schedule corresponds to an iteration
of its program template.
Observe that the Harmonic Schedule computes the prefix sums of s(p) elements in p parallel time steps as
follows: for the schedule computes at the k th step
We use induction on number of parallel steps Assume that at the end of the k th step for
the first s(k) prefix sums ah1; 1i; ah1; as well as
will be available.
At the end of the p th step, the Harmonic Schedule computes
The number of time steps taken by Schedule H to compute ms(p) final values in m iterations can be
determined as follows.
(number of iterations for N elements)(number of time steps per iteration)
have shown that schedule H computes ms(p) final values in some multiple of p steps.
Next, we show that the performance stated in Theorem 4.1 is also true for any N ? p(p subject to a
ceiling effect.
Theorem 4.2 (Extended Harmonic Schedule) Schedule H can be extended to compute the prefix sums of
size N - s(p) in time 1)e, yielding a speedup S
Proof: The previous theorem proved the statement above for 1. Suffice to show
that the above statement is true for N ? s(p), and N 6= ms(p) for m - 1. The proof proceeds in two cases.
Case 1: s(p). The last q elements are called
the trailing elements. The final operations that compute the q trailing elements are called the trailing final
operations, and the redundant operations whose values are used by the trailing final operations are called the
trailing redundant operations. Without loss of generality, let us look at the example for Figure 4.13a[1]
m=1, p=7.
new
delayed ops in step 3 to 7.4746755511811913
Use delayable slots in step 3 to 7 to compute intermediate values.
Use idle slots in step 8 to 13 to compute

Figure

4: The amortizing scheme for extended schedule H with odd p.
In the (mp+ 1)-th step, we want to compute (p final operations and (p \Gamma 1)=2 redundant operations.
How do we do it, given that a redundant tree of height 3 takes exactly 3 steps to compute? The solution is
m=1, p=6.
to compute intermediate values.
Use delayed operations' slots and idle slots
delayed ops in step 4 to 6.
Use idle slots in step 7 to 11 to compute
new4667551081197108

Figure

5: The amortizing scheme for extended schedule H with even p.
to amortize the computation, i.e., to delay some of the final operations in steps ((m
and to use these freed processor time slots to compute the redundant trees incurred by those q steps, and then
to compute those delayed operations with the idle processor slots in steps mp 1. For
example in Figure 4, the redundant tree used in step 8 is computed in step 5, 6 and 7, which causes three final
operations, one in each of step 5 to 7 to be delayed. Then, three idle slots in step 8 are used to compute the
three delayed operations in step 5 through 7.
The question is whether there is a feasible amortizing scheme between the delayed operations and the idle
processor time slots, i.e., whether there are always enough delayable operations to match the tailing redundant
operations in this fashion. Note that there are
final operations in each iteration that can be
delayed because no other operations depend on them. Hence there are enough delayable operations to match
the trailing redundant operations. In similar fashion, we can always find a feasible amortizing scheme for steps
mp+1 through (m+ 1)p \Gamma 1. The above arguments are true for all odd p - 2. Therefore, the extended schedule
H computes prefix sums of size N ? s(p) in time processors.
Case 2: p - 2 is even. Let N be the same as for case 1. The amortizing scheme is shown in Figure 5.
Note that for even p the heights of the trailing local trees are in turn b(p subject to the
number of trailing elements, while for odd p the height of local trees is always (p subject to the number
of trailing elements. The rest of the proof is similar to case 1. Hence, the extended schedule H computes prefix
sums of size N ? s(p) in time theorem 4.2, we can construct the extended part of schedule H as follows. We unwind the last iteration
Minimum number of steps = number of non-redundantly scheduled elements number of redundant trees
This schedule needs at least 12 steps to complete.
Non-redundantly scheduled elements redundantly scheduled elements
Redundant tree
Redundant tree
Redundant tree

Figure

Redundant trees, redundantly scheduled elements and non-redundantly scheduled elements
in schedules.
of the unextended schedule H, and use our amortizing scheme between the delayable operations in the last
iteration and the idle processor slots in those q steps. Thus, we obtain a generic extended schedule H with
epilogues that handles all length of trailing steps for 1 - q ! p. Note that although the precise q depends on
N , the generic extended schedule H can be precomputed and installed as a library routine with
When q is known at run time, the corresponding epilogue will be chosen to run.
5 Optimality of the Harmonic Schedule
In this section we show that schedule H computes in strict optimal time (steps) prefix sums of size N ? s(p) on
processors. Lemma 5.1 presents a lower bound on time for a parallel schedule A for p processors.
Lemma 5.3 shows, for all schedules A with O r (A) - O r (H), that T p (A) - T (H) given the same number of
processors (p). Theorem 5.1 proves the optimality of schedule H.
Consider the elements of the given prefix problem that are stored in array a. We call an element of array
a a redundantly scheduled element if it is used in a redundant operation, otherwise we call it a non-redundantly
scheduled element. A non-redundantly scheduled element does not participate in redundant operations and it
is directly used by a final operation, i.e., there is a direct arc from a non-redundantly scheduled element to a
final operation. In Figure 6, elements are non-redundantly scheduled and elements
redundantly scheduled.
A set of redundant operations is said to form a redundant computation cluster (redundant cluster for short) iff
the dependences of these operations form a connected graph after removing the final operations in the dependence
graph that use the results produced by these redundant operations and without considering directedness of
the resulting graph. A redundant cluster provides redundant lookahead values that can be used by the final
operations in a parallel step in a schedule, as shown in Figure 6. Note that the dependence graph of a redundant
cluster in schedule A is not restricted to a tree.
The non-leaf nodes of a redundant cluster are those redundant values produced by the redundant operations
in the cluster. The leaves of a redundant cluster are those redundantly scheduled elements in the cluster. A
redundant cluster covers those redundantly scheduled elements as its leaves, i.e., it uses them to compute
redundant values.
Lemma 5.1 For any schedule A that computes prefix sums, (number of non-redundantly scheduled
elements (number of redundant clusters).
Proof: In a single parallel step, at most one non-redundantly scheduled element alone or the redundant
values of one redundant cluster alone can be used to compute final values.
In particular, if a schedule A for prefix sums has T redundant clusters, then it takes at least T
A to complete.Lemma 5.2 In a parallel schedule A for prefix sums of size N , the number of redundantly scheduled elements is
smaller than or equal to the sum of the number of redundant operations and the number of redundant clusters,
i.e.,
(number of redundantly scheduled elements in A)- O r (A)+number of redundant clusters.
Proof: A redundant cluster C with O r (C) redundant operations that uses h (redundantly scheduled) elements
of array a has at least c be
the number of redundant clusters in schedule A. Note also that the redundant clusters in A are disconnected,
i.e., there is no dependence between any pair of redundant clusters. Thus we have
(number of redundantly scheduled elements in
(number of redundantly scheduled elements in redundant cluster C j in
O r (A)+number of redundant clusters in A.Lemma 5.3 For prefix sums of size and T is a multiple of p and any
schedule A with O r (A) - O r (H), TP (A) - no such schedule A can compute the given prefix
in fewer steps than schedule H.
Proof:
By Lemma 5.2,
(the number of non-redundantly scheduled elements in
(array size)\Gamma(number of redundantly scheduled elements in
(A)+(number of redundant clusters in A)).
By Lemma 5.1,
(number of redundant clusters in (number of non-redundantly scheduled elements in A \Gamma 1)
- (number of redundant clusters in
(A)+(number of redundant clusters in A))-1]
O r Theorem 4.2, T (p O r
From the two statements above and given that O r (A) - O r (H), we have
O r
T109100918273645546101938881746760534673676155494337312519615651464136312621162624222018164945413733292521171393532292623221916131074336298577696153453737221141412108642242220181614121086428642T is time steps, p number of processors, N array size.

Figure

7: The maximum size N of prefix sums that can be done in time T using p processors.
for 2. 2
Theorem 5.1 (Optimality of Schedule H) Given p processors and a prefix problem of size
schedule A must have time
Proof: The number of final operations in any schedule computing prefix sums of size N is N \Gamma 1. Hence it
suffices to show that (1) any schedule A with more redundant operations than H cannot compute prefix of size
N in fewer steps than H, and (2) any schedule A with no more redundant operations than H cannot compute
prefix of size N in fewer steps than H.
Statement (1) is true because schedule H has maximum possible processor utilization in T - p steps.
Any schedule with more redundant operations than H in T steps can only produce fewer final results than H
regardless of how the redundant operations are arranged, assuming it fully utilizes p processors.
Statement (2) holds by Lemma 5.3. 2
Corollary 5.1 (Optimality of Extended Schedule H) Given p processors and a prefix problem of size
strict optimal time T p
Proof: Theorem 5.1 proves this statement for multiple of s(p). For not a multiple of s(p),
Theorem 4.2 states that schedule H achieves time T p 1)e with the amortization scheme.
The optimality of this time can be shown in similar way to the proof of Theorem 5.1. 2
Corollary 5.2 (Ratio) For any time-optimal schedule for prefix sums, the ratio of the final to the redundant
operations is (p a multiple of p.
Proof: Follows from Theorem 4.2 and Theorem 5.1. 2
Corollary 5.2 can be used in deriving simpler, more concise and more program-space efficient optimal
schedules.
To illustrate, in Figure 7, we show the maximum size N of prefix sums that can be computed in time
processors. Each number on the diagonal is equal to 1 s(p). Starting from
each number on the diagonal is p larger than the preceding number on the diagonal. This implies the
optimality-given one more step, p more final values can be computed. In each row for odd p starting from
increases by (p+1)=2 as T increases by one. In each row for even p starting from increases
by one, N increases in turn by b(p 1)=2e, so N increases on average by (p
6 The Pipelined Schedule
Schedule H is strict time-optimal for prefix sums of size N ? s(p). The schedule has p iterations in the inner
loop body. We wondered whether simpler (shorter) schedules with comparable performance exist. By Corollary
5.2, the ratio of final to redundant operations of an optimal schedule is (p
H achieves this ratio in every iteration of p steps. If a schedule can achieve this ratio in fewer steps than p,
then it has a smaller loop body than H and is still optimal. Applying the idea of software pipelining, we can
indeed derive a simpler, more concise and more program-space efficient schedule than H, which we call Pipelined
Schedule, or schedule P . Schedule P has in its loop body a single parallel step of (p final and (p \Gamma 1)=2
redundant operations yielding the same speedup as schedule H except for a small constant number of steps for
startup. For odd p we can achieve the ratio (p in a single parallel step, but for even p, "amortizing"
is needed to achieve the same ratio. In the remainder of this section, we give the complete Schedule P for an
odd number of processors p. The schedule P for an even number of processors p can be derived similarly.
Prefix sums of size N can be computed by the Pipelined Schedule with an odd number of processors p.
The first (p steps of the schedule set up for the actual iterations. The iteration
step computes both final values(using preceding final values, and previously computed redundant values), and
redundant values for future iterations. The array subscripts in an instantiated schedule P can be simplified at
compile time when p is given. Note that all operations in the loop body are in a single step and thus execute
in parallel.
Schedule 6.1 (The Pipelined Schedule(P))
do each step in parallel on p processors
for.In each iteration, p 1 final values of the array are computed by the first p 1 expressions, and (p
values are computed by the last (p In comparison with schedule H, schedule P does not have
to choose the proper epilogue at either compile or run time. Also, schedule P may be extended to handle a loop
with multiple statements more easily than schedule H.
1-3 are initial steps and 4 and above are iteration steps.

Figure

8: The Pipelined Schedule for 7.
5 and above are iteration steps.
1-4 are initial steps.

Figure

9: The Pipelined Schedule for
Example 6.1 Let us instantiate a schedule P with 7. The schedule is given below and is illustrated in

Figure

8. Each operation in a step is done in parallel on one of the processors.
step 3
do each step in parallel on p processors
Figure

9 illustrates the schedule derived for In general, the schedule obtained for for an even number
of processors p is an amortized schedule; for odd iterations it computes b(p+1)=2c final and d(p \Gamma 1)=2e redundant
operations, while for even iterations it computes d(p final and b(p \Gamma 1)=2c redundant operations.
Theorem 6.1 Prefix sums of size N can be computed by schedule P on p - 2 processors in time d2N=(p
Schedule P has speedup S utilization U
to infinity.
Proof: The proof is straightforward. 2
7 A Formulation of Strict Time-Optimal Schedules
We have derived strict time-optimal schedules for prefix sums of size N ? s(p). While schedules for N ? s(p)
are very useful in parallelizing loops containing loop-carried dependences, schedules for N - s(p) are equally
useful in designing high-speed circuits[13, 5].
In this section we present a new formulation of finding strict time-optimal schedules in terms of combinatorial
optimization that unifies in a single framework the optimal schedules for prefix problems for N - s(p)
s(p). Thus this new approach yields a general scheme for optimal schedules for prefix sums for all N and
p. We establish connections between structures of prefix computation and Pascal's Triangle, and thus formulate
the problem of finding strict time-optimal schedules as solving a system of inequalities, based on which an
algorithm for constructing optimal schedules can be derived. We first give an intuition of our solution. We
then characterize different costs of the final results in a full THR graph . Finally, we find the minimum cost for
producing N final results on p processors. In particular, this will form a foundation for the algorithm presented
in the next section, that builds the time-optimal schedules for prefix problem of size N on p processors where
in the next section.
is the strict time lower bound for N = s(p)+1, for any schedule A,
Given N - s(p) and p ? 1, finding optimal T p is equivalent to finding the maximum size N of prefix sums that
can be computed in T ! p steps. We shall find optimal schedules for N - s(p) following this line of thinking.
By Lemma 5.1, an optimal schedule in T steps can have no more than clusters. Thus
with processors, an optimal schedule must compute the maximum number of final values with no more
than clusters. The only way to do this is to make each redundant cluster produce, within
its maximum allowable height, as many redundant results as possible that will be used to compute the final
results. That is, we want to make each redundant cluster cover as many elements of array a as possible within
the maximum allowable height. The maximum allowable height of a redundant cluster is determined by the
relative position of the cluster among redundant clusters and non-redundantly scheduled elements in the graph,
such that if a redundant cluster exceeds its maximum allowable height, the critical path of the computation
will be lengthened. Neither should the heights of the redundant clusters be lowered, because it would make
the redundant clusters cover fewer original elements, i.e., produce fewer final results than they could otherwise.
For a computation tree of height k, the maximum number of original elements that can be covered by it is 2 k .
With enough processors, all redundant clusters in a schedule will grow to full binary dependence graphs. The
schedule is then saturated, i.e., no more final results can be computed with more processors in T steps.
The basic idea is to try and achieve the dual goals: maximum utilization of processors and minimum
number of redundant operations. However, for N - s(p), the Harmonic Schedule in Section 4 is no longer
applicable, because (intuitively) there are not enough prefix elements to make a single period(the minimum
number of prefix elements that make a single period is s(p)(the period length), plus a starting element). Hence,
given that no regular pattern of computation exists for N - s(p), the difficulty lies in determining how many
redundant operations should be used and how the redundant clusters are organized so that the dual goals can
be accomplished.
Definition 7.1 A node N 1 in a binary dependence graph is said to right depend on node N 2 iff N 1 uses as the
second operand the value produced by N 2 or a given value represented by N 2 . A node N 1 is said to right depend
a a a a a
a
a
a a a a a a
a
a
a

Figure

10: The right-dependences of a computation tree.
on node N k+1 with a distance of k iff there exist distinct nodes such that N i right depends on
k. The concept of left dependence and left dependence with a distance of k are defined
similarly.
Notation 7.1 [Cost Vector] Let be the top fringe operations of a computation graph of height
cost vector where d j is the right-dependence distance from
operation to a[j] for m. The value d j in a cost vector is equal to the number of operations that the
jth partial sum of this graph right depends on. Thus the sum of d j 's, 0 - j - m, is equal to the number of
operations in the whole graph.
As shown in Figure 10, the cost vectors for the graphs (from left to right) is (0;
respectively, and the total numbers of operations for the graphs are equal to (0
respectively. We shall see soon that a dependence
graph can be constructed once a cost vector is determined. Theorem 7.1 and its corollary characterize different
costs of final values in a full THR graph and show relevant properties, which will help us minimize the total
cost when problem size and number of processors are given.
Theorem 7.1 In a full graph of height k, the number of nodes on the top fringe that have a right-dependence
distance of j,
Proof: We prove this theorem by induction on the height k of a full graph.
Base. For graph height there is only one node on the top fringe and it is of right-dependence distance
We show one more case to facilitate understanding. For graph height are
two nodes on the top fringe and they are of right-dependence distance 0 and 1 respectively. As illustrated in

Figure

11, the left leaf of the graph of height 1 is also the node on the top fringe having a right-dependence
distance of 0, and the root is the node on the top fringe having a right-dependence distance of 1. Thus we have
Induction assumption. We assume the theorem holds for
We now show that the theorem holds 1. The intuition is shown in Figure 11: the number of nodes
having a right-dependence distance of j on the top fringe of a full graph of height k+1 is the sum of the number
of height k of height k
of height 0
of height 1
Full graph
Full graph
Full graph
Full graph of height k+1
Full graph

Figure

11: Number of nodes on the top fringe of the graph of height k with a right-dependence distance
of
of top-fringe operation nodes of the first subgraph of height k having right-dependence distance of j and the
number of top-fringe operation nodes of the second subgraph of height k having right-dependence of distance of
since there is a new layer of operation nodes on top of the second subgraph of height k. By the preceding
argument and the induction assumption, we have
:Corollary 7.1 1. The total number of operation nodes on the top fringe of a full graph of height k, k - 0,
is
2. Given n full graphs having height 0 through the sum of the numbers of operation nodes on the top
fringes that have a right-dependence distance of j,
3. The total number of operation nodes on the top fringes of n full graphs of height from 0 through
equal to 2 n \Gamma 1.
Proof: Claim 1 is true because the total number of operations on the top fringe of a full graph of height k is
equal to the sum of the numbers of operations on that top fringe having a right-dependence distance of j, i.e.,
the sum of g kj 's, k. By Theorem 7.1,
. Note that the truth of claim 1 can also be found by
observing the number of array elements covered by a full graph.
Proof of claim 2.
(by requirement of the claim)
(by Theorem 7:1)
43 44
G
G
G
G
G
1*
3*
4*

Figure

12: The correspondence between Theorem 6.1 with Corollary 6.1 and the Pascal's triangle.
3 follows from Claim 1 by summing up G k   ,
Figure

12 shows the correspondence between Theorem 7.1 and its corollary, and the Pascal's triangle.
Corollary 7.2 [Cost vector of a full THR graph] Let ~ 1 i be an i-dimensional vector, all elements of which
are equal to 1, and let dim(~c) be the dimension of vector ~c. The cost vector ~c k of a full graph of height k can
be determined recursively as follows.
Proof: The proof is straightforward. 2
In

Figure

10, the cost vector of the full graph of height 3 is given by the following recursive sequence:
In what follows, we try to find the minimum cost for the dependence graph for prefix of size N on p
processors. Theorem 7.2 gives a system of inequalities for determining the minimum time steps required to
compute prefix problems using p processors.
Theorem 7.2 A lower bound T on the time required to compute a prefix problem of size N -
processors can be determined using the following system of inequalities.
. The number of the top-fringe operations (i.e., number of
final results) that have a right-dependence distance of k is equal to l; and k is the maximum right-dependence
distance used by the schedule.
Proof: By Theorem 7.1,
\Delta is the number of operations (i.e., number of final results) on the top fringe of
the graph having a right-dependence distance of i(which can be seen as a cost of i) in a full graph of height T .
is the number of final operations having right-dependence distance i - k in a full graph
of height T .
Our goal is to choose to use in our schedule final operations with the minimum sum of cost (i.e., right-
dependence distances), and simultaneously to maximally utilize p processors.
Solving the first inequality for T and k means finding the minimum graph height T and the minimum
right-dependence distance k such that the given prefix can be computed in time T with final operations of
right-dependence distance i - k. Since the number of processors p is not involved in the first inequality, there
may be multiple pairs of solutions (T and k), i.e., each pair of T and k gives the minimum number of operations
to be used to compute the prefix with respect to a particular number of processors. Given the number
of processors p, the unique pair of T and k can be determined for computing results of the given prefix
with minimum number of operations.
The second inequality is used to choose T and k with respect to p, i.e., the pair of T and k we are to choose
has to enable us to construct our schedules with p processors maximally utilized. In the second inequality,
equals the number of operations required by T redundant clusters having height 0 through
means that there are sufficiently many
processor slots in T steps on p processors to compute those operations required by the clusters
that cover N prefix elements. pT \Gamma
means that T is no more than the minimum number
of steps that produce final results on p processors. Thus the second inequality states that T is the
lower bound on time that gives sufficiently many processor slots to compute the minimum number of operations
required to produce prefix results on p processors. 2
The solutions for the inequalities implies the widths of schedules that ensure time-optimality, because our
goal was to achieve minimum cost (number of operations) and maximum resource utilization simultaneously.
The "width" of a schedule for prefix computation in this paper is defined to be the maximum number of
operations that can be computed in a single step in that schedule. In many cases, the width of the schedule
must be larger than the number of resources p in order to ensure the existence of a legal schedule for the given
resources, as will be shown in Example 8.1. Restricting the width of a schedule to being equal to the number
of processors p could in no way lead to the findings of strict time-optimal schedules.
For schedules where N - s(p) Theorem 7.2 suggest that we construct the schedules starting from a full
THR graph for 2 T (the minimum number no smaller than N ) by cutting most expensive "columns" from the
graph.
For optimization produces precisely the Harmonic Schedule, which has been proven
strictly time-optimal. Example 8.3 will illustrate the derivation.
For N - s(p), to prove that this optimization in general constructs strict time-optimal schedules, we need
to prove that (1) legal schedules can be devised using this optimization for all N , p and N - s(p), and (2) these
schedules are strictly time-optimal.
We will show in the next section, for a class of N and p where N - s(p), that this optimization enables us
to derive legal schedules. The optimality of these schedules follows from Theorem 7.2 subject to the condition
as mentioned above that these schedules are derived from a full THR graph by cutting the most expensive
"columns".
Devising Schedules in N - s(p)
Based on Theorem 7.2, we construct our schedule for computing a prefix of N elements on p processors in
using Algorithm 8.1 given below.
Algorithm 8.1
Input: a prefix computation of N elements and number of processors p.
Output: a dependence graph for making a parallel schedule that performs the prefix computation.
construct schedule for ppc(N , p) f
1. find min time min p(N , p);
2. find min cost vector(T , k, l);
3. construct graph(~c T , M TN );
gWe describe the three procedures of Algorithm 8.1 in the remainder of this section, and complete this section
with examples. Once we have built a dependence graph, the parallel schedule for the given prefix can be
completed by allocating the operations in the graph to the p processors. We shall discuss processor allocation
at the end of this section.
Procedure 8.1 [find min time]
Input: A prefix of size N and number of processors p.
Output: Procedure "find min time min p(N , p)" solves the inequalities in Theorem 7.2 for the minimum time
T , the minimum number of processors p 0 required by T , the maximum right-dependence distance k of our
resulting schedule, and the number of final results l having right-dependence distance k. If the given p is greater
than the derived p 0 , the procedure completes and the resulting schedule will be constructed using
since the remaining processors would be of no use in achieving the minimum time. If the given p is
smaller than the derived p 0 , Procedure "find min time for p(N , p)" continues to search for the minimum time
for N and p.
This procedure can be further sped up by starting with a better T and k than the one for the outer loops
in both procedures. This optimization is omitted in favor of readability.
find min time(N , p) f
find min time min p(N , p);
find min time min p(N , p) f
1.for
2. for
3.
4. if (
5. ffind m such that 2 m -
6. for (p
7. if (0 - pT \Gamma
8. if (p -
else return ; g g g
find min time for p(N , p) f
1. for
2. for
3. if (
and
(0
return (T; k; l);g gProcedure 8.2 [construct cost vector (Cutting Scheme)] This procedure takes as input the solutions
and l from Procedure 8.1, and generates as output a cost vector, from which a computation graph for
evaluation of the given prefix will be constructed. The dimension of the resulting vector is equal to the size N
of the given prefix. The cost vector of a full graph is derived using the technique given in Corollary 7.2.
construct cost vector(T , k, l) f
1. derive cost vector ~c T for full THR graph of height T ;
2. remove from ~c T elements greater than k;
3. remove from ~c T (
l of them) equal to k as follows
(where "group" means a group of consecutive elements equal to k in ~c T
3.1 point to the right-most group and let
3.2 while (i ?
remove the last element in the group pointed to;
shift the pointer to the group on the left
(point to the right-most group after the left-most group
being operated on, i.e., the pointer moves in a clockwise
circular fashion);
4. return ( resulting cost vector ~c T );
gNote that there are other schemes for choosing from ~c i , those l elements equal to k. We chose to use
a simple scheme as stated in step 3 to facilitate understanding. Other cutting schemes are discussed in [20].
Procedure 8.3 [construct graph] This procedure establishes the dependence arcs between the nodes of the
dependence graph, which are placed in a matrix, M TN , to be described next. The matrix encodes a dependence
graph that evaluates the given prefix problem of size N on p processors.
We store the operations of a graph in a T \Theta N sparse matrix M TN , called the construction matrix of
the graph, organized using its cost vector ~c follows. The elements of the given prefix
problem are stored in the 0th row of M TN . The d j operations that the jth partial sum of the graph right
depends on, are stored in the jth column, with the operation with right-dependence distance i placed in the
ith Four fields are associated with an operation o[i; j] in M TN , left source, right source,
right dep distance, and number of depended. Fields o[i; j].left source and o[i; j].right source point to the left
and right source nodes respectively. Field o[i; j].right dep distance stores the right-dependence distance of node
Field o[i; j].number of depended is the number of nodes that node o[i; j] depends on, including o[i; j]
itself.
construct
for
1.
2. o[i; j].right dep distance = 1+ (o[i; j].right source).right dep distance;
3. column of left source=j \Gamma (1+(o[i; j].right source).number of depended);
4. row of left source = d column of left source \Gamma (d
5. o[i; j].left source = o[row of left source; column of left source];
6. j].number depended=
source).number of depended +(o[i; j].right source).number of depended;
gExample 8.1 Find the minimum time and an optimal schedule for a prefix of size
processors.
Procedure "find min time min p" determines that 22 results can be computed on
processors in steps (i.e., in a dependence graph of height results having right-dependence
distance
Procedure "construct cost vector" generates a cost vector
With the cost vector, Procedure "construct graph" constructed the schedule as shown in Figure 13. By Theorem
7.2 and the fact that a valid schedule is constructed using the cost vector, the schedule in Figure 13 achieves
the strict optimal time for a prefix of size 23 on 10 processors.Example 8.2 Find the minimum time and an optimal schedule for a prefix of size
processors. This example shows that our procedure produces a full tree-height-reduction schedule for N a
power of 2, given enough processors.
Procedure "find min time min p" determines that results can be computed on processors
in steps (i.e., in a dependence graph of height having right-dependence distance
We have obtained a full THR schedule of height
Procedure "construct cost vector" generates a cost vector ~c
Procedure "construct graph" constructs the schedule as shown in Figure 14. It is well known that this is the
strict time-optimal schedule for prefix of 2 processors.
Cost vector:32 22

Figure

13: An optimal schedule for a prefix of input size 23 on p processors determined by our
procedure.
Cost vector:

Figure

14: Our procedure generates a full tree-height reduction schedule for Find the minimum time and an optimal schedule for a prefix of size
processors. This example illustrates that our procedure produces precisely a Harmonic Schedule when
Procedure "find min time min p" decides that the minimum time required to compute 28 prefix
sums is 5 steps and the minimum number of processors to accomplish that is p
"find min time for p" therefore continues and finds that the minimum time required to compute 28
prefix sums with processors is 7 steps. That is, 28 results can be computed on processors
in steps (i.e., in a dependence graph of height
results having right-dependence
distance 2.
Procedure "construct cost vector" generates a cost vector:
"construct graph" creates precisely
the same computation graph as that of the Harmonic Schedule as the one shown in Figure 2, which has
been shown to achieve the strict optimal time in Section 5. 2
Algorithm 8.1 constructs a dependence graph for computing the prefix of N elements on p processors. Now,
whether the dependence graph would make a valid schedule depends solely on the existence of a legal processor
allocation onto the computation graph for arbitrary N and p in N - s(p). It turns out that it is very difficult to
prove this existence, since one would need to characterize certain properties of all the dependence graphs for N
and p in N - s(p). We were able to characterize a class of these dependence graphs and to show the existence
of legal processor allocations for them, i.e., the existence of a class of strict time-optimal schedules (because by
Theorem 7.2, the time implied by the dependence graphs is a lower bound).
By Theorem 7.1, there are
columns each with i operation nodes for i - m. We now show that, for
allocations exist, i.e., the strict time-optimal schedules for
the N and p above are found. The following lemma says that the number of processor slots (i.e. the number of
operation nodes in the dependence graph) is always a multiple of m when N
Lemma 8.1 If
Proof: Observe that i
. Thus
\Delta is an integer. 2
Theorem 8.1 If
prefixes of N elements can be computed in m steps with p processors,
. That is, for this class of N and p, m is the strict optimal time (steps) for computing
prefix of N elements on p processors.
Proof: Consider the set of all columns with exactly i 1's. The number of 1's in each row of this set is equal
to
. If we consider the set of all columns with - k 1's, then the number of 1's in each row of this set
(which corresponds to the number of operation nodes at each time step) is equal to
. Now the total
number of processor slots required to compute the
prefixes is
by Lemma 8.1. Thus the prefixes of N elements can be computed in m steps with p processors, where
Since these dependence graphs for N and p characterized in this theorem can also be constructed using
Algorithm 8.1, by Theorem 7.2 (on which Algorithm 8.1 is based), m is the strict optimal time for prefix of size
N on p processors. 2
The dependence graphs for the class of N and p in Theorem 8.1 have the nice structure that there are
exactly p operation nodes at each time step, and thus p is the minimum number of processors required to carry
out the computation in m steps. For general values of N and p in N - s(p), the dependence graphs seem much
less apparent and we do not have as clean a characterization for them as for the class of N and p in Theorem
8.1. Thus the existence of legal processor allocations for the dependence graphs for N and p in N - s(p) that
are not considered in Theorem 8.1 remains open.
The strict time-optimality in Theorem 8.1 is subject to the optimization condition implied by Theorem 7.2
that our schedules for N - s(p) are constructed from a full THR graph by cutting off the most "expensive"
columns. However, we conjecture that our optimization constructs strictly timp-optimal schedules for all N
and p in N - s(p) subject to no optimization condition. That has been supported by these facts: (1)
Algorithm 8.1 constructs precisely the Harmonic Schedules when which has been proven strictly
time-optimal, and (2) for all prefix problems we did where N - s(p)+1, we have constructed strict time-optimal
schedules using algorithm 8.1.
9 Conclusion
We have presented strictly time-optimal schedules for parallel prefix computation with resource constraints.
We have divided the parallel schedules for prefix computation of size N in two areas according to number of
processors p: schedules in N ? s(p) and in N - s(p)+1 2 . While prefix schedules for N ? s(p) are very useful in
parallelizing loops containing loop-carried dependences, schedules for N - s(p) are equally useful in designing
high-speed circuits[13, 5].
For prefix of N elements on p processors (p independent of N ) in N ? s(p)(= p(p + 1)=2), we derived
Harmonic Schedules and showed that the Harmonic Schedules achieve the strict optimal time (steps), d2(N \Gamma
Harmonic Schedules for prefix computation where can also be constructed using Algorithm 8.1.
1)e. We also derived Pipelined Schedules, optimal schedules with
time, which take a constant overhead of d(p \Gamma 1)=2e time steps more than the strict optimal time. Both the
Harmonic Schedules and the Pipelined Schedules are expressed in program templates that are parameterized
for the number of processors p, i.e., they can be generated in negligible time at compile time when p is known.
Both the Harmonic Schedules and the Pipelined Schedules exhibit simple and nice patterns of loop structure
which makes it easy to implement. A main advantage of the Pipelined Schedules over the Harmonic Schedules
is that the former has a single parallel step in the loop body (i.e., small program size).
For prefix of N elements on p processors (p independent of N ) in N - s(p), the Harmonic Schedules are not
time-optimal, because N is not large enough to accommodate any repeating pattern as in N ? s(p). For these
cases, we established an optimization method (Theorem 7.2) for determining key parameters of time-optimal
schedules, based on connections (Theorem 7.1 and its Corallaries) between dependence graphs of parallel prefix
and Pascal's triangle we found. Using the derived parameters, we devised Algorithm 8.1 to construct schedules.
For a restricted class of cases in terms of N and p, we have proved that the constructed schedules are strictly
time-optimal, subject to the optimization condition discussed in the end of Section 7. We also give strong
empirical evidence for our conjecture that Algorithm 8.1 constructs strict time-optimal schedules for all case
In fact, our optimization methods can also be applied to derive strict time-optimal schedules
shown in Example 8.3. The existence of legal schedules for other N and p where N - s(p)
under this optimization and the strict time-optimality for all schedules for N and p where N - s(p) remain
open.
Except for this open end, we have concluded the search for strict optimal time and schedules to achieve the
strict optimal time for parallel prefix computation with resource constraints under CREW PRAM model.

Acknowledgements

The authors wish to thank the anonymous reviewers for their valuable comments on an earlier draft of this
paper.



--R

"Computational Fluid Dynamics on Parallel Processors"
"Compilers-Principles, Techniques, and Tools"
Chapter 4
"Automatic program parallelization"
"A heuristic for suffix solutions"
"Faster Optimal Parallel Prefix Sums and List Ranking"
"Parallel prefix computation with few processors,"
Chapter
"New bounds for parallel prefix circuits"
"The Power of Parallel Prefix"
"The Structure of Computers and Computations"
"A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations"
"Parallel Prefix Computation"
Parallel Computing using the prefix problem
Introduction to Parallel Algorithms and Architectures: Arrays-Trees-Hypercubes
"Parallelism exposure and exploitation in programs"
"Optimal Schedules for Parallel Prefix Computation with Bounded Resources"
"On the algorithmic complexity of discrete functions"
"Depth-size Trade-offs for Parallel Prefix Computation"
"Parallelization of programs containing loop-carried dependences with resource constraints"
--TR

--CTR
Sukanya Suranauwarat , Hideo Taniguchi, The design, implementation and initial evaluation of an advanced knowledge-based process scheduler, ACM SIGOPS Operating Systems Review, v.35 n.4, p.61-81, October 2001
Yen-Chun Lin , Chao-Cheng Shih, A New Class of Depth-Size Optimal Parallel Prefix Circuits, The Journal of Supercomputing, v.14 n.1, p.39-52, July 1999
Armita Peymandoust , Giovanni De Micheli, Symbolic algebra and timing driven data-flow synthesis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
Yen-Chun Lin , Yao-Hsien Hsu , Chun-Keng Liu, Constructing H4, a Fast Depth-Size Optimal Parallel Prefix Circuit, The Journal of Supercomputing, v.24 n.3, p.279-304, March
Yen-Chun Lin , Jian-Nan Chen, Z4: a new depth-size optimal parallel prefix circuit with small depth, Neural, Parallel & Scientific Computations, v.11 n.3, p.221-236, September
Yen-Chun Lin , Jun-Wei Hsiao, A new approach to constructing optimal parallel prefix circuits with small depth, Journal of Parallel and Distributed Computing, v.64 n.1, p.97-107, January 2004
Jin Hwan Park , H. K. Dai, Reconfigurable hardware solution to parallel prefix computation, The Journal of Supercomputing, v.43 n.1, p.43-58, January   2008
Yen-Chun Lin , Chin-Yu Su, Faster optimal parallel prefix circuits: new algorithmic construction, Journal of Parallel and Distributed Computing, v.65 n.12, p.1585-1595, December 2005
pascal's triangle;loop-carried dependences;loop parallelization;combinatorial optimization;parallel prefix computation;scan operator resource-constrained parallel algorithms;tree-height reduction;strict time-optimal schedules;associative operations