Search

A new theoretical model for reconfigurable processor arrays is introduced. Most of the models considered in the literature are similar to the reconfigurable mesh (RMESH), in which each processing element (PE) is connected to its four neighbors by reconfigurable buses. In the new model, called the “well-connected processor array” (wecpar), every PE is connected to each neighbor by ${\mbi{k}}\ {\bf \geq 1}$ point-to-point lines, and it also controls the switching between those lines. ${\mbi{k}}$ is called the connectivity of the wecpar. Any line entering the PE can either be connected to the PE itself, or it can be connected by the PE to another line, thus enabling complex switching configurations. This model is suitable for arrays in which the computation and memory areas of a PE are very much larger than a switch area. The concept of a burden placed on a PE by the lines connected to or passing through it is introduced. This is used to derive a lower bound of ${\mbi{k}}=\Omegab({\mbi{d}}^{\bf 3/2}/{\mbi{e}})$ on the connectivity required by a wecpar to embed any graph of degree ${\bf \geq}{\mbi{d}}$ with expansion ${\mbi{e}}$ ; for ${\mbi{e}}\ {\bf = 1}$ , this result is sharp. Various other issues are examined: graph embeddings, algorithms, broadcasting, routing, and self-simulation. A novel transportation-type routing method utilizes the connectivity for efficient routing. A sample algorithmic result is that an ${\mbi{n}}$ -point FFT can be done in logarithmic time on a wecpar of ${\mbi{n}}$ PEs with a connectivity of $\sqrt{{\mbi{n}}/{\bf 2}}$ .

Two VLSI architectures for the computationally efficient implementation of the elementary 3D geometrical transformations are introduced. The first one is based on a single floating-point multiply/add unit, while the other one comprises a four processing-element vector unit. By exploiting the structure of the elementary transformation matrices, some of the elements of which are ones and zeros, the proposed architectures avoid full-matrix multiplication for the matrix multiplications involved in the calculation of the transformation matrix by treating them as updates of specific elements, the new values of which are obtained by scalar operations in the case of the single-processor architecture or by simple vector operations in the case of the processor array. Thus, the floating-point operation count and the number of memory accesses required by a transformation are reduced and, therefore, the performance of the circuit which computes the transformation matrix, in terms of execution time, is improved at minimal hardware cost. Furthermore, a circuit is proposed which, for each sequence of transformations, selects the most appropriate direction for computing the product of the matrices in the corresponding stack of transformation matrices in order to further reduce the number of floating-point operations compared to the case where the direction of the computation of the successive matrix products is predetermined. The proposed single-processor architecture is suitable for low-cost applications, while the parallel execution scheme implemented by the introduced parallel processor may be implemented by any four-PE processor with small overhead.

A mesh-connected processor array consists of many similar processing elements (PEs) which can be executed in both parallel and pipeline processing. For the implementation of an array of large numbers of processors, some fault-tolerant issues are necessary to enhance the (fabrication-time) yield and the (run-time) reliability. In this paper, we propose a fault-tolerant reconfigurable processor array using single-track switches like Kung et al.'s model. The reconfiguration process in our model is executed based on the concept of the "compensation path" like Kung et al.'s method, too. In our model, spare PEs are not necessarily put around the array, but are more flexibly put in the array by changing connections between spare PEs and nonspare PEs while retaining the connections among nonspare PEs in the same manner in Kung et al.'s model. The proposed model has such a desirable property that physical distances between logically adjacent PEs in the reconfigured array are within a constant, that is, independent of sizes of arrays. We show that the hardware overhead of the proposed model is a little greater than that of Kung et al.'s model, while the yield of the proposed model is much better than that of Kung et al.'s model.

This paper introduces MorphoSys, a reconfigurable computing system developed to investigate the effectiveness of combining reconfigurable hardware with general-purpose processors for word-level, computation-intensive applications. MorphoSys is a coarse-grain, integrated, and reconfigurable system-on-chip, targeted at high-throughput and data-parallel applications. It is comprised of a reconfigurable array of processing cells, a modified RISC processor core, and an efficient memory interface unit. This paper describes the MorphoSys architecture, including the reconfigurable processor array, the control processor, and data and configuration memories. The suitability of MorphoSys for the target application domain is then illustrated with examples such as video compression, data encryption and target recognition. Performance evaluation of these applications indicates improvements of up to an order of magnitude (or more) on MorphoSys, in comparison with other systems.

An advanced spare-connection scheme for k-out-of-n redundancy called "generalized additional bypass linking" is proposed for constructing fault-tolerant massively parallel computers with series-connected, mesh-connected, or tree-connected processing element (PE) arrays. This scheme uses bypass links with wired OR connections to selectively connect the primary PEs to a spare PE in parallel. These bypass links are allocated to the primary PEs by node-coloring of a graph with a minimum inter-node distance of three in order to minimize the number of bypass links (i.e., the chromatic number). The main advantage of this scheme is that it can be used for constructing various k-out-of-n configurations capable of enhanced PE-to-PE communication and broadcast while still achieving strong fault tolerance for these PEs and links. In particular, it enables the construction of optimal r-strongly-fault-tolerant configurations capable of direct k-out-of-n selections by providing r spare PEs and r extra connections per PE for any kind of array when node-coloring with a distance of three is used. This simple spare-circuit structure enhances fault tolerance more than conventional schemes do. The node-coloring patterns were constructed using new node-coloring algorithms and the chromatic numbers were evaluated theoretically. Enhanced PE-to-PE communication and broadcast were achieved by using new fault-tolerant routing algorithms based on the properties of the node-coloring patterns with four or five message transmission steps being optimal configurations with any size array.

Algorithm-based fault tolerance (ABFT) is used to provide low-cost error protection for VLSI processor arrays used in real-time digital signal processing. The main objective of incorporating an ABFT technique in a processor array is to improve its reliability. All previous approaches on ABFT are evaluated in terms of their error detecting/correcting capabilities, the reliability improvement has never been addressed. In this paper, we develop a stochastic model for an array processor incorporating ABFT that takes the behavior of transient/intermittent failures and hardware overhead into account. This model is then used to evaluate reliability and reliability improvements of several existing ABFT techniques that tolerate single faults. Therefore, a user can evaluate a number of ABFT techniques and make a trade-off between reliability and cost prior to the implementation. Moreover, we have conducted extensive simulation experiments and the simulation results validate the proposed model.

Present new results on systematic procedures for reconfiguring processor arrays in the presence of faulty processors. In particular, the authors consider models that use multiple tracks along every channel and a single spare row (or column) of processing elements (PEs) along each boundary of the array. In the presence of faulty PEs the general methodology for reconfiguration involves replacing every faulty PE logically (rather than physically) by a spare PE through a sequence of logical substitutions; these sequences of substitutions are referred to as compensation paths. The authors show that if there exists a set of compensation paths subjected only to the constraints of continuity and nonintersection, then routing channels with three tracks are enough for the reconfiguration of the array. They refer to the underlying model as a S-track-l-spare model; this is done to distinguish it from other models that not only use multiple tracks but also multiple spare rows (or columns) along each boundary. An efficient algorithm for reconfiguration in our 3-track-1-spare model is presented and its performance evaluated. Experimental results show that the 3-track-1-spare model has much higher reconfiguration probability than other models that use considerably more spare processors. >

Implementations of neural networks on programmable massively parallel computers are addressed. The methods are based on a graph theoretic approach and are applicable to a large class of networks in which the computations can be described by means of matrix and vector operations. A detailed characterization of the target machine is provided. Two mappings are presented. The first is designed for a processor array consisting of a very large number of small processing units. The neurons and the nonzero synaptic weights are assigned to the processors in a predetermined order, one per processor. The data transfers between processors containing neurons and weights are implemented using a novel routing algorithm. The second mapping is designed for the data array of size N*N and a smaller processor array of size P*P, P >

The Berlekamp-Massey algorithm (BMA) (E. Berlekamp, 1968; J. Massey, 1969) is important in the decoding of Reed-Solomon (RS), and more generally, Bose-Chaudhuri-Hocquenghem (BCH) block error control codes. For a t-error correcting code the BMA has time complexity O(t/sup 2/) when implemented on a sequential computer. However, the BMA does not run efficiently on a parallel computer. The BMA can be mapped into the Schur BMA. The paper presents the implementation of the BMA and Schur BMA together on a linearly connected array of 2t processors. The resulting machine computes the error locator polynomial with a time complexity of O(t). >

Methods of implementing fast radix 2 transforms on array processors are considered. The complexity of arithmetic and data routing operations is analyzed for the methods given. It is shown that all methods give an O(P) speed-up in the arithmetic operations for a P processor array. However the methods incur an overhead in data organization. Theorems are presented that prove one method to be superior in minimizing this overhead for transforms of length N > P.

Fault-tolerance is undoubtedly a desirable property of any processor array. However, increased design and implementation costs should be expected when fault-tolerance is being introduced into the architecture of a processor array. When the processor array is implemented within a single VLSI chip, these cost increases are directly related to the chip silicon area. Thus, the increase in area should be weighed against the improved performance of the gracefully degrading fault-tolerant processor array. In addition, a larger chip area might reduce the wafer yield to an unaceptable level making the use of fault-tolerant VLSI processor arrays impractical. The objective of this paper is to devise performance measures for the evaluation of the effectiveness and area utilization of various fault-tolerant techniques. Another goal is to analyze the reduction in wafer yield and investigate the possibility of yield enhancement through redundancy.

The use of two parallel architectures, a single-instruction-stream, multiple-data-stream (SIMD) machine and a VLSI processor array, to implement an isolated word recognition system is examined. SIMD and VLSI processor array algorithms are written for each of the components of the recognition system. The component parallel algorithms are simulated along with two complete recognition systems, one composed of SIMD algorithms and other composed of VLSI processor array algorithms. The simulations show that a SIMD machine with 100 processing elements, each based on an 8-MHz MC68000, can perform isolated word recognition over a large vocabulary in real time. The VLSI processor array simulations show that an array using 51 cells, each containing a 12-MHz Intel 8051, can recognize speech in real time over a small vocabulary. The simulation revealed certain architectural features that can enhance the overall performance of the speech system. >

A class of novel fault-tolerant multiprocessor networks is proposed. These networks are restructurable in that they can assume different logical configurations to suit different problem environments. More importantly, this restructuriing capability is not altered even after the occurrence of faults. These networks are novel in that they uniquely combine certain desirable features, including self-routing of messages, dynamic reconfigurability, fault-tolerance, the ability to incorporate incremental extension, as well as the capacity to be partitioned with fault-tolerance. What is important about these fault-tolerant features is that they are built-in as an integral part of the design, and not as done traditionally, by means of redundancy.

The evolution of technology provides the opportunity of forming large processor ensembles working closely together. When decomposing application programs and assigning subtasks to different processors we expect not only high throughput, but also the fastest possible execution of each individual demand. The level of performance in these areas is strongly influenced by the hardware interconnection structure and by the communication software.

The regularity of systolic arrays and the potential for redundancy in residue number systems are used to provide fault tolerance in VLSI systems. The fault tolerance is concurrent with normal circuit operation and allows a continuous flow of correct data when a fault occurs. There is no interruption of valid data flow while the circuits are reconfigured. The technique also obviates the need for ultrahigh-reliability switches and switching control circuits. A fault-tolerant implementation of a finite-impulse-response filter with five residue channels, two of which are redundant, demonstrates the technique. As long as not more than one cell in each processing block is faulty, the filter outputs contain no errors. >

A two-parameter description of any computer is given that characterizes the performance of serial, pipelined, and array-like architectures. The first parameter (r∞) is the traditional maximum performance in megaflops, and the new second parameter (n½) measures the apparent parallelism of the computer. For computers with a single instruction stream (unicomputers), the relative performance of two algorithms on the same computer depends only on n½ and the average vector length of the algorithm. The performance of a family of FACR direct methods for solving Poisson's equation is optimized on the basis of this characterization.

An O(n) algorithm to sort n2elements on an Illiac IV-like n × n mesh-connected processor array is presented. This algorithm sorts the n2elements into row-major order and is an adaptation of Batcher's bitonic sort. A slight modification of our algorithm yields an O(n) algorithm to sort n2elements into snake-like row-major order. Extensions to the case of a j-dimensional processor array are discussed.

A new approach to the design of gracefully degradable processor arrays is discussed. Fault tolerance and graceful degradation are achieved by simultaneously reconfiguring the processor array and the algorithm in execution. Two types of algorithm reconfigurability are considered, namely, row reconfigurability (RR) and row-column reconfigurability (RCR). correspondingly, two array reconfiguration schemes are discussed, i.e., successive row elimination (SRE) and alternate row-column elimination (ARCE). It is shown that the computations of any algorithm executable in a processor array can always be (re) organized so that the resultant algorithm has the RR and/or RCR properties. Upper bounds on the increase in execution time of an algorithm due to reorganization of computations for reconfigurability are derived. Detailed analysis of performance and reliability is done for both SRE and ARCE reconfiguration schemes. These reconfiguration techniques are applicable to any processor array and suitable for VLSI technology.

A pure systolic realization of an algorithm for solving the n*n assignment problem is presented. This systolic algorithm can be implemented on an homogeneous hexagonal processor array and requires O(n/sup 2/) area complexity and O(n/sup 2/) time complexity. >

A parallel algorithm for sorting n data items in O(n) steps is presented. Its simple structure and the fact that it needs local communication only make it suitable for an implementation in VLSI technology. The algorithm is based on a merge algorithm that merges four subfiles stored in a mesh-connected processor array. This merge algorithm is composed of the perfect shuffle and odd-even-transposition sort. For the VLSI implementation a systolic version of the algorithm is presented. The area and time complexities for a bit-serial and a bit-parallel version of this implementation are analyzed.

The problem of finding the maximum of a set of values stored one per processor on a two-dimensional array of processors with a time-shared global bus is considered. The algorithm given by Bokhari is shown to be optimal, within a multiplicative constant, for this network and for other d-dimensional arrays. We generalize this model and demonstrate optimal bounds for finding the maximum of a set of values stored in a d-dimensional array with k time-shared global buses.