跳到主要內容

臺灣博碩士論文加值系統

(3.87.33.97) 您好!臺灣時間:2022/01/27 16:38
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:李增奎
研究生(外文):Tseng-Kuei Li
論文名稱:交錯立方體
論文名稱(外文):The Shuffle Cubes
指導教授:徐力行徐力行引用關係譚建民譚建民引用關係
指導教授(外文):Lih-Hsing HsuJimmy J.M. Tan
學位類別:博士
校院名稱:國立交通大學
系所名稱:資訊科學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:116
中文關鍵詞:連結網路超立方體直徑邊壅塞度交錯立方體寬直徑有錯漢米爾頓
外文關鍵詞:Interconnection networksHypercubesDiameterEdge congestionShuffle cubesWide diameterFault hamiltonian
相關次數:
  • 被引用被引用: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-tolerant
ring 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.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top