(18.206.177.17) 您好!臺灣時間:2021/04/23 05:39
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:蔡世峰
研究生(外文):Shie-Feng Tsai
論文名稱:嵌入二元樹於超立方體
論文名稱(外文):On arbitrary binary trees of hypercubes
指導教授:黃惠苓
指導教授(外文):Hui-Ling Huang
學位類別:碩士
校院名稱:南台科技大學
系所名稱:資訊管理系
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:26
中文關鍵詞:(tree)超立方體(hypercube)嵌入(embedding)前序追蹤(preorder traversal)格雷碼(Gray code)膨脹係數(dilation)
外文關鍵詞:binary treediameterdilationembeddingGray codehypercubepreorder traversalrecursivenesssymmetry
相關次數:
  • 被引用被引用:0
  • 點閱點閱:134
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:6
  • 收藏至我的研究室書目清單書目收藏:0
嵌入樹(tree)於超立方體(hypercube)的問題在過去二十年中一直引起許多研究者的關注。超立方體是一個最受注意和討論的連結網路結構,而且被實際建構成為真正可用的平行電腦,這是因為它有著相當好的性質,如模組化、對稱性(symmetry)、規則性(regularity)、較小的直徑(diameter)和容錯(fault-tolerant)能力等等。而樹更是重要的結構,在二元樹上已被研究出很多相當有效率的演算法,可以解決各種應用問題。為了將現存某一網路上的演算法能夠輕易的轉移使用在另一網路上,嵌入(embedding)的問題就因應而生。嵌入在多處理機連結網路上是一重要的研究主題,假如我們能將某一網路嵌入另一網路,即代表在此網路上所設計的演算法都可很容易地轉移至另一網路上。本篇論文改進之前Chen與Stallmann的研究成果,我們提出一個新的遞迴演算法將任意二元樹嵌入超立方體結構中,在一般情況下我們的嵌入演算法其膨脹(dilation)係數會小於等於Chen與Stallmann的方法。
關鍵詞: 樹(tree)、超立方體(hypercube)、嵌入(embedding)、前序追蹤(preorder traversal)、格雷碼(Gray code)、膨脹係數(dilation)
The problems of embedding trees into hypercubes have attracted considerable attention in the literature for the past 20 years. Especially, many researches were devoted to the problem of embedding binary trees into hypercubes. Hypercubes are very important interconnection networks because they own many good topological properties such as recursiveness, symmetry, small diameter, and fault-tolerant capability. Besides, hypercubes have been implemented as commercial computers. On the other hand, binary trees are the one of the most important topologies since many efficient algorithms can be executed on them. Embedding binary trees into hypercubes will make these efficient algorithms of trees easily transfer to commercial hypercube-computers. In this paper, we improve Chen and Stallmann’s previous work and propose a new recursive algorithm to embed arbitrary binary trees into hypercubes. In general cases, the dilation of our embedding algorithm will be smaller than or equal to the dilation of Chen and Stallmann.
Keyword:binary tree, diameter, dilation, embedding, Gray code, hypercube, preorder traversal, recursiveness, symmetry
摘要 vi
英文摘要 v
誌謝 vi
目次 vii
圖目錄 viii
第一章 簡介 1
第二章 符號與定義 4
第三章 二元樹嵌入演算法 8
第四章 總結 20
參考文獻 21
附錄 24
[1] J. L. Bentley, and H. T. Kung, “A tree machine for searching problems,” Proceedings of International Conference on Parallel Processing, pp. 257-266, 1979.
[2] S. N. Bhatt, and I. C. F. Ipsen, “How to embedded trees in hypercubes,” Yale University Research Report, RR-443, Dec. 1985.
[3] S. N. Bhatt, F. R. K. Chung, F. T. Leighton, and A. L. Rosenberg, “Efficient ebmedding of trees in hypercubes,” SIAM Journal on Scientific Computing, vol. 21, pp. 151-162, Feb. 1992.
[4] S. N. Bhatt, F. Chung, T. Leighton, and Rosenberg, “A. optimal simulation of tree machines,” Proceedings of the 27th Annual Symposium of Foundations of Computer Science, pp. 274-282, 1986.
[5] L. Bhuyan, and D. P. Agrawal, “Generalized hypercubes and hyperbus structures for a computer network,” IEEE Transactions on Computers, C-33, pp. 323-333, 1984.
[6] J. Blazewicz, and M. Drozdowski, “Scheduling divisible jobs on hypercubes,” Parallel Computing, vol. 21, pp. 1945-1956, 1995.
[7] Y. W. Chen, and K. L. Chung, “Improved fault-tolerant sorting algorithm in hypercubes,” Theoretical Computer Science, vol. 255, pp. 649-658, 2001.
[8] W. Chen, and M. F. M. Stallmann, “On embedding einary trees into hypercubes,” Journal of Parallel and Distributed Computing, vol. 24, pp. 132-138, 1995.
[9] A. M. Despain, and D. A. Patterson, “X-tree: A tree structured multiprocessor computer architecture,” Proceedings of the 5th Annual Symposium on Computer Architecture, pp. 144-151, 1978.
[10] S. R. Desphance, and R. Jenevein, “Scalability of binary trees on a hypercube,” Proceedings of International Conference on Parallel Processing, pp. 661-668, 1986.
[11] K. Efe, “Embedding mesh of trees in the hypercube,” Journal of Parallel and Distributed Computing, vol. 11, pp. 222-230, 1991.
[12] J. P. Hayes, T. N. Mudge, Q. F. Stout, S. Colley and J. Palmer, “A microprocessor-based hypercube supercomputer,” IEEE Micro, vol. 6, pp. 6-17, 1986.
[13] C. T. Ho, and S. L. Johnsson, “Spanning balanced trees in boolean cubes,” SIAM Journal on Scientific Computing, vol.10-4, pp. 607-630, July 1989.
[14] E. Horowitz, and A. Zorat, “The binary tree as an interconnection network:Applications to multiprocessor systems and VLSI,” IEEE Transactions on Computers, vol. 30, pp. 247-253, 1981.
[15] F. T. Leighton, “Introduction to parallel algorithms and architectures: arrays, trees and hypercubes,” Morgan Kaufmann, San Mateo CA, 1992.
[16] F. T. Leighton, “Parallel computing using mesh of trees,” Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science, pp. 200-218, 1983.
[17] I. L. Leiss, and H. N. Reddy, “Embedding complete binary trees into hypercubes,” Information processing letters, vol. 38, pp. 197-199, May 1991.
[18] P. Mohapatra, “Dynamic real-time task scheduling on hypercubes,” Journal of Parallel and Distributed Computing, vol. 46, pp. 91-100, 1997.
[19] D. A. Read and R. M. Fujimoto, “Multi- computer network: message-based parallel Processing,” MIT Press, Cambridge MA, 1987.
[20] Y. Saad and M. H. Schultz, “Topological properties of hypercubes,” IEEE Transactions on Computers, vol. C-37, pp. 867-872, 1988.
[21] A. Wagner, “Embedding arbitrary binary trees in a hypercube,” Journal of Parallel and Distributed Computing, vol. 7, pp. 503-520, 1989.
[22] A. Y. Wu, “Embedding of tree networks into hypercubes,” Journal of Parallel and Distributed Computing, vol. 2, pp. 238-249, 1985.
[23] J. Wu, “Optimal broadcasting in hypercubes with link faults using limited global information,” Journal of Systems Architecture, vol. 42, pp. 367-380, 1996.
[24] J. Wu, E. B. Fernandez, and Y. Luo, “Embedding of Binomial Trees in Hypercubes with Link Faults,” Journal of Parallel and Distributed Computing, vol. 54, pp. 59-74, 1998.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔