JZUS - Journal of Zhejiang University SCIENCE

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

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

Share this article to： More <<< Previous Article \|Next Article >>>

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.

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>

Similar articles

- Go to

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

Reference