Search

A method for adapting shortperiodic sorting algorithms to defective arrays is presented. The approach is based on nearest neighbor interconnections and thus requires no additional wiring and switches for bypassing defective cells. The algorithm is adapted by reindexing, i.e., by modifying the ordering of the sorted sequence (indexing scheme). An efficient strategy for determining an indexing scheme is presented. A worst case sorting time of O( N ) is proved for these sorters. Simulation results show thatthe typical sorting time is only slightly higher than O(√N) and thus all advantages of the two-dimensional sorter are preserved. A sorting network implementing the adapted algorithm has the same topology as that for the algorithm in the fault-free case. The only modification is the programmability of the exchange operation of the cells. A simple and efficient method for testing the array is presented.

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