臺灣博碩士論文加值系統

略

In this thesis we propose a new Hamiltonian cycle model to exploit the feature of the symmetric networks. Based on this model two efficient multicast routing algorithms, uniform multicast routing algorithm and fixed multicast routing algorithm, are developed. These multicast routing algorithms allow the multicast communication to utilize the channels uniformly in order to balance the path length of the message worms, making the multicasting more efficient in the symmetric networks. Then the Hamiltonian cycle model is mapped to torus and star networks. Thus the messages can be multicasted in these two networks using uniform and fixed multicast routing algorithms. The simulation results are also given to show the performance of these two multicast routing algorithms on the 2D/3D torus networks and the 6-star network. These two multicast routing algorithms do perform significantly faster multicasting than the Hamiltonian path based schemes on the symmetric networks. Besides providing the efficient multicast communication, the Hamiltonian cycle model only needs two sets of the virtual channels to avoid the deadlock. The Hamiltonian cycle model is really an efficient and economic strategy for multicasting in the symmetric networks.
Overview of Some Background Knowledge
Hamiltonian Cycle Model
Multicast Routing Algorithms
Hamiltonian Cycle Model in Torus and Star Networks
Performance Study
Conculsions and Future Work

S. B. Akers, D. Harel and B. Krishnamurthy, ``The star graph: an attractive
alternative to the n-cube,'' Proceedings of 1987 International Conference
on Parallel Processing, pp. 393-400
S. B. Akers and B. Krishnamurthy, ``A Group-Theoretic Model for Symmetric
Interconnection Networks,'' IEEE transactions on Computers, vol. 38,
no. 4, pp. 555-566. 1989
W. C. Athas and C. L. Seitz, ``Multicomputers: Message-Passing Concurrent
Computers,'' Computer, vol. 21, no. 8, pp. 9-24,1988
T. S. Chen, C. Y. Chang, and J. P. Sheu, ``Efficient Multicast Communication
in Multidestination Wormhole-Routed Mesh Networks,'' Proceedings
of International Conference on Parallel and Distributed Processing
Techniques and Applications, vol. 11, pp. 674-681, 1996
T. S. Chen, N. C. Wang, and C. P. Chu, ``Path-Based Multicast Communication
in Wormhole-Routed Star Graph Multicomputers,'' Proceedings of International
Conference on Parallel and Distributed System, pp. 350-357, 1998
W. J. Dally, ``Virtual-Channel Flow Control,'' IEEE transactions on
Parallel and Distributed Systems, vol. 3, no. 2, pp. 194-205, 1992
W. J. Dally and C. L. Seitz, ``The Torus Routing Chip,'' Journal of
Distributed Computing, vol. 1, no. 3, pp. 187-196, 1986
W. J. Dally and C. L. Seitz, ``Deadlock-free message routing in multiprocessor
interconnection networks,'' IEEE transactions on Computers, vol. 36,
pp. 547-553, 1987
J. Duato, S. Yalamanchili, and L. Ni, Interconnection Networks: An
Engineering Approach, IEEE COMPUTER SOCIETY, Los Alamitos, 1997
F. P. Fan and C. T. King, ``Turn Grouping for Efficient Multicast in
Wormhole Mesh Networks,'' Proceedings of 6th Symp. on Frontiers of
Massively Parallel Computing, pp. 50-57, 1996
E. Fleury and P. Fraigniaud, ``Strategies for Path-Based Multicasting
in Wormhole-Routed Meshes,'' Journal of Parallel and Distributed Computing,
vol. 53, pp. 26-62, 1998
M. J. Flynn, ``Some Computer Organizations and Their Effectiveness,''
IEEE transactions on Computing, C-21, pp. 948-960, 1972
A. Geist, A. Beguelin, J. Dongarra, R. Manchek, W. Jaing, and V. Sunderam,
PVM: A Users' Guide and Tutorial for Networked Parallel Computing,
MIT Press, Boston, 1994.
K. Hwang and Z. Xu, Scalable Parallel Computing: Technology, Architecture,
Programming, WCB McGraw-Hill, 1997
. E. Kessler and J. I. Schwarzmeier, ``CRAY T3D, A New Dimension for
Cray Research,'' Compcon Spring '93, Digest of Papers, pp. 176-182
X. Lin, P. K. McKinley, and L. M. Ni, ``Deadlock-Free Multicast Wormhole
Routing in 2D Mesh Multicomputers,'' IEEE transactions on Parallel
and Distributed Systems, vol. 5, no. 8, pp. 793-804, 1994
X. Lin and L. M. Ni, ``Deadlock-Free Multicast Wormhole Routing in
Multicomputer Network,'' Proceedings of International Symposium on
Computer Architecture, pp. 116-124, 1991
D. H. Linder and J. C. Harden, ``An Adaptive and Fault-Tolerance Wormhole
Routing Strategy for k-ary n-cubes,'' IEEE transactions on Computers,
vol. 40, no 1, pp 2-12, 1991
P. K. McKinley, H, Xu, A. H. Esfahanianm, and L. M. Lin, ``Unicast-based
Multicast Communication in Wormhole-Routed Networks,'' IEEE transactions
on Parallel and Distributed Systems, vol. 5, no. 12, pp. 1252-1265,
1994
L. M. Ni, ``Issues in designing truly scalable interconnection networks,''
Proceedings of 1996 ICPP Workshop on Challenges for Parallel Processing,
pp. 74-83, 1996
L. M. Ni and P. K. McKinley, ``A Survey of Wormhole Routing Techniques
in Direct Networks,'' Computer, vol. 26, no. 2, pp. 62-76, 1993
M. Nigam, S.Sahni, and B. Kirshnamurthy, ``Embedding Hamiltonians and
Hypercubes in Star Interconnection Graphs,'' Proceedings of International
Conference on Parallel Processing, vol. 3, pp. 340-343, 1990
D. K. Panda, S. Singal, R. Kesavan, ``Multidestination Message Passing
in Wormhole k-ary n-cube Networks with Base Routing Conformed Paths,''
IEEE transactions on Parallel and Distributed Systems, vol. 10, pp.
76-96, 1999
D. K. Panda, S. Singal, and P. Prabhakaran, ``Multidestination Message
Passing Mechanism Confirming to Base Wormhole Routing Scheme,'' Proceedings
of the Parallel and Computer Routings and Communication Workshop (PCRCW
'94), Lecture Note in Computer Science, no. 853, pp. 131-145, 1994
T. S. Chen, C. Y. Chang, and J. P. Sheu, ``Efficient Multicast Communication
in Multidestination Wormhole-Routed Mesh Networks,'' Proceedings
of International Conference on Parallel and Distributed Processing
Techniques and Applications, vol. 11, pp. 674-681, 1996
D. F. Robinson, P. K. McKinley, and B. H. C. Cheng, ``Path-Based Multicast
Communication in Wormhole-routed Unidirectional Torus Network,'' Journal
of Parallel and Distributed Computing, vol. 45, pp. 104-121, 1997
M. Snir, S. Otto, S. Huss-Lederman, D. Walker, J. Dongarra, MPI: The
Complete Reference Vol. 1, The MPI Core, MIT Press, Boston, 1998.
Y. C. Tseng, T. Y. Juang, and M. H. Yang, ``An Euler-Path-Based Multicasting
Model for Wormhole-Routed Networks: Its Applications to Damaged 2D
tori and Meshes,'' Proceedings of International Performance, Computing,
and Communication Conference, pp. 444-450, 1997
Y. C. Tseng, D. K. Panda, and T. H. Lai, ``A Trip-Based Multicasting
Model in Wormhole-Routed Networks with Virtual Channels,'' IEEE transactions
on Parallel and Distributed Systems, vol. 7, no. 2, pp. 138-150, 1996
N. C. Wang, Multicast Algorithms in Wormhole-Routed Star Graph Interconnection
Networks, M.S. Thesis, Institute of Computer Science and Information
Engineering, National Cheng Kung University, 1998
X. Wu and X.H. Sun, ``Performance Modeling for Interconnection Networks,''
Proceedings of High Performance Computing in the Asia-Pacific Region
2000, vol. 1, pp 380-385, 2000