Design and analysis of defect tolerant hierarchical sorting networks

A hierarchical modular sorting network which achieves a balance in area-time cost between the odd-even transposition sort and the bitonic sort is presented. It consumes less hardware than a single-level odd-even sorter and reduces the wire complexity of the bitonic sorter in VLSI or WSI (wafer-scale integration) implementation. The optimal number of levels in the hierarchy is evaluated, and the sorting capability of each level is derived so as to minimize the hardware overhead. The hierarchical sorting network is very regular in structure and hence defect tolerance capability can be included more easily than in any existing sorting network with the same time complexity. Redundancy is provided at every level of the hierarchy. Hierarchical reconfiguration is performed by replacing the defective cells at the bottom level with the spare cells first and repeating the process at the next higher level if there is not enough redundancy at the current level. Yield analysis is performed to demonstrate the effectiveness of the approach.<>