Search

We developed a multilane photonic spectral processor array integrated with a spatial and planar optical circuit platform. This device enables individual control of the optical power in the spatial and wavelength domains by controlling the phase pattern on liquid crystal on a silicon spatial light modulator and the heater electricity of a waveguide-based variable attenuator. We constructed a prototype device including an array of seven spectral processors. We transmitted 100-Gbps DP-QPSK signals over seven spans with a small optical-signal-to-noise ratio penalty of 0.05 dB, which suggests that the device can work in actual networks. As an application, we demonstrated gain equalizing of a multicore erbium-doped fiber amplifier (MC-EDFA). The device equalized the gain spectra of the MC-EDFA to an accuracy of ±0.8 dB over 30 nm.

We present a systematic methodology for exploring the design space of similarity distance computation in machine learning algorithms. Previous architectures proposed in the literature have been obtained using ad hoc techniques that do not allow for design space exploration. The size and dimensionality of the input datasets have not been taken into consideration in previous works. This may result in impractical designs that are not amenable for hardware implementation. The methodology presented in this work is used to obtain the 3-D computation domain of the similarity distance computation algorithm. A scheduling function determines whether an algorithm variable is pipelined or broadcast. Four linear scheduling functions are presented, and six possible 2-D processor array architectures are obtained and classified based on the size and dimensionality of the input datasets. The obtained designs are analyzed in terms of speed and area, and compared with previously obtained designs. The proposed designs achieve better time and area complexities.

A processor array containing 1000 independent processors and 12 memory modules was fabricated in 32-nm partially depleted silicon on insulator CMOS. The programmable processors occupy 0.055 mm2 each, contain no algorithm-specific hardware, and operate up to an average maximum clock frequency of 1.78 GHz at 1.1 V. At 0.9 V, processors operating at an average of 1.24 GHz dissipate 17 mW while issuing one instruction per cycle. At 0.56 V, processors operating at an average of 115 MHz dissipate 0.61 mW while issuing one instruction per cycle, resulting in an energy consumption of 5.3 pJ/instruction. On-die communication is performed by complementary circuit and packet-based networks that yield a total array bisection bandwidth of 4.2 Tb/s. Independent memory modules handle data and instructions and operate up to an average maximum clock frequency of 1.77 GHz at 1.1 V. All processors, their packet routers, and the memory modules contain unconstrained clock oscillators within independent clock domains that adapt to large supply voltage noise. Compared with a variety of Intel i7s and Nvidia GPUs, the KiloCore at 1.1 V has geometric mean improvements of 4.3 $\times$ higher throughput per area and 9.4 $\times$ higher energy efficiency for AES encryption, 4095-b low-density parity-check decoding, 4096-point complex fast Fourier transform, and 100-B record sorting applications.

Many important applications can be expressed as a group of fine-grained interconnected tasks, in which individual tasks require under 100 instructions and little data memory. KiloCore, an array of 1,000 independent processors and 12 memory modules, has been designed to efficiently support these applications, and has been fabricated in 32-nm PD-SOI CMOS. Each programmable processor occupies 0.055 mm 2 and supports energy-efficient computation of small tasks, requiring 17 mW to operate with a clock frequency of 1.24 GHz at 0.9 V. Processors may operate up to 1.78 GHz at 1.1 V, or down to 115 MHz and 0.61 mW at 0.56 V. Coarse-grained tasks are supported with the assistance of the independent memory modules, which can each supply 64 Kbytes of data and instructions to neighboring processors. Processors are connected using complementary circuit and packet-based networks, which offer a total array bisection bandwidth of up to 4.2 Tbps at 1.1 V. Fine-grained tasks are found to have low communication link densities in sampled applications, allowing a large majority of links to be assigned to the energy-efficient, high-performance circuit network.

Increasing the size of target arrays is beneficial to reuse fault-free processing elements (PEs) for reconfiguring 2-D mesh-connected processor arrays with faults. In this paper, we discuss the reconfiguration problem under the row and column rerouting constraint. We present a novel approach, making use of the idea of integer programming, for constructing larger size target arrays. Meanwhile, we propose a new method to deal with the fault-free processing elements in the physical row that is selected for exclusion. Compared with the state-of-arts algorithms, our method can make the fault-free PEs used as much as possible, which means the size of the target array can be significantly improved. Experimental results show that, compared with previous studies, the proposed algorithm achieves better results in terms of the usage rate of fault-free PEs in the host array.

A two-dimensional mesh-connected processor array is an extensively investigated architecture used in parallel processing. Massive studies have addressed the use of reconfiguration algorithms for the processor arrays with faults. However, the subarray generated by previous algorithms contains a large number of long interconnects, which in turn leads to more communication costs, capacitance and dynamic power dissipation. In this paper, we propose novel techniques, making use of the idea of network flow, to construct the high-performance subarray, which has the minimum number of long interconnects. First, we construct a network flow model according to the host array under a specific constraint. Second, we show that the reconfiguration problem of high-performance subarray can be optimally solved in polynomial time by using efficient minimum-cost flow algorithms. Finally, we prove that the geometric properties of the resulted subarray meet the system requirements. Simulations based on several random and clustered fault scenarios clearly reveal the advantage of the proposed technique for reducing the number of long interconnects. It is shown that, for a host array of size $512 \times 512$ , the number of long interconnects in the subarray can be reduced by up to 70.05 percent for clustered faults and by up to 55.28 percent for random faults with density of 1 percent as compared to the-state-of-the-art.

This paper presents the design and the VLSI implementation of an asynchronous cellular logic array for fast binary image processing. The proposed processor array employs trigger-wave propagation and collision detection mechanisms for binary image skeletonization, and Voronoi tessellation. Low power, low area, and high processing speed are achieved using full custom dynamic logic design. The prototype array consisting of 64 $\times$ 96 cells is fabricated in a standard 90 nm CMOS technology. The experimental results confirm the fast operation of the array, capable of extracting up to $2.78\times 10^{6}$ skeletons per second, consuming less than 1 nJ/skeleton. The asynchronous operation enables circular wave contours, which improves the quality of the extracted skeletons. The proposed asynchronous processing module consists of 24 MOS transistors and occupies $5.5\ \mu{\rm m}\times 7.4\ \mu{\rm m}$ area. Such array can be used as a co-processing unit aiding global binary image processing in standard pixel-parallel SIMD architectures in vision chips.

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}}$ .

Coarse grained arrays (CGAs) with run-time reconfigurability play an important role in accelerating reconfigurable computing applications. It is challenging to design on-chip communication networks (OCNs) for such CGAs with dynamic run-time reconfigurability whilst satisfying the tight budgets of power and area for an embedded system. This paper presents a silicon-proven design of a 64-PE circuit-switched OCN fabric with a dynamic path-setup scheme capable of supporting an embedded coarse-grained processor array. A proof-of-concept test chip fabricated in a 0.13 μm CMOS process occupies a silicon area of 23 mm2 and consumes a peak power of 200 mW @ 128 MHz and 1.2 Vcc, at room temperature. The OCN overhead consumes 9.4% of the area and 18% of the power of the total chip. Experimental results and analysis show that the proposed OCN fabric with its dynamic path-setup is suitable for use in an embedded CGA supporting fast run-time reconfigurability.

This paper describes an architecture and implementation of a digital vision chip that features mixed asynchronous/synchronous processing techniques. The vision chip is based on a massively parallel cellular array of processing elements, which incorporate a photo-sensor with an ADC and digital processing circuit, consisting of 64 bits of local memory, ALU, flag register and communication units. The architecture has two modes of operation: synchronous SIMD mode for low-level image processing based on local pixel data, and continuous-time mode for global operations. Additionally, the periphery circuits enable asynchronous address extraction, fixed pattern addressing and flexible, random access data I/O. A 19 × 22 proof-of-concept array has been manufactured in 0.35 μm CMOS technology. The chip delivers 15.6 GOPS for binary and 1 GOPS for grayscale operations dissipating 26.4 mW, while operating at 2.5 V and 75 MHz clock. Experimental measurements indicate that the presented concept favorably compares with other digital and analog vision chips. The results of low- and medium-level image processing on the chip are presented.

This paper presents a systematic methodology for exploring possible processor arrays of scalable radix 4 modular Montgomery multiplication algorithm. In this methodology, the algorithm is first expressed as a regular iterative expression, then the algorithm data dependence graph and a suitable affine scheduling function are obtained. Four possible processor arrays are obtained and analyzed in terms of speed, area, and power consumption. To reduce power consumption, we applied low power techniques for reducing the glitches and the Expected Switching Activity (ESA) of high fan-out signals in our processor array architectures. The resulting processor arrays are compared to other efficient ones in terms of area, speed, and power consumption.

As object recognition requires huge computation power to deal with complex image processing tasks, it is very challenging to meet real-time processing demands under low-power constraints for embedded systems. In this paper, a configurable heterogeneous multicore architecture with a dual-mode linear processor array and a cellular neural network on the network-on-chip platform is presented for real-time object recognition. The bio-inspired attention-based object recognition algorithm is devised to reduce computational complexity of the object recognition. The cellular neural network is utilized to accelerate the visual attention algorithm for selecting salient image regions rapidly. The dual-mode parallel processor is configured into single instruction, multiple data (SIMD) or multiple-instruction-multiple-data modes to perform data-intensive image processing operations while exploiting pixel-level and feature-level parallelisms required for the attention-based object recognition. The algorithm's hybrid parallelization strategy on the proposed architecture is adopted to obtain maximum performance improvement. The performance analysis results, using a cycle-accurate architecture simulator, show that the proposed architecture achieves a speedup of 2.8 times for the target algorithm over conventional massively parallel SIMD architecture at low hardware cost overhead. A prototype chip of the proposed architecture, fabricated in 0.13 mum complementary metal-oxide-semiconductor technology, achieves 22 frames/s real-time object recognition with less than 600 mW power consumption.

iVisual, an intelligent visual sensor SoC integrating 2790 fps CMOS image sensor and 76.8 GOPS, 374 mW vision processor, is implemented on a 7.5 mm t 9.4 mm die in a UMC 0.18 mum CMOS Image Sensor process. Light-in, answer-out SoC architecture is adopted to avoid possible privacy problems. A feature processor is designed to eliminate the dataflow mismatch between processor array and scalar processor to increase 36% of average throughput. To increase hardware utilization, an inter-processor synchronization scheme is adopted to increase 23% of average throughput. Memory access is reduced by 94% to save 726 mW of power consumption. A bitplane-based single port memory structure is adopted to reduce SRAM area. The 205 GOPS/W power efficiency and 1.16 GOPS/mm2 area efficiency are therefore achieved by use of the proposed techniques.

This paper presents a new processor array architecture for scalable radix 2 Montgomery modular multiplication algorithm. In this architecture, the multiplicand and the modulus words are allocated to each processing element rather than pipelined between the processing elements as in the previous architecture extracted by C. Koc. Also, the multiplier bits are fed serially to the first processing element of the processor array every odd clock cycle. By analyzing this architecture, we found that it has a better performance-in terms of area and speed-and lower power consumption than the previous architecture extracted by C. Koc.

A resonant adiabatic mixed-signal VLSI array delivers 480 GMACS (109 multiply-and-accumulates per second) throughput for every mW of power, a 25-fold improvement over the energy efficiency obtained when resonant clock generator and line drivers are replaced with static CMOS drivers. Losses in resonant clock generation are minimized by activating switches between the LC tank and DC supply with a periodic pulse signal, and by minimizing the variability of the capacitive load to maintain resonance. We show that minimum energy is attained for relatively wide pulse width, and that typical load distribution in template-based charge-mode computation implies almost constant capacitive load. The resonantly driven 256 times 512 array of 3-T charge-conserving multiply-accumulate cells is embedded in a template matching processor for image classification and validated in a face detection task.

Motion estimation (ME) is the most critical component of a video coding system, and it also dominates the major part of computation complexity and memory bandwidth. For H.264/AVC integer motion estimation (IME), this paper presents a novel memory-access and computation efficient full-search block-matching hardware architecture. With the highest level of on-chip data reuse, one-access for off-chip reference pixels is achieved, and the off-chip memory bandwidth is thus minimized. By distributed data caching and virtual connection of reference picture boundaries, the data traffic scheduling is simple, regular and efficient. The computation engine employs a two-dimensional (2-D) systolic processor array to calculate the absolute differences in single-instruction multiple-data (SIMD) manner, and 2-D adder trees to sum up the absolute differences, all with 100% utilization. The proposed architecture fully supports variable block-size matching of H.264/AVC, and can produce 41 sums of absolute differences (SADs) for one search point every cycle without bubble. The architecture is described in parameterized design, and an implementation for standard-definition digital TV encoding applications is presented. Theoretical analysis and experimental results show that, the proposed architecture can achieve the minimum off-chip memory bandwidth and the maximum computational performance.

We examine the diagnosis of processor array systems formed as two-dimensional arrays, with boundaries, and either four or eight neighbors for each interior processor. We employ a parallel test schedule. Neighboring processors test each other, and report the results. Our diagnostic objective is to find a fault-free processor or set of processors. The system may then be sequentially diagnosed by repairing those processors tested faulty according to the identified fault-free set, or a job may be run on the identified fault-free processors. We establish an upper bound on the maximum number of faults which can be sustained without invalidating the test results under worst case conditions. We give test schedules and diagnostic algorithms which meet the upper bound as far as the highest order term. We compare these near optimal diagnostic algorithms to alternative algorithms, both new and already in the literature, and against an upper bound ideal case algorithm, which is not necessarily practically realizable. For eight-way array systems with N processors, an ideal algorithm has diagnosability 3N/sup 2/3/-2N/sup 1/2/ plus lower-order terms. No algorithm exists which can exceed this. We give an algorithm which starts with tests on diagonally connected processors, and which achieves approximately this diagnosability. So the given algorithm is optimal to within the two most significant terms of the maximum diagnosability. Similarly, for four-way array systems with N processors, no algorithm can have diagnosability exceeding 3N/sup 2/3//2/sup 1/3/-2N/sup 1/2/ plus lower-order terms. And we give an algorithm which begins with tests arranged in a zigzag pattern, one consisting of pairing nodes for tests in two different directions in two consecutive test stages; this algorithm achieves diagnosability (3/2)(5/2)/sup 1/3/N/sup 2/3/-(5/4)N/sup 1/2/ plus lower-order terms, which is about 0.85 of the upper bound due to an ideal algorithm.

We present a single-chip integration of a CMOS image sensor with an embedded flexible processing array and dedicated analog-to-digital converter. The processor array is designed to perform convolution and transformation algorithms with arbitrary kernels. It has been designed to carry out the multiplication of analog image data with given digital kernel coefficients and to add up the results. The processor array is an analog implementation of a highly parallel architecture which is scalable to any desired sensor resolution while preserving video-rate operation. A prototype implementation has been realized in a 0.6-/spl mu/m CMOS technology. Switched current technique has been applied to obtain compact and robust circuits. The prototype's sensor resolution is 64 /spl times/ 128 pixels. The processor array occupies a small chip area and consumes only a small percentage of the power (250 /spl mu/W) of the whole image sensor.

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 single-chip rendering engine that consists of a DRAM frame buffer, a SRAM serial access memory, pixel/edge processor array and 32-b RISC core is proposed for low-power three-dimensional (3-D) graphics in portable systems. The main features are two-dimensional (2-D) hierarchical octet tree (HOT) array structure with bandwidth amplification, three dedicated network schemes, virtual page mapping, memory-coupled logic pipeline, low-power operation, 7.1-GB/s memory bandwidth, and 11.1-Mpolygon/s drawing speed. The 56-mm/sup 2/ prototype die integrating one edge processor, eight pixel processors, eight frame buffers, and a RISC core are fabricated using 0.35-/spl mu/m CMOS embedded memory logic (EML) technology with four poly layers and three metal layers. The fabricated test chip, 590 mW at 100 MHz 3.3 V operation, is demonstrated with a host PC through a PCI bridge.

Mesh-connected computers (MCCs) are a class of important parallel architectures due to their simple and regular interconnections. However, their performances are restricted by their large diameters. Various augmenting mechanisms have been proposed to enhance the communication efficiency of MCCs. One major approach is to add nonconfigurable buses for improved broadcasting. A typical example is the mesh-connected computer with multiple buses (MMB). We propose a new class of generalized MMBs, the improved generalized MMBs (IMMBs). We compare IMMBs with MMBs and a class of previously proposed generalized MMBs (GMMBs). We show the power of IMMBs by considering semigroup and prefix computations. Specifically, as our main result we show that for any constant 0

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.

The distance calculation in an image is a basic operation in computer vision, pattern recognition, and robotics. Several parallel algorithms have been proposed for calculating the Euclidean distance transform (EDT). Recently, Chen and Chuang proposed a parallel algorithm for computing the EDT on mesh-connected SIMD computers (1995). For an n/spl times/n image, their algorithm runs in O(n) time on a two-dimensional (2-D) n/spl times/n mesh-connected processor array. In this paper, we propose a more efficient parallel algorithm for computing the EDT on a reconfigurable mesh model. For the same problem, our algorithm runs in O(log /sup 2/n) time on a 2-D n/spl times/n reconfigurable mesh. Since a reconfigurable mesh uses the same amount of VLSI area as a plain mesh of the same size does when implemented in VLSI, our algorithm improves the result in [3] significantly.

A novel architecture named window-memory sharing processor array is proposed, which targets window operations in image processing. The architecture can be used not only for conventional image filtering, but also in practical window operations such as motion vector search in MPEG2. The derived architecture is flexible enough to satisfy user's requirement for either area or speed.

Digital signal processing algorithms with multiple shift-invariant dependence graphs (DGs) can be mapped to field programmable gate array hardware in many different types of systolic processor arrays. Because of the finite amount of hardware resources, the problem is to use a "right" amount of hardware in a specific configuration so to maximize the processing speed. In this paper, the problem of finding the right processor array configuration is formulated as a constrained optimization problem where the cost function includes not only the cost of individual processor arrays but also the cost of interfacing circuits. Three heuristic algorithms are presented for the optimization problem. Among them, both the Lth axial neighbor algorithm and the simulated annealing algorithm produce good results on a test case. Simulation results on the test case also indicate that the initial configuration is important in getting a good configuration for both algorithms. The Lth axial neighbor algorithm has the extra advantage of requiring less amount of performance tuning.

We illustrate the potential of techniques and results from the theory of network emulations to enhance the performance of a parallel architecture. The vehicle for this demonstration is a suite of algorithms that endow an N-processor bit-serial processor array A with a "meta-instruction" GAUGE k, which (logically) reconfigures A into an N/k-processor virtual machine B/sub k/ that has: 1) a datapath and memory bus whose emulated width is k bits, as opposed to A's 1-bit width and 2) an instruction set that operates on k-bit words, in contrast to A's instruction set, which operates on 1-bit words. In order to stress the strength of the approach, we show (via pseudocode) how our emulation techniques can be implemented efficiently even if A operates in strict SIMD mode, with only single-bit masking capabilities and with no indexed memory accesses. We describe at an algorithmic level how to implement our technique-including datapath conversion ("corner-turning") and the creation of the word-parallel instruction sets-on arrays of any regular network topology. We instantiate our technique in detail for arrays based on topologies with quite disparate characteristics: the hypercube, the de Bruijn network, and a genre of mesh with reconfigurable buses. Importantly, the emulations that underlie our technique do not alter the native machine's instruction set, hence allowing an invariant programming model across gauges.

We present an area-efficient parallel architecture that implements the constant-geometry, in-place Fast Fourier transform. It consists of a specific purpose processor array interconnected by means of a perfect unshuffle network. For a radix r transform of N=r/sup n/ data of size D and a column of P=r/sup p/ processors, each processor has only one local memory of N/rP words of size rD, with only one read port and one write port that, nevertheless, make it possible to read the r inputs of a butterfly and write r intermediate results in each memory cycle. The address generating circuit that permits the in-place implementation is simple and the same for all the local memories. The data how has been designed to efficiently exploit the pipelining of the processing section with no cycle loss. This architecture reduces the area by almost 50% of other designs with a similar performance.

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.

In this paper, we study the design of a coprocessor (CoP) to execute efficiently recursive algorithms with uniform dependencies. Our design is based on two objectives: 1) fixed bandwidth to main memory (MM) and 2) scalability to higher performance without increasing MM bandwidth. Our CoP has an access unit (AU) organized as multiple queues, a processor array (PA) with regularly connected processing elements (PEs), and input/output networks for data routing. Our design is unique because it addresses input/output bottleneck and scalability, two of the most important issues in integrating processor arrays in current systems. To allow processor arrays to be widely usable, they must be scalable to high performance with little or no impact on the supporting memory system. The use of multiple queues in AU also eliminates the use of explicit data addresses, thereby simplifying the design of the control program. We present a mapping algorithm that partitions a data dependence graph (DG) of an application into regular blocks, sequences the blocks through AU, and schedules the execution of the blocks, one at a time, on PA. We show that our mapping procedure minimizes the amount of communication between blocks in the partitioned DG, and sequences the blocks through AU to reduce the communication between AU and MM. Using the matrix-product and transitive-closure applications, we study design trade-offs involving 1) division of a fixed chip area between PA and AU, and 2) improvements in speedup with respect to increases in chip area. Our results show, for a fixed chip area, 1) that there is little degradation in throughput in using a linear PA as compared to a PA organized as a square mesh, and 2) that the design is not sensitive to the division of chip area between PA and AU. We further show that, for a fixed throughput, there is an inverse square root relationship between speedup and total chip area. Our study demonstrates the feasibility of a low-cost, memory bandwidth-limited, and scalable coprocessor system for evaluating recurrent algorithms with uniform dependencies.

The first half of this paper presents the design rationale for CNAPS, a specialized one-dimensional (1-D) processor array developed by Adaptive Solutions Inc. In this context, we discuss the problem of Amdahl's law which severely constrains special-purpose architectures. We also discuss specific architectural decisions such as the kind of parallelism, the computational precision of the processors, on-chip versus off-chip processor memory, and-most importantly-the interprocessor communication architecture. We argue that, for our particular set of applications, a 1-D architecture gives the best "bang for the buck", even when compared to the more traditional two-dimensional (2-D) architecture. The second half of this paper describes how several simple algorithms map to the CNAPS array. Our results show that the CNAPS 1-D array offers excellent performance over a range of IP algorithms. We also briefly look at the performance of CNAPS as a pattern recognition engine because many image processing and pattern recognition problems are intimately related.

Processor arrays, featuring modularity, regular interconnection, and high parallelism, are well suited for VLSI/WSI implementation and specific applications with high computational requirements. Error detection and recovery are important for some applications of processor arrays. Concurrent error detection (CED) techniques, which check normal system operations, are designed to detect errors caused by transient and intermittent faults, However, CED techniques typically suffer from costly hardware penalties or performance costs. This paper describes the periodic application of concurrent error detection (PACED) technique which allows the performance costs incurred through the use of time-redundant CED in processor array architectures to be reduced. The application of CED is varied in both time and space to provide probabilistic detection of errors in processor arrays. The probability of correctness of outputs from processor arrays is studied. Formulae are derived that predict, upon error detection, the amount of possibly erroneous output, for single processors, linear arrays and 2-dimensional mesh processor arrays. The results indicate that the error coverage can be surprisingly high when PACED is applied in processor arrays, e.g., 95% for checking performed 50% of the time.

Dictionary machine is an important VLSI system performing high speed data archival operations. In this paper, we present a design which can efficiently implement dictionary machines in VLSI processor arrays. In order to effectively process the operations of dictionary machine, hexagonal mesh is selected as the host topology in which two different networks for update and query operation are embedded. The proposed design is simple to implement as well as allows high throughput.

Processor arrays are frequently used to deliver high performance in many applications with computationally intensive operations. This paper presents the general parameter method (GPM), a systematic parameter-based approach for synthesizing such algorithm-specific architectures. GPM can synthesize processor arrays of any lower dimension from a uniform-recurrence description of the algorithm. The design objective is a general nonlinear and nonmonotonic user-specified function, and depends on attributes such as computation time of the recurrence on the processor array, completion time, load time, and drain time. In addition, bounds on some or all of these attributes can be specified. GPM performs an efficient search of polynomial complexity to find the optimal design satisfying the user-specified design constraints. As an illustration, we show how GPM can be used to find optimal linear processor arrays for computing transitive closures. We consider design objectives that minimize computation time, or processor count, or completion time (including load and drain times), and user-specified constraints on number of processing elements and/or computation/completion times. We show that GPM can be used to obtain optimal designs that trade between number of processing elements and completion time, thereby allowing the designer to choose a design that best meets the specified design objectives. We also show the equivalence between the model assumed in GPM and that in the popular dependence-based methods. Consequently, GPM can be used to find optimal designs for both models.

Algorithm-based fault tolerance (ABFT) can provide a low-cost error protection for array processors and multiprocessor systems. Several ABFT techniques (weighted check-sum) have been proposed to design fault-tolerant matrix operations. In these schemes, encoding/decoding uses either multiplications or divisions so that overhead is high. In this paper, new encoding/decoding methods are proposed for designing fault-tolerant matrix operations. The unique feature of these new methods is that only additions and subtractions are used in encoding/decoding. In this paper, new algorithms are proposed to construct error detecting/correcting codes with the minimum Hamming distance 3 and 4. We will show that the overhead introduced due to the incorporation of fault tolerance is drastically reduced by using these new coding schemes.

A methodology for partitioning and mapping of arbitrary uniform recurrence equations (UREs) expressed as computation graphs onto a given regular array is proposed. Deriving and based on a set of canonical dependencies together with two models of space projection, we give a general method of parallelization. The method has significant advantages in mapping an arbitrary computation graph onto a given processor array while preserving high efficiency in both communication and computation. >

We propose a novel implementation of the discrete cosine transform (DCT) and the inverse DCT (IDCT) algorithms using a CORDIC (coordinate rotation digital computer)-based systolic processor array structure. First, we reformulate an N-point DCT or IDCT algorithm into a rotation formulation which makes it suitable for CORDIC processor implementation. We then propose to use a pipelined CORDIC processor as the basic building block to construct l-D and 2-D systolic-type processor arrays to speed up the DCT and IDCT computation. Due to the proposed novel rotation formulation, we achieve 100% processor utilization in both 1-D and 2-D configurations. Furthermore, we show that for the 2-D configurations, the same data processing throughput rate ran be maintained as long as the processor array dimensions are increased linearly with N. Neither the algorithm formulation or the array configuration need to be modified. Hence, the proposed parallel architecture is scalable to the problem size. These desirable features make this novel implementation compare favorably to previously proposed DCT implementations. >

In this paper, we present an O(1) time algorithm to solve the minimum coloring problem defined on a set of intervals, which is also called the channel assignment problem. This problem has not been solved in O(1) time before, even on the idealistic CRCW PRAM model. For large-sized problems, it is desirable to have fast hardware-solutions. Our algorithm is based on the processor arrays with a reconfigurable bus system (abbreviated to PARBS) that consists of a processor array and a reconfigurable bus system. In order to solve this problem with constant time complexity, we first transform the "left-edge" channel assignment algorithm to the parenthesis-matching problem. Based on this novel scheme, we are able to explore constant-time parallel algorithms to solve the minimum coloring problem for n intervals, which is also called the channel assignment problem, on a PARBS with O(n/sup 2/) processors. >

The successive doubling method is an efficient procedure for the design of fast algorithms for orthogonal transforms of length N=r/sup n/, where the radix r is a power of 2. A partitioned systolic architecture is presented for the two standard radix successive doubling algorithms: decimation in time (DIT) and decimation in frequency (DIF). The index space of the data is projected onto the index space associated with a column of processors, interconnected using a perfect unshuffle (DIT) or shuffle (DIF) interconnection network, defined by permutations of the order log/sub 2/r. The result is a partitioned systolic array with Q processors (Q=r/sup i/, 0 >

Different standards for video compression require a flexible approach for integrating this functionality into multimedia terminals and computers. A programmable processor array (reduced instruction set computer, dataflow, four processor elements) and the corresponding decoding software are presented for this task. Specifically, the simulation results show that the use of fast algorithms combined with careful programming with respect to the statistical behavior of the coded video data leads to high decoding performance. Therefore, despite the fact that it is universally programmable, the processor array has about the same decoding performance/number of devices ratio as dedicated or hybrid architectures. This means that regular, scalable, and universally programmable processor arrays are competitive solutions for MPEG (Motion Picture Experts Group) video decompression and similar kinds of complex data processing algorithms. >

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. >

A general-purpose interconnection switch applicable to reconfigurable architectures is described. The switch has been used in the design of reconfigurable architectures and in processor arrays that require reconfigurable interconnections. The reconfigurable switch has the desirable properties that it is both scalable and C-testable. Furthermore, the switch is shown to be C-configurable: that is, the number of configurations required to test a network of switches is independent of the size of the network. Criteria are given for selecting built-in-test (BIT) techniques and implementations for reconfigurable architectures. Algorithms for generating configuration values and test data are presented. The BIT implementation is presented and analyzed and is shown to provide 100% fault coverage for single S-A-0, S-A-1, bridging, and high-impedance, permanent combinational faults. >

An overview of a VLSI system compiler that generates a highly parallel and fast processor array on a VLSI chip for general digital signal processing algorithms is described. The modularization and the synchronization of general digital signal processing algorithms in order to convert them into suitable forms for implementation by a processor array on a VLSI chip are described. Signal processing algorithms are modularized into the minimum number of inner-product modules by the proposed modularization procedure. Modularizing digital signal processing algorithms with low coefficient sensitivity parameters is also proposed. These modules are assigned to inner product processors. After processors have been placed and communication paths between them have been routed on a VLSI chip, the synchronization procedure derives a schedule for this VLSI system. The scheduling, which is free of both data conflict on interprocessor data links and inner-product operation execution conflict on processors, is investigated. >

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 >

A programmable trigger processor for the recognition of Cerenkov rings in a RICH (ring image Cerenkov) counter is described. It identifies open electron pairs and suppresses close conversion and Dalitz pairs within 20 mu s. More generally, the system can be used for correlating pixel images with pattern masks in order to locate all relatively well defined patterns of a certain type. The trigger processor consists of a systolic processor array of 160*176, i.e. 28160 identical processing elements (PEs) that filter out open electron pairs, and a pseudo adder array that determines whether there was at least one such pair. Ring identification is done by a two-dimensional correlation of the input image with a circle, yielding the probability of finding circles at certain locations. All PEs run synchronously at a clock frequency of 30 MHz. The total computing power therefore amounts to 844800 million operations/s, where a typical operation is the combination of a 6-b addition and a shift. >

Consideration is given to the development of a highly parallel, block-type, order-recursive algorithm for least-squares finite-impulse-response (LS FIR) filter identification and prediction. The computation of the required reflection coefficients is achieved by a technique that does not involve inner vector product operations. Its origin can be traced to the classical Schur algorithm for Toeplitz systems. The algorithm derived is simple and can be implemented on a linear array of O(p) modular processing elements with localized communication requirements, where p is the order of the system, which makes it suitable for VLSI implementation. In a parallel processing environment, the algorithm can be completed in O(p)+O(L) time units, where L is the length of the data block. A novel mode of operation that computes the reflection coefficients as well as the unknown filter's impulse response concurrently and on the same linear processor array is proposed. The algorithm is suitable either for processing a single block of data or for a block adaptive mode of operation, and it can track variations from block to block. The use of the algorithm for parameter adaptation on each time instant is discussed. >

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). >

Some aspects of a long-term parallel-processing research project (PACS, Pax, and Qcd Pax) begun in 1977 at Kyoto University and Hitachi Corporation's Nuclear Power Division are discussed. The discussion is based on an analysis of a number of papers, a book detailing this work, several visits to the project laboratory in Japan, and an examination of some programs that now run on cd Pax. The initial name, processor array for continuum simulation (PACS), was soon changed to Processor Array experiment, or Pax. Qcd Pax (for quantum chromodynamics) is the current running computer. The characteristics of the family are described, and the hardware, communication, and memory functions of the host computer, the use of four levels of parallelism programming, and performance are examined. >