臺灣博碩士論文加值系統

兩個點之間簡單的訊息傳遞及容錯能力是迪布恩圖具有吸引力的特性。在有向的迪布恩圖中，從點V到點W的最短路徑可藉由比較兩點的標籤中其中一點的右邊與另一點左邊的共同部份或其中一點的左邊與另一點右邊的共同部份而得知。當共同部份確定後，將依其結果使用左運算或右運算來完成繞徑行程。不過這個方法在無向的迪布恩圖中就不一定可以一直找到兩點之間的最短路徑。本論文提出一個尋找最短路徑的方法，這個方法需要的計算時間為 O(m2)。此外，亦提出一個容錯的繞徑方法，這個方法在二元迪布恩網圖環境下提供兩點之間兩條不相交的路徑：一條為兩點之間的最短路徑，而另一條與最短路徑不相交的路徑，長度頂多為 m + log2m + 4。在二元迪布恩網圖環境下，我們的方法允許一個點的毀損。

在並行系統中，一個公平的輪流系統，如果每個處理器能在最少的步驟中具有進入一次臨界區間的機會，那這樣的系統設計是最佳的。這樣的設計如同使用最少的顏色，對系統內的處理器塗色，而且是互相連接的處理器不能塗相同的顏色。我們提出一個簡單又快速的方法解決了無向二元迪布恩圖的塗色問題。在二元迪布恩圖中，我們的方法使用了三個顏色，是最佳的方法。我們也推展這個方法，嘗試解決 k元迪布恩圖的塗色問題。我們首先提出一個簡單的方法解決 k元迪布恩圖的塗色問題，這個方法需要 2k 個顏色。藉由更深入的分析，只要將方法稍為修改，便可將塗色所需要的顏色數目降低至 k+1。

de Bruijn graphs are attractive due to its simplicity of routing messages between two nodes and the capability of fault tolerance. The shortest path from a node V to a node W in the directed binary de Bruijn graph can be obtained by firstly determining the longest substring, common to the right/left of V and to the left/right of W. Then L-operations/R-operations are performed to finish this routing process. However, this method does not always find the shortest path in the undirected binary de Bruijn graph. In this dissertation, we propose a shortest path routing algorithm which requires O(m2) time. We also design a fault-tolerant routing algorithm which provides the shortest path and another node-disjoint path of length at most m + log2m + 4. Our algorithm can tolerate one node failure in the m-dimensional binary de Bruijn network.

In concurrent systems, a 1-fair alternator design is optimal if each processor can execute the critical step once in the fewest steps. This problem corresponds to use the minimum number of colors to color the processors in the system. Thus, the optimal
design of a 1-fair alternator problem can be transformed into the coloring problem. We propose a simple and fast algorithm to solve the node coloring problem on the undirected binary de Bruijn graph. In our algorithm, the number of colors used is 3, and it is an optimal design. We also extend our method to solve the coloring problem on k-ary de Bruijn graphs. We first present a simple algorithm which needs 2k colors. By slight improvement, the number of required colors is reduced to k+1.

CONTENTS
Chapter 1.Introduction … 1
Chapter 2.Previous Researches … 8
2.1 Recursive Structure of de Bruijn Graphs … 9
2.2 de Bruijn Sequences … 11
2.3 Routing Algorithms on de Bruijn Networks … 16
2.4 Broadcasting Algorithms … 22
2.5 Generalized de Bruijn Graphs … 24
2.6 Fault-Tolerant Ring Embedding in de Bruijn Networks … 27
2.7 The Shuffle-Exchange Graph and the de Bruijn Graph … 31
2.8 The de Bruijn Network as a Sorting Network … 33
2.9 Hierarchical Design for de Bruijn Networks …36
2.10 Simulation of Hypercube Algorithms …40
Chapter 3.The Routing Problems on de Bruijn Networks … 43
3.1 Notations … 45
3.2 The Shortest Path Routing Algorithm … 46
3.3 Fault-tolerant Routing … 53
3.3.1 Case l …54
3.3.2 Case 2 … 59
3.3.3 Case 3 … 62
3.3.4 Case 4 … 63
3.3.5 Case 5 … 66
3.4 Summary … 67
Chapter 4.The Node Coloring Method on de Bruijn Graphs … 69
4.1 The Design of Node Coloring for the Binary de Bruijn Graph … 72
4.2 A Coloring Method for the k-ary de Bruijn Graph with 2k Colors … 79
4.3 A Coloring Method for the k-ary de Bruijn Graph with k+1 Colors … 84
4.4 The Design for l-fair Alternator … 90
4.5 Summary … 94
Chapter 5. Conclusions … 96

[1]A. V. Aho, J. E. Hopcroft, and J. D. Ullman, Data Structures and Algorithms. Addison-Wesley Publishing Company, 1983.
[2]A. Arora, S. Dolev, and M. Gouda, “Maintaining digital clocks in step,” Parallel Processing Letters, Vol. 1, pp. 11—18, 1991.
[3]S. Baase, Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley Publishing Company, 1988.
[4]P. Banerjee, J. T. Rahmeh, C. Stunkel, V. S. Nair, K. Roy, V. Balasubranian, and J. A. Abraham, “Algorithm-based fault tolerance on a hypercube multiprocessor,” IEEE Transactions on Computers, Vol. 39, No. 9, pp. 1132—1145, Sep. 1990.
[5]M. Beale and S. M. S. Lau, “Complexity and auto-correlation properties of a class of de Bruijn sequence,” Electronic Letters, Vol. 22, pp. 1046—1047, May 1986.
[6] J. C. Bermond and P. Fraigniaud, “Broadcasting and gossiping in de Bruijn networks,” SIAM Journal on Computing, Vol. 23, pp. 212—225, Feb. 1994.
[7]J. C. Bermond, Z. Liu, and M. Syska, “Mean eccentricities of de Bruijn networks,” Networks, Vol. 30, pp. 187—203, 1997.
[8]J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. The Macmillan Press Ltd., 1976.
[9]G. Brassard and P. Bratley, Algorithmics: Theory and Practice. Prentice-Hall, Inc., 1988.
[10]J. Bruck, R. Cypher, and C. T. Ho, “Fault-fault de bruijn and shuffle-exchange networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 5, pp. 548—553, May 1994.
[11]A. Chan, R. Games, and E. Key, “On the complexities of debruijn sequences,” Journal of Combinatoral Theory Series A, Vol. 33, No. 3, pp. 233—246, 1982.
[12]M. Y. Chan and F. Chin, “Parallelized simulation of grids by hypercubes,” Proc. of International Computer Symposium, Hsinchu, Taiwan, R. 0. C., pp. 535—544, Dec. 17—19, 1990.
[13]T. F. Chan and Y. Saad, “Multigrid algorithms on the hypercube multiprocessor,” IEEE Transactions on Computers, Vol. C-35, No. 11, pp. 969—977, Nov. 1986.
[14]M. Chean and J. A. B. Fortes, “A taxonomy of reconfiguration techniques for fault-tolerant processor arrays,” IEEE Computers, Vol. 23, No. 1, pp. 55—69, Jan. 1990.
[15]M. S. Chen and K. G. Shin, “Adaptive fault-tolerant routing in hypercube multicomputers,” IEEE Transactions on Computers, Vol. 39, No. 12, pp. 1406— 1416, Dec. 1990.
[16]T. C. Chen, V. Y. Lum, and C. Tung, “The rebound sorter: An efficient sort engine for large files,” Proc. of the International Conference on Very Large Data Bases, pp. 312—318, 1978.
[17]N. D. de Bruijn, “A combinatorial problem,” Koninklijke Netherlands: Academe Van Wetenschappen, Vol. 49, pp. 758—764, 1946.
[18]D. Du and F. K. Hwang, “Generalized de Bruijn digraphs,” Networks, Vol. 18, pp. 27—38, 1988.
[19]D. Z. Du, Y. D. Lyuu, and D. F. Hsu, “Line digraph iterations and connectivity analysis of de Bruijn and kautz graphs,” IEEE Transactions On Computers, Vol. 42, pp. 612—616, May 1993.
[20]K. Efe and A. Fernández, “Products of networks with logarithmic diameter and fix degree,” IEEE Transactions on Parallel and Distributed Systems, Vol. 6, pp. 963—975, Sep. 1995.
[21]A. H. Esfahanian and S. L. Hakimi, “Fault-tolerant routing in debruijn communication networks,” IEEE Transactions on Computers, Vol. C-34, No. 9, pp. 777—788, Sep. 1985.
[22]T. Etzion and A. Lempel, “On the distribution of debruijn sequences of given complexity,” IEEE Transactions on Information Theory, Vol. IT-30, No. 4, pp. 611—614, 1984.
[23]H. Fredricksen, “A survey of full length nonlinear shift register cycle algorithms,” SIAM Review, Vol. 24, No. 2, pp. 195—221, Apr. 1982.
[24]R. Ginosar and D. Egozi, “Topological comparison of perfect shuffle and hypercube,” International Journal of Parallel Programming, Vol. 18, No. 1, pp. 37—68, 1989.
[25]M. G. Gouda and F. Haddix, “The alternator,” Proc. 19 th IEEE International Conference on Distributed Computing Systems, pp. 48—53, 1999.
[26]Q. P. Gu and S. Peng, “Cluster fault-tolerant routing in star graphs,” Networks, Vol. 35, pp. 83—90, 2000.
[27]R. Harbane and C. Padró, “Spanners of de Bruijn and kautz graphs,” Information Processing Letters, Vol. 62, pp. 231—236, 1997.
[28]T. Hasunuma and Y. Shibata, “Counting small cycles in generalized de Bruijn digraphs,” Networks, Vol. 29, pp. 39—47, 1997.
[29]T. Herman and S. Ghosh, “Stabilizing phase-clocks,” Information Processing Letters, Vol. 54, pp. 259—265, 1995.
[30]M. C. Heydemann, J. Opatrny, and D. Sotteau, “Broadcasting and spanning trees in de Bruijn and kautz networks,” Discrete Applied Mathematics, Vol. 37, pp. 297—317, 1992.
[31]D. F. Hsu and D. S. L. Wei, “Efficient routing and sorting schemes for de Bruijn networks,” IEEE Transactions on Parallel and Distributed Systems, Vol. 8, pp. 1157—1170, Nov. 1997.
[32]S. T. Huang, “Leader election in uniform rings,” ACM Trans. Programming Language Systems, Vol. 15, pp. 563—573, 1993.
[33]S. T. Huang and B. W. Chen, “Optimal 1-fair alternators,” Information Processing Letters, Vol. 80, pp. 159—163, 2001.
[34]M. Imase and M. Itoh, “Design to minimize diameter on building-block network,” IEEE Transactions on Computers, Vol. C-30, No. 6, pp. 439—442, Jun. 1981.
[35]M. Imase and M. Itoh, “A design for directed graph with minimum diameter,” IEEE Transactions on Computers, Vol. C-32, No. 8, pp. 782—784, Aug. 1983.
[36]J. S. Jwo, “Properties of star graph, bubble-sort graph, prefix-reversal graph and complete-transposition graph,” Journal of Information Science and Engineering, Vol. 12, pp. 603—617, 1996.
[37]S. Kulkarni and A. Arora, “Multitolerance barrier synchronization,” Information Processing Letters, Vol. 64, pp. 29—36, 1997.
[38]S. Y. Kuo and W. K. Fuchs, “Reconfigurable cube-connected cycles architectures,” Journal of Parallel and Distributed Computing, Vol. 9, No. 1, pp. 1—10, 1990.
[39]K. Y. Lee, G. Liu, and H. F. Jordan, “Hierarchical networks for optical communications,” Journal of Parallel and Distributed Computing, Vol. 60, pp. 1—16, 2000.
[40]F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. 2929 Campus Drive, Suite 260, San Mateo, CA 94403:
Morgan Kaufmann Publishers, Inc., 1992.
[41]J. C. Lin and N. C. Hsien, “Reconfiguring binary tree structures in a fault supercube with unbounded expansion,” Parallel Computing, Vol. 28, pp. 471— 483, 2002.
[42]G. Liu and K. Y. Lee, “Optimal routing algorithms de bruijn networks,” Proceedings of 1993 International Conference on Parallel Processing, pp. III 167— 174, 1993.
[43]M. Liu, “Homomorphisms and automorphisms of 2-d debruijn-good graph,” Discrete Mathematics, Vol. 85, No. 1, pp. 105—109, 1990.
[44]Z. Liu and T. Y. Sung, “Routing and transmitting problems in de Bruijn networks,” IEEE Transactions on Computers, Vol. 45, pp. 1056—1062, Sep. 1996.
[45]Y. D. Lyuu, “Fast fault-tolerant parallel communication for de Bruijn and digit-exchange networks using information dispersal,” Networks, Vol. 23, pp. 365— 378, 1993.
[46]J. W. Mao and C. B. Yang, “Shortest path routing and fault-tolerant routing on de Bruijn networks,” Networks, Vol. 35, pp. 207—215, 2000.
[47]J. W. Mao and C. B. Yang, “A design for node coloring and 1-fair alternator on de bruijn networks,” Proc. of the International Conference on Parallel and Distributed Processing Techniques and Applications, Las Vegas, Nevada, USA, June 2003.
[48] G. Mayhew and S. W. Golomb, “Linear spans of modified de Bruijn sequences,” IEEE Transactions on Information Theory, Vol. 36, pp. 1166—1167, 1990.
[49]J. Misra, “Phase synchronization,” Information Processing Letters, Vol. 38, pp. 101—105, 1991.
[50]B. Obrenić, M. C. Herbordt, A. L. Rosenberg, and C. C. Weems, “Using emulations to enhance the performance of parallel architectures,” IEEE Transactions on Parallel and Distributed Systems, Vol. 10, No. 10, pp. 1067—1081, Oct. 1999.
[51]D. K. Pradhan and S. M. Reddy, “A fault-tolerant communication architecture for distributed systems,” IEEE Transactions on Computers, Vol. 31, pp. 863— 870, Sep. 1982.
[52]F. P. Preparata and J. Vuillemin, “The cube-connected cycles: A versatile network for parallel computation,” Commun. ACM, Vol. 24, No. 5, pp. 300— 309, May 1981.
[53] C. P. Ravikumar, T. Rai, and V. Verma, “Kautz graphs as attractive logical topologies in multihop lightwave networks,” Computer Communications, Vol. 20, pp. 1259—1270, 1997.
[54] S. M. Reddy, D. K. Pradhan, and J. C. Kuhl, “Direct graphs with minimal and maximal connectivity,” Tech. Rep., School of Engineering, Oakland University, July 1980.
[55] R. A. Rowley and B. Bose, “Fault-tolerant ring embedding in de Bruijn networks,” IEEE Transactions on Computers, Vol. 42, pp. 1480—1486, Dec. 1993.
[56]M. R. Samatham and D. K. Pradhan, “The de Bruijn multiprocessor network: A versatile parallel processing and sorting network for VLSI,” IEEE Transactions on Computers, Vol. 38, No. 4, pp. 567—581, 1989.
[57] W. Shi and P. K. Srimani, “A regular scalable fault tolerant interconnection network for distributed processing,” Parallel Computing, Vol. 27, pp. 1897— 1919, 2001.
[58]S. W. Song, “A highly concurrent tree machine for data base applications,” Proc. of the International Conference on Parallel Processing, pp. 259—268, Aug. 1980.
[59] M. A. Sridhar, “On the connectivity of the de Bruijn graph,” Information Processing Letters, Vol. 27, pp. 315—318, 1988.
[60]M. A. Sridhar, “The undirected de Bruijn graph: Fault tolerance and routing algorithms,” IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, Vol. 39, pp. 45—48, 1992.
[61]M. A. Sridhar and C. S. Raghavendra, “Fault-tolerant networks based on the de bruijn graph,” IEEE Transactions on Computers, Vol. 40, No. 10, pp. 1167— 1174, Oct. 1991.
[62]H. S. Stone, “Parallel processing with perfect shuffle,” IEEE Transactions on Computers, Vol. C-20, No. 2, pp. 153—161, 1971.
[63]N. Tsuda, “Fault-tolerant processor arrays using additional bypass linking allocated by graph-node coloring,” IEEE Transactions on Computers, Vol. 49, pp. 431—442, May 2000.
[64] N. Tsuda, “Fault-tolerant ring- and toroidal mesh-connected processor arrays able to enhance emulation of hypercubes,” IEEE Transactions on Information and Systems, Vol. E84-D, pp. 1452—1461, Nov. 2001.
[65]C. B. Yang and Y. J. Yeh, “The model and properties of the traffic light problem,” Proc. of international Conference on Algorithms, Kaohsiung, Taiwan, pp. 19—26, Dec. 1996.