多播(multicast)的溝通方式可以大幅地提高單晶片網路的傳輸效能。目前主要的多播傳輸繞徑方法有二，以樹狀為基礎(tree-based)的多播繞徑方法與以路經為基礎(path-based)的多播繞徑方法。前者可能會遭遇到多播死鎖(multicast deadlock)的問題，而後者可能會需要很長的傳輸路徑。在這篇論文中，我們提出了一個混合式多播繞徑方法，結合樹狀為基礎與路經為基礎兩種多播繞徑方法的優點。我們所提出來的方法可以確保多播的傳輸無死鎖現象，並且不需要額外的虛擬通道或大面積的緩衝空間來儲存整筆的封包。我們的多播繞徑方法可以藉由判斷網路的流量負載來調整繞徑策略以達到高的傳輸效率。我們也改變一些繞徑條件來探索繞徑的方法，並且找到一個最佳的繞徑演算法。實驗結果顯示，我們所提出來的繞徑演算法，其飽和點(就可處理的封包發送頻率而言)高於目前最新的樹狀為基礎與路經為基礎兩種多播繞徑方法。我們也模擬各種實驗，包含不同的網路規模、緩衝器容量、封包大小以及目的個數，並且設定多種封包發送頻率。結果顯示在所有這些實驗中，我們所提出來的繞徑演算法效能都優於其他兩種演算法。

Multicast communication can greatly enhance the performance of Networks-on-Chip. Currently most multicast routing methods are either tree-based or path-based. The former may suffer from the problem of multicast deadlocks and the latter may require long routing paths. In this thesis, we propose a hybrid multicast routing approach that combines the advantages of both path-based and tree-based methods. The proposed approach ensures deadlock-free multicast routing without requiring additional virtual channels or large buffers to hold large packets. High routing performance is achieved due to an adaptive routing strategy according to the traffic load. We also investigate several variations of this hybrid approach and identify an algorithm that can achieve the best performance in general. Experimental results show that the saturation point (in terms of injection ratio) of this algorithm is significantly higher than those of the state-of-the-art tree- and path-based multicast routing algorithms. In fact experiments with different network dimensions, buffer sizes, packet sizes, and numbers of destinations per packet under various traffic injection rates have been carried out and the results show that the proposed algorithm outperforms the other two algorithms in all of these experiments.

[1] W.O. Cesário, D. Lyonnard, G. Nicolescu, Y. Paviot, S.Yoo, A.A. Jerraya, L. Gauthier, and M. Diaz-Nava, “Multiprocessor SoC platforms: a component-based design approach,” IEEE Des. Test. Comput., vol. 19, no. 6, pp. 52–63, Nov./Dec. 2002.
[2] T. Bjerregaard and S. Mahadevan, "A survey of research and practices of Network-on-chip," ACM Comput. Surv., vol. 38, no. 1, pp. 1-51, 2006.
[3] X. Lin, P. K. McKinley, and L. M. Ni, “Deadlock-free multicast wormhole routing in 2-D mesh multicomputers,” IEEE Trans. Parallel and Distrib. Syst., vol. 5, no. 8, pp. 793-804, Aug. 1994.
[4] X. Lin and L.M. Ni, “Multicast communication in multicomputer networks,’’ IEEE Trans. Parallel and Distrib. Syst., vol. 4, no. 10, pp. 1,105-1,117, Oct. 1993.
[5] C. J. Glass and L. M. Ni, “Adaptive routing in mesh-connected networks,” in Proc. 12th Int. Conf. Distributed Computing Systems, pp. 12–19, 1992.
[6] C. Ge-Ming, "The odd-even turn model for adaptive routing," IEEE Trans. Parallel and Distrib. Syst., vol. 11, no. 7, pp. 729-738, July, 2000.
[7] F. A. Samman, T. Hollstein, and M. Glesner, “New Theory for Deadlock-Free Multicast Routing in Wormhole-Switched Virtual-Channelless Networks-on-Chip,” IEEE Trans. Parallel and Distrib. Syst., vol. 22, no. 4, pp. 544–557, April 2011.
[8] F. A. Samman, T. Hollstein, and M. Glesner, “Adaptive and Deadlock-Free Tree-Based Multicast Routing for Networks-on-Chip,” IEEE Trans. Very Large Scale Integr., vol. 18, no. 7, pp. 1067–1080, Jul. 2010.
[9] M. P. Malumbres, J. Duato and J. Torrelas, “An efficient implementation of tree-based multicast routing for distributed shared-memory multiprocessors,” Proc. 8th IEEE Symp. Parallel and Distributed Process., pp.186-189, 1996.
[10] N.E. Jerger, L.S. Peh, and M. Lipasti, “Virtual Circuit Tree Multicasting: A Case for On-Chip Hardware Multicast Support,” Proc. 35th Int’l Symp. Computer Architecture (ISCA ’08), pp. 229-240, June 2008.
[11] W. Hu, Z. Lu, A. Jantsch, and H. Liu, “Power-efficient tree-based multicast support for Networks-on-Chip,” in Proc. Asia and South Pacific Des. Autom. Conf., Jan. 2011, pp. 363-368.
[12] D. R. Kumar, W. A. Najjar, P. K. Srimani, “A new adaptive hardware tree-based multicast routing in k-ary n-cubes,” IEEE Trans. Computers, vol. 50, no. 7, pp. 647–659, Jul. 2001.
[13] M. Ebrahimi, M. Daneshtalab, P. Liljeberg, and H. Tenhunen, “HAMUM – A Novel Routing Protocol for Unicast and Multicast Traffic in MPSoCs,” in Proc. Euromicro Int. Conf. Parallel, Distrib. Network-Based Process, 2010, pp. 525-532.
[14] N. McKeown, “The iSLIP scheduling algorithm for input-queued switches,” Networking, IEEE/ACM Transactions on, vol. 7, pp. 188-201, 1999.
[15] R.V. Boppana, S. Chalasani, and C.S. Raghavendra, “Resource deadlock and performance of wormhole multicast routing algorithms,” IEEE Trans. Parallel and Distrib. Syst., vol. 9, no. 6, pp. 535-549, June 1998.
[16] M. Daneshtalab, M. Ebrahimi, S. Mohammadi, and A. Afzali-Kusha, “Low-Distance Path-Based Multicast Routing Algorithm for Network-on-Chips,” IET Computer & Digital Techniques, Vol. 3, No. 5, pp. 430-442, 2009.