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,
+b0119}@mail.ntou.edu.tw
++Department of Electric Engineering
National Taiwan University of Science and Technology
Taipei, 106 Taiwan
E-mail: D9102102@mail.ntust.edu.tw

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.