Fast algorithm for VLSI net extraction

Mario A. Lopez, Ravi Janardan, Sartaj Sahni

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Net extraction is crucial in VLSI design verification. Current algorithms for net extraction do not exploit the fact that the number, c, of different orientations of the line segments or polygon edges in a practical VLSI mask design is small relative to the number, n, of segments or edges. Instead they rely on computing all intersections in the input and hence take time that is at least proportional to the number of intersections. In this paper we develop a simple and practical algorithm for net extraction that runs in O(cn log n) time and O(n) space, which is optimal for fixed c. Experiments indicate that the algorithm will generally outperform existing algorithms on practical VLSI designs. We expect that the techniques presented will be useful in other VLSI/CAD problems that operate with restricted orientation geometries.

Original languageEnglish (US)
Title of host publicationProc 1993 IEEE ACM Int Conf Comput Aided Des
Editors Anon
PublisherPubl by IEEE
Pages770-774
Number of pages5
ISBN (Print)0818644923
StatePublished - Dec 1 1993
EventProceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design - Santa Clara, CA, USA
Duration: Nov 7 1993Nov 11 1993

Other

OtherProceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design
CitySanta Clara, CA, USA
Period11/7/9311/11/93

Fingerprint

Masks
Computer aided design
Geometry
Experiments

Cite this

Lopez, M. A., Janardan, R., & Sahni, S. (1993). Fast algorithm for VLSI net extraction. In Anon (Ed.), Proc 1993 IEEE ACM Int Conf Comput Aided Des (pp. 770-774). Publ by IEEE.

Fast algorithm for VLSI net extraction. / Lopez, Mario A.; Janardan, Ravi; Sahni, Sartaj.

Proc 1993 IEEE ACM Int Conf Comput Aided Des. ed. / Anon. Publ by IEEE, 1993. p. 770-774.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Lopez, MA, Janardan, R & Sahni, S 1993, Fast algorithm for VLSI net extraction. in Anon (ed.), Proc 1993 IEEE ACM Int Conf Comput Aided Des. Publ by IEEE, pp. 770-774, Proceedings of the 1993 IEEE/ACM International Conference on Computer-Aided Design, Santa Clara, CA, USA, 11/7/93.
Lopez MA, Janardan R, Sahni S. Fast algorithm for VLSI net extraction. In Anon, editor, Proc 1993 IEEE ACM Int Conf Comput Aided Des. Publ by IEEE. 1993. p. 770-774
Lopez, Mario A. ; Janardan, Ravi ; Sahni, Sartaj. / Fast algorithm for VLSI net extraction. Proc 1993 IEEE ACM Int Conf Comput Aided Des. editor / Anon. Publ by IEEE, 1993. pp. 770-774
@inproceedings{97c378eef7c44125bf1297e223c184cc,
title = "Fast algorithm for VLSI net extraction",
abstract = "Net extraction is crucial in VLSI design verification. Current algorithms for net extraction do not exploit the fact that the number, c, of different orientations of the line segments or polygon edges in a practical VLSI mask design is small relative to the number, n, of segments or edges. Instead they rely on computing all intersections in the input and hence take time that is at least proportional to the number of intersections. In this paper we develop a simple and practical algorithm for net extraction that runs in O(cn log n) time and O(n) space, which is optimal for fixed c. Experiments indicate that the algorithm will generally outperform existing algorithms on practical VLSI designs. We expect that the techniques presented will be useful in other VLSI/CAD problems that operate with restricted orientation geometries.",
author = "Lopez, {Mario A.} and Ravi Janardan and Sartaj Sahni",
year = "1993",
month = "12",
day = "1",
language = "English (US)",
isbn = "0818644923",
pages = "770--774",
editor = "Anon",
booktitle = "Proc 1993 IEEE ACM Int Conf Comput Aided Des",
publisher = "Publ by IEEE",

}

TY - GEN

T1 - Fast algorithm for VLSI net extraction

AU - Lopez, Mario A.

AU - Janardan, Ravi

AU - Sahni, Sartaj

PY - 1993/12/1

Y1 - 1993/12/1

N2 - Net extraction is crucial in VLSI design verification. Current algorithms for net extraction do not exploit the fact that the number, c, of different orientations of the line segments or polygon edges in a practical VLSI mask design is small relative to the number, n, of segments or edges. Instead they rely on computing all intersections in the input and hence take time that is at least proportional to the number of intersections. In this paper we develop a simple and practical algorithm for net extraction that runs in O(cn log n) time and O(n) space, which is optimal for fixed c. Experiments indicate that the algorithm will generally outperform existing algorithms on practical VLSI designs. We expect that the techniques presented will be useful in other VLSI/CAD problems that operate with restricted orientation geometries.

AB - Net extraction is crucial in VLSI design verification. Current algorithms for net extraction do not exploit the fact that the number, c, of different orientations of the line segments or polygon edges in a practical VLSI mask design is small relative to the number, n, of segments or edges. Instead they rely on computing all intersections in the input and hence take time that is at least proportional to the number of intersections. In this paper we develop a simple and practical algorithm for net extraction that runs in O(cn log n) time and O(n) space, which is optimal for fixed c. Experiments indicate that the algorithm will generally outperform existing algorithms on practical VLSI designs. We expect that the techniques presented will be useful in other VLSI/CAD problems that operate with restricted orientation geometries.

UR - http://www.scopus.com/inward/record.url?scp=0027839132&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027839132&partnerID=8YFLogxK

M3 - Conference contribution

SN - 0818644923

SP - 770

EP - 774

BT - Proc 1993 IEEE ACM Int Conf Comput Aided Des

A2 - Anon, null

PB - Publ by IEEE

ER -