The Micro-Grain Array Processor-2 (MGAP-2) is a two-dimensional SIMD array of 49152 fine-grain processors designed primarily for high-performance signal and image processing. Each processor can compute two arbitrary three-input Boolean functions, contains local RAM, and has additional logic for interprocessor communication. The MGAP-2 differs from existing fine-grain arrays in that it has a high degree of integration while incorporating processor level interconnect control. Each processor can independently select its communication direction. This allows a programmer to map algorithms onto the array in a more efficient manner than if the processors communicated in the standard SIMD fashion. Also, the MGAP-2's processor level interconnect allows groups of processors to be clustered into larger computational units, making the basic computational units as powerful as they need to be for a given problem.

This paper presents a technique used to do po wer analysis of a real p rocessor at the architectural lev el. The target processor in tegrates a 16-bit DSP an d a 32-bit RISC on a single c hip. O ur po wer estimator pro vides po wer consumption data of the architecture based on the instruction/data flo w stream We demonstrat e the accuracy of the estimator by com paring the po wer valu es it p roduces against measurem en tsm adeby a gate level po wer sim ulator for th e same benc hmark set. Our estimation approac h has been shown to pro vide v ery efficient accurate pow er an alysis at the architectural level.

The Micro-Grain Array Processor (MGAP) is a family of massively parallel SIMD arrays of fine grain processing elements powerful enough to perform complex signal and image processing algorithms in real time. The MGAP was also designed to be compact enough to conveniently fit as an add-on board to a standard workstation at a fraction of the development cost of other comparable parallel machines. In this paper we update the status of the MGAP-2 which became operational in October 1996, and present a comparison of the MGAP-1 and the MGAP-2. We also give performance comparisons of the two designs through three popular image/video compression algorithms: the Discrete Cosine Transform, Motion Estimation, and Fractal Compression.

This paper presents a CMOS circuit methodology for designing pipeline stages which are both faster than comparable domino based stages and that also have increased functional capability. The basic gates offer considerably faster switching speeds than domino, while also eliminating the feedback and buffering circuitry required by domino gates for reliable operation. In addition to faster gates, the dual-rail nature of the proposed circuit technique provides greater logic functionality per gate. This results in a reduction of the number of gate delays required for implementing complex functions of high fan-in. Several benchmark circuits were simulated in a 0.5 /spl mu/m, 3.3 V CMOS process. The results show that the proposed circuit technique provides significant speed improvement over domino.

The paper describes a near neighbor mesh connected SIMD array processor with mixed autonomy local interconnect. The processing element is based on the MGAP processing element. It is shown that for low level image processing tasks, the availability of a local interconnect which can operate autonomously or under global control improves performance significantly.

In this paper, we note and analyze a key trade-off: as the complexity of caches increases (higher set-associativity, larger block size, and larger overall size), the power consumed by a cache access increases.However, because the hit rate also increases, the number of main memory accesses decreases and thus the power consumed by a memory access decreases.Recent papers which consider the power consumption of caches tend to ignore hit rates.This is unfortunate, because it is undesirable to have energy-efficient caches which are also very slow.Hit rates also play a key role in truly evaluating the energy efficiency of a cache, because low hit rates lead to more frequent main memory accesses which consume more power than cache accesses.

The energy consumption of a system depends upon the hardware rutd software component of a system.Since it is the software which drives the hardware in most systems.decisions taken during software design has significant impact on the energy consumption of the processor.The paper focuses on decreasing energy consumption of o processor using software techniques.A novel compiler technique is proposed which Educes energy consumption by proper register labeling during the compilation phase.The idea behind this technique is to reduce the energy of the processor by reducing the energy of the instruction register (also the instruction data bus) and the register file decoder by encoding the register labels such that the sum of the switching costs between all the register labels in the tmnsition graph is minimized.There is no hardware pen&y since this is purely a compiler optimization.Results on benchmarks show that the energy consumption of the DLX processor can be.reduced by 9.82% (maximum) and 4.25% (avenge) (as measured by DLX energy simulator).In addition seveml compiler techniques such os loop unrolling, software pipelining, recursion elimination and of effects of different algorithms on power and energy consumption are studied.This evaluation methodology is usefid for computer architects to evaluate energy improvements of their hardware, compiler writers to evaluate energy of the compiled code nnd program writers to evaluate energy of data structures and algodhltls.v---e.?_ .

A routing algorithm that generates a Steiner route for a set of sinks with near optimal Elmore delay to the critical sink is presented. The algorithm outperforms the best existing alternative for Elmore-delay-based critical sink routing. With no critical sinks present, the algorithm produces routes comparable to the best previously existing Steiner router. Since performance-oriented layout generators employ iterative techniques that require a large number of calls to the routing algorithm for layout evaluation, a fast algorithm for routing is desirable. The algorithm presented here has a fast (O(n/sup 2/), where n is the number of points) and practical implementation using simple data structures and techniques.

Scientific visualization and virtual reality have pushed three-dimensional graphics engines to their limits for updating scenes in real-time. One bottleneck of graphic systems is the transformation of an object's vertices into normalized space based on an evaluated transformation stack. This operation as often done in floating point, requiring a fast floating point multiply-accumulate unit. This paper presents architectural optimizations to a graphics pipeline floating point multiply-accumulate unit by using block floating point and parallelism to bypass or merge trivial operations in the matrix multiplications.

Fractal image compression has many features that makes it a powerful compression scheme, but it has been mainly restricted to archival storage due to its time consuming encoding algorithm. In this paper, we take a known quad-tree fractal encoding algorithm and design an ASIC parallel image processing array that can encode reasonably sized gray-scale images in real-time. In designing this architecture, we include novel optimizations that result in speed improvements at the algorithmic, architectural, and circuit levels.

This paper presents an architecture which is equally efficient at computing both the discrete wavelet transform (the DWT) and the inverse discrete wavelet transform (the IDWT). Given the seemingly fundamental difference between the structure of a DWT filter bank and the structure of an IDWT filter bank, it is somewhat surprising that such an architecture can be derived. Our architecture allows the building of a single chip which can efficiently compute both transforms. Tandem use of the architecture (/spl rarr/DWT/spl rarr/IDWT/spl rarr/) is simplified by the fact that the j'th octave is generated by the architecture when it is in DWT mode at the sane rate at which it is consumed by the architecture when it is in IDWT mode.

We illustrate a new method to characterize the energy dissipation of circuits by collapsing closely related input transition vectors and energy patterns into capacitive coecients.Energy characterization needs to be done only once for each module (ALU, multiplier etc.,) in order to build a library of these capacitive coecients.A direct high-level energy simulator or pro ler can then use the library of pre-characterized modules and a sequence of input vectors to compute the total energy dissipation.A heuristic algorithm which performs energy clustering under objective constraints has been devised.The worst case running time of this algorithm is O(m 3 n), where m is the number of simulation points and n is the number of inputs of the circuit.The designer can experiment with the criterion function by setting the appropriate relative error norms to control the `goodness' of the clustering algorithm and the sampling error and con dence level to maintain the suciency of representation of each cluster.Experiments on circuits show a signi cant reduction of the energy table size under a specied criterion function, cluster sampling error and con dence level.

The contribution of interconnect delay to the stage delay of a circuit is increasing with scaling of the minimum feature size. At larger feature size the interconnect delay contribution was small and the driver resistance was very large compared to wire resistance. Consequently, a simple lumped model was sufficient for evaluating and optimizing circuit delay. However, with sub-micron processes, the contribution of interconnect delay dominates the stage delay and the wire resistance becomes noticeable, making the interconnect delay dependent on the routing topology. Hence it is becoming necessary to use a more accurate model for estimating and optimizing interconnect delay. This paper surveys the recent advancements in techniques for generating on-chip interconnect topology for optimizing circuit performance.

Gray code addressing is one of the techniques previously proposed to reduce switching activity on high capacitance address bus lines. However in order to convert a system to gray address encoding there are several issues a designer needs to consider. This paper analyzes two issues which include gray code encodings for counter increments other than one and tradeoffs in power consumption incurred due to code conversions (binary to gray, gray to binary) when considering address increments and adders. Results are shown for different encodings and different configurations.

In this paper a dynamic programming algorithm for simultaneous speech segmentation and phoneme recognition is presented. Given a sequence of samples of an unknown speech pattern and a library of phonemes, this algorithm finds the best phonological match and, with a backtracking step, identifies the phoneme boundaries. This approach is different from a traditional two step process whereby first the phoneme boundaries are determined locally and then speech recognition is performed. Its advantage over the two step process is that incorrect phoneme boundaries due to slurring or sudden changes in the speech are reduced. Unlike other dynamic programming algorithms, it does not lend itself to systolic wavefront processing, hence an alternate parallel algorithm is presented.

This paper describes a method to model the software component of energy dissipation from an architectural description of an embedded system. An embedded system is characterized by a dedicated processor (a DSP processor or an "off the shelf" microprocessor) and the application specific software that runs on it. The hardware model of the system consists of several interacting modules (e.g. ALU, register file, controller etc.). A black box model of a cell from each module is built which consists of a table of switching capacitances (from IRSIM-CAP) for each combination of previous to present input transitions. Using this black box cell model and the past and present inputs to the module it is possible to accurately calculate the energy dissipation of the module. By performing a simple "bookkeeping" operation of all the modules activated during the instruction, it is possible to exactly estimate the energy dissipation of an instruction. A power profiler (PPROF) is built which takes as an input the program and the model of the basic units of each module and profiles the energy for each instruction of the program. In addition, it also outputs the energy consumption statistics for each type of instruction and for each module. A programmable microprocessor with sixteen instructions has been designed, and programs written for this machine are analysed using PPROF. The results of the estimated instruction energy are within 8% maximum error when compared with IRSIM-CAP.

Data shifting is required in many key computer operations from address decoding to computer arithmetic. Full barrel shifters are often on the critical path, which has led most research to be directed toward speed optimizations. With the advent of mobile computing, power has become as important as speed for circuit designs. In this paper we present a power-delay analysis for a range of 32-bit barrel shifters that vary at the gate, architecture, and environment levels.

A direct approach to transistor sizing for minimizing the power consumption of a CMOS circuit under a delay constraint is presented. In contrast to the existing assumption that the power consumption of a static CMOS circuit is proportional to the active area of the circuit, it is shown that the power consumption is a convex function of the active area. Analytical formulation for the power dissipation of a circuit in terms of the transistor size is derived which includes both the capacitive and the short circuit power dissipation. SPICE circuit simulation results are presented to confirm the correctness of the analytical model. Based on the intuitions drawn from the analytical model, heuristics for initial transistor sizing on critical and noncritical paths for minimum power consumption are developed. Further, fast heuristics to perform transistor sizing in CMOS circuits for minimizing power consumption while meeting the given delay constraints are presented.

In this paper we consider the problem of multiplying reasonably small integers using fewer counters than that required by straightforward partial product accumulation. Not surprisingly the method we use is based on the observation that integer multiplication can be formulated as aperiodic convolution. However, instead of using something like the Fast Fourier Transform to compute the aperiodic convolution, we use what are known as a "fast" convolution algorithms. In this way we can construct multipliers for as small as eighteen bit integers which use fewer counters than that required by straightforward partial product accumulation. Because of the perceived "overhead" involved with an aperiodic formulation of integer multiplication, the ability to do this goes somewhat against the conventional wisdom that aperiodic formulation of integer multiplication gains an advantage over a straightforward partial product formulation only for fairly large integers.>

The MGAP is a special-purpose, workstation co-processor board in which the computing elements are fine grain processors implemented as custom ASICs. In this paper we present the language *CC++, used for programming on the MGAP. Using the class concept of C++ we create special parallel data-types like bit, digit, word and array and overload operators to manipulate the parallel data required by the MGAP. The hierarchical relationships among the data-types are used by the compiler to generate parallel code for the MGAP. We demonstrate that by using the same high-level language and the same program we can operate on data at all levels of granularity, from bits to arrays, without any loss in performance.

Motion estimation plays a key role in video coding, (e.g., video telephone, MPEG, HDTV). Among the previous motion estimation algorithms, full-search block matching algorithms (BMA) are preferred because of their simplicity and lower control overhead when those algorithms are implemented in VLSI array processors. Previous full-search BMAs have considered one block matching at a time. There exist, however shared data in the search areas for adjacent template blocks. Therefore, if we process adjacent template blocks in parallel, we can reduce the data memory accesses for the shared data. In this paper we propose a new dataflow scheme for the efficient, systolic, full-search BMA on programmable array processors so that we can process as many adjacent template blocks as possible in unison in order to reduce the data memory accesses. We present an efficient implementation of the BMA on the Micro Grained Array Processor (MGAP) which is a fine-grained mesh-connected programmable VLSI array processor being developed at Penn State University. As a result, the BMA for the MPEG SIF video format (352/spl times/240 pixels) with a block size of 16/spl times/16 pixels, displacement range of 16 pixels, frame rate of 30 frames/sec can be computed at a real time processing rate on the MGAP.

Several techniques to estimate power consumption o f a combinational circuit using probabilistic methods have been proposed.However none of these techniques take i n to account circuit activity when two o r more inputs change simultaneously or when glitching occurs.A formulation is presented in this paper which includes signal correlation and multiple gate input switching.Work is also presented in estimating the glitching contribution to the switching activity.Results obtained from benchmarks and test circuits show v ery good accuracy when compared to actual activities as measured by SPICE and IRSIM.

We present a routing algorithm which minimizes the Elmore delay to the identified critical sinks while producing routes comparable to the best previously existing Steiner router. Since performance oriented layout generators employ iterative techniques that require a large number of calls to the routing algorithm for layout evaluation, a fast algorithm for routing is desirable. Our algorithm has a fast (O(n/sup 2/), where n is the number of points) and practical implementation using simple data structures and techniques. Comparisons with other existing algorithms are presented along with results from a performance driven layout generator using our routing algorithm.

Wavelet transforms have proven to be useful tools for several applications, including signal analysis, signal coding, and image compression. This paper surveys the VLSI architectures that have been proposed for computing the discrete and continuous wavelet transforms for 1-D and 2-D signals. The proposed architectures range from SIMD arrays to folded architectures such as systolic arrays and parallel filters. The SIMD arrays have a size that is proportional to that of the data sequence and are optimal with respect to time. The folded architectures, on the other hand, support single chip implementations and are optimal with respect to both area and time under the word-serial model.

The micro-grain array processor (MGAP) is a family of two-dimensional, micro-grained array processors. The processor cell architecture is extremely compact and simple, ensuring fine grainness, a very high processor density, and programming flexibility. Flexibility is maintained through a programmable interconnect which clusters array cells into larger computational units. We discuss the design and optimization issues of the MGAP-2, both at the processor array and system levels. Various design strategies and tradeoffs are being investigated at both levels. We show how lessons learned from building and using the MGAP-1 have been applied in this new design effort. We also describe our MGAP programming environment and an application example-the two-dimensional discrete cosine transform, a powerful image compression tool.

In this paper, we present a heuristic to synthesize a finite state machine as a set of smaller interacting submachines based on FPGA technology. This heuristic partitions inputs as well as outputs. Experimental results show that the sizes of submachines are much smaller than the size of original machine. As a result, the distributed smaller submachines can be operated faster than the original machine because of shorter critical paths.>

The paper describes a digit pipelined architecture for the 1D discrete wavelet transform, assuming a digit-serial model of computation. The use of simple operations and data movement makes it suitable for VLSI implementation and it can be easily mapped onto fine-grain custom VLSI and FPGA-based architectures. It achieves a factor of two speedup over a previous implementation of the same algorithm by virtue of digit pipelining made possible by the use of signed-digit arithmetic. In addition, the system can be clocked faster since it uses only nearest neighbor connections on a mesh, thus avoiding the signal propagation delays associated with long routing paths. An N-point DWT takes O(Nk) time and requires O(LJk) area, where L is the filter size, J is the number of octaves and k is the precision.>

We study the relative performance of three different massively parallel fine-grain, VLSI, control-flow architectures. The processor architectures being considered are: an associative memory architecture, a Mux-based SIMD architecture and a modification of the Mux-based architecture using RAMs making it suitable for systolic MIMD/MISD computation. All three architectures are organized as two-dimensional, near-neighbor mesh connected, array of processors. All three are very similar in their construction, and in their control and data-flow requirements. The custom hardware for all three architectures was built using the same technology. We compare and contrast the performance of these three VLSI architectures for a select set of applications. To evaluate the computational power of the three architectures we use the area time product, AT, as the metric. The three designs are known to perform well in their niche applications and we find that for non-niche applications all three designs are comparable in power to within a small constant factor. The performance of the Mux-based SIMD architecture is better in general than the other two in terms of speed though the associative architecture is found to out-perform the SIMD architecture for certain numeric applications like the FFT and matrix multiplication in the AT sense.>

Considers polynomial time testability of combinational circuits generated by input decomposition, especially those generated by the logic synthesis tool FACTOR. First, the complexity of the fault detection problem in this class of circuits is explored using a stuck-at fault model. An O(2/sup k/m) algorithm for detecting a single stuck-at fault is given that is faster than the O(16/sup k/m), previously reported best algorithm proposed by Fujiwara(1990), where k is the number of inputs in a subcircuit and m the number of signal lines in the circuit. Efficient, polynomial time algorithms are described for generating a test set for all single stuck-at faults in the circuit. The basic strategy is to eliminate backtracks during line justification by constructing tables or vector sets in each subcircuit, which makes the fault propagation procedure very simple and eventually results in an efficient test generation procedure. This presentation of efficient polynomial time test generation algorithms for FACTOR-generated circuits is important, since it shows that it is possible to synthesize circuits that are optimized for area and are polynomial time testable at the same time.>

A new approximation heuristic for finding a rectilinear Steiner tree of a set of nodes is presented. It starts with a rectilinear minimum spanning tree of the nodes and repeatedly connects a node to the nearest point on the rectangular layout of an edge, removing the longest edge of the loop thus formed. A simple implementation of the heuristic using conventional data structures is compared with previously existing algorithms. The performance (i.e., quality of the route produced) of our algorithm is as good as the best reported algorithm, while the running time is an order of magnitude better than that of this best algorithm. It is also shown that the asymptotic time complexity for the algorithm can be improved to O(n log n), where n is the number of points in the set.>

In this paper, we consider the problem of configuring Field Programmable Gate Arrays (FPGA's) so that some given function is computed by the device. Obtaining the information necessary to configure a FPGA entails both logic synthesis and logic embedding. Due to the very constrained nature of the embedding process, this problem differs from traditional multilevel logic synthesis in that the structure (or lack thereof) of the synthesized logic is much more important. Furthermore, a metric-like literal count is much less important. We present a communication complexity-based decomposition technique that appears to be more suitable for FPGA synthesis than other multilevel logic synthesis methods. The key is that our logic optimization technique based on reducing communication complexity is good enough to allow a simple technology mapping to work well for FPGA devices.>

An approach to designing CMOS adders for both high speed and low power is presented by analyzing the performance of three types of adders - linear time adders, logN time adders and constant time adders. The representative adders used are a ripple carry adder, a blocked carry lookahead adder and several signed-digit adders, respectively. Some of the tradeoffs that are possible during the logic design of an adder to improve its power-delay product are identified. An effective way of improving the speed of a circuit is by transistor sizing which unfortunately increases power dissipation to a large extent. It is shown that by sizing transistors judiciously it is possible to gain significant speed improvements at the cost of only a slight increase in power and hence a better power-delay product. Perflex, an in-house performance driven layout generator, is used to systematically generate sized layouts.>

In this paper, the authors present a novel scheme for performing arithmetic efficiently on fine-grain programmable architectures and FPGA-based systems. They achieve an O(n) speedup over the bit-serial methods of existing fine-grain systems such as the DAP, the MPP and the CM2, within the constraints of regular, near neighbor communication and only a small amount of on-chip memory. This is possible by means of digit systolic algorithms which avoid broadcast and operate in a fully systolic manner at the digit level. They use digit online techniques coupled with a base 4, signed-digit number system to limit carry propagation. Although the algorithms are bit-serial, the authors are able to match the performance of the bit-parallel methods, while retaining low communication complexity. Efficient O(n) time algorithms for multiplication and division of fixed-point, variable precision numbers are given. By using the organization of logic blocks suggested in this paper, problems of placement and routing that exist in systems built using FPGAs can be avoided. Since the algorithms are amenable to pipelining, very high throughput can be obtained.>

The Arithmetic Cube II, a high-performance signal processing system designed and built at Penn State University, is described. The architecture implements the so-called small-n algorithms, and is the first system making use of this approach to signal processing. The system is capable of computing a 1008-point complex-in complex-out discrete Fourier transform (DFT) in 3.54 ms. This high performance rate is achieved using very modest technology (2- mu CMOS). An overview of the small-n algorithms is provided. The architectural design and implementation of the system and the transform development environment are described, and results of operating the system are reported.>

This paper describes the design and implementation of high performance micrograined architectures. These architectures are capable of teraops performance. Each architecture is organized as a systolic array of processors. A prototyping system for the architectures is proposed. The prototyping system provides control, I/O, and an interface to a host system for each of the micro-grained architectures. The prototyping system has been designed with flexibility in mind to support a wide variety of these micro-grained architectures. Beyond the research outlined, the authors anticipate using the prototyping system as a 'test-bed' for various class/student VLSI design projects within the department. Three micro-grained architectures are described: an associative memory-based architecture, a Mux-based architecture and a RAM-based architecture. These architectures are useful for solving a number of important problems, such as: edge detection, locating connected components, two-dimensional signal and image processing, sorting elements, and performing element permutations.>

Three architectures, based on linear systolic arrays, for computing the discrete wavelet transform, are described. The AT/sup 2/ lower bound for computing the DWT in a systolic model is derived and shown to be AT/sup 2/= Omega (N/sup 2/N/sub w/k). Two of the architectures are within a factor of log N from optimal, but they are of practical importance due to their regular structure, scalability and limited I/O needs. The third architecture is optimal, but it requires complex control.>

A very-fine-grain, VLSI processor is described. Very-fine-grain VLSI processors are especially suited for problems with a high degree of parallelism. However, to maintain their fine grainness (i.e., small size) most fine grain processors are relatively inflexible. Attempts to increase flexibility usually increase processor complexity and, thereby, decreases grainness. The two-dimensional, micrograined processor maintains both a high degree of flexibility and fine grainness by reducing each processing cell to a small RAM and several multiplexers. For even greater speed, arithmetic operations are based on a redundant number representation. Algorithms for single-instruction multiple-data (SIMD), mesh architectures can be easily adapted for the micrograined processor. This is particularly true for algorithms for certain two-dimensional signal and image processing problems.>

The lower bounds on the area and time complexity of computing the wavelet transforms in VLSI are derived. The discrete wavelet transform (DWT) is shown to have a lower bound that matches the lower bound for the DFT, while it is seen that the discrete short time Fourier transform (DSTFT) is, in general, more difficult to compute. It is shown that for the DWT, AT/sup 2/= Omega (N/sup 2/ log/sup 2/(N)) and for the DSTFT, AT/sup 2/= Omega (N/sup 2/M/sup 2/log/sup 2/(N/sub w/+N)).>

A new addition algorithm, ELM, is presented. This algorithm makes use of a tree of simple processors and requires O(log n) time, where n is the number of bits in the augend and addend. The sum itself is computed in one pass through the tree. This algorithm was discovered by a VLSI CAD tool, FACTOR, developed for use in synthesizing CMOS VLSI circuits.>

A new method for computing the communication complexity of a given partitioning whose running time is O(pq), where p is the number of implicants (cubes) in the minimum covering of the function and q is the number of different overlapping of those cubes, is presented. Two heuristics for finding a good partition which give encouraging results are presented. Together, these two techniques allow a much larger class of functions to be synthesized. Two heuristic partitioning methods have been tested for certain circuits from the MCNC benchmark set. Using either heuristic, 11 out of 14 examples actually achieve the optimal solutions. A prototype program designed using the above techniques was developed and tested for circuits from the MCNC benchmark set. The experiment shows that the new symbolic manipulation technique is several orders of magnitude faster than an old version.>

This paper examines the error performance and presents simulation results of the Arithmetic Cube. The Arithmetic Cube is a special purpose architecture for computing high speed convolution and the DFT. An error analysis is performed for convolution and the DFT, as computed on the Cube. An upper bound on the number of bits lost is derived. The Cube looses at most an extra two bits (four bits), while computing convolution (DFT), more than the number of bits lost if computed by the direct, limited precision convolution (DFT). A VHDL description of the Cube was written and simulations were run. Simulation results substantiate the derived upper bounds. A comparison of the Winograd Fourier-transform-algorithm (WFTA), computed by the Cube, and a rounded FFT, shows that the Cube is at least as accurate as the rounded FFT. Contrary to previous results, it is argued that the WFTA performs better, with respect to accuracy, than the Prime Factor Algorithm (PFA), if both are computed on the Cube.>

A description is given of the synthesis, design, and simulation of the arithmetic cube II, a second-generation, high-performance digital signal processing architecture. The architecture implements the so-called small-n algorithms. The authors are currently building a CMOS prototype system which should be capable of computing a 1024 point complex DFT in 410 mu s.>

The authors present a novel, very fine grain associative architecture. This architecture maintains both a high degree of flexibility and fine graininess. This is done by reducing each processor to an associative memory cell. Unlike other associative memory processors, this architecture uses a two-dimensional interconnect and a physically compact memory structure. Arithmetic operations are based on the use of a redundant number system. These features provide a high level of performance. This is particularly true for certain two-dimensional problems which can be solved very efficiently on the proposed architecture.>

The authors present a new template-matching algorithm with good recognition performance. However, this new algorithm exhibits a complex, four-dimensional, wavefront architecture. Thus, for VLSI implementation, reduced architectures with fewer connections and processors need to be derived. For this purpose, the authors develop a systematic reduction methodology to manually map wavefront computations from high-dimension to low-dimension. This methodology consists of seven steps. Based on this methodology, the authors derive several two-dimensional architectures which are suitable for VLSI implementation for the new template-matching algorithm and have simulated one of the architectures by using the Intel Hypercube Machine iPSC/2.>

A very-fine-grained architecture which can solve certain two-dimensional machine vision problems very efficiently is discussed. The architecture maintains both a high degree of flexibility and fine-grainness. This is done by reducing each processor to an associative memory cell. However, unlike classical associative memory processors, the present processor uses a two-dimensional nearest-neighbor interconnect. Arithmetic operations are based on the use of a redundant number system and a physically compact memory word structure. These features provide a high level performance.>

An image matching algorithm, called the dynamic space-warping algorithm (DSWA), is presented. It is based on both local-distance diagrams and dynamic programming. The DSWA can solve space-warping problems (e.g., shrinking, enlarging, rotation, and distortion) with good performance by embedding controllable flexibility (or warping). The concept of flexibility can be explained using local-distance diagrams. With flexibility, the local-distance diagram between two two-dimensional images is four dimensional. Based on compression and expansion, DSWA generates a minimum distance from the four-dimensional local-distance diagram. Experimental results show that the DSWA is very reliable.>

The use of communication complexity based logic synthesis when configuring programmable logic devices (PLDs) is discussed. Configuration of a PLD involves the two processes of logic synthesis and logic embedding. Since the allowable PLD logic primitives usually include a very large number of gates, the processes of logic synthesis and technology mapping cannot be completely decoupled as they normally are in traditional logic synthesis systems. The proposed communication-complexity-based logic synthesis tool has the advantage of not completely decoupling these two processes. It is more suited to PLD configuring than other multilevel logic synthesis methods.>

The logic synthesis tool FACTOR generates circuits by finding the best decomposition of the inputs to minimize the communication complexity. It tries to minimize the number of connections in the circuit, instead of the number of gates, for area optimization. In addition to the area optimization, FACTOR also has the feature of generating circuits for which test vectors can be easily generated. Because it tries to find an input partitioning which provides the minimal number of connections between subcircuits, the generated circuits are tree-type with restricted reconvergent fanouts. It is shown how improved testability can be achieved at the same time as area optimization by presenting an efficient test generation algorithm for the restricted tree-type circuits generated by FACTOR using a single stuck-type fault model.>

Outlines an integrated, multi-level VLSI synthesis system. First, an architectural synthesis tool is used to compile the high level behavioral specification of the target architecture into a register transfer level specification. Constraints are supplied as inputs to allow the user to selectively explore various portions of the design space. The goal is to let the user perform global design tradeoffs, while the system synthesizes the best designs that meet the user's constraints. Once the register transfer level description has been synthesized, the data path and control path are separated and control logic synthesis is performed. Boolean library descriptions of various components which have been presynthesized with a multi-level logic synthesis tool are used to construct the data path. Finally a gate matrix module generator is used to produce layout. With the availability of these low level synthesis tools, the high level architectural system need not rely on just estimates of delay, area, and power metrics for quantifying design alternatives.>

It is shown that from an implementation point of view it is often the case that the chip area occupied by a VLSI signal processor is dominated and, therefore, largely determined by the area which must be devoted to multipliers. Therefore, signal processors which have high multiplier utilization (i.e. attain a higher throughput for a given number of multipliers) are of interest because it is possible for them to also attain good VLSI area utilization. Several signal processing architectures which have optimal multiplier utilization, are presented. These architectures are compared to several more conventional alternatives. It is also shown how the architectures achieve better multiplier utilization and, hence VLSI area utilization without suffering a degradation in utilization of other sources (e.g. adders and interconnect).>

A multilevel logic synthesis technique based on minimizing communication complexity is presented. This approach is believed to be viable because, for many types of circuits, the area needed is dominated by interconnections. By minimizing communication complexity and interconnect, area is reduced. This approach performs especially well for functions that are hierarchically decomposable (e.g., adders, parity generators, comparators, etc.). Unlike many other multilevel logic synthesis techniques, a lower bound can be computed to determine how well the synthesis was performed. A new multilevel logic synthesis program based on the techniques described for reducing communication complexity is presented.>

We present a new multi-level logic synthesis technique based on minimizing communication complexity. Intuitively, we believe this approach is viable because for many types of circuits lower bounds on the area needed to implement those circuits have been obtained considering only communication complexity. It performs especially well for functions which are hierarchically decomposable (e.g., adders, parity generators, comparators, etc.). Unlike many other multi-level logic synthesis techniques, a lower bound can be computed to determine how well the synthesis was performed. We also present a new multi-level logic synthesis program based on the techniques described for reducing communication complexity.

A comparison of four layout tools is presented. The layout style is a two-dimensional gate matrix. The first layout tool discussed uses standard simulated annealing. Annealing on gate clusters instead of individual gates can be used to improve the layout results. Two different ways of determining good gate clusters for use in the annealing process are compared. The first way uses clusters derived from user specified gate hierarchies, while the second determines clusters based on gate connectivity. The fourth layout tool uses a decomposition scheme based on quadrisection. Layout results for a set of benchmark circuits are presented for each of the tools.

The authors consider the problem of developing VLSI signal processors for computing convolutions. Convolutions can be efficiently computed by VLSI processors that consist of arrays of adders when they are stated in terms of matrices with elements consisting of only 1, 0, or -1. Unfortunately, when stated in matrix form the published algorithms have matrices with elements other than 1, 0, or -1. The authors explore why this occurs and show how it can be prevented when an algorithm is developed. If this fails, they propose a technique for addressing this problem that consists of replacing each such matrix by the product of two or more matrices whose elements are 1, 0, or -1.>

Several algorithms are presented for the l-dimensional cyclic convolution of n points. It is shown how these algorithms can be executed on a VLSI processor called the arithmetic cube, which has regular layout, simple control, and a bounded length and number of interconnects. It is also shown how changing the dimensionality of a transform can be used to efficiently compute an arbitrary problem on an arithmetic cube of given size. Finally, area and time bounds are developed for the arithmetic cube.>

The VLSI design of two digit serial adders, one which processes operand digits and produces online result digits least-significant digit first, and one which processes operands and produces online result digits most-significant digit first, is presented. They are compared with respect to number of gates, interconnect lines, layout area, and digit and operand add time. An optimal gate level description suitable for static CMOS implementation for one of the adders is given. This gate-level description can be input to a layout tool to automatically produce the CMOS gate matrix layout of the description. Finally, word-parallel adders built out of the two digit serial adders are discussed and compared.>

Digit serial data transmission can be used to an advantage in the design of special purpose processors where communication issues dominate and where digit pipelining can be used to maintain high data rates. VLSI signal processing is one such problem domain. We propose designs of systolic and semi-systolic digit serial multipliers. These multipliers are programmable i.e. one operand is pre-stored in the multiplier and the other operand is fed in a digit serial fashion. The VLSI implementation of the systolic multiplier is also given. This systolic multiplier is used in our VLSI signal processing system.

This paper introduces a standard structure for VLSI design which we call the mesh array and describes a design tool called LOGICIAN which minimizes a set of functions for realization in CMOS mesh arrays. LOGICIAN features multi-level logic synthesis through recursive enumeration of each function. Several techniques to speed-up the minimization process in LOGICIAN are described.

This paper overviews a CAD system under development at Penn State which will allow fast and near optimal implementation of a restricted class of VLSI architectures. Our target architectures are hierarchical mesh extensions of systolic meshes. Our target applications are primarily in the signal processing domain. The primitive components, at the lowest level in the mesh hierarchy, are one of the unique features of our target architectures. The CAD system under development includes: a tool for target architecture decomposition into primitive components, a tool for multi-level logic reduction for the primitive components; a tool for automatic gate placement within a primitive component; a tool for component placement within the target architecture; a high-level simulation tool; and a layout verification tool.

We present the design of a VLSI processor which can be programmed to compute the discrete Fourier transform of a sequence of n points and which achieves the theoretical AT2lower bound of Ω(n2) for n ∈ n where n is an infinite set. Furthermore, since the set n is also sufficiently dense, the processor achieves for any n the theoretical AT2lower bound of Ω(n2) for computing the cyclic convolution of two sequences of n points. Uniquely, our design achieves this bound without the use of data shuffling or long wires. Also, the processor uses only approximately θn multipliers, while many other designs need √(n) multipliers to achieve the same time bounds. Since multipliers are usually much larger than adders, the processor presented in this paper should be smaller. The design also features layout regularity, minimal control, and nearest neighbor interconnect of arithmetic cells of a few different types. These characteristics make it an ideal candidate for VLSI implementation.

This paper describes a high-level development system that can be used to design, simulate, and test high performance VLSI signal processors (filters, convolvers, transformers). While the system uses a number of previously studied techniques (silicon compilation, hierarchical design, and hardware description languages), they are combined in a novel way within the development system. Furthermore, the development system allowed us to investigate how these techniques interrelate with one another. The design process is fully automated and requires that the user specify only a few parameters such as operation, precision, size, and architecture type. The built-in digit pipelined architectures are based on a class of fast algorithms for the above operations. The basic components are compact and have a very small gate delay.

This correspondence examines the problem of sorting on a network of processors, where each processor consists of a single storage register and a small control unit capable of comparing two numbers and has a single serial memory attached to it. We show how to sort optimally on one- or two-dimensional arrays of p processors in time θ(n + (n2/p2)) and θ((n/√p) + (n2/p2)), respectively. Because of the implementational advantages of serial memories, we feel that our architecture will be attractive for several applications.

We propose a new VLSI architecture which allows many problems to be solved quite efficiently on chips with very small processing areas. We consider in detail the sorting problem and show how it can be solved quickly and elegantly on our model. We show that sorting n numbers can be done on a chip with processing area A = o(n) with an almost optimal speedup in a network with mesh-connected interconnections. The control is shown to be simple and easily implementable in VLSI.

A fully digit online arithmetic unit generates at least the i most (least) significant digits of the result after having been supplied no more than the (i+k) most (least) significant digits of each operand, where k is a small constant. This digit serial property can be used to reduce the aggregate fill and flush times of a chained array of digit online arithmetic units and to reduce their VLSI interconnection complexity. However, because of this digit serial property, unique and inherent limitations may have to be imposed on any arithmetic unit which performs digit online operations. For some calculations, these limitations may be so severe as to make digit online evaluation virtually impossible. We show several important signal processing problems where these limitations have either been avoided or their effect greatly reduced.

Research in computer architecture in the last decade has been driven largely by the motivation to overcome the "von Neumann" bottleneck. This paper describes the design and use of one such architecture—fully digit on-line networks. First, digit on-line algorithms and processing are defined. The key advantage to digit on-line processing is that it allows a digit serial, most significant digit first, type of data flow. Processing of the most significant operand digits starts immediately and generation of the most significant result digits soon follows. The minimum set of primitive logic operations required to implement a digit on-line processing component in VLSI are outlined. Then, digit on-line networks consisting of many of these digit on-line components are examined. Finally, two different network configurations are discussed and compared.

A fully digit on-line arithmetic unit generates at least the i most (least) significant digits of the output after having been supplied no more than the (i + k) most (least) significant digits of each input, where k is some small constant. This digit serial property can be used to reduce the aggregate fill and flush times of a chained list of digit on-line arithmetic units (which in turn reduces the required amount of parallelism needed to obtain high hardware utilization), and the VLSI interconnection complexity (which in turn reduces pin count). However, because of this digit serial property, unique limitations may be imposed on any arithmetic unit which performs certain operations in a digit on-line manner. Furthermore, these limitations are inherent in the sense that any fully digit on-line arithmetic unit which performs these operations will have some type of similar limitations. For some calculations, these limitations may be so severe as to make evaluation of that calculation by a digit on-line arithmetic unit virtually impossible. For other calculations, these limitations may not be nearly as severe. We will investigate techniques to either avoid or reduce the impact of these limitations.

This paper describes a systematic method which has been successfully used to create several digit online algorithms. Basically, the method entails converting in a systematic way a known continued sums/products algorithm and combining the converted form of the continued sums/product algorithm with a generalized digitization algorithm. Not only does the method seem to have wide applicability in the creation of digit online algorithms for many elementary functions but the algorithms which have resulted from this method themselves have several desirable properties.

This paper presents a class of algorithms, On-Line Continued Sums/Products, which are amenable for the efficient implementation by a pipeline architecture. The implementation of these algorithms provides a simple and fast method for the evaluation of several of the elementary functions; i.e., addition, subtraction, multiplication, division, logarithm, exponentiation, sine, cosine, and tangent. In addition to possessing the expected properties necessary for the efficient implementation in a pipeline architecture, the On-Line Continued Sums/Products algorithms allow for the possibility of implementing a pipeline architecture which is dynamically reconfigurable and which can process variable precision operands.