多播(multicast)的溝通方式可以大幅地提高單晶片網路的傳輸效能。目前主要的多播傳輸繞徑方法有二，以樹狀為基礎(tree-based)的多播繞徑方法與以路經為基礎(path-based)的多播繞徑方法。前者有較低傳輸延遲時間但需要透過額外的硬體資源來解決多播死鎖(multicast deadlock)的問題，而後者較簡單的方式處理死鎖問題但可能會需要很長的傳輸路徑。在這篇論文中，我們提出了一個混合式多播繞徑方法，結合樹狀為基礎與路經為基礎兩種多播繞徑方法的優點。我們所提出來的方法可以確保多播的傳輸無死鎖現象，並且不需要額外的虛擬通道或大面積的緩衝空間來儲存整筆的封包。我們的多播繞徑方法可以藉由判斷網路的流量負載來調整繞徑策略以達到高的傳輸效率。我們更進一步強化我們的多播繞進方法，利用我們發展的兩個技術，結點平衡的方法和路徑平衡的方法來強化混和式多播繞徑方法。我們模擬各種實驗，包含不同的緩衝器容量封包大小以、目的個數及交通情況，並且設定多種封包發送頻率。結果顯示在所有這些實驗中，我們所提出來的繞徑演算法效能都優於其他兩種演算法。

Multicast communication can greatly enhance the performance of Networks-on-Chip. Currently, most multicast routing algorithms are either tree-based or path-based. The former have low latency but needs to solve multicast deadlocks through additional hardware resources. The latter can avoid deadlocks easily but 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 using an adaptive routing strategy according to the traffic load. We further developed two techniques, node balancing and path balancing, to enhance this hybrid multicast routing algorithm. Experiments with different buffer sizes, packet sizes and numbers of destinations per packet under random and Rent’s rule traffic at various traffic injection rates have been conducted. The results show that our approach outperforms the current tree- and path-based multicast routing algorithms.

[1] W.O. Cesario, 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 Design & Test. Computers, 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,” J. ACM Computting Surveys, vol 38, no. 1, pp. 1-51, June. 2006.
[3] H. Xu, P. K. McKinley, E. Kalns, and L. M. Ni, “Efficient implementation of barrier synchronization in wormhole-routed hypercube multicomputers,” J. Parallel and Distributed Computing, vol 16, pp. 172-184, Oct. 1992.
[4] X. Lin, P. K. McKinley, and L. M. Ni, “Deadlock-free multicast wormhole routing in 2-D mesh multicomputers,” IEEE Trans. Parallel and Distributed Systems, vol. 5, no. 8, pp. 793-804, Aug. 1994.
[5] K. Li, and R. Schaefer, “A Hypercube Shared Virtual Memory,” Proc. Int. Conf. ICPP, pp. 125-132, 1989.
[6] M. Azevedo, and D. Blough, “Fault-Tolerant Clock Synchronization of Large Multicomputers via Multistep Interactive Convergence,” Proc. Int. Conf. ICDCS, pp. 249-257, 1996.
[7] M. Ebrahimi, M. Daneshtalab, P. Liljeberg, and H. Tenhunen, “HAMUM – A novel routing protocol for unicast and multicast traffic in MPSoCs,” Proc. 18th Euromicro Int. Conf. Parallel Distributed and Network-Based Processing, pp. 525-532, 2010.
[8] C. J. Glass and L. M. Ni, “Adaptive routing in mesh-connected networks,” Proc. 12th Int. Conf. Distributed Computing Systems, pp. 12–19, 1992.
[9] C. Ge-Ming, “The odd-even turn model for adaptive routing,” IEEE Trans. Parallel and Distributed Systems., vol. 11, no. 7, pp. 729-738, Jul. 2000.
[10] 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.
[11] W. Hu, Z. Lu, A. Jantsch, and H. Liu, “Power-efficient tree-based multicast support for Networks-on-Chip,” Proc. 16th Asia and South Pacific Design Automation Conf., pp. 363-368, 2011.
[12] K.J. Lee, C.Y. Chang, and H.Y. Yang, “An efficient deadlock-free multicast routing algorithm for mesh-based networks-on-chip,” Proc. IEEE Int’l Symp. VLSI Design Automation and Test, pp.1-4, Apr. 2013.
[13] G. B.P. Bezerra, S. Forrest, M. Moses, A. Davis, and P. Zarkesh-Ha, “Modeling NoC traffic locality and energy consumption with Rent’s communication probability distribution.” Proc. ACM Int’l Workshop System level interconnect prediction, pp. 3–8, June 2010.
[14] M. Daneshtalab, M. Ebrahimi, S. Mohammadi, and A. Afzali-Kusha, “Low-Distance Path-Based Multicast Routing Algorithm for Network-on-Chips,” J. IET Computer & Digital Techniques, vol. 3, no. 5, pp. 430-442, Sep. 2009.
[15] F. A. Samman, T. Hollstein and M. Glesner, “Planar Adaptive Router Microarchitecture for Tree-Based Multicast Network-on-Chip,” Proc. Int’l Workshop Network-on-Chip Architecture, pp. 6-13, 2008.
[16] 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 Distributed Systems, vol. 22, no. 4, pp. 544–557, Apr. 2011.
[17] 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 Integration, vol. 18, no. 7, pp. 1067–1080, Jul. 2010.
[18] L. Wang, Y. Jin, H. Kim, and E. J. Kim, “Recursive partitioning multicast: A bandwidth-efficient routing for Networks-on-Chip,” Proc. IEEE Symp. Networks-on-Chip, pp. 64-73, May 2009.
[19] Zhong, Ming, et al. "An improved minimal multicast routing algorithm for mesh-based Networks-on-Chip.", Proc. IEEE Int’l Conf. Signal Processing, Communications and Computing, pp. 755-779, Aug. 2014.
[20] Li, Jianhua, Chun Jason Xue, and Yinlong Xu. "LADPM: Latency-aware dual-partition multicast routing for mesh-based network-on-chips," Proc. IEEE Int’l Conf. Parallel and Distributed Systems, pp. 423-430, Dec. 2010.
[21] Z. Wang, H. Gu, Y. Yang, H. Zhang, and Y. Chen, “An adaptive partition-based multicast routing scheme for mesh-based Networks-on-Chip,” J. Computers & Electrical Engineering,vol. 51, pp. 235-251, Apr. 2016.
[22] M. Ebrahimi, M. Daneshtalab, P. Liljeberg, J. Plosila, J. Flich, and H. Tenhunen, “Path-based partitioning methods for 3D networks-on-chip with minimal adaptive routing,” IEEE Trans. Computers, vol. 63, no. 3, pp. 718-733, Mar. 2014.
[23] P. Bahrebar and D. Stroobandt, “The Hamiltonian-based odd–even turn model for maximally adaptive routing in 2D mesh networks-on-chip,” J. Computers & Electrical Engineering, vol. 45, pp. 386-401, Jul. 2015.
[24] Y. H. Kang, J. Sondeen, and J. Draper, “Implementing Tree-Based Multicast Routing for Write Invalidation Messages in Networks-on-Chip,” Proc. IEEE Int’l Midwest Symp. Circuits and Systems, pp. 1118-1121, Aug. 2009.
[25] S. Ma, N. E. Jerger, and Z. Wang, “Supporting Efficient Collective Communication in NoCs,” Proc. Int’l Symp. High Performance Computer Architecture, pp. 1-12, Feb. 2012.
[26] F. A. Samman, T. Hollstein and M. Glesner, “Multicast Parallel Pipeline Router Architecture for Network-on-Chip,” Proc. Design, Automation, and Test in Europe., pp. 1396-1401, Mar. 2008.
[27] Y.H. Kang, J. Sondeen, and J. Draper, “Multicast routing with dynamic packet fragmentation,” Proc. ACM Great Lakes symp. VLSI, pp. 113-116, May 2009.
[28] R. V. Boppana, S. Chalasani, and C. S. Raghavendra, “Resource deadlocks and performance of wormhole multicast routing algorithms,” IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 6, pp. 535-549, Jun. 1988.
[29] E. G. Coffmam, M. Elphick, and A. Shoshani, “System deadlocks,” J. ACM Computing Surveys, vol. 3, no. 2, pp. 67-78, June 1971.
[30] N.E. Jerger, L.S. Peh, and M. Lipasti, “Virtual Circuit Tree Multicasting: A Case for On-Chip Hardware Multicast Support,” Proc. Int’l Symp. Computer Architecture, pp. 229-240, June 2008.
[31] M. Y. Lanzerotti, G. Fiorenza, and R. A. Rand, “Microminiature packaging and integrated circuitry: The work of E. F. Rent, with an application to on-chip interconnection requirements,” J. IBM Research and Development, vol. 46, no. 4.5, pp. 777-803, July 2005.
[32] A. B. Kahng, B. Lin, and S. Nath, “Explicit modeling of control and data for improved NoC router estimation,” Proc. ACM Conf. Design Automation, pp. 392-397, June 2012.