Title :
Efficient exact spare allocation via Boolean satisfiability
Author :
Yu, Fang ; Tsai, Chung-Hung ; Huang, Yao-Wen ; Lin, Hung-Yau ; Lee, D.T. ; Kuo, Sy-Yen
Author_Institution :
Inst. of Inf. Sci., Acad. Sinica, Taipei, Taiwan
Abstract :
Fabricating large memory and processor arrays is subject to physical failures resulting in yield degradation. The strategy of incorporating spare rows and columns to obtain reasonable production yields was first proposed in the 1970s, and continues to play an important role in recent VLSI developments. The spare allocation problem (SAP) in general is known to be intractable, an efficient exact spare allocation algorithm has great value. We propose a new Boolean encoding of SAP and a new SAT-based exact algorithm SATRepair. We used a realistic fault distribution model to compare SATRepair´s performances against those of BDDRepair and several algorithms found in the literature. We found that a) our Boolean encoding of SAP facilitates the development of efficient exact SAP algorithms, and b) our SAT-based algorithm outperforms previous algorithms, especially for large problems.
Keywords :
Boolean functions; computability; fault diagnosis; integrated circuit testing; logic testing; Boolean encoding; Boolean satisfiability; SAT based exact algorithm; SATRepair algorithm; exact spare allocation; fault distribution model; memory arrays; processor arrays; spare allocation problem; Approximation algorithms; Chemical technology; Councils; Encoding; Fabrication; Information science; Lithography; Redundancy; Transistors; Very large scale integration;
Conference_Titel :
Defect and Fault Tolerance in VLSI Systems, 2005. DFT 2005. 20th IEEE International Symposium on
Print_ISBN :
0-7695-2464-8
DOI :
10.1109/DFTVS.2005.32