Search

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. [ABSTRACT FROM AUTHOR]

Effective fault tolerance techniques are essential for improving the reliability of multiprocessor systems. At the same time, fault tolerance must be achieved at high speed to meet the real-time constraints of embedded systems. While parallelism has often been exploited to increase performance, to the best of our knowledge, there has been no previously reported work on parallel reconfiguration of mesh-connected processor arrays with faults. This paper presents two parallel algorithms to accelerate reconfiguration of the processor arrays. The first algorithm reconfigures a host array in parallel in a multithreading manner. The threads in the parallel algorithm execute independently within a safe rerouting distance. The second algorithm is based on a divide-and-conquer approach to first generate the leftmost segments in parallel and then merge the segments in parallel. When compared to the conventional algorithm, simulation results from a large number of instances confirm that the proposed algorithms significantly accelerate the reconfiguration without loss of harvest. [ABSTRACT FROM AUTHOR]

This paper presents an efficient IrisCode classifier, built from phase features which uses AdaBoost for the selection of Gabor wavelets bandwidths. The final iris classifier consists of a weighted contribution of weak classifiers. As weak classifiers we use three-split decision trees that identify a candidate based on the Levenshtein distance between phase vectors of the respective iris images. Our experiments show that the Levenshtein distance has better discrimination in comparing IrisCodes than the Hamming distance. Our process also differs from existing methods because the wavelengths of the Gabor filters used, and their final weights in the decision function, are chosen from the robust final classifier, instead of being fixed and/or limited by the programmer, thus yielding higher iris recognition rates. A pyramidal strategy for cascading filters with increasing complexity makes the system suitable for real-time operation. We have designed a processor array to accelerate the computation of the Levenshtein distance. The processing elements are simple basic cells, interconnected by relatively short paths, which makes it suitable for a VLSI implementation. [ABSTRACT FROM AUTHOR]

Copyright of Canadian Journal of Electrical & Computer Engineering is the property of IEEE and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Shorter total interconnect and fewer switches in a processor array definitely lead to less capacitance, power dissipation and dynamic communication cost between the processing elements. This paper presents an algorithm to find a maximum logical array (MLA) that has shorter interconnect and fewer switches in a reconfigurable VLSI array with hard/soft faults. The proposed algorithm initially generates the middle (⌊ k/2⌋ th) logical column and then makes it nearly straight for the MLA with k logical columns. A dynamic programming approach is presented to compact other logical columns toward the middle logical column, resulting in a tightly-coupled MLA. In addition, the lower bound of the interconnect length of the MLA is proposed. Experimental results show that the resultant logical array is nearly optimal for the host array with large fault size, according to the proposed lower bound. [ABSTRACT FROM AUTHOR]

A high-speed analog VLSI image acquisition and low-level image processing system are presented. The architecture of the chip is based on a dynamically reconfigurable SIMD processor array. The chip features a massively parallel architecture enabling the computation of programmable mask-based image processing in each pixel. Extraction of spatial gradients and convolutions such as Sobel operators are implemented on the circuit. Each pixel includes a photodiode, an amplifier, two storage capacitors, and an analog arithmetic unit based on a four-quadrant multiplier architecture. A pixel proof-of-concept chip was fabricated in a 0.35 m standard CMOS process, with a pixel size of 35 m 35 m. A dedicated embedded platform including FPGA and ADCs has also been designed to evaluate the vision chip. The chip can capture raw images up to 10 000 frames per second and runs low-level image processing at a framerate of 2 000 to 5 000 frames per second. [ABSTRACT FROM AUTHOR]

This paper presents a systematic technique for expressing a string search algorithm as a regular iterative expression to explore all possible processor arrays for deep packet classification. The computation domain of the algorithm is obtained and three affine scheduling functions are presented. The technique allows some of the algorithm variables to be pipelined while others are broadcast over system-wide buses. Nine possible processor array structures are obtained and analyzed in terms of speed, area, power, and I/O timing requirements. Time complexities are derived analytically and through extensive numerical simulations. The proposed designs exhibit optimum speed and area complexities. The processor arrays are compared with previously derived processor arrays for the string matching problem. [ABSTRACT FROM AUTHOR]

We present fast and highly scalable parallel computations for a number of important and fundamental matrix problems on linear arrays with reconfigurable pipelined optical bus systems. These problems include computing the powers, the inverse, the characteristic polynomial. the determinant, the rank and an LU- and a QR-factorization of a matrix; multiplying a chain of matrices; and solving linear systems of equations. These computations are based on efficient implementation of the fastest sequential matrix multiplication algorithm, and are highly scalable over a wide range of system size. Such fast and sealable parallel matrix computations were not seen before on distributed memory parallel computing systems. [ABSTRACT FROM AUTHOR]

dBus-array(k, n) is an n-dimensional processor array of kn nodes connected via kn−1 dBuses. A dBus is a unidirectional bus which receives signals from a set of k nodes (input set), and transmits signals to a different set of k nodes (output set). Two optical implementations of the dBus-array(k, n) are discussed. One implementation uses the wavelength division multiplexing as in the wavelength division multiple access channel hypercube WMCH [7]. WMCH(k, n) and dBus-array(k, n) have the same diameter and about the same average internode distance, while the dBus-array requires only one tunable transmitter/receiver per node, compared to n tunable transmitters/receivers per node for the WMCH. The other implementation uses one fixed-wavelength transmitter/receiver per node and the dilated slipped banyan switching network (DSB) [17] to combine time division and wavelength division multiplexing. [ABSTRACT FROM AUTHOR]

We show that the product of two N × N boolean matrices can be calculated in constant time on an LARPBS with O(N3 / log N) processors. All data communications and computations are performed on the bit level. To the best of the author's knowledge, this is the first parallel boolean matrix multiplication algorithm that has constant execution time, and is executed on a distributed memory system with (N3) processors. By using our boolean matrix multiplication algorithm, it is shown that the transitive closure of a directed graph can be obtained in O(log N) time ( measured by bit level operations) on an LARPBS with O (N3 / log N) processors. To the best of our knowledge, this is the first parallel algorithm for tansitive closure of directed graphs with time complexity O(log N) (comparable to that of CRCW PRAM) and cost O (N3) on a realistic parallel computing model, which has no shared memory, and interprocessor communications are dealt with explicitly and efficiently. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM PUBLISHER]