Defect tolerant sorting networks for WSI implementation

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. A hierarchical fault tolerant sorting network which satisfies both application requirements and area-time complexity constraints is presented. It is very regular in structure and hence more easily reconfigurable than any existing sorting network with the same time complexity. Redundancy is provided at each level of the hierarchy. Hierarchical reconfiguration is implemented by replacing the faulty cells with spare cells at the lowest level first, and going to the next higher level to perform reconfiguration if there is not enough redundancy at the current level. In addition to defect tolerance after fabrication, these redundant cells can be used for single error correction at run time.