Fault-tolerant VLSI sorters

Parallel sorting algorithms have been proposed for VLSI implementation. Random defects in the silicon wafer and fabrication errors render processors in the wafer faulty, and may cause these algorithms to fail despite a significant number of nonfaulty processors. This paper presents two fault-tolerant pipelined sorting algorithms that would work on a wafer comprised of faulty and nonfaulty processors. Both the algorithms use O(n) processors and require O(n) time to sort n elements.