|
Journal of Zhejiang University SCIENCE C
ISSN 1869-1951(Print), 1869-196x(Online), Monthly
2012 Vol.13 No.3 P.232-237
Array based HV/VH tree: an effective data structure for layout representation
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
References:
Open peer comments: Debate/Discuss/Question/Opinion
<1>
DOI:
10.1631/jzus.C1100193
CLC number:
TN47
Download Full Text:
Downloaded:
4839
Clicked:
7328
Cited:
0
On-line Access:
2012-03-01
Received:
2011-07-04
Revision Accepted:
2011-10-25
Crosschecked:
2012-02-08