DocumentCode
1122349
Title
A space-efficient short-finding algorithm [VLSI layouts]
Author
Su, Shun-Lin ; Barry, Charles H. ; Lo, Chi-Yuan
Author_Institution
AT&T Bell Labs., Allentown, PA, USA
Volume
13
Issue
8
fYear
1994
fDate
8/1/1994 12:00:00 AM
Firstpage
1065
Lastpage
1068
Abstract
A common method of locating electrical shorts in VLSI layouts is to build a connectivity graph of the shorted net and then find the shortest path between the two offending signals. The memory requirement of this method is proportional to the size of the net, which can be quite large. This paper presents a dynamic graph construction algorithm that significantly reduces the peak memory requirement. The algorithmic framework allows continuous trade-offs between run times and memory requirements
Keywords
VLSI; circuit analysis computing; circuit layout CAD; fault location; graph theory; integrated circuit technology; IC design; VLSI layouts; connectivity graph; dynamic graph construction algorithm; electrical shorts; peak memory requirement reduction; space-efficient short-finding algorithm; Adders; Circuits; Frequency; Geometry; Heuristic algorithms; Very large scale integration; Workstations;
fLanguage
English
Journal_Title
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher
ieee
ISSN
0278-0070
Type
jour
DOI
10.1109/43.298043
Filename
298043
Link To Document