臺灣博碩士論文加值系統

(3.87.33.97) 您好！臺灣時間：2022/01/27 16:38

:::

詳目顯示

:

• 被引用:0
• 點閱:139
• 評分:
• 下載:16
• 書目收藏:0
 一個平行分散式系統的效能深受其網路拓樸的影響，n維的超立方體Qn便是一個很有名的連結網路拓樸，它具有許多好的特性，但仍然沒有完全善用其硬體資源，因此，有許多它的變形被提出，譬如：雙扭立方體，雙扭立方體改善了超立方體的直徑，使得減少為大約一半。 在論文的第一部份，我們研究n維雙扭立方體TQn的邊壅塞度，對一個圖的某個路由而言，邊壅塞度代表的是所有邊中最高的訊息流量，因此，一個圖的邊壅塞度即可定義為所有路由中最小的邊壅塞度，相反地，如果一個路由的邊壅塞度即是某個圖的邊壅塞度，我們稱此路由為最佳的。在這個研究裡，我們發現TQn原始路由的邊壅塞度大於2n，這也就是為什麼在之前的研究中顯示TQn的動態效能反而比Qn差的原因，因此，我們提出一個新的路由演算法，並且證明了該路由的邊壅塞度是2n，這剛好與我們所算得的下限相等，因而證明了此路由是最佳的，而TQn的邊壅塞度就是2n，這是和Qn相同的。另一方面，我們同時也證明了TQn的切半寬度為2n-1。 在論文的第二部份，我們試著模仿雙扭立方體的架構去建構一個新的變形，這個新的變形稱作交錯立方體，這個嘗試是起自於對於是否存在一個更低直徑變形的懷疑。一個交錯立方體SQn，與Qn一樣具有2n個點，而每個點連結n條邊，更重要的是，我們證明了，它的直徑是 ，這大約是TQn的直徑的一半。這個結果比之前所有超立體變形的直徑都要好。 在論文的第三部份，我們探討SQn的一些特性。首先，我們證明了SQn的連通度為n，這表示當有壞點或壞線但不超過n-1個時，SQn還會是連通的。其次，我們證明了SQn寬直徑的上限為 ，寬直徑所顯示的是一個網路拓樸在多路徑路由下的效能，這個結果說明了在SQn中任兩點間，存在n條不相交路徑，其最大的長度不超過 ，同時這個結果也保證了在壞點或壞線不超過n-1個時，SQn的直徑不會超過 。第三，我們證明了SQn是具有漢米爾頓環路的，這表示在SQn裡，是可以在膨脹度1、壅塞度1、負載1的條件下嵌入號誌環。第四，我們證明了SQn是(n-2)-漢米爾頓及(n-3)-漢米爾頓連通的，前項的結果保證在壞點或壞線不超過n-2個時，SQn仍具有漢米爾頓環路，後一項的結果則保證在壞點或壞線不超過n-3個時，SQn中的任兩點之間仍存在漢米爾頓路徑，這兩個結果都是最佳的，因為，SQn是n正則的。最後，我們證明了SQn的邊壅塞度大於2n，這是SQn的一個缺點，我們希望在未來，我們可以建構出一個具有較小邊壅塞度的變形。 在論文的最後一個部份，我們將交錯立方體的架構加以一般化：給定一個正整數常數g，我們發展出一套方法來建構一個n維的一般化交錯立方體，它的直徑會是 ，其中C也是一個正整數常數。這是一個重要的結果，因為它說明了我們可以儘可能地降低直徑，只要n夠大的話。
 The performance of a distributed system is significantly determined by its network topology. The $n$-dimensional hypercube, denoted by $Q_n$, is one of the most famous interconnection network topologies. It possesses many good properties, but it does not make the best use of its hardware. As a result, there are many variations of $Q_n$ being proposed, for example, the $n$-dimensional twisted cubes $TQ_n$. The diameter of $TQ_n$ is about half of that of $Q_n$, which is an improvement. In the first part of the dissertation, we study the edge congestion of $TQ_n$. For a routing algorithm of a graph, the edge congestion is the maximum traffic among all edges. Then the edge congestion of a graph is the minimum edge congestion among all routings of the graph. We say that a routing of a graph is optimal if the edge congestion of the routing is minimum. In the study, we find the edge congestion of the original routing of $TQ_n$ is greater than $2^n$. This is the reason why the dynamic performance of $TQ_n$ is worse than that of $Q_n$ in the previous studies. Thus, we propose a new routing algorithm and show that the edge congestion of the routing is $2^n$, which matches the lower bound we have obtained. So the routing is optimal with respect to the edge congestion, and the edge congestion of $TQ_n$ is $2^n$, which is equal to that of $Q_n$. And we simultaneously show that the bisection width of $TQ_n$ is $2^{n-1}$. In the second part of the dissertation, we try to construct a new variation based on the structure of the twisted cube, called the shuffle cube. The attempt arises from the doubt of whether the diameter of the variations of $Q_n$ can be reduced more. The $n$-dimensional shuffle cubes, denoted by $SQ_n$, also has $2^n$ nodes, and each node in $SQ_n$ connects to $n$ edges, which is the same as $Q_n$. Most importantly, we show that the diameter of $SQ_n$ is $\lceil \frac{n}4 \rceil +3$, which is about half of that of $TQ_n$. This result is better than the various diameters of all the previous variations of the hypercubes. In the third part of the dissertation, we investigate some properties of $SQ_n$. First, we show that the connectivity of $SQ_n$ is $n$, which means that $SQ_n$ is connected when the number of faults is less than $(n-1)$. This result is optimal since $SQ_n$ is $n$-regular. Second, we show that the wide diameter of $SQ_n$ is bounded by $\lceil \frac{n}4 \rceil +7$. The wide diameter is one of the indicators measuring the performance of multi-path routing of the given network topology. This result shows that between any pair of nodes in $SQ_n$, there are $n$ internally disjoint paths of length at most $\lceil \frac{n}4 \rceil +7$. It also guarantees that when there are at most $(n-1)$ faults in $SQ_n$, the diameter of $SQ_n$ is bounded by $\lceil \frac{n}4 \rceil +7$. Third, we show that $SQ_n$ is hamiltonian, which means that the token ring can be embedded into $SQ_n$ with dilation 1, congestion 1, and load 1. Fourth, we show that $SQ_n$ is $(n-2)$-hamiltonian and $(n-3)$-hamiltonian connected. The former guarantees that $SQ_n$ is still hamiltonian when there are at most $(n-2)$ faults in it. And the latter guarantees that for any pair of nodes $x$ and $y$ in $SQ_n$, there still exists a hamiltonian path between $x$ and $y$ when there are at most $(n-3)$ faults in $SQ_n$. The result is optimal since $SQ_n$ is $n$-regular. Finally, we show that the edge congestion of $SQ_n$ is greater than $2^n$. This is a drawback of $SQ_n$. We hope that we will construct a new variation with lower edge congestion in the future. In the final part of the dissertation, we generalize the model of the shuffle cube. Given a positive integer constant $g$, we develop a strategy to construct an $n$-dimensional generalized shuffle cube with diameter $\lceil \frac{n}g \rceil +C$, where $C$ is also a positive integer constant. This is an important result since it shows that we can reduce the diameter as we wish if $n$ is large enough.
 1. Introduction 1.1 Basic Terms and Notations 1.2 Edge Congestion and Bisection Width 1.3 The Hypercubes and Their Variations 1.3.1 Hypercubes 1.3.2 Twisted Cubes 1.3.3 Crossed Cubes and Mobius Cubes 1.3.4 Other Variations 1.4 Properties of the Hypercubes and Their Variations 1.5 Motivation and Results 1.6 Organization of the Dissertation 2. Edge Congestion of the Twisted Cubes 2.1 A Lower Bound of the Edge Congestion of the Twisted Cubes 2.2 Edge Congestion of the Original Routing Algorithms for the Twisted Cubes 2.3 A New Routing Algorithm for the Twisted Cubes 2.4 Edge Congestion and Bisection Width of the Twisted Cubes 3. The Shuffle Cubes 3.1 Construction of the Shuffle Cubes 3.2 Routing and Diameter 4. Somce Properties of the Shuffle Cubes 4.1 Connectivity 4.2 Wide Diameter 4.3 Hamiltonian Cycle 4.4 Fault Hamiltonian 4.5 Edge Congestion 5. The Generalized Shuffle Cubes 5.1 Generalization of the Shuffle Cubes 5.2 Routings and Diameters of the Generalized Shuffle Cubes 6. Conclusion and Future Work
 1. S. Abraham and K. Padmanabhan, Performance of the direct binary $n$-cube network for multiprocessors,'' IEEE Trans. Computers, vol. 38, no. 7, pp.1000-1011, July 1989.2. S. Abraham and K. Padmanabhan, The twisted cube topology for multiprocessors: A study in network asymmetry,'' Journal of Parallel and Distributed Computing, vol. 13, pp.104-110, 1991.3. S.B. Akers, D. Harel and B. Krishnamurthy, The star graph: An attractive alternative to the $n$-cube,'' Proceedings of the International Conference on Parallel Processing, pp.393-400, 1987.4. S.B. Akers and B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks,'' IEEE Trans. Computers, vol. 38, no. 4, pp.555-566, Apr. 1989.5. A. AI-Amaway and S. Latifi, Properties and performance of folded hypercubes,'' IEEE Trans. Parallel and Distributed Systems, vol. 2, no. 1, pp.31-42, Jan. 1991.6. V. Auletta, A.A. Rescigno, and V. Scarano, Fualt tolerant routing in the supercube,'' Parallel Processing Letters, vol. 3, no. 4, pp.393-405, 1993.7. L.N. Bhuyan and D.P. Agrawal, Generalized hypercube and hyperbus structures for a computer network,'' IEEE Trans. Computers, vol. C-33, pp.323-333, Apr. 1984.8. J.A. Bondy and U.S.R. Murty, Graph theory with applications, North Holland, New York, 1980.9. M.Y. Chan and S.J. Lee, On the existence of hamiltonian circuits in faulty hypercubes,'' SIAM J. Discrete Mathematics, vol. 4, no. 4, pp.511-527, Nov. 1991.10. C.P. Chang, J.N. Wang, and L.H. Hsu, Topologial Properties of Twisted Cubes", Information Sciences, vol. 113, pp.147-167, 1999.11. C.P. Chang, T.Y. Sung, and L.H. Hsu, Edge congestion and topological properties of crossed cubes,'' IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 1, pp.64-79, Jan. 2000.12. F.B. Chedid and R.B. Chedid, A new variation on hypercubes with smaller diameter,'' Information Processing Letters, vol. 46, pp.275-280, July 1993.13. F.B. Chedid, On the generalized twisted cube,'' Information Processing Letters, vol. 55, pp.49-52, 1995.14. P. Cull and S.M. Larson, Static and dynamic performance of the M$\ddot{o}$bius cubes,'' PARLE'93: Parallel Languages and Architectures Europe, pp.92-103, Springer-Verlag, 1993.15. P. Cull and S.M. Larson, A Linear Equation Model for Twisted Cube Networks,'' ICPADS'94: Internat. Conf. on Parallel and Distributed System (IEEE Computer Society Press, Portland, OR, 1994), pp.709-714, 1994.16. P. Cull and S.M. Larson, The M$\ddot{o}$bius Cubes,''IEEE Transections on Computers, vol. 44, no. 5, pp.647-659, May 1995.17. P. Cull and S.M. Larson, On generalized twisted cubes,'' Information Processing Letters, vol. 55, pp.53-55, 1995.18. W.J. Dally and C.L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks,'' IEEE Transections on Computers, vol. C-36, pp.547-553, May 1987.19. S.K. Das, N. Deo, and S. Prasad, Parallel graph algorithms for hypercube computers,'' Parallel Computing, vol. 13, pp.143-158, 1990.20. D.M. Dias and J.R. Jump, Packet switching interconnection networks for modular systems,'' IEEE Transections on Computers, vol. 14, pp.43-53, Dec. 1981.21. K.Efe, A Variation on the Hypercube with lower Diameter,''IEEE Transections on Computers, vol. 40, no. 11, pp.1312-1316, Nov. 1991.22. K. Efe, The Crossed Cube Architecture for Parallel Computing,'' IEEE Transections on Parallel and Distributed Systems, vol. 3, no. 5, pp.513-524, Sept. 1992.23. K. Efe, P.K. Blackwell, W. Sloubh and T. Shiau, Topological Properties of the Crossed Cube Architecture,'' Parallel Computing, vol. 20, pp.1763-1775, 1994.24. A.H. Estafahanian and S.L. Hakimi, On computing a conditional edge-connectivity of a graph,'' Information Processing Letters, vol. 27, pp.195-199, 1988.25. A.H. Estafahanian, Generalized measures of fault tolerance with application to $n$-cube networks,'' IEEE Transections on Computers, vol. 38, no.11, pp.1585-1591, 1989.26. A.H. Estafahanian, L.M. Ni, and B. Sagan, The twisted $N$-cube with application to multiprocessing,'' IEEE Transections on Computers, vol. 40, no. 1, pp.88-93, Jan 1991.27. T.Y. Feng, A survey of interconnection networks,'' Computer, vol. 14, no. 1, pp.12-27, Dec. 1981.28. C. M. Fiduccia and P. J. Hedrick, Edge congestion of shortest path systems for all-to-all communication,'' IEEE Transections on Parallel and Distributed Systems, vol8, no. 10, pp.1043-1054, Oct. 1997.29. F. Harary, Graph theory, Reading, MA: Addison-wesley, 1972.30. F. Harary, Conditional connectivity,'' Networks, vol. 13, pp.346-357, 1983.31. F. Harary, J. Hayes, and H.J. Wu, A survey of the theory of hypercube graphs,'' Computers and Mathematics, vol. 15, pp.277-289, 1988.32. P. A. J. Hilbers, M. R. J. Koopman, and J. L. A. van de Snepscheut, The twisted cub,'' Parallel Archetectures Languages Europe, Lectue Notes in Computer Science, pp.152-158, June 1987.33. S.Y. Hsieh, G.H. Chen, and C.W. Ho, Longest fault-free paths in star graphs with edge faults,'' IEEE Transections on Computers, vol. 50, no. 9, pp.960-971, Sep. 2001.34. D. Frank Hsu,  On Container Width and Length in Graphs, Groups, and Networks,'' IEICE Transaction on Fundamentals, vol. E77-A, no. 4, pp.668-680, 1994.35. W.T. Huang, Y.C. Chuang, J.M. Tan, and L.H. Hsu Fault-Free Hamiltonian Cycle in Faulty M$\ddot{o}$bius Cubes,'' Journal of Computing and Systems, vol. 4, pp.106-114, 2000.36. W.T. Huang, J.M. Tan, C.N. Hung, and L.H. Hsu, Fault-Tolerant Hamiltonicity of Twisted Cubes,'' accepted by Journal of Parallel and Distributed Computing, 2001.37. W.T. Huang, Y.C. Chuang, L.H. Hsu, and J.M. Tan, On the Fault-Tolerant Hamiltonicity of Faulty Crossed Cubes,'' accepted by IEICE Transaction on Fundamentals, 2002.38. H. Katseff, Incomplete hypercube,'' IEEE Transections on Computers, vol. 37, pp.604-607, 1988.39. M.S. Krishnamoorthy and B. Krishnamurthy, Fault diameter of interconnection networks,'' Comput. Math. Appl, vol. 13, pp.577-582, 1987.40. C.P. Kruskal and M. Snir, The performance of multistage interconnection networks for multiprocessors,'' IEEE Transections on Computers, vol. C-32, pp.1091-1098, Dec. 1983.41. P. Kulasinghe and S. Bettayeb, Embedding Binary Trees into Crossed Cubes,'' IEEE Transections on Computers, vol. 44, no. 7, pp.923-929, July 1995.42. P. Kulasinghe, Connectivity of the Crossed Cube,'' Information Processing Letters, vol. 61, pp.221-226, Feb. 1997.43. J.M. Kumar, L.M. Patnaik, Extended hypercube: A hierarchical interconnection network of hypercubes,'' IEEE Transections on Parallel and Distributed Systems, vol. 3, pp.45-57, 1992.44. S. Lakshmivarahan and S.K. Dhall, A new hierarchy of hypercube interconnection schemes for parallel computers,'' Journal of Supercomputing, vol. 2, pp.81-108, 1988.45. S. Lakshmivarahan and S.K. Dhall, Ring, torus, and hypercube architectures/algorithms for parallel computing,'' Parallel Computing, vol. 25, pp.1877-1906, 1999.46. S. Latifi, S.Q. Zheng, and N. Bagherzadeh, Optimal ring embedding in hypercubes with faulty links,'' Proceedings of the IEEE Symposium on Fault-Tolerant Computing,42, pp.178-184, 1992.47. S. Latifi, Combinatorial analysis of the fault-diameter of the $n$-cube,'' IEEE Transections on Computers, vol. 42, no. 1, pp.27-33, 1993.48. F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, San Mateo, Calif.: Morgan Kaufmann, 1992.49. M. Lewinter and W. Widulski, Hyper-Hamilton Laceable and Caterpillar-Spannable Product Graphs,'' Computers Math. Applic., vol. 34, pp.99-104, 1997.50. T.K. Li, J.M. Tan, L.H. Hsu, and T.Y. Sung, Optimum congested routing strategy on twisted cubes,'' Journal of Interconnection Networks, vol. 1, no. 2, pp.115-134, 2000.51. T.K. Li, J.M. Tan, L.H. Hsu, and T.Y. Sung, The shuffle cubes and their generalization,'' Information Processing Letters, vol. 77, pp.35-41, 2001.52. T.K. Li, J.M. Tan, and L.H. Hsu, The wide diameter of the shuffle cube,'' Proceedings of the Nineteenth IASTED International Conference on Applied Informatics, pp.402-407, Feb. 2001.53. O.A. McBryan and E.F. van de Velde, Hypercube algorithms and implementation,'' SIAM Journal on Scientific and Statistical Computing, vol. 8, pp.227-287, 1987.54. S. $ddot{O}$hring and S. Das, Folded Peterson cube networks: new competitors for the hypercube,'' IEEE Transections on Parallel and Distributed Systems, vol. 7, pp.151-168, 1996.55. M.C. Pease, The indirect binary $n$-cube microprocessor array,'' IEEE Transections on Computers, vol. C-26, pp.458-473, May 1977.56. J.H. Patel, Performance of processor-memory interconnections for multiprocessors,'' IEEE Transections on Computers, vol. C-30, pp.771-780, Oct. 1981.57. R.A. Rowley and B. Bose,Fault-tolerant ring embedding in de-Bruijn networks,'' IEEE Transections on Computers, vol. 42, no. 12, pp.1480-1486, Dec. 1993.58. Y. Saad and M.H. Schultz, Topological Properties of Hypercubes,''IEEE Transections on Computers, vol. 37, no. 7, pp.867-872, July 1988.59. C.L. Seitz, Concurrent VLSI architectures,'' IEEE Transections on Computers, vol. 33, no. 12, p1247-1264, Dec 1984.60. A. Sen, Supercube: An optimally fault tolerant network architecture,'' Acta Inform., vol. 26, pp.741-748, 1989.61. A. Sen, A. Sengupta, and S. Bandyopadnyay, On the routing problem in faulty supercubes,'' Information Processing Letters, vol. 42, pp.39-46, 1992.62. J.J. Sheu and L.H. Hsu, Fault Diameter for Supercubes,'' Parallel Processing Letters, vol. 9, pp.21-30, 1999.63. J.J. Sheu, J.M. Tan, and L.H. Hsu, Routing Properties of Supercubes", Information Sciences, vol. 131, pp.107-128, Jan 2001.64. M.K. Singhvi and Kanad Ghose, The MCube,'' Technical report, State University of New York, 1992.65. Y.C. Tseng, S.H. Chang, and J.P. Sheu, Fault-tolerantring embedding in a star graph with both link and node failure,''IEEE Transections on Parallel and Distributed Systems, pp.1185-1195, 1997.66. K. Wada, T. Ikeo, K. Kawaguchi, and W. Chen, Highly Fault-Tolerant Routings and Fault-Induced Diameter for Generalized Hypercube Graphs,'' Journal of Parallel and Distributed Computing, vol. 43, pp.57-62, 1997.67. A.Y. Wu, Embedding of tree networks into hypercubes,'' Journal of Parallel Distributed Computers, vol. 2, pp.238-249, 1985.68. S.M. Yuan, Topological properties of supercube,'' Information Processing Letters, vol. 37, pp.241-245, 1991.69. S.Q. Zheng and Shahram Latifi, Optimal Simulation of Linear Multiprocess Architectures on Multiply-Twisted Cube Using Generalized Gray Code,'' IEEE Transections on Parallel and Distributed Systems, vol. 7, no. 6, pp.612-619, June 1996.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 階層式交叉立方體泛圈特性之研究 2 迪布恩圖的直徑與寬直徑 3 (n,k)-星狀圖之廣義直徑 4 條件錯誤下交錯立方體上的容錯問題 5 金字塔網路的寬直徑 6 在超立方體上當壞一點之情況下要建造最長路徑之所能容忍的最大錯邊個數 7 K等價圖的拓樸性質和最佳繞徑 8 在有錯邊的莫氏立方體上的全圓性 9 超立方體多處理機電腦系統之集訊、單播、多播與負載平衡 10 超級立方體網路之拓樸性質 11 超立方體與CCC上快速自我傳繞之連接演算法 12 雙扭立方體及交錯立方體網路之拓樸性質 13 二階超網路之研究 14 Cayley圖的直徑與寬直徑之研究 15 雙扭立方體的拓蹼特性

 1 6.黃榮松，各種實地最大有氧能力測驗的效度探討， 中華民國體育會體育學報，第22輯，第249-260頁（1997）。 2 9.薛淑琦、薛淑琳，最大耗氧量的預測方法，中華體育，第3期，第141-148頁（1996）。

 1 蝴蝶圖,遞迴式循環圖及立方體上漢米爾頓容錯性質的研究 2 雙扭超方體, 交錯超方體, 和梅式超方體之容錯漢米爾頓性質 3 無線隨意感應器網路上以拓樸控制暨能源管理之省電模式 4 建立在位元映射索引上的特徵選取方法 5 最佳容錯漢米爾頓及漢米爾頓連接圖 6 (n,k)星狀圖之容錯漢米爾頓性質與容錯漢米爾頓連通性質 7 物件導向地對空飛彈操控訓練系統 8 一個新的行動合作架構 9 有限資源設備上的可延伸式計算環境 10 適應性租約:一個在WWW快取伺服器上的同步機制 11 透過發射功率調整以改善無線網路定位的準確度 12 叢集式網路伺服器分派架構之研究 13 中國山水畫中樹木型態之模擬 14 山形步移漫遊中國山水畫 15 中國水墨畫的渲染技法之研究

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室