Fast search algorithms for reconfiguration problems
- 9 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15505774,p. 260-273
- https://doi.org/10.1109/dftvs.1991.199969
Abstract
A number of reconfiguration strategies have been proposed for increasing the yield of VLSI chips. In most cases the associated reconfiguration problems are NP-complete. Therefore, exhaustive search algorithms are generally used in order to find a solution when one exists. In this paper we present the notion of admissible sets and show how such sets can be used to significantly reduce the running time of many exhaustive search algorithms for reconfiguration problems. As an example, the authors find a class of admissible sets called excess-k critical sets that can be used in the design of fast search algorithms for the problem of reconfiguring redundant random access memories (RRAMs). They also consider applications to the problems of reconfiguring RRAMs with shared spares and reconfiguring redundant programmable logic arrays (RPLAs). Experimental results indicate that this approach is very powerful.<>Keywords
This publication has 13 references indexed in Scilit:
- Location and identification for single and multiple faults in testable redundant PLAs for yield enhancementPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Minimum fault coverage in reconfigurable arraysPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Fault covers in reconfigurable PLAsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the repair of redundant RAMsPublished by Association for Computing Machinery (ACM) ,1989
- On yield consideration for the design of redundant programmable logic arraysIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1988
- On the Repair of Redundant RAM'sIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- On the design of a redundant programmable logic array (RPLA)IEEE Journal of Solid-State Circuits, 1987
- Efficient Spare Allocation for Reconfigurable ArraysIEEE Design & Test of Computers, 1987
- A review of fault-tolerant techniques for the enhancement of integrated circuit yieldProceedings of the IEEE, 1986
- Data Structures and Network AlgorithmsPublished by Society for Industrial & Applied Mathematics (SIAM) ,1983