Fault-tolerant sorting using VLSI processor arrays

Parallel sorting is one of the most important computational problem. An efficient scheme for fault tolerant sorting is proposed, which is based on odd-even transposition sort with a linear array of processing elements (PEs). The faults in the array are tolerated as far as no more than a single compare-and-swap (CS) module fault exists in any three consecutive CS modules using the voting approach. The hardware overhead is basically an additional register and a voter per PE. The scheme can also be easily adapted to a two-dimensional processor arrays, using Shear sort. If the proposed approach is employed for only error detection, then multiple faults can be detected in each step of computation using only a simple XOR circuitry in each PE