A SPACE-EFFICIENT SHORT-FINDING ALGORITHM

Authors
SU SL BARRY CH LO CY
Citation
Sl. Su et al., A SPACE-EFFICIENT SHORT-FINDING ALGORITHM, IEEE transactions on computer-aided design of integrated circuits and systems, 13(8), 1994, pp. 1065-1068
Citations number
8
Categorie Soggetti
Computer Application, Chemistry & Engineering","Computer Science Hardware & Architecture
Journal title
IEEE transactions on computer-aided design of integrated circuits and systems → ACNP
ISSN journal
02780070
Volume
13
Issue
8
Year of publication
1994
Pages
1065 - 1068
Database
ISI
SICI code
0278-0070(1994)13:8<1065:ASSA>2.0.ZU;2-T
Abstract
A common method of locating electrical shorts in VLSI layouts is to bu ild a connectivity graph of the shorted net and then find the shortest path between the two offending signals. The memory requirement of thi s method is proportional to the size of the net, which can be quite la rge. This paper presents a dynamic graph construction algorithm that s ignificantly reduces the peak memory requirement. The algorithmic fram ework allows continuous trade-offs between run times and memory requir ements.