DocumentCode
2824885
Title
An effective data structure for VLSI layout systems
Author
Iwasaki, Hiroaki ; Murakata, Masami ; Mitsuhashi, Takashi
Author_Institution
ULSI Res. Center, Toshiba Corp., Japan
fYear
1991
fDate
11-14 Jun 1991
Firstpage
3134
Abstract
An effective data structure is presented which is called a B-2 tree (bucket tree with 2-D binary trees) suitable for VLSI layout systems. The B-2 tree consists of a main binary tree which forms a directory for buckets, and bisector lists with 2-D binary trees. Experimental results have shown that the B-2 tree is superior to other data structures in region search performance even for huge size data. It has also been shown that its region search performance is not influenced by the distribution of objects on a chip
Keywords
VLSI; circuit layout CAD; data structures; search problems; trees (mathematics); 2D binary trees; B-2 tree; VLSI layout systems; bisector lists; bucket tree; data structure; directory; region search performance; size data; Binary trees; Circuits; Complexity theory; Data structures; Database systems; Degradation; Spatial databases; Tree data structures; Ultra large scale integration; Very large scale integration;
fLanguage
English
Publisher
ieee
Conference_Titel
Circuits and Systems, 1991., IEEE International Sympoisum on
Print_ISBN
0-7803-0050-5
Type
conf
DOI
10.1109/ISCAS.1991.176215
Filename
176215
Link To Document