Full Text:   <2734>

CLC number: TN47

On-line Access: 2012-03-01

Received: 2011-07-04

Revision Accepted: 2011-10-25

Crosschecked: 2012-02-08

Cited: 0

Clicked: 3356

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2012 Vol.13 No.3 P.232-237

http://doi.org/10.1631/jzus.C1100193


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


Author(s):  Jie Ren, Wei-wei Pan, Yong-jun Zheng, Zheng Shi, Xiao-lang Yan

Affiliation(s):  Institute of VLSI Design, Zhejiang University, Hangzhou 310027, China

Corresponding email(s):   renjie@vlsi.zju.edu.cn, shiz@vlsi.zju.edu.cn

Key Words:  Very large scale integration (VLSI), Layout representation, HV/VH trees, Region query


Jie Ren, Wei-wei Pan, Yong-jun Zheng, Zheng Shi, Xiao-lang Yan. Array based HV/VH tree: an effective data structure for layout representation[J]. Journal of Zhejiang University Science C, 2012, 13(3): 232-237.

@article{title="Array based HV/VH tree: an effective data structure for layout representation",
author="Jie Ren, Wei-wei Pan, Yong-jun Zheng, Zheng Shi, Xiao-lang Yan",
journal="Journal of Zhejiang University Science C",
volume="13",
number="3",
pages="232-237",
year="2012",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1100193"
}

%0 Journal Article
%T Array based HV/VH tree: an effective data structure for layout representation
%A Jie Ren
%A Wei-wei Pan
%A Yong-jun Zheng
%A Zheng Shi
%A Xiao-lang Yan
%J Journal of Zhejiang University SCIENCE C
%V 13
%N 3
%P 232-237
%@ 1869-1951
%D 2012
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1100193

TY - JOUR
T1 - Array based HV/VH tree: an effective data structure for layout representation
A1 - Jie Ren
A1 - Wei-wei Pan
A1 - Yong-jun Zheng
A1 - Zheng Shi
A1 - Xiao-lang Yan
J0 - Journal of Zhejiang University Science C
VL - 13
IS - 3
SP - 232
EP - 237
%@ 1869-1951
Y1 - 2012
PB - Zhejiang University Press & Springer
ER -
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.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

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

[2]Brown, R.L., 1986. Multiple storage quad trees: a simpler faster alternative to bisector list quad trees. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 5(3):413-419.

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

[4]Lai, G.G., Fussell, D., Wong, D.F., 1993. HV/VH Trees: a New Spatial Data Structure for Fast Region Queries. Proc. 30th Int. Design Automation Conf., p.43-47.

[5]Lai, G.G., Fussell, D.S., Wong, D.F., 1996. Hinted quad trees for VLSI geometry DRC based on efficient searching for neighbors. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 15(3):317-324.

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

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

[8]Ousterhout, J.K., 1982. Corner stitching: a data structure technique for VLSI layout tools. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 3(1):87-100.

[9]Pitaksanonkul, A., Thanawastien, S., Lursinsap, C., 1989. Comparisons of quad trees and 4-D trees: new results. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 8(11):1157-1164.

[10]Rosenberg, J.B., 1985. Geographical data structures compared: a study of data structures supporting region queries. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 4(1):53-67.

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

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

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

[14]Weyten, L., de Pauw, W., 1989. Quad list quad trees: a geometrical data structure with improved performance for large region queries. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 8(3):229-233.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE