DocumentCode :
2584173
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
fYear :
2005
fDate :
3-5 Oct. 2005
Firstpage :
361
Lastpage :
370
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Defect and Fault Tolerance in VLSI Systems, 2005. DFT 2005. 20th IEEE International Symposium on
ISSN :
1550-5774
Print_ISBN :
0-7695-2464-8
Type :
conf
DOI :
10.1109/DFTVS.2005.32
Filename :
1544535
Link To Document :
بازگشت