在一個多處理機的電腦網路裡每一個處理器常常會為了某種原因而需要與其他處理器相互通訊交換訊息，因此於處理器之間提供一套有效的通訊方式被認為是高效能計算中最重要的一個部份。在這其中研究最多的部份都是重在於單一一個處理器的廣播(broadcast)或是群播(multicast)。但是在實際的情況中，同時有多個處理器在做廣播或群播的現象所佔的比率也相當大，因此在這篇論文中，我們的重點就是著重於改善因為多重群播 （也就是同時間有任意個sources要將訊息multicast到任意個數目的目的地去）時引起的網路擁擠而造成訊息延遲效應的現象。
在這篇論文裡，我們提出一個在2D torus/mesh蟲洞式繞徑網路中用網路切割 (network partition) 的方式來做到多重群播（Multi-node Multicast）的能力。為了降低在網路中傳輸路徑擁擠的情況，因此在我們的方法中首先是定義出一組相互獨立的DDNs(Data Distributed Networks) 以及DCNs(Data Collection Networks)，然後在將這些多重群播重新導向load-balancing到這些獨立的子網路上。在這篇論文中我們提出了幾種定義子網路的方式並且藉由模擬的實驗來驗證我們的方法的確能在某種情況下提供一個不錯的方式來做到多重的群播。
另外，由於電腦技術的快速發展，越來越多人利用高速的交換器與網路設備將多個具有高速計算能力的ＰＣ或是工作站連接在一起而提供出一個具有高速計算能力的分散式運算環境，稱之為Network of Workstations (NOWs)。由於我們先前在 tori/meshes 這種較規則的網路裡利用網路切割的方式在單一或是多重的群播中獲的一些經驗，因此我們在這篇論文中運用“網路切割”概念提出一個單一節點廣播的演算法於NOWs這種網路的拓樸架構呈現不規則變化的環境中，且期望能獲的與tori/meshes上相同的成果。

In a multicomputer network, processors often need to communicate with each other for various reasons, such as data exchange and event synchronization. Efficient communication is critical for high-performance computing in MPPs. This is especially true for those collective communication patterns, such as broadcast and multicast, which involve more than one source and/or destination.
This paper considers the multi-node multicast problem in a wormhole-routed 2D torus/mesh, where an arbitrary number of source nodes each intending to multicast a message to an arbitrary set of destinations. To resolve the contention and the congestion problems, we propose to partition the network into subnetworks to distribute, and thus balance, the traffic load among all network links. Several ways to partition the network are explored. Simulation results show significant improvement over existing results for torus and mesh networks.
More recently, high speed switches and network equipment are used to connect high performance PC or workstations to build a high speed and performance distributed computing environment called NOWs(Network of Workstations). From our previous researches, the network partition schemes have some kind of improvements better than others algorithm on some collective communications in regular networks. In this paper we will show how to use the concept of "network partition scheme" on NOWs environment. And we hope that the idea "network partition scheme", will also have some improvement on NOWs environment.

1. Introduction
2. Preliminaries
2.1 Network Model
2.2 Subnetworks of a Wormhole Network
2.3 A General Model for Multi-Node Multicasts
3. Subnetworks of a 2D Torus/Mesh
3.1 DDN's and DCN's in a 2D Torus
3.2 DDN's and DCN's in a 2D Mesh
4. Multi-Node Multicast in a 2D Torus
4.1 Phase 1: Balancing Traffic among DDNs
4.2 Phase 2: Multicasting in DDNs
4.3 Phase 3: Multicasting in DCNs
4.4 Simulation and Performance Comparison
5. Multi-Node Multicast in a 2D Mesh
5.1 Phase 2: Modified Multicasting in DDNs
5.2 Simulation and Performance Comparison
6. Future Work: Reduce the communication latency on NOWs by
Network Partition Theme
6.1 Collection Communication on NOWs :
A Single-Node Broadcast by Network Partition
6.2 Approach 1: Numbering-Based Scheme
6.3 Approach 2: Local-Numbering Based Scheme
6.4 Approach 3: Tree-Level Based Scheme
7. Conclusions

[1] Intel Corporation. A Touchstone DELTA system description,
1990.
[2] Message Passing Interface Forum. Document for standard
message-passing interface, Nov. 1993.
[3] Cray Research Inc. CRAY T3E scalable parallel processing
system, 1995.
[4] N. Agrawal and C. P. Ravikumar. An euler path based
technique for deadlock-free mutlicasting. In Int'l Conf. on
Parallel Processing, pages 378-383, 1997.
[5] Thomas E. Anderson, David E. Culler, David A. Patterson,
and NOW team. A case for networks of workstations: NOW.
IEEE Micro, pages 54-64, Feb. 1995.
[6] W. C. Athas and C. L. Seitz. Multicomputers: Message
passing concurrent computers. IEEE Computers, pages 9-25,
Aug. 1988.
[7] V. Bala, J. Bruck, R. Cypher, P. Elustondo, A. Ho, C. T.
Ho, S. Kipmis, and M. Snir. CCL: A portable and tunable
collective communication library for scalable parallel
computers. In Int'l Parallel Processing Symp., pages 835-
843,Cancun, Mexico, Apr. 1994.
[8] N. J. Boden, D. Cohen, and et. al. Myrinet: A gigabit per
second local area network. IEEE Micro, pages 29-36, Feb.
1995.
[9] H. D. Cheng, Y. Y. Tang, and C. Y. Suen. Parallel image
transformation and its
VLSI implementation. Pattern Recognition, 23(10):113-129,
1990.
[10] J. Choi, J. J. Dongarra, R. Pozo, and D. W. Walker.
ScaLAPACK: A scalable
linear algebra library for distributed memory concurrent
computers. In Symp. on Frontiers of Massively Parallel
Computation, pages 120-127, 1992.
[11] L. D. Coster, N. Dewulf, and C.-T. Ho. Efficient multi-
packet multicast
algorithms on meshes with wormhole and dimension-ordered
routing. In Int'l Conf. on Parallel Processing, volume 3,
pages 137-141, 1995.
[12] W. J. Dally and C. L. Seitz. The torus routing chip. J. of
Distributed Computing, l(3):187-196,1986.
[13] B. Duzett and R. Buck. An overview of the nCUBE 3
supercomputer. In Symp.on Frontiers of Massively Parallel
Computation, pages 458-464, 1992.
[14] C. T. Ho and M. T. Raghunath. Efficient communication
primitives on hypercubes. Journal of Concurrency: Practice
and Experience, 4(6):427-457, Sep 1992.
[15] R. Horst. ServerNet deadlock avoiddance and fractahedral
topologies. In Int'l Parallel Processing Symp., pages 274-
280, April 1996.
[16] R. Kesavan and D.K. Panda. Multiple multicast with
minimize node contention on wormhole k-ary n-cube
networks. Int'l Conf. on Parallel Processing, pages
188-195,1996.
[17] R. E. Lessler and J. L. Schwazmeier. CRAY T3D: A new
dimension for Cray
Reasearch. In COMPCON, pages 176-182, 1993.
[18] K. Li and R. Chaefer. A hypercube shared virtual memory.
In Int'l Conf. on
Parallel Processing, volume 1, pages 125-132, 1989
[19] X. Lin, P. K. McKmley, and L. M. Ni. Deadlock-free
multicast wormhole routing in 2D mesh multicomputers.
IEEE Trans. on Paral. and Distrib. Sys., 5(8):793-804,
Aug. 1994.
[20] P. K. Mckinley, H. Xu, A.-H. Esfahanian, and L. M. Ni.
Unicast-based multicast communication in wormhole-routed
networks. IEEE Trans. on Paral. and Distrib. Sys., 5
(12):1252-1265, Dec. 1994.
[21] L. M. Ni and P. K. McKinley. A survey of wormhole routing
techniques in directed network.
IEEE Computers, 26(2):62-76, Feb. 1993.
[22] P. R. Nuth and W. J. Dally. The J-machine network. In IEEE
Int'l Conf. on Computer Design: VLSI in Computer and
Processors, pages 420-423, 1992.
[23] D. F. Robinson, P. K. Mckinley, and Betty H. C. Cheng.
Optimal multicast communication in wormhole-routed torus
networks. IEEE Trans. on Paral. and Distrib. Sys., 6
(10):1029-1042, Oct. 1995.
[24] Michael D. Schroeder, Andrew D. Birrell, Michael Burrows,
Hal Murray, Roger M. Needham, Thomas L. Rodeheffer, Edwin
H. Satterthwaite, and Charles P. Thacker. Autonet: A high
speed, self-configuring local area network using
point-to-point links. Technical Report Technical Report
SRC research report
59, DEC, April 1990.
[25] H. D. Schwetman. Using csim to model complex systems. In
Proceedings of the 1988 Winter Simulation Conference,
pages 246-253, 1988.
[26] G. D. Stamoulis and J. N. Tsitsikiis. Efficient routing
schemes for multiple broad-casts in hypercubes. IEEE
Trans. on Paral. and Distrib. Sys.,
4(7):725-739, July
[27] Y.-C. Tseng, M.-H. Yang, and T.-Y. Juang. An eulei-path-
based multicasting model for wormhole-routed networks with
multi-destination capability. In Int'l Conf. on Parallel
Processing, pages 366-373, 1998.
[28] San-Yuan Wang, Yu-Chee Tseng, and Chin-Wen Ho. Efficient
multicast in wormhole-routed 2d mesh/torus multicomputers:
A network-partitioning approach. Symp. on Frontiers of
Massively Parallel Computation, pages 42-49, 1996.
[29] H. Xu, P. K. McKinley, and L. M. Ni. Efficient
implementation of barrier synchronization in wormhole-
routed hypercubes multicomputers. J. of Parallel and
Distrib. Comput., 16:172-184,1992.