Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Deadlock-free adaptive 3D network-on-chips routing algorithm with repetitive turn concept

© The Institution of Engineering and Technology
Received 15/03/2019, Accepted 25/03/2020, Revised 12/02/2020, Published 01/04/2020

With the emergence of a large number of multi-core systems, many 3D routing schemes have been developed for network-on-chips (NoCs) in order to obtain low overhead and high-performance. Nevertheless, it is difficult to possess these characteristics for contemporary 3D routing algorithms. This study presents a new routing algorithm for 3D stacked NoCs based on the repetitive turn concept. The authors propose the high-performance minimum pressure turn model (MPTM) routing algorithm that can be applied to a 3D case. Repetitive prohibited turns are spread in the row and column of the planes and vertical direction in the MPTM routing algorithm with no virtual channels. Besides, the MPTM routing algorithm has minimum routing pressure by exploring the whole 3D space. Considering network average latency and throughput, the results acquired show that the MPTM scheme improves performance over existing work.

Inspec keywords: network-on-chip; three-dimensional integrated circuits; network routing

Other keywords: high-performance minimum pressure turn model routing algorithm; network throughput; repetitive turn concept; 3D routing schemes; repetitive prohibited turns; 3D stacked NoCs; MPTM routing algorithm; deadlock-free adaptive 3D network-on-chip routing algorithm; contemporary 3D routing algorithms; minimum routing pressure; multicore systems; network average latency

Subjects: Network-on-chip; Network-on-chip

References

    1. 1)
      • 25. Xiang, D., Zhang, Y.L., Pan, Y., et al: ‘Deadlock-free adaptive routing in meshes based on cost-effective deadlock avoidance schemes’. 2007 Int. Conf. on Parallel Processing (ICPP 2007), Xi'an, China, September 2007, p. 41.
    2. 2)
      • 30. Chiu, G.: ‘The odd-even turn model for adaptive routing’, IEEE Trans. Parallel Distrib. Syst., 2000, 11, (7), pp. 729–738.
    3. 3)
      • 34. Ebrahimi, M., Daneshtalab, M., Liljeberg, P., et al: ‘Fault-tolerant method with distributed monitoring and management technique for 3D stacked meshes’. CSI Int. Symp. on Computer Architecture and Digital Systems, Tehran, Iran, October 2013, pp. 93–98.
    4. 4)
      • 17. Rahmani, A., Vaddina, K.R., Liljeberg, P., et al: ‘Power and area optimization of 3d networks-on-chip using smart and efficient vertical channels’. 21st Int. Workshop on Integrated Circuit and System Design Power and Timing Modeling, Optimization,and Simulation (PATMOS 2011), Madrid, Spain, September 2011, pp. 278–287.
    5. 5)
      • 14. Marculescu, R., Ogras, Ü.Y., Peh, L., et al: ‘Outstanding research problems in noc design: system, microarchitecture, and circuit perspectives’, IEEE Trans. CAD Integrated Circuits Syst., 2009, 28, (1), pp. 3–21.
    6. 6)
      • 27. Xiang, D., Zhang, Y., Shan, S.C., et al: ‘A fault-tolerant routing algorithm design for on-chip optical networks’. IEEE 32nd Symp. on Reliable Distributed Systems (SRDS 2013), Braga, Portugal, October 2013, pp. 1–9.
    7. 7)
      • 41. Bienia, C., Kumar, S., Singh, J.P., et al: ‘The PARSEC benchmark suite: characterization and architectural implications’. 17th Int. Conf. on Parallel Architecture and Compilation Techniques (PACT 2008), Toronto, Ontario, Canada, October 2008, pp. 72–81.
    8. 8)
      • 10. Feero, B., Pande, P.P.: ‘Networks-on-chip in a three-dimensional environment: a performance evaluation’, IEEE Trans. Comput., 2009, 58, (1), pp. 32–45.
    9. 9)
      • 22. Allen, F., Almasi, G., Andreoni, W., et al: ‘Blue gene: a vision for protein science using a petaflop supercomputer’, IBM Syst. J., 2001, 40, (2), pp. 310–327.
    10. 10)
      • 21. Dally, W., Towles, B.: ‘Principles and practices of interconnection networks’ (Morgan Kaufmann, San Francisco, 2003).
    11. 11)
      • 23. Mukherjee, S.S., Bannon, P.J., Lang, S., et al: ‘The alpha 21364 network architecture’, IEEE Micro, 2002, 22, (1), pp. 26–35.
    12. 12)
      • 32. Ebrahimi, M., Chang, X., Daneshtalab, M., et al: ‘Dyxyz: fully adaptive routing algorithm for 3D NoCs’. 21st Euromicro Int. Conf. on Parallel, Distributed, and Network-Based Processing, PDP, Belfast, United Kingdom, February 2013, pp. 499–503.
    13. 13)
      • 11. Davis, W.R., Wilson, J.M., Mick, S., et al: ‘Demystifying 3D ICS: the pros and cons of going vertical’, IEEE Des. Test Comput., 2005, 22, (6), pp. 498–510.
    14. 14)
      • 15. Pavlidis, V.F., Friedman, E.G.: ‘3-d topologies for networks-on-chip’, IEEE Trans. VLSI Syst., 2007, 15, (10), pp. 1081–1090.
    15. 15)
      • 39. Dahir, N., Mak, T.S.T., Al-Dujaily, R., et al: ‘Highly adaptive and deadlock-free routing for three-dimensional networks-on-chip’, IET Comput. Digit. Tech., 2013, 7, (6), pp. 255–263.
    16. 16)
      • 20. Gorgues, M., Xiang, D., Flich, J., et al: ‘Achieving balanced buffer utilization with a proper co-design of flow control and routing algorithm’. Eighth IEEE/ACM Int. Symp. on Networks-on-Chip (NoCS 2014), Ferrara, Italy, September 2014, pp. 25–32.
    17. 17)
      • 4. Lee, H.G., Chang, N., Ogras, Ü.Y., et al: ‘On-chip communication architecture exploration: a quantitative evaluation of point-to-point, bus, and network-on-chip approaches’, ACM Trans. Des. Autom. Electr. Syst., 2007, 12, (3), pp. 23:1–23:20.
    18. 18)
      • 42. Hestness, J., Grot, B., Keckler, S.W.: ‘Netrace: dependency-driven trace-based network-on-chip simulation’. Third Int. Workshop on Network on Chip Architectures, (NoCArc’10), Atlanta, GA, USA, December 2010, pp. 31–36.
    19. 19)
      • 37. Salamat, R., Khayambashi, M., Ebrahimi, M., et al: ‘LEAD: an adaptive 3D-NoC routing algorithm with queuing-theory based analytical verification’, IEEE Trans. Comput., 2018, 67, (8), pp. 1153–1166.
    20. 20)
      • 26. Xiang, D., Luo, W.: ‘An efficient adaptive deadlock-free routing algorithm for torus networks’, IEEE Trans. Parallel Distrib. Syst., 2012, 23, (5), pp. 800–808.
    21. 21)
      • 29. Glass, C.J., Ni, L.M.: ‘The turn model for adaptive routing’, JACM, 1994, 41, (5), pp. 874–902.
    22. 22)
      • 38. Pasricha, S., Zou, Y.: ‘A low overhead fault tolerant routing scheme for 3D networks-on-chip’. Proc. of the 12th Int. Symp. on Quality Electronic Design (ISQED), Santa Clara, California, USA, March 2011, pp. 204–211.
    23. 23)
      • 19. Burns, J., McIlrath, L., Keast, C., et al: ‘Three-dimensional integrated circuits for low-power, high-bandwidth system on a chip’. IEEE Int. Solid-State Circuits Conf., San Francisco, CA, USA, February 2001, pp. 268–269.
    24. 24)
      • 1. Borkar, S.: ‘Thousand core chipsa technology perspective’. Proc. of the 44th Design Automation Conf. (DAC 2007), San Diego, CA, USA, June 2007, pp. 746–749.
    25. 25)
      • 13. Pavlidis, V.F., Friedman, E.G.: ‘Three-dimensional integrated circuit design’ (Morgan Kaufmann, San Francisco, 2008).
    26. 26)
      • 2. Wang, X.H., Yang, M., Jiang, Y.T., et al: ‘On self-tuning networks-on-chip for dynamic network-flow dominance adaptation’, ACM Trans. Embedded Comput. Syst., 2014, 13, (2s), pp. 73:1–73:21.
    27. 27)
      • 18. Dubois, F., Sheibanyrad, A., Pétrot, F., et al: ‘Elevator-first: a deadlock-free distributed routing algorithm for vertically partially connected 3D-NoCs’, IEEE Trans. Comput., 2013, 62, (3), pp. 609–615.
    28. 28)
      • 16. Manna, K., Swami, S., Chattopadhyay, S., et al: ‘Integrated through-silicon via placement and application mapping for 3D mesh-based noc design’, ACM Trans. Embedded Comput. Syst., 2016, 16, (1), pp. 24:1–24:25.
    29. 29)
      • 12. Knickerbocker, J.U., Andry, P.S., Dang, B., et al: ‘Three-dimensional silicon integration’, IBM J. Res.Dev., 2008, 52, (6), pp. 553–569.
    30. 30)
      • 5. Wentzlaff, D., Griffin, P., Hoffmann, H., et al: ‘On-chip interconnection architecture of the tile processor’, IEEE Micro, 2007, 27, (5), pp. 15–31.
    31. 31)
      • 35. Lee, J., Kang, K., Choi, K.: ‘REDELF: an energy-efficient deadlock-free routing for 3D NoCs with partial vertical connections’, JETC, 2015, 12, (3), pp. 26:1–26:22.
    32. 32)
      • 3. Benini, L., Micheli, G.D.: ‘Networks on chips: a new SoC paradigm’, IEEE Comput., 2002, 35, (1), pp. 70–78.
    33. 33)
      • 36. Salamat, R., Khayambashi, M., Ebrahimi, M., et al: ‘A resilient routing algorithm with formal reliability analysis for partially connected 3D-NoCs’, IEEE Trans. Comput., 2016, 65, (11), pp. 3265–3279.
    34. 34)
      • 28. Tang, M.H., Lin, X.L., Palesi, M.: ‘The repetitive turn model for adaptive routing’, IEEE Trans. Comput., 2017, 66, (1), pp. 138–146.
    35. 35)
      • 24. Carloni, L.P., Pande, P., Xie, Y.: ‘Networks-on-chip in emerging interconnect paradigms: advantages and challenges’. Third Int. Symp. on Networks-on-Chips (NoCs 2009), La Jolla, CA, USA, May 2009, pp. 93–102.
    36. 36)
      • 6. Zahavi, E., Cidon, I., Kolodny, A.: ‘Gana: A novel low-cost conflict-free noc architecture’, ACM Trans. Embedded Comput. Syst., 2013, 12, (4), pp. 109:1–109:20.
    37. 37)
      • 7. Xiang, D., Zhang, Y.L., Pan, Y.: ‘Practical deadlock-free fault-tolerant routing in meshes based on the planar network fault model’, IEEE Trans. Comput., 2009, 58, (5), pp. 620–633.
    38. 38)
      • 9. Topol, A.W., Shi, L., Frank, D.J., et al: ‘Three-dimensional integrated circuits’, IBM J. Res. Dev., 2006, 50, (4-5), pp. 491–506.
    39. 39)
      • 33. Akbari, S., Shafiee, A., Fathy, M., et al: ‘AFRA: A low cost high performance reliable routing for 3D mesh NoCs’. 2012 Design, Automation & Test in Europe Conf. & Exhibition (DATE 2012), Dresden, Germany, March 2012, pp. 332–337.
    40. 40)
      • 40. Duato, J., Yalamanchili, S., Ni, L.M.: ‘Interconnection networks: an engineering approach’ (Morgan Kaufmann, San Francisco, 2003).
    41. 41)
      • 8. Dally, W.J., Towles, B.: ‘Route packets, not wires: ‘on-chip interconnection networks’. Proc. of the 38th Design Automation Conf. (DAC 2001), Las Vegas, NV, USA, June 2001, pp. 684–689.
    42. 42)
      • 31. Tang, M.H., Lin, X.L., Palesi, M.: ‘Routing pressure: a channel-related and traffic-aware metric of routing algorithm’, IEEE Trans. Parallel Distrib. Syst., 2015, 26, (3), pp. 891–901.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-com.2019.0269
Loading

Related content

content/journals/10.1049/iet-com.2019.0269
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address