Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2012, Vol. 13 Issue (3): 232-237    DOI: 10.1631/jzus.C1100193
    
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
Institute of VLSI Design, Zhejiang University, Hangzhou 310027, China
Download:   PDF(0KB)
Export: BibTeX | EndNote (RIS)      

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.

Key words： Very large scale integration (VLSI)      Layout representation      HV/VH trees      Region query     
Received: 04 July 2011      Published: 01 March 2012
CLC:  TN47  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Jie Ren
Wei-wei Pan
Yong-jun Zheng
Zheng Shi
Xiao-lang Yan
Cite this article:

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. Front. Inform. Technol. Electron. Eng., 2012, 13(3): 232-237.

URL:

http://www.zjujournals.com/xueshu/fitee/10.1631/jzus.C1100193     OR     http://www.zjujournals.com/xueshu/fitee/Y2012/V13/I3/232


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

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.

关键词： Very large scale integration (VLSI),  Layout representation,  HV/VH trees,  Region query 
[1] Mao-qun Yao, Kai Yang, Cong-yuan Xu, Ji-zhong Shen. Design of a novel RTD-based three-variable universal logic gate[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(8): 694-699.
[2] Kai Huang, Xiao-xu Zhang, Si-wen Xiu, Dan-dan Zheng, Min Yu, De Ma, Kai Huang, Gang Chen, Xiao-lang Yan. Profiling and annotation combined method for multimedia application specific MPSoC performance estimation[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(2): 135-151.
[3] Kai-sheng Luo, Zheng Shi, Xiao-lang Yan, Zhen Geng. SVM based layout retargeting for fast and regularized inverse lithography[J]. Front. Inform. Technol. Electron. Eng., 2014, 15(5): 390-400.
[4] Zhen Geng, Zheng Shi, Xiao-lang Yan, Kai-sheng Luo. Regularized level-set-based inverse lithography algorithm for IC mask synthesis[J]. Front. Inform. Technol. Electron. Eng., 2013, 14(10): 799-807.
[5] Bin Lin, Xiao-lang Yan, Zheng Shi, Yi-wei Yang. A sparse matrix model-based optical proximity correction algorithm with model-based mapping between segments and control sites[J]. Front. Inform. Technol. Electron. Eng., 2011, 12(5): 436-442.
[6] Di Li, Yin-tang Yang, Jiang-an Wang, Bing Li, Qiang Long, Jary Wei, Nai-di Wang, Lei Wang, Qian-kun Liu, Da-long Zhang. Design of a low power GPS receiver in 0.18 μm CMOS technology with a ΣΔ fractional-N synthesizer[J]. Front. Inform. Technol. Electron. Eng., 2010, 11(6): 444-449.