晶片網路是一種高效能的傳輸架構，這種平行計算系統被廣泛應用在大型積體電路的設計中，而路由演算法為晶片網路的核心，主宰了整個晶片網路效能的優劣，節點與節點之間的傳輸藉由路由演算法的計算將封包從起始節點分配適當的輸出阜到各個中繼節點，直到達到目的地節點為止，故對於路由演算法的設計而言，如何降低封包平均傳遞時間的延遲是最重要的課題。

另一方面，雖然我們對於計算機系統的效能、流量、以及速度之需求日益增加，而功率消耗與面積也是我們必須考量的重點。為了解決路由矩陣的問題，一種排列組合樹方法被提出來用於建立封包的路徑，但此種方法需要運算非常多種路由情況，所以基於此種方法上，我們提出了一個只需簡單運算的低功率路由演算法，同時能夠在封包傳輸時運算出最佳的封包路徑。

在固定或不同的封包流量下，實驗結果皆顯示我們路由演算法相較於排列展開樹演算法有較佳的效能表現，由於利用簡單數學運算做決策的關係也達到節省面積與節省功率消耗的效果。

Network-on-chip (NoC) architecture is a high performance communication framework. It has been widely used for the hardware design with large-scale chips. Routing algorithm is one of the critical designs in the NoC architecture. For the quality maintenance of the communication between nodes, packets are forwarded from a source node to a destination node in the NoC. The design of routing system is very necessary to suppress the average latency of packets. On the other hand, it is also significant as power and area are both considered for the packet switched on-chip network. To deal with the values of the routing matrix, a permutation tree is used to construct the datapath. With the branches of the tree, there are too many cases of routing decisions to be computed. Based on the scheme, we developed an algorithm which only uses simple arithmetic of operations in order to achieve low power design. This adaptive routing algorithm also select the best route for communication flows. Experimental results show that the performance of our algorithm is better than the routing algorithm with permutation tree under uniform and transpose traffic. Furthermore, the proposed algorithm is also more energy-efficient and area-economic, while the power consumption is much lower than the compared circuit with larger chip area.

[1] H. G. Lee, N. Chang, U. Y. Ogras, and R. Marculescu, “On-chip Communication architecture exploration: A quantitative evaluation of point-to-point, bus, and networkon-chip approaches,”ACM Transact. Des. Automat. Electron. Syst., vol. 12, no. 3, pp. 1-20, Aug. 2007.
[2] S. Borkar, “Thousand core chips: A technology perspective,”in Proc. ACM/IEEE Design Autom. Conf., Jun. 2007, pp. 746-749.
[3] M. Pastrnak, P. H. N. With, and J. Meerbergen, “QoS concept for scalable MPEG-4 video object decoding on multimedia (NoC) chips,”IEEE Trans. Consum. Electron., vol. 52, no. 4, pp. 1418-1426, Nov. 2006.
[4] Y. Jin, E. J. Kim, and K. H. Yum, “Design and analysis of on-chip networks for large-scale cache systems,”IEEE Trans. Comput., vol. 59, no. 3, pp. 332-344, Mar.2010.
[5] W. Jang and D. Z. Pan,“Application-aware NoC design for efficient SDRAM access,”IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 30, no. 10, pp. 1521-1533, Oct. 2011.
[6] A. O. Balkan, G. Qu, and U. Vishkin,“Mesh-of-trees and alternative interconnection networks for single-chip parallelism,”IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 17, no. 10, pp. 1419-1432, Oct. 2009.
[7] C.A.M. Marcon, E.I. Moreno, N.L.V. Calazans, and F.G. Moraes, “Comparison of network-on-chip mapping algorithms targeting low energy consumption,”IET Comput. Digit. Tech., vol. 2, no. 6, pp. 471-482, Apr. 2008.
[8] A. Kohler, G. Schley, and M. Radetzki, “Fault tolerant network on chip switching with graceful performance degradation,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 29, no. 6, pp. 883-896, Jun. 2010.
[9] R. I. Greenberg and L. Guan,“On the area of hypercube layouts,”Inf. Process. Lett., vol. 84, no. 1, pp. 41-46, Oct. 2002.
[10] J. Kim, J. Balfour, and W. J. Dally, “Flattened butterfly topology for on-chip networks,”IEEE Computer Architecture Letters, vol. 6, no. 2, pp. 37-40, Feb. 2007.
[11] H. Matsutani, M. Koibuchi, Y. Yamada, D. F. Hsu, and H. Amano, “Fat H-tree: A cost-efficient tree-based on-chip network,”IEEE Trans. Parallel Distrib. Syst., vol. 20, no. 8, pp. 1126-1141, Aug. 2009.
[12] S. Murali, L. Benini, and G. D. Micheli, “An application-specific design methodology for on-chip crossbar generation,”IEEE Trans. Comput-Aided Des. Integr. Circuits Syst., vol. 26, no. 7, pp. 1283-1296, Jul. 2007.
[13] M. Forsell,“Performance comparison of some shared memory organizations for 2D mesh-like NOCs,”Microprocess. Microsyst., vol. 35, no. 2, pp. 274-284, Mar. 2011.
[14] H. Sarbazi-Azad,“Constraint-based performance comparison of multi-dimensional interconnection networks with deterministic and adaptive routing strategies,”Comput. Electr. Eng., vol. 30, no. 3, pp. 167-182, Apr. 2004.
[15] M. Modarressi, A. Tavakkol, H. Sarbazi-Azad "Application-Aware Topology Reconfiguration for On-Chip Networks," IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol.19, no.11, pp.2010-2022, Nov. 2011
[16] M. Hosseinabady, J.L. Nunez-Yanez, "Run-time stochastic task mapping on a large scale network-on-chip with dynamically reconfigurable tiles," Comput. Digit. Tech. IET , vol.6, no.1, pp.1-11, Jan. 2012
[17] F.A. Samman, T. Hollstein, M. Glesner, "Adaptive and Deadlock-Free Tree-Based Multicast Routing for Networks-on-Chip," IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol.18, no.7, pp.1067-1080, Jul. 2010
[18] T. Mak, P.Y.K. Cheung, Lam Kai-Pui, W. Luk , "Adaptive Routing in Network-on-Chips Using a Dynamic-Programming Network," IEEE Trans. Indus. Electr., vol.58, no.8, pp.3701-3716, Aug. 2011
[19] A. Mejia, M. Palesi, J. Flich, S. Kumar, P. Lopez, R. Holsmark, J. Duato, "Region-Based Routing: A Mechanism to Support Efficient Routing Algorithms in NoCs," IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol.17, no.3, pp.356-369, Mar. 2009
[20] D. Atienza, F. Angiolini, S. Murali, A. Pullini, L. Benini, G. D. Micheli, "Networkon-Chip design and synthesis outlook" Very Large Scale Integr. Jour., vol.41, pp.340–359 , Dec.2007
[21] W. J. Dally,“Virtual-channel flow control,”IEEE Trans. on Paral. Distri. Syst.,vol., no., pp.60-68, 28-31 May 1990
[22] C. G´omez, M. E. G´omez, P. L´opez, and J. Duato, “Reducing packet dropping in a bufferless NoC,”Proc. 14th intl. Euro-Par conf. Paral. Proces. 2008.
[23] T. Moscibroda and O. Mutlu, “A case for bufferless routing in on-chip networks,”Proc. annu. Intl. Symp. Comput. Arch., 2009.