Using a multiple storage quad tree on a hierarchical VLSI compaction scheme
- 1 May 1990
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 9 (5) , 522-536
- https://doi.org/10.1109/43.55182
Abstract
A graph-generating algorithm and the experimental results of a hierarchical mask-layout-compaction scheme based on a plane-sweep algorithm, a fast region-query and a space-efficient data structure called the hierarchical multiple-storage quad tree are presented. For a mask-layout design, a rectangle is used as the primary element of the layout. Hence, in the hierarchical mask-compaction scheme, the graph-generating algorithm is based on the edges of rectangles rather than the central lines of symbols for the symbolic-compaction design. The plane-sweep algorithm is also called a dynamic event scheduling algorithm and can be applied to solve some other problems in the field of computational geometry and image processing. The efficiencies of the plane-sweep algorithm and the graph-generating algorithm are dependent on the region-query operations of the spatial data structure. By using the improved multiple storage quad tree as the spatial data structure in the system, the mask-layout compactor has been accomplished in a practically linear time performance in terms of the rectangles in the source layoutKeywords
This publication has 29 references indexed in Scilit:
- Automatic tub region generation for symbolic layout compactionPublished by Association for Computing Machinery (ACM) ,1989
- New algorithms for increased efficiency in hierarchical design rule checkingIntegration, 1987
- Algorithmic Aspects of One-Dimensional Layout CompactionIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- A new compaction scheme based on compression ridgesPublished by Association for Computing Machinery (ACM) ,1987
- Two-Dimensional Compaction by 'Zone Refining'Published by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Minplex---a compactor that minimizes the bounding rectangle and individual rectangles in a layoutPublished by Association for Computing Machinery (ACM) ,1986
- Corner Stitching: A Data-Structuring Technique for VLSI Layout ToolsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1984
- Chip Layout Optimization Using Critical Path WeightingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- An Algorithm to Compact a VLSI Symbolic Layout with Mixed ConstraintsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1983
- Data Structures for Range SearchingACM Computing Surveys, 1979