在多處理器網路中，互相間有許多的理由需要通訊，例如資料的通訊或事件的同步。集體通訊的例子，例如有廣播或群播。應用包括parallel unmerial algorithms, graph algorithm, image process algorithm, cache coherence, 及 barrier synchronization。 蟲洞繞徑是一個在內連接網路的轉換技術，它具有低通訊延遲及在沒有競爭情形下對於繞徑距離不敏感的特性。 本篇論文討論多維度多點群播問題使用蟲洞繞徑、維度順序繞徑、單埠模型在多維的torus及meah網路。由任意數目的起始點送群播的訊息到任意數目的目的地端點。問題的挑戰點在於也許存在於一連串的碰撞當起始目的點的數目很大或有hot-spot現象時(起始點或是目的地點集中在一個小區域時)，為了解決這個問題我們應用了兩個策略：網路分割及負載平衡。我們先將網路分成許多的子網路，並將群播的訊息傳送到各子網路以達到交通負載的平衡。 本篇論文是對於原先的2D Tori/meshes 上群播的擴充，我們將之推展到高維度tori/meshes。我們提出將torus/mesh網路切割成一些的子網路，這些子網路仍然是一個torus/mesh的結構。若現在做一個多點群播，第一步先將群播訊息在每一子網路上傳播，希望將所有的交通流量均勻的分配到各子網路。然後每一個子網路執行相同數目的群播訊息。根據之前的經驗，藉由以上的步驟可以得到效能上很大的改進。在本篇論文中，我們將提出幾種網路切割方式在torus/mesh上。透過廣泛的模擬，我們證明在許多種的情形下，我們所提出的網路切割在與u-torus/u-mesh等方法比較時，會有較好的效能。此外在出現有hot-spot現象時，就是有起始點或目的點集中在一小區域時，我們所提出平衡負載，在這種現象將扮演更重要的角色。 This thesis considers the multi-node multicast problem in a multi-dimensional wormhole-routed torus/mesh, where there are an arbitrary number of source nodes each intending to multicast a message to an arbitrary set of destinations. This problem requires a large amount of bandwidth, and thus typically incurs heavy contention and congestion. Evenly balancing the traffic load around the network is a critical issue to achieve good performance. We show how to use a network-partitioning approach to achieve this goal. Simulation results show significant improvement over existing results in 3D tori and meshes. This work is an extension of our earlier work from 2D tori/meshes to higher dimensional ones.
