Space Efficient Algorithms for VLSI Artwork Analysis
- 1 January 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 734-739
- https://doi.org/10.1109/dac.1983.1585739
Abstract
We present algorithms for performing connectivity analysis, transistor identification, and boolean geometric operations with region numbering. Previous methods all require O(n) space where n is the number of edges in the circuit artwork; our method takes only O(√n) space and can therefore handle circuits of any foreseeable size. Our algorithms are based on traditional scanline techniques in such a way that any implementation of our method will be at least as fast, as well as more compact. Statistics on one such implementation are presented.Keywords
This publication has 8 references indexed in Scilit:
- Plane-sweep algorithms for intersecting geometric figuresCommunications of the ACM, 1982
- A hardware assisted design rule check architecturePublished by Association for Computing Machinery (ACM) ,1982
- Efficient Boolean Operations on IC MasksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- An O (N log N) Algorithm for Boolean Mask OperationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- An integrated mask artwork analysis systemPublished by Association for Computing Machinery (ACM) ,1980
- A hierarchical bit-map format for the representation of IC mask dataPublished by Association for Computing Machinery (ACM) ,1980
- Topological Analysis for VLSI CircuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Set Merging AlgorithmsSIAM Journal on Computing, 1973