Quadtree layout

Sourav Bhattacharya; Shekar Kirani; Wei Tek Tsai

Quadtree layout

Sourav Bhattacharya^*
, Shekar Kirani
, Wei Tek Tsai

^*Corresponding author for this work

University of Minnesota Twin Cities

Research output: Contribution to conference › Paper › peer-review

Abstract

Quadtree data structure has been used in a number of applications. However, VLSI embedding of quadtree based parallel architecture using grid model has not been studied. This paper studies VLSI embedding of quadtree using grid model. H-tree layout for binary tree is extended for trivial quadtree layout, followed by developing two layout strategies for rectangular grids. Then, two generic layout styles (standard layout and X-layout) are proposed for higher order grids (e.g., hexagonal and octagonal grids). Base tile layout patterns are proposed for area compaction with recursive X-layout. In each case, layout dimensions and I/O bandwidth are computed. We demonstrate how the two generic layouts can be mixed to obtain higher I/O bandwidth and estimate the area sacrifice. An improved recursive layout mixing strategy is proposed.

Original language	English
Pages	74-81
Number of pages	8
State	Published - 1991
Externally published	Yes
Event	Proceedings of the Second Great Lakes Symposium on VLSI - Kalamazoo, MI, USA Duration: 28 Feb 1992 → 29 Feb 1992

Conference

Conference	Proceedings of the Second Great Lakes Symposium on VLSI
City	Kalamazoo, MI, USA
Period	28/02/92 → 29/02/92

Cite this

@conference{73215c4fac9a49d89a971ead8c4ec259,

title = "Quadtree layout",

abstract = "Quadtree data structure has been used in a number of applications. However, VLSI embedding of quadtree based parallel architecture using grid model has not been studied. This paper studies VLSI embedding of quadtree using grid model. H-tree layout for binary tree is extended for trivial quadtree layout, followed by developing two layout strategies for rectangular grids. Then, two generic layout styles (standard layout and X-layout) are proposed for higher order grids (e.g., hexagonal and octagonal grids). Base tile layout patterns are proposed for area compaction with recursive X-layout. In each case, layout dimensions and I/O bandwidth are computed. We demonstrate how the two generic layouts can be mixed to obtain higher I/O bandwidth and estimate the area sacrifice. An improved recursive layout mixing strategy is proposed.",

author = "Sourav Bhattacharya and Shekar Kirani and Tsai, \{Wei Tek\}",

year = "1991",

language = "英语",

pages = "74--81",

note = "Proceedings of the Second Great Lakes Symposium on VLSI ; Conference date: 28-02-1992 Through 29-02-1992",

}

TY - CONF

T1 - Quadtree layout

AU - Bhattacharya, Sourav

AU - Kirani, Shekar

AU - Tsai, Wei Tek

PY - 1991

Y1 - 1991

N2 - Quadtree data structure has been used in a number of applications. However, VLSI embedding of quadtree based parallel architecture using grid model has not been studied. This paper studies VLSI embedding of quadtree using grid model. H-tree layout for binary tree is extended for trivial quadtree layout, followed by developing two layout strategies for rectangular grids. Then, two generic layout styles (standard layout and X-layout) are proposed for higher order grids (e.g., hexagonal and octagonal grids). Base tile layout patterns are proposed for area compaction with recursive X-layout. In each case, layout dimensions and I/O bandwidth are computed. We demonstrate how the two generic layouts can be mixed to obtain higher I/O bandwidth and estimate the area sacrifice. An improved recursive layout mixing strategy is proposed.

AB - Quadtree data structure has been used in a number of applications. However, VLSI embedding of quadtree based parallel architecture using grid model has not been studied. This paper studies VLSI embedding of quadtree using grid model. H-tree layout for binary tree is extended for trivial quadtree layout, followed by developing two layout strategies for rectangular grids. Then, two generic layout styles (standard layout and X-layout) are proposed for higher order grids (e.g., hexagonal and octagonal grids). Base tile layout patterns are proposed for area compaction with recursive X-layout. In each case, layout dimensions and I/O bandwidth are computed. We demonstrate how the two generic layouts can be mixed to obtain higher I/O bandwidth and estimate the area sacrifice. An improved recursive layout mixing strategy is proposed.

UR - https://www.scopus.com/pages/publications/0026379353

M3 - 论文

AN - SCOPUS:0026379353

SP - 74

EP - 81

T2 - Proceedings of the Second Great Lakes Symposium on VLSI

Y2 - 28 February 1992 through 29 February 1992

ER -

Quadtree layout

Abstract

Conference

Other files and links

Fingerprint

Cite this