Narrow Results

A systolic array processing technique is applied to implementing the stack algorithm form of the sequential decoding algorithm. It is shown that sorting, a key function in the stack algorithm, can be efficiently realized by a special type of systolic arrays known as systolic priority queues. Compared to the stack-bucket algorithm, this approach is shown to have the advantages that the decoding always moves along the optimal path, that it has a fast and constant decoding speed and that its simple and regular hardware architecture is suitable for VLSI implementation. Three types of systolic priority queues are discussed: random access scheme, shift register scheme and ripple register scheme. The property of the entries stored in the systolic priority queue is also investigated. The results are applicable to many other basic sorting type problems.

Much work has been done on the problem of synthesizing a processor array from a system of recurrence equations. Some researchers limit communication to nearest neighbors in the array; others use broadcast. In many cases, neither of the above approaches result in an optimal execution time.

In this paper a technique called bounded broadcast is explored whereby an element of a processor array can broadcast to a bounded number of other processors. This technique is applied to the problems of transitive closure and all-pairs shortest distance, resulting in time complexities that are smaller than those reported previously. In general, the technique can be used to design bounded broadcast systolic arrays for algorithms whose implementation can benefit from broadcasting.

A fully parallel algorithm for updating and downdating the singular value decompositions (SVD’s) of an m-by-n(m≥n) matrix A is described. The algorithm uses similar chasing techniques for modifying the SVD’s described in [3], but requires fewer plane rotations, and can be implemented almost identically for both updating and downdating. Both cyclic and consecutive storage schemes are considered in parallel implementation. We show that the latter scheme outperforms the former on a distributed memory MIMD multiprocessor. We present the experimental results on the 32-node Connection Machine (CM-5).

A systolic array provides an alternative computing paradigm to the von Neumann architecture. Though its hardware implementation has failed as a paradigm to design integrated circuits in the past, we are now discovering that the systolic array as a software virtualization layer can lead to an extremely scalable execution paradigm. To demonstrate this scalability, in this paper, we design and implement a 3D virtual systolic array to compute a tile QR decomposition of a tall-and-skinny dense matrix. Our implementation is based on a state-of-the-art algorithm that factorizes a panel based on a tree-reduction. Freed from the constraint of a planar layout, we present a three-dimensional virtual systolic array architecture for this algorithm. Using a runtime developed as a part of the Parallel Ultra Light Systolic Array Runtime (PULSAR) project, we demonstrate on a Cray-XT5 machine how our virtual systolic array can be mapped to a large-scale machine and obtain excellent parallel performance. This is an important contribution since such a QR decomposition is used, for example, to compute a least squares solution of an overdetermined system, which arises in many scientific and engineering problems.

The parallelization of loops can be made formal by basing it on an algebraic theory of loop transformations. In this theory, the concept of unimodularity arises. We discuss the pros and cons of insisting on unimodularity.

In this paper, two linear systolic arrays for the solution of general, strongly regular Toeplitz system of equations are presented. They arise from systolization of the efficient serial Schur-like algorithm. Both arrays are time-minimal and they complete the solution in 3n – 4 time cycles (without the initialization and the retrieval of results). The first array requires 2n – 2 processors, and the second one uses only n – 1 processors.

The paper, using a directed acyclic graph (dag) model of algorithms, investigates precedence constrained multiprocessor schedules for the n_x×n_y×n_z directed rectilinear mesh. Its completion requires at least n_x+n_y+n_z−2 multiprocessor steps. Time-minimal multiprocessor schedules that use as few processors as possible are called processor-time-minimal. Lower bounds are shown for the n_x×n_y×n_z directed mesh, and these bounds are shown to be exact by constructing a processor-time-minimal multiprocessor schedule that can be realized on a systolic array whose topology is either a two dimensional mesh or skewed cylinder.

In this paper we propose studying several ways to implement a realistic and efficient VLSI design for a gradient-based dense motion estimator. The kind of estimator we focus on belongs to the class of differential methods. It is classically based on the optical flow constraint equation in association with a smoothness regularization term and also incorporates robust cost functions to alleviate the influence of large residuals. This estimator is expressed as the minimization of a global energy function defined within the framework of an incremental formulation associated with a multiresolution setup. In order to make possible the conception of efficient hardware, we consider a modified minimization strategy. This new minimization strategy is not only well suited to VLSI derivation, it is also very efficient in terms of quality of the result. The complete VLSI derivation is realized using high-level specifications.

The recognition of patterns is an important task in robot and computer vision. The patterns themselves could be one- or two-dimensional, depending upon the application. Pattern matching is a computationally intensive and time consuming operation. The design of special purpose hardware could speed up the matching task considerably, making real-time responses possible. Advances in parallel processing and VLSI technologies have made it possible to implement inexpensive, efficient and very fast custom designs. Many approaches and solutions have been proposed in the literature for hardware implementations of pattern matching techniques. In this paper, we present a detailed overview of some of the important contributions in the area of hardware algorithms and architectures for pattern matching.

The recognition of polygons in 3-D space is an important task in robot vision. Advances in VLSI technology have now made it possible to implement inexpensive, efficient and very fast custom designs. The authors have earlier proposed a class of VLSI architectures for this computationally intensive task, which makes use of a set of local shape descriptors for polygons which are invariant under affine transformations, i.e. translation, scaling, rotation and orthographic projection from 3-D to any 2-D plane. This paper discusses the design and implementation of PMAC, a prototype for polygon matching, as a custom CMOS VLSI chip. The recognition procedure is based on the matching of edge-length ratios using a simplified version of the dynamic programming procedure commonly employed for string matching. The matching procedure also copes with partial occlusions of polygons. The implemented architecture is systolic and fully utilizes the principles of pipelining and parallelism in order to obtain high speed and throughput.

In this paper, a new architecture for radix-2ⁿ serial–serial multiplication/reduction for the finite field GF(2^m) is presented. The input operands are serially entered one digit at a time and the output result is computed serially one digit at a time. The reduction polynomial is also fed serially to the structure so that changing the reduction polynomial will not require rewriting or rewiring the structure. The structure utilizes a serial transfer which reduces the bus width needed to transfer data back and forth between memory and multiplication unit. The structure possesses features of regularity, modularity and scalability which are a design requirement for an efficient utilization of FPGA resources. Also, a systolic scalable area efficient design which provides a 50% reduction in hardware without degrading the speed performance is proposed. A radix-4 version of the proposed architecture has been designed, simulated and synthesized using Xilinx ISE 10.1 targeting a Xilinx Virtex-5 FPGA.

Applications like biosequence alignment are currently addressed using traditional technology at the price of a huge overhead in terms of area and power dissipation. Nanoarrays are expected to outperform current limits especially in terms of processing capabilities. The purpose of this work is to assess the real terms of these expectations. Our contribution deals with: (i) a new model for nanowire FETs used to evaluate transistor’s essential performance; (ii) a new switch-level simulator for nanoarray structure used to evaluate its switching activity; (iii) a nanoarray implementation for biosequence alignment based on a systolic array and the modeling of its essential performance based on (i) and (ii); (iv) the evaluation of the potential improvement of the nanoarray-based systolic structure with respect to an equivalent CMOS one in terms of processing capabilities, area, and power dissipation. Depending on the possible technological scenario, the performance of nanoarray is impressive, especially considering the density achievable in terms of processing per unit area. A wide solution space can be explored to find the optimal solution in terms of trading power and performance considering the technological limitations of a realistic implementation.

In this paper, hybrid architecture for DTCWT computation is designed and implemented on FPGA based on DA algorithm. The distributive arithmetic (DA) algorithm is combined with multiplexer based algorithm to optimize the resource utilization on configurable logic block (CLB). The filter coefficients of DTCWT are quantized, rounded to its nearest integer for DTCWT computation and the loss in rounding and quantization is limited to 0.5dB as compared with software implementation. The parallel architecture designed computes row elements simultaneously and pipelined architecture is designed to compute column elements. The proposed architecture is modeled using Verilog and implemented on Xilinx FPGA. The design operates at a maximum frequency of 496MHz and consumes power less than 0.2W.

In this paper, systolic array-based novel architecture for dual-tree complex wavelet transform (DTCWT) computation is designed and implemented on FPGA. The wavelet filter coefficients of DTCWT are quantized and rounded to nearest integer and the loss in rounding and quantization is limited to 0.5dB as compared with software implementation. The parallel architecture designed computes row elements simultaneously and pipelined architecture is designed to compute column elements. The proposed architecture is modeled using Verilog and implemented on Xilinx Virtex II FPGA. For 2D implementation, the design operates at a maximum frequency of 156MHz and consumes power less than 3W. This is the first design with systolic array architecture on FPGA for DTCWT computation operating at frequencies greater than 100MHz.

The recognition of polygons in 3-D space is an important task in robot vision. Advances in VLSI technology have now made it possible to implement inexpensive, efficient and very fast custom designs. The authors have earlier proposed a class of VLSI architectures for this computationally intensive task, which makes use of a set of local shape descriptors for polygons which are invariant under affine transformations, i.e. translation, scaling, rotation and orthographic projection from 3-D to any 2-D plane. This paper discusses the design and implementation of PMAC, a prototype for polygon matching, as a custom CMOS VLSI chip. The recognition procedure is based on the matching of edge-length ratios using a simplified version of the dynamic programming procedure commonly employed for string matching. The matching procedure also copes with partial occlusions of polygons. The implemented architecture is systolic and fully utilizes the principles of pipelining and parallelism in order to obtain high speed and throughput.