臺灣博碩士論文加值系統

在文獻 [3]中, 陳尚寬學長, 黃光明老師, 以及劉昱綺學姊提出了「混合的弦環式網路」的一個新的網路架構。 他們推導出「混合的弦環式網路」的直徑的上下界, 發現「混合的弦環式網路」的直徑可達到(2N)^(1/2) (N為網路中的節點數), 相較於使用相同數量硬體的雙環式網路而言, 這是一項很大的改進。 在這篇論文中, 我們提出一個只花O(logN)時間的計算「混合的弦環式網路」的直徑的演算法。

Recently, Chen, Hwang and Liu [3] proposed a new network called the mixed chordal ring network which is very comparable to the double-loop network. They proved the
surprising result that the mixed chordal ring network can achieve diameter about (2N)^(1/2) which is a huge improvement over the double-loop network (here N is the number of nodes in the network). They derived the upper and the lower bounds for the diameter of a mixed chordal ring
network. The purpose of this thesis is to propose an O(log N)-time algorithm for deriving the exact value of the diameter of a mixed chordal ring network.

[1] B. W. Arden and H. Lee, Analysis of chordal ring
networks, IEEE Trans. Comput. 30 (1981) 291-295.

[2] C. Y. Chen and F. K. Hwang, "The minimum distance
diagram of double-loop networks", IEEE Trans. Comput.
49 (2000), 977-979.

[3] S. K. Chen, F. K. Hwang and Y. C. Liu, Some
combinatorial properties of mixed chordal rings, J.
Interconnection Networks 4 (2003), 3-16.

[4] Y. Cheng and F. K. Hwang, Diameters of weighted double
loop networks, J. Algorithms 9 (1988), 401-410.

[5] M. A. Fiol, M. Valero, J. L. A. Yebra, I. Alegre, and
T. Lang, Optimization of double-loop structures for
local networks, in Proc. XIX Int. Symp. MIMI'82, Paris,
France (1982), 37-41.

[6] M. A. Fiol, J. L. A. Yebra, I. Alegre, and M.
Valero, "A discrete optimization problem in local
networks and data alignment", IEEE Trans. Comput. C-36
(1987), 702-713.

[7] F. K. Hwang, A "complementary survey on double-loop
networks", Theoret. Comput. Sci. A 263 (2001), 211-229.

[8] F. K. Hwang and P. E. Wright, Survival reliability of
some double-loop netwroks and chordal rings, IEEE
Trans. Comput. 44 (1995) 1468-1471.

[9] F. K. Hwang and Y. H. Xu, "Double loop networks with
minimum delay", Disc. Math. 66 (1987), 109-118.

[10] O. J. Rodseth,Weighted multi-connected loop networks,
Discr Math. 148 (1996), 161-173.

[11] C. K. Wong and D. Coppersmith, "A combinatorial
problem related to multimodule memory organizations",
J. Assoc. Comput. Mach. 21 (1974), 392-402.