Search

In the image processing world the detection, location, and identification of explosive events is accomplished usually by single detectors, single element detector arrays, or higher cost cameras (primarily infrared). Imaging systems have been limited by the too few event frames, high costs of components, and poor false alarm rates. For the last three years NRL’s Advanced Techniques Digital Technologies section has been researching ultra-fast framerate explosive event detection. NRL has designed, fabricated, and tested a multi-sensor array of low cost camera modules, each with its own field programmable gate array processor, which are then networked together to implement a system capable of imaging explosive events at 16-30kHz framerates in real time. These camera modules work in the visible band and open up the possibility of exploiting 30-60 frames of an explosive event. With this array it is possible not only to image burning gases and high intensity flashes but also low signature moving effluent and airborne particles. By using processors behind each camera module it is possible to leverage different parts of the algorithm to accomplish computationally expensive operations on individual frames. Networking the array together allows further distribution of the processing for further temporal analysis. Finally all of the resulting images are sent to a central processor where the final parts of the algorithm are completed. The cost of this system once optimized for production will be close to that of acoustic systems but with much higher precision.

Video compression algorithms such as H.264 offer much potential for parallel processing that is not always exploited by the technology of a particular implementation. Consumer mobile encoding devices often achieve real-time performance and low power consumption through parallel processing in Application Specific Integrated Circuit (ASIC) technology, but many other applications require a software-defined encoder. High quality compression features needed for some applications such as 10-bit sample depth or 4:2:2 chroma format often go beyond the capability of a typical consumer electronics device. An application may also need to efficiently combine compression with other functions such as noise reduction, image stabilization, real time clocks, GPS data, mission/ESD/user data or software-defined radio in a low power, field upgradable implementation. Low power, software-defined encoders may be implemented using a massively parallel memory-network processor array with 100 or more cores and distributed memory. The large number of processor elements allow the silicon device to operate more efficiently than conventional DSP or CPU technology. A dataflow programming methodology may be used to express all of the encoding processes including motion compensation, transform and quantization, and entropy coding. This is a declarative programming model in which the parallelism of the compression algorithm is expressed as a hierarchical graph of tasks with message communication. Data parallel and task parallel design patterns are supported without the need for explicit global synchronization control. An example is described of an H.264 encoder developed for a commercially available, massively parallel memorynetwork processor device.

Optical Character Recognition (OCR) techniques are widely used in data/text entry, process automation. Decades of research efforts have made the accurate recognition of typewritten text largely accepted as a solved problem. Driven by practical usage demands, the low complexity and high performance implementation techniques of OCR systems are studied. Recent research shows that it may not be possible even for a simple OCR to run on a portable device without a specialized digital signal processor. In this paper, we present a highly data-parallelized implementation of OCR for typewritten text onto the linear processor array of the Xetal chip. Besides the preprocessing stage, the most computation intensive part of OCR recognizing individual characters is highly parallelized onto the Single Instruction Multiple Data (SIMD) engine of the Xetal chip, which can process a VGA-resolution text frame within one tenth of a second. In addition, different parallelization schemes are explored to make trade-off between the degree of parallelism and the costs of preprocessing to reorganize data to feed the SIMD engine and post-processing to assemble and collect results. The exploration of parallelized OCR application brings additional performance gain when mapped onto the linear processor array of the Xetal chip.

In the paper we present a massively parallel VLSI architecture for future smart CMOS camera chips with up to one billion transistors. To exploit efficiently the potential offered by future micro- or nanoelectronic devices traditional on central structures oriented parallel architectures based on MIMD or SIMD approaches will fail. They require too long and too many global interconnects for the distribution of code or the access to common memory. On the other hand nature developed self-organising and emergent principles to manage successfully complex structures based on lots of interacting simple elements. Therefore we developed a new as Marching Pixels denoted emergent computing paradigm based on a mixture of bio-inspired computing models like cellular automaton and artificial ants. In the paper we present different Marching Pixels algorithms and the corresponding VLSI array architecture. A detailed synthesis result for a 0.18 mm CMOS process shows that a 256×256 pixel image is processed in less than 10 ms assuming a moderate 100 MHz clock rate for the processor array. Future higher integration densities and a 3D chip stacking technology will allow the integration and processing of Mega pixels within the same time since our architecture is fully scalable.

We present a chip, which is suited for applications in data-communication areas as well as in image-processing applications. Through the combination of parallel signal gathering and processing, we save components and we can increase the processing rate. We think thereby on problems like pre processing in camera systems also called "intelligent sensor". The chip has a structure as follows. Every processor element contains an optical detector, a trans-impedance amplifier and a comparator. A digital logic is directly connected to these components. This logic realizes the programmable processing of the signals. Each processor element is connected to its four direct orthogonal neighbours within the processor array. The digital parts consist of a special processor. It realises simple hard-wired image algorithms. As an example for cooperation of the analogue and digital part we have implemented some morphologic operations. Our receiver consists of a 8×8 photodiode array. A data rate of 625 Mbit/s for an average optical power in the range of 25 µW to 500 µW is possible for a bit-error-rate of 10-9 per channel. Signal processing limits the frequency to 200 MHz for a processor element according to simulations. Using an image with a size of 6×6 according to parallel data transfer a data throughput of 7.2 GHz results.

Analog CNN array computer arises as an alternative to traditional digital processors in many industrial inspection like visual quality control of metal laminants, capable of make in a single chip Tera equivalent operations per second. A 4096 analog CNN processor array is able to perform complex space-time image analysis, being much faster than a camera- computer system in continuous inspection applications. Both chips have been implemented in CMOS technology and they are managed by a 32-bit high-performance low-cost micro- controller that closes the pan, tilt, lighting, focus and zoom loops required in the implementation of the active vision strategies. Several convolution masks for the Cellular Processors has been selected to detect particular changes in the texture, size, direction or orientation of the image entities, reprogramming `on the fly' the pixel resolution of shape when necessary. Laboratory results present these Cellular Processors and multiple resolution imager circuits as a promising architecture for visual inspection of industrial processes in real time.

Processor's architecture has great effect on the performance of whole processor array. In order to improve the performance of SIMD array architecture, we modified the structure of BAP (bit-serial array processor) processing element based on the BAP128 processor. The array processor chip of modified bit-serial array processor (MBAP in abbreviation) with 0.35 micrometers CMOS technology is designed for embedded image understanding system. This paper not only presents MBAP architecture, but also gives the architecture feature about this design. Toward basic macro instructions and low-level processing algorithms of image understanding, the performance of BAP and MBAP is compared. The result shows that the performance of MBAP has much improvement on BAP, at the cost of increasing 5% chip resource.

Many industrial inspection such visual quality control of metal laminates require billions of operations per second. Analog CNN array computer arises as an alternative to traditional digital processors, capable of make in a single chip Tera equivalent operations per second. A 4096 analog CNN processor array is able to perform complex space-time image analysis, being much faster than a camera-computer system in continuous inspection applications. Both chips have been implemented in CMOS technology and they are managed by a 32- bit high-performance low-cost micro-controller that closes the pan, tilt, lighting, focus and zoom loops required in the implementation of the active vision strategies. Several convolution masks for the Cellular Processors has been selected to detect particular changes in the texture, size, direction or orientation of the image entities, reprogramming 'on the fly' the pixel resolution or shape when necessary. Laboratory results present these Cellular Processors and multiple resolution imager circuits as a promising architecture for visual inspection of industrial processes in real time.© (2000) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

In this paper, we introduce the architecture of a new embedded field programmable processor array (E-FPPA) which consists of a low-power multiprocessor system embedded with standard programmable logic blocks and memory. Each block (processor, programmable logic,...) is coupled to a transfer controller responsible of all the transfers between blocks. Instead of using a classical crossbar interconnection network, we propose a low cost hierarchical ring which combines simple interface and high performance communications when data locally is observed. This architecture is fully scalable and is based on a numa (non- uniform access time memory) multiprocessor scheme. The core of the architecture is a small RISC processor (actually, a very low power CoolRisc has been chosen) which is embedded with programmable logic blocks (similar to standard CPLD or FPGA), static RAMs and other devices (DSP coprocessor, peripherals, ...). By using the 8-bit CoolRisc processor, an E-FPPA including a cluster of 16 processors, 16 TC, 4 Kbytes data memory and 5.5 Kbytes program memory for each processor can deliver up to 3200 Mops at 100 MHz. The chip size has been evaluated in 0.35 micrometers to 52 mm2.© (1998) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

This article introduces a model of MPP system by the aspects of overall machine architecture, processor interconnection net, algorithm model. This system adopts some basic design principles of MPP system, while it has its own characteristics in concrete structure. For example, in the overall machine architecture MPP system is used as co- processor and a high performance personal computer is used as host machine; the system adopts distributing memory principle, uses register as local memory, uses column buffer as the adapter between shared memory and processor array. This system is mainly used for developing data parallelism. Under the CU (Control Unit) centralized controlling, all processors execute same instruction. This kind of structure is very suited for different kinds of image processing, such as convolution, transformation and median filtering. Another characteristic of this system is scalability. It can dynamically expand with question's size in logic and physical sense. In addition, this article uses two laws of parallel processing. Amdahl law and Gustafson law, to explain why the MPP system is suited for primitive image understanding.© (1998) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

We propose a pipelined asynchronous time division multiplexing optical bus. Such a bus can use one of the two hardwared priority schemes, the linear priority scheme and the round-robin priority scheme. Our simulation results show that the performances of our proposed buses are significantly better than the performances of known pipelined synchronous time division multiplexing optical buses. We also propose a class of processor arrays connected by pipelined asynchronous time division multiplexing optical buses. We claim that our proposed processor array not only have better performance, but also have better scalabilities than the existing processor arrays connected by pipelined synchronous time division multiplexing optical buses.

A new architecture for real-time MPEG-2 encoding/decoding is presented in this paper. This architecture is based on an array of TI MVPs. The main feature of this architecture is its programmability. The inherent parallelism of the MPEG-2 algorithm is investigated in order to map it to the processor array. An I/O algorithm for the major encoding function, motion estimation, is developed to demonstrate the possibility of overlapping processing and I/O.© (1997) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

We present a new family of architectures for processor arrays to implement Jacobi SVD which allow systolic loading and unloading of input and result matrices. Unlike most of the previous SVD arrays in the literature, our architectures do not require special handling of external I/O and hence are closer to the traditional concept of systolic architectures. The boundary processors communicate with the host the same way any of the interior processors communicate with their neighbors. The arrays are surprisingly uniform and simple. The various architectures in the family represent different throughput-hardware tradeoffs corresponding to the degree to which the multiple sweeps have been unrolled and determine the number of independent SVDs which may be pipelined on the array. We achieved systolic loading by using the flexibility provided by the cyclic Jacobi method on the order in which pivot pairs may be chosen. The array operates on the matrix data even as it is being loaded. Once the pipeline is full, the ordering is very similar to odd-even ordering. Our ordering is equivalent to cyclic-by-rows ordering and hence the algorithm is guaranteed to converge. Our systolic loading scheme is very important in an I/O limited system, since it allows more communication to occur in parallel, where the communication includes the loading and unloading operations. The array with the highest throughput in our family of architectures, which implement one-sided Jacobi (either Hestenes' method or Eberlein and Park's method), is a linear array of processors with unidirectional links between neighbors. The architectures with lower throughput require fewer processors connected in a ring, allowing data to recirculate among the processors. The input matrix is loaded one column at a time from the left and the results stream out one column at a time from the right.

The Accurate Automation Corporation (AAC) neural network processor (NNP) module is a fully programmable multiple instruction multiple data (MIMD) parallel processor optimized for the implementation of neural networks. The AAC NNP design fully exploits the intrinsic sparseness of neural network topologies. Moreover, by using a MIMD parallel processing architecture one can update multiple neurons in parallel with efficiency approaching 100 percent as the size of the network increases. Each AAC NNP module has 8 K neurons and 32 K interconnections and is capable of 140,000,000 connections per second with an eight processor array capable of over one billion connections per second.© (1994) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

We consider the problem of linear object extraction from binary and graylevel images. For this purpose we use mathematical morphology and some related filters. They are efficiently implemented on the neighborhood connected processor array and are based on Bresenham's approximation of arbitrary linear element in a square discrete grid.© (1993) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

Machine vision algorithms are partitioned into three distinct levels: low level (image to image transformation), intermediate level (image to symbolic transformations) and high level (symbolic manipulation). Low level image processing requires a large amount of data manipulation which can be cost effectively processed using a linear processor array. When performing intermediate level operations, however, the linear processor array is liable to generate communications bottlenecks which reduce its efficiency. The aim of this work is to enhance the linear processor array architecture for intermediate level processing. An investigation of the matching of intermediate level algorithms to appropriate computer architectures is presented. Consequently an augmented tree-structured MIMD processor network is devised, tightly coupling the low, intermediate, and high level image processing stages. The network is realized using the Inmos Transputer. A representative selection of intermediate level algorithms are executed on the machine. The performance of the realized network is compared to several commercially available systems. As the network is increased in size, it is shown that the communications bottlenecks in the linear processor array are reduced to a negligible amount. Future enhancements to the system are finally considered, including automated object and feature recognition, and a tree structured hierarchy of Prolog processes.© (1992) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

Automatic road detection is an important part in many scene recognition applications. The extraction of roads provides a means of navigation and position update for remotely piloted vehicles or autonomous vehicles. Roads supply strong contextual information which can be used to improve the performance of automatic target recognition (ATh) systems by directing the search for targets and adjusting target classification confidences. This paper will describe algorithmic techniques for labeling roads in high-resolution infrared imagery. In addition, realtime implementation of this structural approach using a processor array based on the Martin Marietta Geometric Arithmetic Parallel Processor (GAPPTh) chip will be addressed. The algorithm described is based on the hypothesis that a road consists of pairs of line segments separated by a distance "d" with opposite gradient directions (antiparallel). The general nature of the algorithm, in addition to its parallel implementation in a single instruction, multiple data (SIMD) machine, are improvements to existing work. The algorithm seeks to identify line segments meeting the road hypothesis in a manner that performs well, even when the side of the road is fragmented due to occlusion or intersections. The use of geometrical relationships between line segments is a powerful yet flexible method of road classification which is independent of orientation. In addition, this approach can be used to nominate other types of objects with minor parametric changes.

The amount of data generated by computed tomography (CT) scanners is enormous, making the image reconstruction operation slow, especially for 3-D and limited-data scans requiring iterative algorithms. The inverse Radon transform, commonly used for CT image reconstructions from projections, and the forward Radon transform are computationally burdensome for single-processor computer architectures. Fortunately, the forward Radon transform and the back projection operation (involved in the inverse Radon transform) are easily calculated using a parallel pipelined processor array. Using this array the processing time for the Radon transform and the back projection can be reduced dramatically. This paper describes a unified, pipelined architecture for an integrated circuit that computes both the forward Radon transform and the back projection operation at a 10 MHz data rate in a pipelined processor array. The trade-offs between computational complexity and reconstruction error of different interpolation schemes are presented along with an evaluation of the architecture's noise characteristics due to finite word lengths. The fully pipelined architecture is designed to reconstruct 1024 pixel by 1024 pixel images using up to 1024 projections over 180 degrees. The chip contains three pipelined data-paths, each five stages long, and uses a single multiplier.© (1990) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

A focal-plane-array chip designed for real-time, general-purpose, image preprocessing is reported. A 48 X 48 pixel detector array and a 24 X 24 processing element processor array are monolithically integrated on the chip. The analog, charge-coupled device-based VLSI chip operates in the charge domain and has sensing, storing, and computing capabilities. It captures the image data and performs local neighborhood operations. The processor array is digitally programmable and uses a single-instruction, multiple-data parallel architecture. Various image preprocessing tasks such as level shifting, gain adjustment, thresholding, smoothing, sharpening, and edge detection can be implemented and A/D conversion can be performed prior to output. Frame-to-frame operations such as motion detection and tracking can be implemented as well. The chip was fabricated with a double-poly, double-metal process in a commercial CCD foundry. The prediction of the performance is based on numerical analysis and experimental results of testing a prototype charge-coupled computer. Operating at a modest clock frequency of 25 MHz, the chip is projected to achieve an internal throughput as high as 576 Mops with a 54 dB dynamic range (9-bit equivalent accuracy). The simulation of an edge detection algorithm implemented by the chip is presented. The power dissipation is estimated to be 20 mW and the total size of the 59-pad chip is 9.4 X 9.4 mm2.

Systolic architectures for eigenvalues and singular values are discussed. One "triangular" processor array and associated algorithms for computing the QR-decomposition, the singular value decomposition, the generalized singular value decomposition and the CS-decomposition are described in detail.

The paper discusses mapping of a Fast Fourier Transform (FFT), Haar Transform and Hadamard Transform algorithms onto a small, two-dimensional, mesh-connected array of processors. The FFT algorithm is an in-place, decimation in frequency, Cooley-Tuckey algorithm in radix 2 and radix 4 versions applied to multidimensional, complex inputs. The data flow of the algorithms has been implemented on the array using an efficient, regular data transfer pattern, uniform for all the algorithms. The inputs and constants used in the algorithms are prestored in the local memories of the processors. The mapping makes it possible to reduce significantly the number of memory locations needed for the constants. A partitioning scheme has been developed for the algorithms which allows us to execute them with inputs of arbitrary size on a small processor array. Also an algorithm has been proposed for the processor array, which efficiently unscrambles the bit reversed output of the FFT algorithm. The processors of the array have East, West, North, South interconnections with their nearest neighbors. The local memory of the processors is small, on the order of hundreds of locations. The processors are controlled in Single Instruction Multiple Data Stream (SIMD) mode and can be selectively disabled using simple masks, consisting of combinations of rows or columns.

Because processor arrays have only limited connections between neighboring processors, fault-tolerance schemes may require additional interconnect, switching and control hardware in order to allow for reconfiguration when faults occur. In general, the larger the reconfiguration capability, the greater is the probability that a processor array can survive a given distribution of faults. In other words, the coverage of the reconfiguration procedure increases directly with the amount of extra hardware required to support it. However, this is true only if the added hardware does not fail itself. For this reason and depending on, among other factors, the size of the processor array and the size of each processor, dis-tinct reconfiguration schemes may be best suited for different arrays. Also, in general, previously proposed schemes may still result in unacceptably low reliabilities in very large processor arrays. This paper proposes a class of reconfiguration schemes which have a hierarchical nature. According to this approach, a processor array is logically partitioned into smaller subarrays and, once faults occur, reconfiguration takes place within each of the subarrays (where faults are present) if possible and, otherwise, the full subarray is replaced by a spare subarray. Arrays of this type are referred to as bi-level fault-tolerant processor arrays and, by allowing several levels of reconfiguration, multi-level arrays can be defined similarly. While several levels of reconfiguration are possible, the case of two levels is emphasized in this paper. Also, the reconfiguration schemes used in each level are not necessarily identical. This class of hierarchical reconfiguration schemes provide much higher reliability than previously proposed ones, particularly in the case of very large arrays. To design a hierarchical reconfiguration scheme for a given processor array it is necessary to choose the size of the subarrays for every level in the hierarchy as well as the reconfiguration scheme at that level. A design methodology is provided which mathematically solves these problems, i.e. it enables the choice of the subarrays size and the reconfiguration scheme to be used at each level so to obtain a processor array with optimal reliability.

The architecture of an electronic mesh array for image processing by simulated annealing is described. On the algorithm side, it is well suited to cases where the input data is a grey-level picture, the output data is a binary picture, and the energy model is a generalization of the Ising model with external field. The example of digital halftoning is covered. On the implementation side, this architecture is intended for VLSI monolithic integration. Its PE uses both analog and digital devices, and is specifically designed to take advantage of an optical random number generator. These features result in a compact processor array with near real time performances for binary pictures stochastic relaxation.

Current and future adaptive optical systems that utilize deformable or segmented mirrors as the adaptive element may require that matrix calculations be performed on a real time basis to keep the mirror properly figured. A two-dimensional array of processor nodes (the "Solver") has been developed that is capable of computing the required positions of several hundred to several thousand mirror actuator elements in a real time environment. The processor has been demonstrated as a two-board system capable of performing 3.4 x 109 integer operations per second, and with input/output (I/O) bandwidth of 200 Mbytes/sec. The architecture is well suited to matrix algebra and iterative type operations and is scalable to larger computational rates. System costs have been kept low and software tools have been developed to ease the implementation of algorithms. This work has been performed under contract with the Office of Naval Research, and the authors thank them for their support.

A focal-plane-array chip designed for real-time, general-purpose, image preprocessing is reported. A 48 X 48 pixel detector array and a 24 X 24 processing element processor array are monolithically integrated on the chip. The analog, charge-coupled device-based VLSI chip operates in the charge domain and has sensing, storing, and computing capabilities. It captures the image data and performs local neighborhood operations. It is digitally programmable and uses a single instruction, multiple data parallel architecture. Various image preprocessing tasks such as level shifting, gain adjustment, thresholding, smoothing, sharpening, and edge detection can be implemented. Frame-to-frame operations such as motion detection and tracking can be implemented as well. It can be programmed to perform A/D conversion prior to output. The chip was fabricated with a double-poly, double-metal process in a commercial CCD foundry. The prediction of the performance is based on numerical analysis and experimental results of testing a prototype charge-coupled computer. Operating at a modest clock frequency of 25 MHz, the chip is projected to achieve an internal throughput as high as 576 Mops with a 54 dB dynamic range (9-bit equivalent accuracy). The total power dissipation is estimated to be 20 mW. The total size of the 59-pad chip is 9.4 X 9.4 mm2.

Hough transform is an effective method for the detection of the shape of object boundaries in image pattern analysis. Since the Hough transform is very computation intensive, it is essen-tial to parallelize the computation. However, an effective parallel algorithm is harder to obtain because it requires global informa-tion. In this paper we present an efficient parallel Hough transform algorithm for the detection of straight lines using mesh connected processor arrays. While other parallel algo-rithms take either 0(n2) or 0(n2) time, where n is the number of distinct values of a parameter and N is the number of edge pixels, our algorithm takes 0(n) time.

An architecture and alforithms for a VLSI computer for back-projection image reconstruction are described. The computer consists of multiple identical back-projection processors connected in a linear array. Image pixels are pumped through the processor array, collecting at each processor a contribution to the image from one of its projections. Given one back-projection processor for each image projection, the entire reconstruction can be performed in a time comparable to that needed for sequential access of all image pixels. Implementation of a MOS VLSI back-projection processor is well advanced with working designs obtained for most processor subsystems. The processor incorporates a linear interpolator to estimate values between projection samples and accommodates non-linearity in the geometrical relationship between an image and its projection.

A programmable two-dimensional (2D) processor array is fault-tolerant if faulty processors can be detected, and then avoided during program execution. With VLSI the number of processors that can be implemented in a 2D array increases, and as a result more and more cells can be devoted for fault tolerance purposes. In the literature there are many schemes on detecting faulty processors and reconfiguring data routing to avoid them. However, an efficient implementation of these schemes on a 2D array can be an extremely difficult task if application, fault detection and reconfiguration must all be considered at the same time. The virtual channels mechanism of this paper allows these concerns to be dealt with separately and efficiently. An application or fault detection program may assume that every logical connection between processors is implemented by a dedicated physical connection. A physical connection is composed of a sequence of virtual channels. Since the number of virtual channels between any two processors is not bounded by the number of available physical channels, all dedicated physical connections required by the program can be implemented. The mapping of logical connections to physical connections and the scheduling of a physical channel to implement multiple virtual channels are totally transparent to a program, and can be optimized independently. Various fault tolerance schemes are now readily implementable without programming difficulty. For example, it is straightforward to have concurrent execution of application and fault detection programs on the same 2D array. A switch architecture, suitable for VLSI implementation, is presented for implementing the virtual channels mechanism. The switch captures all the architectural features needed to implement the mechanism and can be used with different processors. By using multiple copies of this switch, a variety of fault-tolerant 2D arrays can be formed. In particular the switch architecture is planned to be used in building a fault-tolerant 2D Warp array.

In a recent paper [Lowry 81], we described an architecture for a computer vision rectangular processor array that is suitable for VLSI implementation. In this paper we will review that architecture and discuss extensions to it and present results of an array simulator applied to vision algorithms. We will also present an algorithm for re-routing an array with bad processors into a working subset of the array, making it feasible to implement a large array on one wafer-sized chip.© (1983) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

A VLSI Multiplication Oriented Processor (MOP) element has been designed for use in array-based 1-D and 2-D modern digital radar applications. We describe how this chip can be used to provide extremely high throughput rates for problems such as beam forming, adaptive Doppler filtering, and high resolution direction finding.

The computations of eigenvalues and singular values are key to applications including signal and image processing. Since large amounts of computation are needed for these algorithms, and since many digital signal processing applications have real-time requirements, many different special-purpose processor array structures have been proposed to solve these two algorithms. This paper develops a new methodology to incorporate fault tolerance capability into processor arrays which have been proposed for these problems. In the first part of this paper, earlier techniques of algorithm-based fault tolerance are applied to QR factorization and QR iteration. This technique encodes input data at a high level by using the specific property of each algorithm and checks the output data before they leave the systems. In the second part of the paper, special properities of eigenvalues and singular values are used to achieve the error detection without encoding the input data. Fault location and reconfiguration are performed only after an erroneous signal has been detected. The introduced overhead is extremely low in terms of both hardware and time redundancy.

The RATS algorithm is a gray level threshold selection method which uses simple image statistics consisting of sums of products of gray level and gradient information accummulated over appropriate image areas. The method calculates a threshold in a very direct manner and avoids the often unreliable analysis of a gray level histogram. The contribution of individual pixels are largely local and independent and the method is therefore particularly well suited for implementation on a parallel hierarchic processor array such as a quadtree pyramid. Simple control strategies can be devised to select the most appropriate thresholds for individual pixels from thresholds at a series of different spatial scales. In this paper we consider how a SIMD processor array can be used to efficiently implement the RATS algorithm.

A class of reconfiguration schemes for fault-tolerant processor arrays is proposed and studied. According to these schemes, a processor array that is inoperative due to presence of faulty processors is restructured by logically "spreading" faulty processors as evenly as possible throughout the array. From the characteristics of the proposed reconfiguration schemes and the processor array structures for which they are intended, closed form expressions for processor interconnection requirements are derived and implementation issues are discussed. Next, a special case of the proposed reconfiguration schemes is studied and simulated assuming two different array structures. For one of the array structures, simulation results show that the probability of survival achieved by the reconfiguration scheme is close to 1 for up to a number of faults that equals 50% of the total number of spare processors. For a larger number of faults the probability of survival degrades rapidly. On the other hand, for the other array structure, simulation results show that the probability of survival is lower than that of the first structure when the number of faults is less than 90% of the total number of spares; it is higher otherwise.