Consideration is given to the layout of bounded fan-in and fan-out prefix computation graphs in VLSI, and it is shown that the area requirements of such graphs exhibit this interesting property. A small constant factor reduction in time of computation from 2 log eta to log eta increases the area required to embed an eta node prefix computation graph significantly from O( eta log eta ) to Omega ( eta /sup 2/). The area requirements are also given. This behavior is an example of an extreme area-time tradeoff in VLSI. Since prefix computation also models the carry computation in a carry look-ahead adder, the same behavior is observed in the area requirements of a near-minimum computation time carry look-ahead adder. The authors also present circuits which meet the derived lower bounds for all values of T between log eta and 2 log eta .>

As part of the Horizon project, a set of application programs is being written and their performance is being evaluated. Two of these applications, the fast Fourier transform and sparse matrix computations, are described. For both problems, efficient implementations are developed that take advantage of Horizon's unique features, including fined-grained synchronization, multiple instruction streams, and a horizontal instruction set. The results indicate that Horizon will offer very high performance, sometimes in excess of a sustained rate of one floating point operation per tick.>

Computations with embedded Fast Fourier Transforms (FFT) have many important applications which include high-speed polynomial multiplication. In this paper, we discuss the time-space tradeoff behavior of such computations. In particular, we examine the way compositions of FFT graphs with one another and with other graphs affect this behavior. We model a computation by the well-known pebble game on directed acyclic graphs. We are able to show that the way in which connections are made between subgraphs of a graph exerts a nontrivial effect on the time-space tradeoff behavior. The graphs studied correspond to the problem of finding the maximum of a vector produced by the FFT algorithm, and to problems containing back-to-back FFTs such as polynomial multiplication. For the first problem, we show that different ways of expressing the FFT algorithm lead to very different time-space tradeoff behaviors. Our results for a polynomial multiplication algorithm based on back-to-back FFTs allow us to conclude that it has the connection pattern with the best possible time-space tradeoff behavior.

The author explores modifications of a mesh-connected parallel computer for the purpose of increasing the efficiency of executing important application programs. These modifications are made by adding one or more global mesh structures to the processing array. The author shows how his modifications allow asymptotic improvements in the efficiency of executing computations having low to medium interprocessor communication requirements (e.g. tree computations, prefix computations, or finding the connected components of a graph). For computations with high interprocessor communication requirements such as sorting, the author shows that they offer no speedup. He also compares the modified mesh-connected parallel computer to other similar organization including the pyramid, the X-tree, and the mesh-of-trees.>

In this paper, we study area-time tradeoffs in VLSI for prefix computation using graph representations of this problem. Since the problem is intimately related to binary addition, the results we obtain lead to the design of area-time efficient VLSI adders. This is a major goal of our work: to design very low latency addition circuitry that is also area efficient. To this end, we present a new graph representation for prefix computation that leads to the design of a fast, area-efficient binary adder. The new graph is a combination of previously known graph representations for prefix computation, and its area is close to known lower bounds on the VLSI area of parallel prefix graphs. Using it, we are able to design VLSI adders having area A = 0(n log n) whose delay time is the lowest possible value, i. e. the fastest possible area-efficient VLSI adder.

This paper examines the performance of back-to-back applications of a fast Fourier transform algorithm with respect to computational time and space. Using a well-known pebble game as an analysis technique, a lower bound is derived on the product of time and space, which is of the form T · S = Ω(n2 log2n) for an n-input back-to-back FFT. The implications of this lower bound on applications of a back-to-back FFT circuit, such as polynomial multiplication and permutation graphs, are also discussed.

The pebble game on directed acyclic graphs can be used to model the space-time tradeoff behavior of a straight-line algorithm (SLA). In this game, the maximum number of pebbles used at any one time corresponds to the number of temporary registers available and is called space. The number of moves made to reach the outputs of the graph, or the time, corresponds to the number of operations required by the SLA. In this paper, it is shown that there exist infinite families of constructible graphs on N nodes which possess an extreme time-space tradeoff. For a particular set of graphs, if space is restricted to fall in the range of Θ(log N) to Θ((@@@@N/log N)), then the pebbling time necessary is superpolynomial in N. This result is obtained by deriving a lower bound on time when extra space is restricted, and then diagonalizing over the amount of this space. An extension of this argument shows that the minimum space requirement for such constructible graph families can grow as any slowly increasing function of N.