臺灣博碩士論文加值系統

四元樹和金字塔的架構近年來頗受重視，二者在數位影像及訊號處理方面的應用有逐漸增加的趨勢。因此如何將這二種架構嵌入超大型積體電路已成為值得重視的研究課題。關於四元樹和金字塔的平面嵌入，本論文提出將此二種架構分別嵌入矩形、六角形以及八角形平面網狀架構的方法，並且探討不同節點形狀對於超大型積體電路面積利用率的影響。我們的研究顯示八角形網狀架構的平面嵌入可獲得高達67%的節點利用率，較目前文獻上最佳之利用率高出25%。我們的分析也指出，當綜合考量面積利用率與節點間所需之繞線空間時，八角形之嵌入結果最為理想。最後，我們也提出一個新的傳繞演算法，能使金字塔的頂點不致成為訊息傳繞之瓶頸。

Quadtree and pyramid architectures have attracted considerable attention in recent years. They are being applied, on an increasing basis, to the fields of digital image and signal processing. Consequently, efficient embedding of these architectures in VLSI arrays has become an important research topic. In this thesis, we propose three schemes to embed a quadtree/pyramid structure on three two-dimensional arrays, namely, rectangular-, hexagonal-, and octagonal-connected meshes. Our analyses show that the highest achievable node utilization is 67% when the embedding takes place on an octagonal-connected mesh. This result outperforms the best utilization recorded in literature by 25%. To understand how the shape of a cell affect the area utilization in the context of the VLSI layout, we analyze a total of three shapes of the cells embedded on meshes. Our study indicates that, among all the cell shapes attempted, the octagonal cell gives the most favorable result considering both the area utilization and the routing space left between cells. Finally, we propose a new routing algorithm to eliminate the communication bottleneck at the apex of the pyramid.

目 錄
圖目錄 ...................................................... Ⅲ
表目錄 ...................................................... Ⅴ
符號定義 .................................................... Ⅵ
第一章 緒論 ............................................... 1
第二章 嵌入方式 ........................................... 3
2-1 金字塔架構 .......................................... 3
2-2 嵌入方法 ............................................ 5
2-2 二維嵌入及結果之分析與比較 .............................. 8
2-2-1 四邊形網格 ..................................... 8
2-2-2 六邊形網格 .................................... 10
2-2-3 八邊形網格 .................................... 12
2-2-3 整體比較 ...................................... 15
第三章 基於不同單於形狀的面積利用 ........................ 17
3-1 四邊形節點 ........................................ 17
3-2 六邊形節點 ........................................ 18
3-3 八邊形節點 ........................................ 20
3-4 整體比較 .......................................... 22
第四章 傳繞演算法 ........................................ 25
4-1 傳繞方式 ........................................... 25
4-2 演算法及效能分析 ................................... 28
第五章 結論 .............................................. 29
參考文獻 ................................................... 30
圖目錄
圖2.1 一個三層的金字塔網路 ................................... 5
圖2.2 四元樹與金字塔網路 ..................................... 7
圖2.3 一個三層的四元樹與金字塔的二維結構 ..................... 7
圖2.4 一個四層四元樹 ......................................... 8
圖2.5 一個四層金字塔 ......................................... 8
圖2.6 三種網格 ............................................... 9
圖2.7 三層四元樹與金字塔嵌入在四邊形連接網格上 .............. 10
圖2.8 四邊形連接網格的效能 .................................. 11
圖2.9 一個四層無跨線的四元樹 ................................ 12
圖2.10 嵌入至六邊形網格後的效能 ............................. 13
圖2.11 一個四層的四元樹嵌入至八邊形網格 ..................... 14
圖2.12 一個四層金字塔嵌入至八邊形網格上 ..................... 15
圖2.13 嵌入至八邊形網格後的效能 ............................. 15
圖2.14 四種嵌入後的曲線圖 ................................... 17
圖3.1 四邊形節點佈局 ........................................ 18
圖3.2 四邊形節點的面積利用率 ................................ 19
圖3.3 六邊形節點佈局 ........................................ 20
圖3.4 六邊形節點的面積利用率 ................................ 20
圖3.5 八邊形節點佈局 ........................................ 21
圖3.6 八邊形節點的面積利用率 ................................ 21
圖3.7 三種節點的面積利用率 .................................. 24
圖3.8 八邊形節點的四元樹 .................................... 24
圖3.9 八邊形節點的金字塔網路 ................................ 25
圖4.1 一個三層的金字塔平面座標 .............................. 26
圖4.2 金字塔結構的縱切面 .................................... 27
圖4.3 從D(2,1) 到S(5,5)的範例 ............................... 28
圖4.4 最佳路徑演算法 ........................................ 29
表目錄
表2.1 嵌入後的數值 .......................................... 16
表3.1 三種不同單元的面積利用率 .............................. 23

[1] Akl, S., Parallel Computation Models and Networks. Prentice- Hall,1997.
[2] Akl, S. and K.A. Lyons, Parallel Computational Geometry.
Prentice-Hall, 1993.
[3] Akl, S., The Design and Analysis of Parallel
Algorithms. Prentice-Hall, 1989.
[4] Akl, S., Parallel Sorting Algorithms. Academic Press, 1985.
[5] Banerjee, P., Parallel Algorithms for VLSI Computation-
Aided Design. Prentice-Hall, 1994.
[6] Battacharya, S., S. Kriani, and W. T. Tsai, “Quadtree
Interconnection Network Layout,” Proceedings of the Second
Great Lakes Symposium on VLSI, pp.81-87, 1991.
[7] Casavant, T. L., P. Turdĭk, and F. Plášil, Parallel
Computers Theory and Practice, IEEE Computer Society Press,
1996.
[8] Codenotti, B. and M. Leoncini, Introduction to Parallel
Processing. Addison-Wesley, 1993.
[9] Fountain, T. J., Parallel Computing Principles and
Practice. Cambridge University Press, 1994.
[10] Gordan, D., I. Koren, and G. M. Silberman, “Embedding
Tree Structures in VLSI Hexagonal Arrays,” IEEE Trans.
Computer, Vol. C-33, no. 1, pp.104-107, 1984.
[11] Gordan, D., “Efficient Embeddings of Binary Tree in VLSI
Arrays,”IEEE Trans. Computer, Vol. C-36, pp.1009-1018.
Sept. 1987.
[12] Grammatikakis, M. D., D. F. Hsu, and M. Hraetzl, Parallel
System Interconnections and Communications. CRC Press,
2001.
[13] Ho, C.-T., and S. Lennart Johnsson., “Dilation d
Embedding of a Hyper-pyramid into a hypercube,”
Proceedings of the Supercomputing conference, pp.294-303,
1989.
[14] Hord, R. M., Understanding Parallel Supercomputing. IEEE
Press, 1999.
[15] Hromkovič, J., Communication Complexity and Parallel
Computing. Springer, 1997.
[16] Hwang, K. and F. A. Briggs, Computer Architecture and
Parallel Processing, McGraw-Hill, 1984.
[17] Krishnamurthy, E. V., Parallel Processing Principles and
Practice, Addison-Wesley, 1989.
[18] Kung, S. Y., VLSI Array Processors. Prentice-Hall, 1988.
[19] Kumar, V. K. P and D. Reisis., “Pyramids versus Enhanced
Arrays for Parallel Image Processing,” Technical Report
CRI-86-16, Department of Electrical Engineering-Systems,
1986, University of Southern California.
[20] Leighton, F. T., Introduction to Parallel Algorithms and
Architectures. Morgon Kaufmann, 1992.
[21] Lyuu, Y. D., Information Dispersal and Parallel
Computation. Cambridge University Press, 1992.
[22] Mead, C. and L. Conway, Introduction to VLSI System.
Addision-Wesley, 1980.
[23] Miller, R. and Q. F. Stout, Parallel Algorithms for
Regular Architectures. MIT Press, 1999.
[24] Mzaik, T., S. Chandra, D. K. Panda, and J. M. Jagadeesh,
“Analysis of Routing in Pyramid Architecture,”
Proceedings of the Aerospace and Electronics Conference,
pp.831-837, 1993.
[25] Nandy, S. K. and I. V. Ramakrishnan, “Dual Quadtree
Representation for VLSI Designs,” Proceedings of the 23th
Design Automation Conference, pp.663-666, 1986.
[26] Nossek, J. A., Parallel Processing on VLSI Arrays. Kluwer
Academic Publishers, 1991
[27] Parhami, B., Introduction to Parallel Processing. Plenum
Press, 1999.
[28] Quinn, M. J., Parallel Computing Theory and Practice.
McGraw-Hill, 1994.
[29] Richards, D. and A. L. Liestman, “Degree-Constrained
Pyramid Spanners,” Journal of Parallel and Distributed
Computing, Vol. 25, pp.1-6, 1995.
[30] Roosta, S. H., Parallel Processing and Parallel
Algorithms. Springer, 2000.
[31] Scherson, I. D. and A. S. Youssef, Interconnection
Networks for High-Performance Parallel Computers. IEEE
Computer Society Press, 1994.
[32] Shen, Z., “A Routing Algorithm for the Pyramid
Structures,”Proceedings of the 2001 ACM symposium on
Applied computing, pp.484-488, 2001.
[33] Suaya, R. and G. M. Birtwustle, VLSI and Parallel
Computation. Morgan Kaufmann, 1990.
[34] Samet, H., “The Quadtree and Related Hierarchical Data
Structures,”ACM Computing Survey, Vol. 16, pp.187-260,
1984.
[35] Snyder, L., “Introduction to the Configurable Highly
Parallel Computer,” IEEE Computer, pp.47-64, Jan. 1982.
[36] Varma, A. and Raghavendra, C. S., Interconnection Networks
for multiprocessors and Multicomputers Theory and
Practice. IEEE Computer Society Press, 1994.
[37] Zomaya, A. Y. H., Parallel and Distributed Handbook.
McGraw-Hill, 1996.