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
fDate :
8/1/1994 12:00:00 AM
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;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
