Array based HV/VH tree: an effective data structure for layout representation

Jie REN; Wei-wei PAN; Yong-jun ZHENG; Zheng SHI; Xiao-lang YAN

doi:10.1631/jzus.C1100193

Your Location：

Home >

Browse articles >

Array based HV/VH tree: an effective data structure for layout representation

电子工程 | Updated：2022-05-19

- Array based HV/VH tree: an effective data structure for layout representation
- Array based HV/VH tree: an effective data structure for layout representation
- 信息与电子工程前沿（英文） 2012年13卷第3期页码：232-237
- Affiliations：
  
  Institute of VLSI Design, Zhejiang University, Hangzhou 310027, China
- Author bio：
  
  [ "Jie REN, E-mail: renjie@vlsi.zju.edu.cn" ]
  Zheng SHI, E-mail: shiz@vlsi.zju.edu.cn
- Funds：
  
  Project supported by the National Natural Science Foundation of China (No. 61106034) and the National Science and Technology Major Project (No. 2009ZX02023-004-1)
- DOI：10.1631/jzus.C1100193
  中图分类号： TN47
- 收稿：2018-07-04，
  
  修回：2012-;2-;8，
  
  纸质出版：2012-03
- Accepted：
Scan QR Code
Array based HV/VH tree: an effective data structure for layout representation[J]. 信息与电子工程前沿（英文）, 2012,13(3):232-237.

Jie REN, Wei-wei PAN, Yong-jun ZHENG, et al. Array based HV/VH tree: an effective data structure for layout representation[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(3): 232-237.
Array based HV/VH tree: an effective data structure for layout representation[J]. 信息与电子工程前沿（英文）, 2012,13(3):232-237. DOI： 10.1631/jzus.C1100193.

Jie REN, Wei-wei PAN, Yong-jun ZHENG, et al. Array based HV/VH tree: an effective data structure for layout representation[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(3): 232-237. DOI： 10.1631/jzus.C1100193.

摘要

Abstract

We present a new data structure for the representation of an integrated circuit layout. It is a modified HV/VH tree using arrays as the primary container in bisector lists and leaf nodes. By grouping and sorting objects within these arrays together with a customized binary search algorithm

our new data structure provides excellent performance in both memory usage and region query speed. Experimental results show that in comparison with the original HV/VH tree

which has been regarded as the best layout data structure to date

the new data structure uses much less memory and can become 30% faster on region query.

关键词

Keywords

references

M.D. Berg , , , O. Cheong , , , M.V. Kreveld , , , M. Overmars . . Computational Geometry: Algorithms and Applications . . Springer, the Netherlands , , 2008 . . p.219 - - 238 . . . .

R.L. Brown . . Multiple storage quad trees: a simpler faster alternative to bisector list quad trees . . IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. , , 1986 . . 5 ( ( 3 ): ): 413 - - 419 . . DOI: 10.1109/TCAD.1986.1270210 http://doi.org/10.1109/TCAD.1986.1270210 . .

G. Kedem . . The Quad-CIF Tree: a Data Structure for Hierarchical On-line Algorithms . . Proc. 19th Design Automation Conf. , , 1982 . . p.352 - - 357 . . . .

G.G. Lai , , , D. Fussell , , , D.F. Wong . . HV/VH Trees: a New Spatial Data Structure for Fast Region Queries . . Proc. 30th Int. Design Automation Conf. , , 1993 . . p.43 - - 47 . . DOI: 10.1145/157485.164562 http://doi.org/10.1145/157485.164562 . .

G.G. Lai , , , D.S. Fussell , , , D.F. Wong . . Hinted quad trees for VLSI geometry DRC based on efficient searching for neighbors . . IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. , , 1996 . . 15 ( ( 3 ): ): 317 - - 324 . . DOI: 10.1109/43.489102 http://doi.org/10.1109/43.489102 . .

D.P. Mehta . . Handbook of Data Structures and Applications . . Chapter 52: Layout Data Structures. Chapman & Hall/CRC, USA , , 2005 . . p.1046 - - 1063 . . . .

D.P. Mehta , , , H. Zhou . . Handbook of Algorithms for Physical Design Automation . . Chapter 4: Basic Data Structures. Auerbach Publications, FL, USA , , 2008 . . p.55 - - 69 . . . .

J.K. Ousterhout . . Corner stitching: a data structure technique for VLSI layout tools . . IEEE Trans. Comput.- Aided Des. Integr. Circ. Syst. , , 1982 . . 3 ( ( 1 ): ): 87 - - 100 . . DOI: 10.1109/TCAD.1984.1270061 http://doi.org/10.1109/TCAD.1984.1270061 . .

A. Pitaksanonkul , , , S. Thanawastien , , , C. Lursinsap . . Comparisons of quad trees and 4-D trees: new results . . IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. , , 1989 . . 8 ( ( 11 ): ): 1157 - - 1164 . . DOI: 10.1109/43.41501 http://doi.org/10.1109/43.41501 . .

J.B. Rosenberg . . Geographical data structures compared: a study of data structures supporting region queries . . IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. , , 1985 . . 4 ( ( 1 ): ): 53 - - 67 . . DOI: 10.1109/TCAD.1985.1270098 http://doi.org/10.1109/TCAD.1985.1270098 . .

H. Samet . . Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS . . Addison-Wesley, MA , , 1990a . . .

H. Samet . . The Design and Analysis of Spatial Data Structures , , : : MA Addison-Wesley , , 1990b . . .

H. Samet . . Foundations of Multidimensional and Metric Data Structures . . Morgan Kaufmann, CA, USA , , 2006 . . p.474 - - 483 . . . .

L. Weyten , , , W. de Pauw . . Quad list quad trees: a geometrical data structure with improved performance for large region queries . . IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. , , 1989 . . 8 ( ( 3 ): ): 229 - - 233 . . DOI: 10.1109/43.21842 http://doi.org/10.1109/43.21842 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据