Abstract
In this paper, we propose a methodology to design routing algorithms for Network-on-Chip (NoC) which are customized for a set of applications. The routing algorithms are achieved by breaking all the cycles in the application specific channel dependency graph(ASCDG). Thus, the result routing algorithms are ensured to be deadlock-free. The proposed method can overcome the shortcomings of the method in [1] which heavily depends on the order of the cycles being treated and has high computational complexity. Simulation results show that the Routing Algorithms by Breaking Cycles (RABC) improves the performance significantly.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Palesi, M., Holsmark, R., Kumar, S., Catania, V.: Application Specific Routing Algorithms for Networks on Chip. IEEE Trans. Parallel and Distributed Systems. 20, 316–330 (2009)
Dally, W.J., Towles, B.: Route Packets, Not Wires: On-Chip Interconnection Networks. In: Design Automation Conf., pp. 684–689 (2001)
Benini, L., De Micheli, G.: Networks on Chips: A New SoC Paradigm. Computer 35, 70–78 (2002)
Millberg, M., Nilsson, E., Thid, R., Kumar, S., Jantsch, A.: The Nostrum backbone - a communication protocol stack for networks on chip. In: VLSI Design Conference, pp. 693–696 (2004)
Rijpkema, E., Goossens, K., Wielage, P.: A router architecture for networks on silicon. In: 2nd Workshop on Embedded Systems (2001)
Kumar, S., Jantsch, A., Soininen, J.P., Forsell, M., Millberg, M., Oberg, J., Tiensyrja, K., Hemani, A.: A Network on Chip Architecture and Design Methodology. In: Proc. IEEE CS Ann. Symp. VLSI, pp. 105–112 (2002)
Karim, F., Nguyen, A., Dey, S.: An Interconnect Architecture for Networking Systems on Chips. IEEE Micro. 22, 36–45 (2002)
Pande, P.P., Grecu, C., Ivanov, A., Saleh, R.: Design of a Switch for Network on Chip Applications. In: Proc. IEEE Intl. Symp. Circuits and Systems, vol. 5, pp. 217–220 (2003)
Marculescu, R., Bogdan, P.: The Chip Is the Network: Toward a Science of Network-on-Chip Design. Foundations and Trends in Electronic Design Automation, 371–461 (2009)
Bjerregaard, T., Mahadevan, S.: A Survey of Research and Practices of Network-on-Chip. ACM Computing Surveys, 1–51 (2006)
Mello, A., Tedesco, L., Calazans, N., Moraes, F.: Virtual Channels in Networks on Chip: Implementation and Evaluation on Hermes NoC. In: Proc. 18th Symp. Integrated Circuits and System Design, pp. 178–183 (2005)
Pullini, A., Angiolini, F., Meloni, P., Atienza, D., Srinivasan MuraliRaffo, L., De Micheli, G., Benini, L.: NoC Design and Implementation in 65 nm Technology. In: Proc. First Intl. Symp. Networks-on-Chip, pp. 273–282 (2007)
Glass, C.J., Ni, L.M.: The Turn Model for Adaptive Routing. J. Assoc. for Computing Machinery 41, 874–902 (1994)
Chien, A.A., Kim, J.H.: Planar-Adaptive Routing: Low-Cost Adaptive Networks for Multiprocessors. J. ACM 42, 91–123 (1995)
Upadhyay, J., Varavithya, V., Mohapatra, P.: A Traffic-Balanced Adaptive Wormhole Routing Scheme for Two-Dimensional Meshes. IEEE Trans. Computers 46, 190–197 (1997)
Chiu, G.M.: The Odd-Even Turn Model for Adaptive Routing. IEEE Trans. Parallel and Distributed Systems 11, 729–738 (2000)
Hu, J., Marculescu, R.: DyADSmart Routing for Networks-on-Chip. In: Proc. 41st Design Automation Conf., pp. 260–263 (2004)
Palesi, M., Kumar, S., Holsmark, R.: A Method for Router Table Compression for Application Specific Routing in Mesh Topology NoC Architectures. In: Proc. Sixth Intl. Workshop Systems, Architectures, Modeling, and Simulation, pp. 373–384 (2006)
Bolotin, E., Cidon, I., Ginosar, R., Kolodny, A.: Routing table minimization for irregular mesh NoCs. In: Proc. Conf. Des., Autom. Test Eur., pp. 942–947 (2007)
Dally, W.J., Towles, B.: Principles and Practices of Interconnection Networks. Morgan Kaufman, San Mateo (2004)
Ascia, G., Catania, V., Palesi, M., Patti, D.: Implementation and Analysis of a New Selection Strategy for Adaptive Routing in Networks-on-Chip. IEEE Trans. Computers 57, 809–820 (2008)
Tang, M.H., Lin, X.L.: An Advanced NoP Selection Strategy for Odd-Even Routing Algorithm in Network-on-Chip. In: Hua, A., Chang, S.-L. (eds.) ICA3PP 2009. LNCS, vol. 5574, pp. 557–568. Springer, Heidelberg (2009)
Dally, W.J., Seitz, C.L.: Deadlock-free message routing in multiprocessor interconnection networks. IEEE Trans. Comput. 36, 547–553 (1987)
Sourceforge.net, Noxim: Network-on-chip simulator (2008), http://noxim.sourceforge.net
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tang, M., Lin, X. (2010). Network-on-Chip Routing Algorithms by Breaking Cycles. In: Hsu, CH., Yang, L.T., Park, J.H., Yeo, SS. (eds) Algorithms and Architectures for Parallel Processing. ICA3PP 2010. Lecture Notes in Computer Science, vol 6081. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13119-6_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-13119-6_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-13118-9
Online ISBN: 978-3-642-13119-6
eBook Packages: Computer ScienceComputer Science (R0)