Your browser does not support JavaScript!

access icon free DICA: destination intensity and congestion-aware output selection strategy for network-on-chip systems

Selection strategy is an essential part of an adaptive routing algorithm that influences the performance of the networks-on-chip (NoC). A selection strategy is used for selecting the best output channel from the available channels according to the network status. This study presents a new output selection strategy called destination intensity and congestion aware (DICA) that uses both local and regional congestion information from adjacent and two hops away neighbours on the path to destination based on the channel and switch information. Also, the proposed output selection strategy uses a new global congestion-aware scheme based on destination node called destination congestion awareness method to distribute traffic more equally over the network. The simulation results show that DICA strategy consistently improves the performance in both throughput and average latency with minimal overhead in terms of area consumption for various synthetic and real application traffic patterns. In addition, the microarchitecture of NoC routers is also presented in this study and it shows that the proposed output selection strategy can be combined with any adaptive routing algorithms. The experimental results show the average delay improvements of DICA to the Bufferlevel, neighbours-on-path, and regional congestion awareness are 87, 57, and 24%, respectively.


    1. 1)
      • 21. Salehi, N., Khademzadeh, A., Dana, A.: ‘Power distribution in NoCs through a fuzzy based selection strategy for adaptive routing’. 13th Euromicro Conf. on Digital System Design: Architectures, Methods and Tools (DSD), Lille, 2010, pp. 4552.
    2. 2)
      • 19. Azampanah, S., Khademzadeh, A., Bagherzadeh, N., et al: ‘Contention-aware selection strategy for application-specific network-on-chip’, IET Comput. Digit. Tech., 2013, 7, (3), pp. 105114.
    3. 3)
      • 42. Palesi, M., Holsmark, R., Kumar, S., et al: ‘A methodology for design of application specific deadlock-free routing algorithms for NoC systems’. Proc. Int. Conf. on Hardware-Software Codesign and System Synthesis, Seoul, Korea, October 2007, pp. 142147.
    4. 4)
      • 36. Dimitrakopoulos, G., Psarras, A., Seitanidis, I.: ‘Microarchitecture of network-on-chip routers, a designer's perspective’ (Springer Press, New York, NY, USA, 2015).
    5. 5)
      • 12. Feng, W., Shin, K.G.: ‘Impact of selection functions on routing algorithm performance in multicomputer networks’. Proc. Int. Conf. Supercomput., New York, NY, USA, 1997, pp. 132139.
    6. 6)
      • 1. Benini, L., De Micheli, G.: ‘Powering networks on chips: energy-efficient and reliable interconnect design for socs’. Proc. of the 14th Int. Symp. on Systems Synthesis, ACM, New York, NY, USA, 2001, pp. 3338.
    7. 7)
      • 24. Gratz, P., Grot, B., Keckler, S.W.: ‘Regional congestion awareness for load balance in networks-on-chip’. 2008 IEEE 14th Int. Symp. on High Performance Computer Architecture, Salt Lake City, UT, 2008, pp. 203214.
    8. 8)
      • 39. Psarras, A., Seitanidis, I., Nicopoulos, C., et al: ‘Shortpath: a network-on-chip router with fine-grained pipeline bypassing’, IEEE Trans. Comput., 2016, 65, (10), pp. 31363147.
    9. 9)
      • 13. Martinez, J.C., Silla, F., Lopez, P., et al: ‘On the influence of the selection function on the performance of networks of workstations’. Proc. Int. Symp. High-Perform. Comput., Berlin, Germany, 2000, pp. 292299.
    10. 10)
      • 33. Van der Tol, E.B., Jaspers, E.G.T.: ‘Mapping of MPEG-4 decoding on a flexible architecture platform’. Proc. SPIE 2002, San Jose, CA, USA, January 2002, pp. 113.
    11. 11)
      • 27. Jose, J., Mahathi, K.V., Shankar, J.S., et al: ‘Tracker: A low overhead adaptive noc router with load balancing selection strategy’. IEEE/ACM Int. Conf. on Computer-Aided Design (ICCAD), New York, NY, USA, 2012, p. pp. 564568.
    12. 12)
      • 5. Marculescu, R., Ogras, U.Y., Peh, L.S., et al: ‘Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives’. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 2009, 28, (1), pp. 321.
    13. 13)
      • 7. Benini, L., De Micheli, G.: ‘Networks on chip: a new paradigm for systems on chip design’. Proc. 2002 Design, Automation and Test in Europe Conf. and Exhibition, Paris, France, 2002, pp. 418419.
    14. 14)
      • 20. Salemi, D., Palesi, M., Catania, V.: ‘Power-aware selection policy for networks on chip’. 6th Int. Conf. on Design & Technology of Integrated Systems in Nanoscale Era (DTIS), Athens, 2011, pp. 14.
    15. 15)
      • 23. Ascia, G., Catania, V., Palesi, M., et al: ‘Implementation and analysis of a new selection strategy for adaptive routing in networks-on-chip’. IEEE Trans. Comput., 2008, 57, (6), pp. 809820.
    16. 16)
      • 22. Ascia, G., Palesi, M., Catania, V.: ‘An adaptive output selection function based on a fuzzy rule base system for network on chip’. 2013 Euromicro Conf. on Digital System Design (DSD), Los Alamitos, CA, 2013, pp. 505512.
    17. 17)
      • 10. Dally, W.J., Aoki, H.: ‘Deadlock-free adaptive routing in multicomputer networks using virtual channels’. IEEE Trans. Parallel Distrib. Syst., 1993, 4, (4), pp. 466475.
    18. 18)
      • 30. Ebrahimi, M., Daneshtalab, M., Liljeberg, P., et al: ‘CATRA- congestion aware trapezoid-based routing algorithm for on-chip networks’. 2012 Design, Automation & Test in Europe Conf. & Exhibition (DATE), Dresden, 2012, pp. 320325.
    19. 19)
      • 31. Foroutan, S., Thonnart, Y., Petrot, F.: ‘An iterative computational technique for performance evaluation of networks-on-chip’, IEEE Trans. Comput., 2013, 62, (8), pp. 16411655.
    20. 20)
      • 32. Dally, W.J., Seitz, C.L.: ‘The torus routing chip’, J. Distrib. Comput., 1986, 1, (4), pp. 187196.
    21. 21)
      • 44. Flich, J., Mejia, A., Lopez, P., et al: ‘Region-based routing. An efficient routing mechanism to tackle unreliable hardware in newtork on chips’. First IEEE/ACM Int. Symp. on Networks-on-Chip, Princeton, NJ, USA, May 2007.
    22. 22)
      • 40. Holsmark, R., Palesi, M., Kumar, S.: ‘Deadlock free routing algorithms for irregular mesh topology NoC systems with rectangular regions’, J. Syst. Archit., 2008, 54, (3–4), pp. 427440.
    23. 23)
      • 2. Dally, W.J., Towles, B.P.: ‘Principles and practices of interconnection networks’ (Elsevier Press, San Francisco, CA, USA, 2004).
    24. 24)
      • 29. Ma, S., Jerger, N. E., Wang, Z.: ‘DBAR: An efficient routing algorithm to support multiple concurrent applications in networks-on-chip’. 2011 38th Annual Int. Symp. on Computer Architecture (ISCA), San Jose, CA, 2011, pp. 413424.
    25. 25)
      • 37. Galles, M.: ‘Spider: a high-speed network interconnect’, IEEE Micro, 1997, 17, (1), pp. 3439.
    26. 26)
      • 38. Daya, B.K., Chen, C.O., Subramanian, S., et al: ‘SCORPIO: A 36-core research chip demonstrating snoopy coherence on a scalable mesh NoC with in-network ordering’. 2014 ACM/IEEE 41st Int. Symp. on Computer Architecture (ISCA), Minneapolis, MN, 2014, pp. 2536.
    27. 27)
      • 8. Chang, E.J., Hsin, H.K., Lin, S.Y., et al: ‘Path-congestion-aware adaptive routing with a contention prediction scheme for network-on-chip systems’, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 2014, 33, (1), pp. 113126.
    28. 28)
      • 43. Palesi, M., Kumar, S., Holsmark, R.: ‘A method for router table compression for application specific routing in mesh topology NoC architectures’. SAMOS VI: Embedded Computer Systems: Architectures, Modeling, and Simulation, Samos, Greece, July 2006.
    29. 29)
      • 25. Ebrahimi, M., Daneshtalab, M., Liljeberg, P., et al: ‘Agent-based on-chip network using efficient selection method’. 2011 IEEE/IFIP 19th Int. Conf. on VLSI and System-on-Chip, Hong Kong, 2011, pp. 284289.
    30. 30)
      • 35. Dehyadegari, M., Daneshtalab, M., Ebrahimi, M., et al: ‘An adaptive fuzzy logic-based routing algorithm for networks-on-chip’. 2011 NASA/ESA Conf. on Adaptive Hardware and Systems (AHS), San Diego, CA, 2011, pp. 208214.
    31. 31)
      • 14. Chiu, G.M.: ‘The odd-even turn model for adaptive routing’, IEEE Trans. Parallel Distrib. Syst., 2000, 11, (7), pp. 729738.
    32. 32)
      • 18. Azampanah, S., Khademzadeh, A., Bagherzadeh, N., et al: ‘LATEX: New selection policy for adaptive routing in application-specific NoC’. 2012 20th Euromicro Int. Conf. on Parallel, Distributed and Network-based Processing, Garching, 2012, pp. 515519.
    33. 33)
      • 4. Duato, J., Yalamanchili, S., Ni, L.M.: ‘Interconnection networks: an engineering Approach’ (Morgan Kaufmann Press, San Diego, CA, USA, 2003).
    34. 34)
      • 26. Liu, S., Chen, T., Li, L., et al: ‘Freerider: non-local adaptive network-on-chip routing with packet-carried propagation of congestion information’. IEEE Trans. Parallel Distrib. Syst., 2015, 26, (8), pp. 22722285.
    35. 35)
      • 34. Pande, P.P., Grecu, C., Jones, M., et al: ‘Performance evaluation and design trade-offs for network-on-chip interconnect architectures’, IEEE Trans. Comput., 2005, 54, (8), pp. 10251040.
    36. 36)
      • 9. Mehranzadeh, A., Khademzadeh, A., Mehran, A.: ‘FADyAD- fault and congestion aware routing algorithm based on DyAD algorithm’. 5th Int. Symp. on Telecommunications, Tehran, 2010, pp. 274279.
    37. 37)
      • 11. Badr, H.G., Podar, S.: ‘An optimal shortest-path routing policy for network computers with regular mesh-connected topologies’, IEEE Trans. Comput., 1989, 38, (10), pp. 13621371.
    38. 38)
      • 15. Catania, V., Mineo, A., Monteleone, S., et al: ‘Cycle-accurate network on chip simulation with Noxim’, ACM Trans. Model. Comput. Simul., 2016, 27, (1), pp. 125.
    39. 39)
      • 45. Bolotin, E., Cidon, I., Ginosar, R., et al: ‘Routing table minimization for irregular mesh NoCs’, Design Automation and Test in Europe, Nice, France, March 2007.
    40. 40)
      • 17. Nilsson, E., Millberg, M., Oberg, J., et al: ‘Load distribution with the proximity congestion awareness in a network on chip’. 2003 Design, Automation and Test in Europe Conf. and Exhibition, Munich, Germany, 2003, pp. 11261127.
    41. 41)
      • 41. Vaidya, A.S., Sivasubramaniam, A., Das, C.R.: ‘LAPSES: A recipe for high performance adaptive router design’. 5th Int. Symp. On High-Performance Computer Architecture, Orlando, FL, USA, January 1999, pp. 236243.
    42. 42)
      • 3. Jantsch, A., Tenhunen, H.: ‘Networks on chip’, vol. 396, (Springer Press, Boston, MA, USA, 2003).
    43. 43)
      • 6. Ogras, U.Y., Bogdan, P., Marculescu, R.: ‘An analytical approach for network-on-chip performance analysis’. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 2010, 29, (12), pp. 20012013.
    44. 44)
      • 28. Ebrahimi, M., Daneshtalab, M., Farahnakian, F., et alHARAQ: congestion-aware learning model for highly adaptive routing algorithm in On-chip networks’. 2012 IEEE/ACM Sixth Int. Symp. on Networks-on-Chip, Copenhagen, 2012, pp. 1926.
    45. 45)
      • 16. Singh, A., Dally, W.J., Gupta, A.K., et al: ‘GOAL: a load-balanced adaptive routing algorithm for torus networks’. 2003. Proc. 30th Annual Int. Symp. on Computer Architecture., San Diego, CA, USA, 2003, pp. 194205.

Related content

This is a required field
Please enter a valid email address