Search

This paper demonstrates an optimal time, fully systolic algorithm for edge detection on a mesh connected processor array. It uses only inexpensive addition and comparison operations which makes it ideal for fine grained parallelism in VLSI. Given anN xN image in the form of a two-dimensional array of pixels, our algorithm computes the Sobel and Laplacian operators for skimming lines in the image and then generates the Hough array using thresholding. The Hough transforms forM different angles of projection are obtained in a fully systolic manner inO(M+N) time, which is asymptotically optimal. In comparison, a previously published multiplication free algorithm has a time complexity ofO(NM). An implementation of our algorithm on a mesh connected finegrained processor array is discussed, which computes at the rate of approximately 170,000 Hough transforms per second using a 50 MHz clock.

The Euclidean distance transform (EDT) converts a binary image into one where each pixel has a value equal to the Euclidean distance to the nearest foreground pixel. It has important uses in image analysis, computer vision and robotics, and so its VLSI implementation is very useful. In this paper, a sequential algorithm which does not require global operations is first presented. We then apply a sequence of algorithm transforms to convert it into one directly realizable as a square shaped systolic array, and a triangular shaped array after folding transformation. For an n x n image on an equal-sized systolic array, the computation consists of a forward scan and a reverse scan with O (n) time complexity. For images larger than the systolic array, an efficient partitioning and scheduling method based on array emulation is also given.

Several systolic Kalman filters have appeared in the literature, with often complex hardware constructs to accomodate the algorithmic `anomalies'. Here, we follow a different route by working the original information filter into a so-called `Jacobi-type' algorithm, which is much more regular and directly fits onto a common and general Jacobi-type systolic array. The efficiency of the resulting systolic implementation is still comparable to what is achieved with the best of the other solutions. The advantage here is that one ends up with one type of array, which is suitable for a whole set of problems/algorithms, whereas otherwise the array is exclusively tuned to Kalman filtering. The aim of this report is thus to demonstrate the usefulness of these Jacobi-type arrays, rather than to come up with yet another systolic Kalman filter.

This paper presents systematic methods, based on graph theoretic approach, for mapping of neural networks onto mesh connected SIMD arrays. The methods are applicable to a large class of multilayer network models, which can be represented in terms of sparse matrix vector operations. The class of computers, that the mappings are suitable for, encompasses most of the experimental and commercial mesh-connected SIMD arrays of processors. There are three methods described in the paper, one for the case of a processor array, which is larger or equal to the network size and two for the partitioned case, i.e. array smaller than the input data size. The methods are illustrated on an example of a multilayer perceptron with back-propagation learning, which consists ofn nuerons ande synaptic connections. For the first method, the processor array is assumed to be of sizeN×N, whereN2?n+e, and the required local memory of processors is limited to only a few registers. The implementation of a single iteration of a recall phase according to the method requires 24(N-1) shifts. For this method we have developed a software tool, which generates a sequence of pseudo instructions, such as elemental data shift and arithmetic operations, that implement a given neural network on a given size processor array. For the two partitioned methods, the processor array is of sizeP×P, whereP2≤n+e, and the local memory in the processors is of sizeO(K). The faster of the two methods requiresO(N3/P3K) time for an iteration of the recall or learning phase.

The Power Factor Approximation (PFA) power estimation method is reviewed and applied to VLSI array processing systems. The power dissipation of 1, 2, and 3 dimensional algorithms implemented on linear, hexagonal, and cubic processor arrays is investigated. Closed form equations are developed which show how the overall power dissipation is influenced by an algorithm's size and dimensionality, the target array processor's size and dimensionality, and the adopted partitioning strategy. The power estimation methods developed in this paper can be applied in the early phases of VLSI algorithm/architecture design, selection, and partitionment. The power dissipation of a matrix-matrix multiplication operation is estimated as an example application.

This paper deals with the parallel execution of algorithms with global and/or irregular data dependencies on a regularly and locally connected processor array. The associated communication problems are solved by the use of a two-dimensional sorting algorithm. The proposed architecture, which is based on a two-dimensional sorting network, offers a high degree of flexibility and allows an efficient mapping of many irregularly structured algorithms. In this architecture a one-dimensional processor array performs all required control and arithmetic operations, whereas the sorter solves complex data transfer problems. The storage capability of the sorting network is also used as memory for data elements. The algorithms for sparse matrix computations, fast Fourier transformation and for the convex hull problem, which are mapped onto this architecture, as well as the simulation of a shared-memory computer show that the utilization of the most complex components, the processors, is O(1).

The problem of mapping algorithms onto regular arrays has received great attention in the past. Results are available on the mapping of regular algorithms onto systolic or wavefront arrays. On the other hand, many algorithms that can be implemented on parallel architectures are not completely regular but are composed of a set of regular subalgorithms. Recently, a class of configurable processor arrays has been proposed that allows the efficient implementation of piecewise regular algorithms. In contrary to pure systolic of wavefront arrays they are distinguished by a dynamic configuration structure. The known trajectories, however, cannot be applied to the design of configurable processor arrays because the functions of the procesing elements and the interconnection structure are time- and space-dependent. In this paper, a systematic procedure is introduced that allows the efficient design of configurable processor arrays including the specification of the processing elements and the generation of control signals. Control signals are propagated through the processor array. The proposed design trajectory can be used for the design of regular arrays or configurable arrays.

A systematic efficient fault diagnosis method for reconfigurable VLSI/WSI array architectures is presented. The basic idea is to utilize the output data path independence among a subset of processing elements (PEs) based on the topology of the array under test. The "divide and conquer" technique is applied to reduce the complexity of test application and enhance the controllability and observability of a processor array. The array under test is divided into nonoverlapping diagnosis blocks. Those PEs in the same diagnosis block can be diagnosed concurrently. The problem of finding diagnosis blocks is shown equivalent to a generalizedEight Queens problem. Three types of PEs and one type of switches, which are designed to be easily testable and reconfigurable, are used to show how to apply this approach. The main contribution of this paper is an efficient switch and link testing procedure, and a novel PE fault diagnosis approach which can speed up the testing by at leastO(?V?1/2) for the processor arrays considered in this paper, where ?V? is the number of PEs. The significance of our approach is the ability to detect as well as to locate multiple PE, switch, and link faults with little or no hardware overhead.

The study of Regular Iterative Algorithms (RIAs) was introduced in a seminal paper by Karp, Miller, and Winograd in 1967. In more recent years, the study of systolic architectures has led to a renewed interest in this class of algorithms, and the class of algorithms implementable on systolic arrays (as commonly understood) has been identified as a precise subclass of RIAs. In this paper, we shall study the dependence structure of RIAs that are not systolic; examples of such RIAs include matrix pivoting algorithms and certain forms of numerically stable two-dimensional filtering algorithms. It has been shown that the so-called hyperplanar scheduling for systolic algorithms can no longer be used to schedule and implement non-systolic RIAs. Based on the analysis of a so-called computability tree we generalize the concept of hyperplanar scheduling and determine linear subspaces in the index space of a given RIA such that all variables lying on the same subspace can be scheduled at the same time. This subspace scheduling technique is shown to be asymptotically optimal, and formal procedures are developed for designing processor arrays that will be compatible with our scheduling schemes. Explicit formulas for the schedule of a given variable are determined whenever possible; subspace scheduling is also applied to obtain lower dimensional processor arrays for systolic algorithms.

Most work on the problem of scheduling computations onto a systolic array is restricted to systems of uniform recurrence equations. In this paper, this restriction is relaxed to include systems of affine recurrence equations. In this broader class, a sufficient condition is given for the system to be computable. Necessary and sufficient conditions are given for the existence of an affine schedule, along with a procedure that constructs the schedule vector, when one exists.