Previous [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]


Journal of Information Science and Engineering, Vol. 20 No. 1, pp. 127-141 (January 2004)

On the Array Embeddings and Layouts
of Quadtrees and Pyramids*

Gene Eu Jan, Shao-Wei Leu+ and  Cheng-Hung Li++
Department of Computer Science Education
+Department of Electrical Engineering
National Taiwan Ocean University
Keelung, 202 Taiwan
E-mail: {b0199,
++Department of Electric Engineering
National Taiwan University of Science and Technology
Taipei, 106 Taiwan

Quadtree and pyramid structures have attracted considerable attention in recent years. They are increasingly being applied to the fields of digital image and signal processing. As a result, the efficient embedding of these structures in VLSI arrays has become an important research topic. In this paper, we propose three schemes to embed either quadtrees or pyramids in a rectangular, hexagonal, or octagonal mesh, respectively, with three different node shapes for VLSI layout. Our analyses show that the best achievable node utilization is 67% when embedding either structure in an octagonal mesh. This result outperforms the best utilization recorded in literature by 25%. Our study also indicates that the octagonal node gives the best balance between area utilization and routing space requirements between the processing nodes.

Keywords: quadtree, pyramid, embedding, mesh, VLSI layout

Full Text () Retrieve PDF document (200401_07.pdf)

Received January 31, 2003; accepted July 4, 2003.
Communicated by Shiuh-Pyng Shieh.
* A preliminary version of this paper was presented at the 2002 International Computer Symposium, 2002.