Prefix 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. 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), [2(N-1)/(p+1)]. 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 N/spl les/p(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 N/spl les/p(p+1)/2.

Many large-scale scientific and engineering computations, e.g., some of the Grand Challenge problems, spend a major portion of execution time in their core loops computing band linear recurrences (BLRs). Conventional compiler parallelization techniques cannot generate scalable parallel code for this type of computation because they respect loop-carried dependences (LCDs) in programs, and there is a limited amount of parallelism in a BLR with respect to LCDs. For many applications, using library routines to replace the core BLR requires the separation of BLR from its dependent computation, which usually incurs significant overhead. In this paper, we present a new scalable algorithm called the Regular Schedule, for parallel evaluation of BLRs. We describe our implementation of the Regular Schedule and discuss how to obtain maximum memory throughput in implementing the schedule on vector supercomputers. We also illustrate our approach, based on our Regular Schedule, to parallelizing programs containing BLR and other kinds of code. Significant improvements in CPU performance for a range of programs containing BLR implemented using the Regular Schedule in C over the same programs implemented using highly optimized coded-in-assembly BLAS routines [11] are demonstrated on Convex C240. Our approach can be used both at the user level in parallel programming code containing BLRs, and in compiler parallelization of such programs combined with recurrence recognition techniques for vector supercomputers.

We present a new technique for the high-level synthesis of scalable^1 MCM-based architectures implementing infinite-impulse response(IIR) filters. Our technique is based on the regular schedules, a class of parallel schedules for computing mth-order IIR filters. The simplicity of the regular schedules facilitates characterization of their inter-processor communications, which is generally difficult to express for parallel algorithms. The characterization of inter-processor communications of the regular schedules enables us to generate instruction-level behavior of the design that can be easily mapped onto MCM-based architectures. We illustrate this mapping of the regular schedules onto an MCM-based architecture by designing a special-purpose processor for the fifth-order elliptic wave filter. Our design yields a scalable performance measured in the filter's sample rate, which is not known to have been achieved by previously published designs. This work differs significantly from "traditional" high-level synthesis techniques in its emphasis on synthesizing scalable, high-performance multichip designs.

An m-th order linear recurrence system of N equations computes x i = c i + P j=i0m i01 a ij x j for 1 i N . Linear recurrences have a role of central importance in computer design, numerical analysis, program analysis, digital signal processing and many non-numerical algorithms. However, programs containing band linear recurrences are difficult to significantly parallelize due to loop-carried dependences. We present a new method for systematically approaching the optimal parallel schedules for computing mth-order linear recurrences with a fixed number of processors p independent of problem size N . Using our method, we first derive two kinds of parallel schedules, called the pipelined schedules and the exact schedules, for parallel evaluation of band linear recurrences. Our schedules have better execution times than the fastest previously published parallel schedules for p ? m 1. In particular, the exact schedules achieve an execution time of (2m 2 + 3m)N p + (m(m+1)(2m+1)) 2...

Given x 1 ; . . . ; xN , parallel prefix computes x 1 ffi x 2 ffi . . . ffi x k , for 1 k N , with associative operation ffi. We show optimal schedules for parallel prefix computation with a fixed number of resources p 2 for a prefix of size N p(p + 1)=2 . The time of the optimal schedules with p resources is d2N=(p + 1)e for N p(p + 1)=2, which we prove to be the strict lower bound(i.e., which is what can be achieved maximally). We then present a pipelined form of optimal schedules with d2N=(p + 1)e + d(p 0 1)=2e 0 1 time, which takes a constant overhead of d(p 0 1)=2e time more than the optimal schedules. Parallel prefix is an important common operation in many algorithms including the evaluation of polynomials, general Hornor expressions, carry look-ahead circuits and ranking and packing problems. A most important application of parallel prefix is loop parallelizing transformation. 1 Introduction Given x 1 ; . . . ; xN , parallel prefix computes x 1 ffi x 2 ffi . . . ffi x...