An Efficient Perfect Algorithm for Memory Repair Problems
Resource
Defect and Fault Tolerance in VLSI Systems, 2004. DFT 2004. Proceedings. 19th IEEE International Symposium on
Journal
19th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems (DFT’04)
Pages
306-313
Date Issued
2004-10
Author(s)
Abstract
Memory repair by using spare rows/columns to replace faulty rows/columns has been proved to be NP-complete. Traditional perfect algorithms are comparison-based exhaustive search algorithms and are not efficient enough for complex problems. To overcome the deficiency of performance, a new algorithm has been devised and presented in this paper. The algorithm transforms a memory repair problem into Boolean function operations. By using BDD (binary decision diagram) to manipulate Boolean functions, a repair function which encodes all repair solutions of a memory repair problem can be constructed. The optimal solution, if it exists, can be found efficiently by traversing the BDD of a repair function only once. The algorithm is very efficient due to the fact that BDD can remove redundant nodes, combine isomorphic subgraphs together, and have very compact representations of Boolean functions if a good variable ordering is chosen. The remarkable performance of the algorithm can be demonstrated by experimental results. Because a memory repair problem can be modeled as a bipartite graph, the algorithm may be useful for researchers in other fields such as graph theory.
Type
conference paper
File(s)![Thumbnail Image]()
Loading...
Name
01347853.pdf
Size
705.54 KB
Format
Adobe PDF
Checksum
(MD5):0e8350e30d1da8a62e62e80af1cde532