Defect-Tolerant Hierarchical Sorting Networks for Wafer-Scale Integration

In order to overcome the yield problem in wafer- scale integration (WSI), it is necessary to include redundancy and use more regular architectures for implementation. In this paper, we present a novel hierarchical defect-tolerant sorting network which meets the application requirements as well as the area-time complexity constraints. It is very regular in structure and hence easier to reconfigure than any existing sorting network with the same time complexity. Redundancy is provided at every level of the hierarchy. Hierarchical reconfiguration is implemented by replacing the defective cells with spare cells at the lowest level first, and reconfiguration goes to the next higher level if there is not enough redundancy at the current level. In addition to defect tolerance after fabrication, these redundant cells can also be used for single error correction at run time. Simulation is performed to demonstrate that significant yield improvements over other approaches can indeed be achieved.