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

access icon free KBMA: A knowledge-based multi-objective application mapping approach for 3D NoC

© The Institution of Engineering and Technology
Received 20/04/2018, Accepted 08/02/2019, Revised 28/10/2018, Published 14/02/2019

Due to increased demands for communication at low power, an efficient application mapping has become vital in the area of network on chip (NoC). Optimisation of architectural structure in on-chip design is essential to maximise the performance of the network and minimise the cost functions. To address this issue, a knowledge-based memetic algorithm (KBMA) is proposed for 3D NoC for successful mapping with standard network topologies. The proposed KBMA adopts power, area and delay as a cost function for an effective mapping. The competence of the proposed method is verified through comparison with other natural inspired algorithms like particle swarm optimisation and genetic algorithm. The presented work is validated through four case studies which include real application benchmarks of NoC and random generated benchmarks using test graph for free.

Inspec keywords: circuit optimisation; three-dimensional integrated circuits; low-power electronics; network-on-chip; genetic algorithms; particle swarm optimisation

Other keywords: low power; NoC; effective mapping; particle swarm optimisation; natural inspired algorithms; knowledge-based multiobjective application mapping approach; random generated benchmarks; standard network topologies; genetic algorithm; network on-chip design; 3D NoC; efficient application mapping; test graph; architectural structure optimization; KBMA; cost function; knowledge-based memetic algorithm; application benchmarks

Subjects: Combinatorial mathematics; Optimisation techniques; Network-on-chip; Optimisation techniques; Network-on-chip

References

    1. 1)
      • 32. Dally, W., Towels, B.: ‘Principles and practices of interconnection networks’ (Morgan Kaufmann Inc., CA, USA, 2003).
    2. 2)
      • 22. Suboh, S., Bakhouya, M., Gaber, J., et al: ‘Analytical modeling and evaluation of network-on-chip architectures’. Proc. 2010 Int. Conf. High Performance Computing Simulation, HPCS, 2010, pp. 615–622.
    3. 3)
      • 17. Sepulveda, J., Gogniat, G., Pires, R., et al: ‘Qos 3D HoC hybrid on chip communication structure for dynamic MPSoC’. Proc. 4th IEEE American Symp. Circuits and Systems (LASCAS), 2013.
    4. 4)
      • 26. Sahu, P.K., Chattopadhyay, S.: ‘A survey on application mapping strategies for network-on-chip design’, J. Syst. Archit., 2013, 59, (1), pp. 60–76.
    5. 5)
      • 24. Salini, S., Aravindhan, A., Lakshminarayanan, G.: ‘A case study on cluster based power aware mapping strategy for 2D NoC’, ICTCAT J. Microelectron., 2017, 2, (4), pp. 315–322.
    6. 6)
      • 31. Sahu, P.K., Shah, T., Manna, K., et al: ‘Application mapping onto mesh based network-on-chip using discrete particle swarm optimization’, IEEE Trans. VLSI, 2014, 22, (2), pp. 300–312.
    7. 7)
      • 3. Awasthi, M., Balasubramonian, R.: ‘Exploring the design space for 3D clustered architectures’. Proc. Third IBM Watson Conf. Interaction between Architecture, Circuits and Compilers, 2006.
    8. 8)
      • 33. Kahng, A.B., Li, B., Peh, L-S., et al: ‘ORION 2.0: a fast and accurate NoC power and area model for early stage design space exploration’. Proc. Int. Conf. Design Automation and Test, France, June 2009, pp. 423–428.
    9. 9)
      • 8. Zhou, X., Yang, J., Xu, Y., et al: ‘Thermal-aware task scheduling for 3D multicore processors’, IEEE Trans. Parallel Distrib. Syst., 2010, 21, (1), pp. 60–71.
    10. 10)
      • 4. Pavlidis, V.F., Friedman, E.G.: ‘3-D topologies for networks-on-chip’. 2006 IEEE Int. System Conf. SOC, 2007, vol. 15, no. 10, pp. 285–288.
    11. 11)
      • 5. Kahng, A.B., Li, B., Li-Shiuan, P., et al: ‘ORION 2.0: a fast and accurate NoC power and area model for early-stage design space exploration’. 2009 Design, Automation & Test in Europe Conf. & Exhibition, 2009, pp. 423–428.
    12. 12)
      • 35. Srinivasan, K., Chatha, K.S., Konjevod, G.: ‘Linear-programming-based techniques for synthesis of network-on-chip architecture’, IEEE Trans. VLSI, 2006, 14, (4), pp. 407–420.
    13. 13)
      • 14. Liu, Z., Wu, N., Zhou, L., et al: ‘A path optimized multicast routing algorithm for 3D network-on-chip’. Proc. World Congress on Engineering and Computer Science, 2015, vol. 1, pp. 1–6.
    14. 14)
      • 36. Murali, S., Meloni, P., Angiolini, F., et al: ‘Designing message dependent deadlock free networks on chips’. Proc. of VLSI-SoC, 2006, pp. 158–163.
    15. 15)
      • 38. Rahmani, A.-M., Ali, A.-M., Pedram, M.: ‘A novel synthetic traffic pattern for power /performance analysis for network on chip using negative exponential distribution’, J. Low Power Electron., 2009, 5, (3), pp. 396–405.
    16. 16)
      • 20. Aravindhan, A., Lakshminarayanan, G.: ‘SAT: A new application mapping method for power optimization in 2D – NoC’. Proc. 20th IEEE Int. Symp. VLSI Design and Test, IIT, Guwahati, 2016, pp. 270–275.
    17. 17)
      • 9. Rahmani, A.-M., Latif, K., Liljeberg, P., et al: ‘3D integration for energy efficient system design’. 19th Int. Euromicro Conf. Parallel, Distributed and Network-Based Processing, 2011, vol. 1, pp. 58–59.
    18. 18)
      • 15. Wang, K., Dong, S., Jiao, F.: ‘TSF3D: MSV-driven power optimization for application-specific 3D network-on-chip’, IEEE Trans. Comput. Des. Integr. Circuits Syst., 2017, 36, (7), pp. 1089–1102.
    19. 19)
      • 27. Krasnogor, N., Smith, J.: ‘A tutorial for competent memetic algorithms: model, taxonomy, and design issues’, IEEE Trans. Evol. Comput., 2005, 9, pp. 474–488.
    20. 20)
      • 6. Feero, B.S., Pande, P.P.: ‘Networks-on-chip in a three-dimensional environment: a performance evaluation’, IEEE Trans. Comput., 2009, 58, (1), pp. 32–45.
    21. 21)
      • 1. Bjerregaard, T., Mahadevan, S.: ‘A survey of research and practices of network-on-chip’, ACM Comput. Surv., 2006, 38, (1), pp. 1–6.
    22. 22)
      • 11. Ebrahimi, M., Daneshtalab, M., Liljeberg, P., et al: ‘Cluster-based topologies for 3D networks-on-chip using advanced inter-layer bus architecture’, J. Comput. Syst. Sci., 2013, 79, (4), pp. 475–491.
    23. 23)
      • 7. Cai, J., Jiang, P., Yao, L., et al: ‘Through-Silicon Via (TSV) capacitance modeling for 3D NoC energy consumption estimation’. ICSICT-2010 – 2010 10th IEEE Int. Conf. on Solid-State and Integrated Circuits Technology Proc., 2010, pp. 815–817.
    24. 24)
      • 18. Sepulveda, J., Gogniat, G., Sepulveda, D., et al: ‘3DMIA: a multi-objective artificial immune algorithm for 3D-MPSoC multi application 3D-NoC mapping’. 15th Annual Conf. Companion on Genetic and Evolutionary Comp. (GECCO), 2013, pp. 167–168.
    25. 25)
      • 29. Murali, S., Micheli, G. D.: ‘SUNMAP: a tool for automatic topology selection and generation for NoCs’. Proc. of the 41st IEEE/ACM Design and Automation Conf. (DAC'04), 2004, pp. 914–919.
    26. 26)
      • 21. Aravindhan, A., Salini, S., Lakshminarayanan, G.: ‘Cluster based application mapping strategy for 2D NoC’, Procedia Tech, 2016, 25, pp. 505–512.
    27. 27)
      • 19. Mosayyebzadeh, A., Amiraski, M.M., Hessabi, S.: ‘Thermal and power aware task mapping on 3D network on chip’, Comput. Electr. Eng., 2016, 51, pp. 157–167.
    28. 28)
      • 2. Banerjee, K., Souri, S.J., Kapur, P., et al: ‘3-D ICs: a novel chip design for improving deep-submicrometer interconnect performance and systems-on-chip integration and systems-on-chip integration’, Proc. IEEE, 2001, 89, (5), pp. 602–632.
    29. 29)
      • 12. Wang, K, Dong, S.: ‘Network-on-chip with multiple supply voltages’. Proc. Asia South Pacific Design Automation Conf. ASP-DAC, 2013, pp. 362–367.
    30. 30)
      • 28. http://ziyang.eecs.umich.edu/~dickrp/tgff/, (accessed January 2016).
    31. 31)
      • 10. Zia, A., Kannan, S., Jonathan Chao, H., et al: ‘3D NOC for many-core processors’, Microelectronics J., 2011, 42, (12), pp. 1380–1390.
    32. 32)
      • 30. Predictive Technology Model (PTM). Arizona State Univ. Available at http://ptm.asu.edu/, (accessed March 2015).
    33. 33)
      • 25. Murali, S., Micheli, G.D.: ‘Bandwidth-constrained mapping of cores onto NoC architectures’. Proc of the 2004 IEEE/ACM Conf. Design, Automation and Test in Europe (DATE'04), 2004, pp. 896–901.
    34. 34)
      • 16. Wang, J., Li, L., Pan, H., et al: ‘Latency aware mapping for 3D NoC using rank-based multi-objective genetic algorithm’. 9th IEEE Int. Conf. ASIC (ASICON), 2011.
    35. 35)
      • 13. Elmiligi, H., El-Kharashi, M.W., Gebali, F.: ‘Power consumption of 3D networks-on-chips: modeling and optimization’, Microprocess. Microsyst., 2013, 37, (6–7), pp. 530–543.
    36. 36)
      • 34. Dijikstra, E. W.: ‘A note on two problems in connextion with graphs’, Numer. Math., 1959, 1, (1), pp. 269–271.
    37. 37)
      • 37. Murali, S., Seiculesu, C., Benini, L., et al: ‘Synthesis of networks on chips for 3D system on chips’. Proc. the 14th Asia and South Pacific Design Automation Conf. (ASPDAC), 2009, pp. 242–247.
    38. 38)
      • 40. Lee, K., Chang, C., Yang, H.: ‘An efficient deadlock-free multicast routing algorithm for mesh based network-on-chip’. IEEE Int. Symp. VLSI Design, Automation, and Test (VLSI-DAT), 2013, pp. 1–4.
    39. 39)
      • 39. Ahmed, A.B, Abderazek, B.: ‘LA-XYZ: low latency, high throughput look-ahead routing algorithm for 3D network on chip (3D NoC) architecture’. Proc. IEEE Int. Symp. Embedded Multicore SoCs (MCSoC), 2012, pp. 167–174.
    40. 40)
      • 23. Morgan, A., El-Kharashi, M.W., Elmiligi, H., et al: ‘Unified multi-objective mapping and architecture customisation of networks-on-chip’, IET Comput. Digit. Tech., 2013, 7, (6), pp. 282–293.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2018.5055
Loading

Related content

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