access icon free σ n LBDR: generic congestion handling routing implementation for two-dimensional mesh network-on-chip

© The Institution of Engineering and Technology
Received 24/10/2015, Accepted 29/06/2016, Revised 03/05/2016, Published 01/09/2016

The number of cores on a chip is increasing from a few cores to thousands. However, the communication mechanisms for these systems do not scale at the same pace, leading to certain challenges. One of them is on-chip congestion. There are many table-based approaches for congestion handling and avoidance, but these are not acceptable as they impose high area and power overheads. In this study, the authors propose two congestion handling strategies aiming to capture the congestion in few bits to avoid congested routes. The first approach called σ n LBDR (logic based distributed routing) captures congestion present at nodes n-hop away from the current node, reducing area, power and overall packet latency. However, all nodes in the network do not experience same congestion level. For this, their second approach, weighted σ n LBDR, uses a different set of bits for each node and results in the further improvement in area and power. This study shows a comparison of both approaches with each other and also with other similar approaches. From their experimental results, they show that σ n LBDR and weighted σ n LBDR improve latency by 20 and 30%, respectively, and have less area and power overhead as compared with baseline table-based approach.

Inspec keywords: network routing; network-on-chip

Other keywords: two-dimensional mesh network-on-chip; communication mechanisms; σnLBDR; packet latency reduction; congestion avoidance; baseline table-based approach; on-chip congestion; power reduction; generic congestion handling routing implementation; area reduction

Subjects: Network-on-chip; Network-on-chip; Digital circuit design, modelling and testing

References

    1. 1)
      • 4. Gratz, P., Grot, B., Keckler, S.W.: ‘Regional congestion awareness for load balance in networks-on-chip’. IEEE 14th Int. Symp. on High Performance Computer Architecture, 2008, pp. 203–214.
    2. 2)
      • 14. Ebrahimi, M., Daneshtalab, M., Farahnakian, F., et al: ‘HARAQ: congestion-aware learning model for highly adaptive routing algorithm in on-chip networks’. Sixth IEEE/ACM Int. Symp. on Networks-on-Chip (NoCS), Copenhagen, Denmark, 9-11 May 2012, pp. 19–26.
    3. 3)
      • 8. Farahnakian, F., Ebrahimi, M., Daneshtalab, M., et al: ‘Q-learning based congestion-aware routing algorithm for on-chip network’. Proc. Second IEEE Int. Conf. on Networked Embedded Systems for Enterprise Applications, NESEA, Perth, Australia, 8–9 December 2011, pp. 1–7.
    4. 4)
      • 27. http://www.gap.upv.es/index.php?option=comcontent&view=article&id=72&Itemid=108:‘gmemnocsim,’.
    5. 5)
      • 11. Ma, S., Jerger, N.E., Wang, Z.: ‘DBAR: an efficient routing algorithm to support multiple concurrent applications in networks-on-chip’. 38th Annual Int. Symp. on Computer Architecture (ISCA), 2011, pp. 413–424.
    6. 6)
      • 18. Bertozzi, D., Benini, L., De Micheli, G.: ‘Low power error resilient encoding for on-chip data buses’. Proc. of the Conf. on Design Automation and Test in Europe, IEEE Computer Society, 2002, p. 102.
    7. 7)
      • 13. 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 (VLSI-SoC), October 2011, pp. 284–289.
    8. 8)
      • 20. Bolotin, E., Cidon, I., Ginosar, R., et al: ‘Routing table minimization for irregular mesh nocs’. Proc. of the Conf. on Design, Automation and Test in Europe, EDA Consortium, 2007, pp. 942–947.
    9. 9)
      • 22. Flich, J., Mejia, A., Lopez, P., et al: ‘Region-based routing: an efficient routing mechanism to tackle unreliable hardware in network on chips’. First Int. Symp. on Networks-on-Chip, 2007, pp. 183–194.
    10. 10)
      • 15. Gupta, N., Kumar, M., Sharma, A., et al: ‘Improved route selection approaches using q-learning framework for 2d nocs’. Proc. Third Int. Workshop on Many-core Embedded Systems (MES'2015) in conjunction with the 42nd Int. Symp. on Computer Architecture (ISCA'2015), Portland, OR, USA, 13 June 2015, pp. 33–40.
    11. 11)
      • 5. Ramakrishna, M., Gratz, P.V., Sprintson, A.: ‘GCA: global congestion awareness for load balance in networks-on-chip’. 2013 Seventh IEEE/ACM Int. Symp. on Networks on Chip (NoCS), 2013, pp. 1–8.
    12. 12)
      • 9. Farahnakian, F., Ebrahimi, M., Daneshtalab, M., et al: ‘Optimized q-learning model for distributing traffic in on-chip networks’. Third IEEE Int. Conf. on Networked Embedded Systems for Every Application, NESEA 2013, Liverpool, UK, 13–14 December 2012, pp. 1–8.
    13. 13)
      • 12. Li, M., Zeng, Q.-A., Jone, W.-B.: ‘DyXy: a proximity congestion-aware deadlock-free dynamic routing method for network on chip’. Proc. 43rd Annual Design Automation Conf., 2006, pp. 849–852.
    14. 14)
    15. 15)
      • 26. Nilsson, E., Millberg, M., Öberg, J., et al: ‘Load distribution with the proximity congestion awareness in a network on chip’. Design, Automation and Test in Europe Conf. and Exhibition, 2003, pp. 1126–1127.
    16. 16)
    17. 17)
      • 25. Duato, J., Yalamanchili, S., Ni, L.M.: ‘Interconnection networks: an engineering approach’ (IEEE Computer Society Press, Los Alamitos, CA, USA, 1997).
    18. 18)
      • 24. Bishnoi, R., Laxmi, V., Gaur, M.S., et al: ‘d 2-lbdr: distance-driven routing to handle permanent failures in 2d mesh nocs’. Proc. 2015 Design, Automation & Test in Europe Conf. & Exhibition, EDA Consortium, 2015, pp. 800–805.
    19. 19)
    20. 20)
      • 16. Mitra, S., McCluskey, E.: ‘Word-voter: a new voter design for triple modular redundant systems’. Proc. 18th IEEE VLSI Test Symp., 2000, pp. 465–470.
    21. 21)
      • 2. Glass, C.J., Ni, L.M.: ‘The turn model for adaptive routing’. ACM SIGARCH Computer Architecture News, 1992, vol. 20, pp. 278–287.
    22. 22)
      • 21. Gomez, M.E., Lopez, P., Duato, J.: ‘A memory-effective routing strategy for regular interconnection networks’. Proc. 19th IEEE Int. Parallel and Distributed Processing Symp., 2005, 2005, p. 41b.
    23. 23)
    24. 24)
      • 10. Ebrahimi, M., Daneshtalab, M., Liljeberg, P., et al: ‘CATRA – congestion aware trapezoid-based routing algorithm for on-chip networks’. Design, Automation & Test in Europe Conf. & Exhibition, DATE, Dresden, Germany, 12–16 March 2012, pp. 320–325.
    25. 25)
    26. 26)
      • 17. Dumitras, T., Marculescu, R.: ‘On-chip stochastic communication’. Proc. Conf. on Design, Automation and Test in Europe – Volume 1, DATE ’03, IEEE Computer Society, 2003, Washington, DC, USA, p. 10790.
    27. 27)
      • 7. Rodrigo, S., Flich, J., Roca, A., et al: ‘Addressing manufacturing challenges with cost-efficient fault tolerant routing’. Fourth ACM/IEEE Int. Symp. on Networks-on-Chip (NOCS), 2010, pp. 25–32.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2015.0196
Loading

Related content

content/journals/10.1049/iet-cdt.2015.0196
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading