Design and Analysis of Defect Tolerant Hierarchical Sorting Networks

A novel 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 to minimize the hardware overhead. The hierarchical sorting network is very regular in structure and hence is easy to include defect tolerance capability than 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 repeat the same process in the next higher level if there is not enough redundancy at the current level. Yield analysis is performed to demonstrate the effectiveness of our approach.