FPGA implementations of block floating point (BFP), streaming, 256-point and 1024-point fast Fourier transform (FFT) circuits are described as examples of a new architectural approach that provides better performance, flexibility, and functionality than commercially available pipelined FFTs. It is based on a matrix formulation of the discreet Fourier transform (DFT) that converts the direct transform into structured sets of arithmetically simple 4-point transforms that are computed on a systolic array. This circuit architecture permits transform lengths that are not a power-of-two, can do 2-D as well as 1-D transforms, is scalable, has low computational latency and utilizes BFP and floating point (FP) features to provide high dynamic range. Circuit comparisons are made with a commercially available pipelined FFT.

An FPGA implementation of a fast Fourier transform (FFT) circuit is described as an example of a new class of parallel FFT architectures that can provide better performance and functionality than traditional pipelined FFTs and is well suited to wireless applications. Any circuit implementation can perform any transform size that is a multiple of 256 as long as adequate memory is provided. Throughput can be adjusted by adding/subtracting identical blocks of hardware. Power is minimized by using only small memories, providing systolic data flow to avoid memory reads/writes, and localizing connections to reduce interconnect overhead. High dynamic range is obtained through a unique multiple block floating point (BFP) feature. The design is regular in structure and is built with only three simple cells. An FPGA based demonstration circuit with 89db signal-to-quantization-noise has been implemented that can perform a 256-point transform continuously at 0.66 musec/transform. Circuit comparisons are made with a modern commercial pipelined FFT.

A systolic architecture for calculating the discrete Fourier transform (DFT) is described which is based on a new matrix formulation that decomposes the transform into sets of 4-point transforms. The architecture supports transform lengths that are not powers of two or based on products of coprime numbers. Compared to previous systolic implementations, the architecture is computationally more efficient and uses less hardware. It provides low latency as well as high throughput, and can do both 1D and 2D DFTs. An automated CAD tool was used to find latency and throughput optimal designs that matched the target field programmable gate array structure and functionality.

"Systolic" algorithms have been shown to be suitable for a very large range of structured problems (i.e., linear algebra, graph theory, computational geometry, number-theoretic algorithms, string matching, sorting/searching, dynamic programming, discreet mathematics). Usage of this systolic architecture class has not been widespread in the past, in part because programmable hardware that supported this computing paradigm was not cost-effective to build and no design tools existed. However, suitable hardware has begun to appear. Complex FPGAs now provide an adequate level of speed, density and programmability in the form of reconfigurable computers, boards, and chips with embedded computational support. Such hardware could allow rapid implementation and change of systolic algorithms leading to inexpensive "programmable" systolic array hardware. Furthermore, the architectural characteristics of much FPGA hardware matches that required by systolic processing, because this technology is constructed from tiling identical memory and logic blocks along with supporting mesh interconnection networks. The symbolic parallel algorithm development environment (SPADE) described here is being developed to allow a designer to easily and rapidly explore the design space of various systolic algorithm implementations so that FPGA system tradeoffs can be efficiently analyzed. The intention is to allow a user to specify his algorithm with traditional high-level code, set some architectural constraints and then view the results in a meaningful graphical format.

The image understanding architecture (IUA) system is designed specifically for computer vision processing that relies heavily on artificial intelligence techniques to classify objects. To provide for low-, intermediate-, and high-level computer vision processing, the IUA system combines three heterogeneous levels of parallelism with associative processing mechanisms. The lowest level of the IUA contains a SIMD array of per pixel bit-serial processing elements with networking capabilities that exceed those of present bit-serial machines. The SIMD level is closely mated with a middle-level MIMD array of high-performance digital signal processing chips that communicate via a flexible, modular message-passing network. The dual-capability architecture is much more effective than a solely SIMD or MIMD organization. The highest level comprises an array of general-purpose microprocessors for symbol manipulation. The first- and second-generation implementations of the IUA architecture are described.>

An efficient parallel processing algorithm for detecting straight lines on a mesh-connected computer enhanced with a gate-connection network (GCN) is presented. The algorithm is composed of a modified Hough transform that projects compressed pixels in parallel in a given direction and a parallel procedure that extracts the beginning and end points of detected lines. Both parts require the flexible communication capabilities of the enhance mesh. The GCN can be used to dynamically reconfigure the interconnections between hundreds of processors. It is shown how the GCN can electrically connect all of the edge pixels on a straight line. For an n*n pixel array, the algorithm can detect all lines in O(log n) time. Initial experimental results obtained using a simulator of the GCN implemented on a very-large-scale integration (VLSI) chip are presented. Though the accuracy of the algorithm depends largely on the assigned threshold values, the authors believe its speed is superior to that of any other Hough-based technique by a factor of at least two orders of magnitude.>

First- and second-generation implementations of an image understanding architecture, IUA, are described. The IUA system is designed specifically for computer vision processing that relies heavily on artificial intelligence techniques to classify objects. To provide for low-, intermediate-, and high-level computer vision processing-required for model-/knowledge-based interpretation of sensor data-the IUA system combines three heterogeneous levels of parallelism with associative processing mechanisms. The tightly coupled symbolic and numeric processing capabilities constitute a unique computing paradigm ideally suited to computer vision applications, which require both control- and data-parallel processing. The IUA architecture, hardware, and software are described.>

Architectural research in support of knowledge-based computer vision is described. Efforts are focused on two major areas: the development of the image understanding architecture (IUA) and the benchmarking of parallel processors for vision. Two aspects of the IUA research are discussed. One is the development of the low-level processor chip, which integrates 64 one-bit (serial) processors, data caches, a communication network, and parallel interfaces to image input/output (I/O) hardware and the intermediate-level processors. The other is the ICAP, which is designed to manipulate tokens (symbolic descriptions of extracted image events and their associated attributes) at the intermediate level and to support database functions that allow access to these tokens. Work on an image understanding work bench is briefly described.>

An algorithm is described that provides an architectural framework for systematic execution of a wide class of linear algebraic operations using a single systolic array and simple data flow. The algorithm has been modified to use numerically stable Given's rotations and is therefore suited to any matrix problem of full rank. When the problem size exceeds that of the hardware array, it can be partitioned in a straightforward, numerically stable way. Numerous simulations have verified the algorithm's correctness.>

Linear systolic arrays are well known examples of a concurrent systems approach which provides the potential for high performance and flexibility without attendant design complexity[1]. Generally such arrays take problems of O(n2) complexity and provide the solution in O(n) time steps using O(n) processors, where n is the order of the system (number of unknowns or filter poles). Although much work has been done defining the capabilities of such an array [2], very few have been built [3,4,5]. We describe here an operational prototype linear systolic array that uses a custom designed VLSI chip for modularity, high performance and design simplicity. We also describe a few applications examples, with emphasis on Toeplitz linear systems, to illustrate its operation.

We describe here a 2-D array of processing elements, connected in a nearest neighbor mesh, which provides a high performance linear algebraic computing capability. To provide this generality of operation, the processor array uses the Faddeev algorithm, mapped into a systolic/cellular architecture with only two different types of processing elements. Examples of how it can be used in robotics for such operations as image processing and inverting Jacobian matrices are given.