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
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
 全文: PDF 
摘要： 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    
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
收稿日期: 2011-07-04 出版日期: 2012-03-01
CLC:  TN47  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Jie Ren
Wei-wei Pan
Yong-jun Zheng
Zheng Shi
Xiao-lang Yan

引用本文:

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.

链接本文:

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

[1] Mao-qun Yao, Kai Yang, Cong-yuan Xu, Ji-zhong Shen. 基于RTD三变量通用逻辑门的设计[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. 面向多媒体特定应用的剖析和标注相结合MPSoC性能评估方法[J]. Front. Inform. Technol. Electron. Eng., 2015, 16(2): 135-151.
[3] Kai-sheng Luo, Zheng Shi, Xiao-lang Yan, Zhen Geng. 基于支持向量机的反向光刻版图重定向算法[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.