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

access icon free Unified multi-objective mapping for network-on-chip using genetic-based hyper-heuristic algorithms

© The Institution of Engineering and Technology
Received 17/07/2017, Accepted 24/12/2017, Revised 29/11/2017, Published 16/01/2018

In this study, a flexible energy- and delay-aware mapping approach is proposed for the co-optimisation of energy consumption and communication latency for network-on-chips (NoCs). A novel genetic-based hyper-heuristic algorithm (GHA) is proposed as the core algorithm. This algorithm consists of bottom-level optimisation which includes a variety of operators and top-level optimisation which selects suitable operators through a ‘reward’ mechanism. As this algorithm can select suitable operators automatically during the mapping process, it noticeably improves convergence speed and demonstrates excellent stability. Compared to the random algorithm, GHA can achieve on average 23.28% delay reduction and 11.81% power reduction. Compared to state-of-the-art mapping algorithms, GHA produces improved mapping results with less time, especially when the size of NoC is large.

Inspec keywords: network-on-chip; genetic algorithms

Other keywords: delay-aware mapping approach; top-level optimisation; energy consumption; GHA; bottom-level optimisation; NoC; network-on-chip; energy-aware mapping approach; unified multiobjective mapping; communication latency; genetic-based hyperheuristic algorithms

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

References

    1. 1)
      • 33. Jiang, N., Balfour, J., Becker, D.U., et al: ‘A detailed and flexible cycle-accurate network-on-chip simulator’. Performance Analysis of Systems and Software (ISPASS), 2013 IEEE Int. Symp. on, 2013.
    2. 2)
      • 22. Elmiligi, H., Morgan, A.A., El-Kharashi, M.W., et al: ‘A delay-aware topology-based design for networks-on-chip applications’. 2009 4th Int. Design and Test Workshop (IDT), 2009.
    3. 3)
      • 19. Bayar, S., Yurdakul, A.: ‘An efficient mapping algorithm on 2-D mesh network-on-chip with reconfigurable switches’. 2016 Int. Conf. on Design and Technology of Integrated Systems in Nanoscale Era (DTIS), 2016.
    4. 4)
      • 1. Cheshmi, K., Mohammadi, S., Versick, D., et al: ‘A clustered gals Noc architecture with communication-aware mapping’. 2015 23rd Euromicro Int. Conf. on Parallel, Distributed, and Network-Based Processing, 2015.
    5. 5)
      • 6. Bhardwaj, K., Mane, P.S.: ‘C3map and arpso based mapping algorithms for energy-efficient regular 3-D Noc architectures’. VLSI Design, Automation and Test (VLSI-DAT), 2014 Int. Symp. on, 2014.
    6. 6)
      • 12. Qingqi, Z., Yanling, Q., Yue, L., et al: ‘Multi-objective mapping for network-on-chip based on bio-inspired optimization algorithms’. 2014 Prognostics and System Health Management Conf. (PHM-2014 Hunan), 2014.
    7. 7)
      • 24. Elmiligi, H., El-Kharashi, M.W., Gebali, F.: ‘A delay model for networks-on-chip output-queuing router’. 2006 6th Int. Workshop on System on Chip for Real Time Applications, 2006.
    8. 8)
      • 29. Cowling, P.I., Kendall, G., Soubeiga, E.: ‘A hyperheuristic approach to scheduling a sales summit’. Practice and Theory of Automated Timetabling III, Third Int. Conf., PATAT 2000, Konstanz, Germany, August 16–18, 2000, Selected Papers, (2001).
    9. 9)
      • 34. Kahng, A.B., Lin, B., Nath, S.: ‘Orion3.0: A comprehensive Noc router estimation tool’, IEEE Embedded Syst. Lett., 2015, 7, (2), pp. 41–45.
    10. 10)
      • 13. Cilardo, A., Fusella, E.: ‘Design automation for application-specific on-chip interconnects: A survey’, Integr. VLSI J., 2016, 52, (Supplement C), pp. 102–121.
    11. 11)
      • 32. Dick, R.P., Rhodes, D.L., Wolf, W.: ‘Tgff: task graphs for free’. Hardware/Software Codesign, 1998. (CODES/CASHE ‘98) Proc. of the Sixth Int. Workshop on, 1998.
    12. 12)
      • 21. Ye, T.T., Benini, L., Micheli, G.D.: ‘Analysis of power consumption on switch fabrics in network routers’. Design Automation Conf., 2002. Proc. 39th, 2002.
    13. 13)
      • 18. Wu, C., Deng, C., Liu, L., et al: ‘A multi-objective model oriented mapping approach for Noc-based computing systems’, IEEE Trans. Parallel Distrib. Syst., 2016, 28, (3), pp. 1–1.
    14. 14)
      • 28. Fusella, E., Cilardo, A.: ‘Phonocmap: An application mapping tool for photonic networks-on-chip’. 2016 Design, Automation & Test in Europe Conf. & Exhibition (DATE), 2016.
    15. 15)
      • 9. Zhu, D., Chen, L., Pinkston, T.M., et al: ‘Tapp: temperature-aware application mapping for Noc-based many-core processors’. 2015 Design, Automation & Test in Europe Conf. & Exhibition (DATE), 2015.
    16. 16)
      • 4. Kim, J., Park, D., Nicopoulos, C., et al: ‘Design and analysis of an Noc architecture from performance, reliability and energy perspective’. Architecture for networking and communications systems, 2005. ANCS 2005. Symp. on, 2005.
    17. 17)
      • 23. Das, A., Kumar, A., Veeravalli, B.: ‘Energy-Aware communication and remapping of tasks for reliable multimedia multiprocessor systems’. 2012 IEEE 18th Int. Conf. on Parallel and Distributed Systems, 2012.
    18. 18)
      • 17. Cheng, C.-H., Chen, W.-M.: ‘Application mapping onto mesh-based network-on-chip using constructive heuristic algorithms’, J. Supercomput., 2016, 72, (11), pp. 4365–4378.
    19. 19)
      • 3. http://www.itrs.net/Links/2013ITRS/Home2013.html., accessed 2016 20 October.
    20. 20)
      • 11. Liu, L., Wu, C., Deng, C., et al: ‘A flexible energy- and reliability-aware application mapping for Noc-based reconfigurable architectures’, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2015, 23, (11), pp. 2566–2580.
    21. 21)
      • 16. Wang, X., Liu, H., Yu, Z.: ‘A novel heuristic algorithm for Ip block mapping onto mesh-based networks-on-chip’, J. Supercomput., 2016, 72, (5), pp. 2035–2058.
    22. 22)
      • 5. Palaniveloo, V.A., Ambrose, J.A., Sowmya, A.: ‘Improving Ga-based Noc mapping algorithms using a formal model’. 2014 IEEE Computer Society Annual Symp. on VLSI, 2014.
    23. 23)
      • 31. 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.
    24. 24)
      • 7. Farias, M., Barros, E., Araújo, A.: ‘An approach for multi-task and multi-application mapping onto Noc-based mpsoc’. 2014 IEEE 57th Int. Midwest Symp. on Circuits and Systems (MWSCAS), 2014.
    25. 25)
      • 26. Jingcao, H., Marculescu, R.: ‘Energy- and performance-aware mapping for regular Noc architectures’, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 2005, 24, (4), pp. 551–562.
    26. 26)
      • 15. Li, Z., Liu, Y., Cheng, M.: ‘Solving Noc mapping problem with improved particle swarm algorithm’. 2013 Sixth Int. Conf. on Advanced Computational Intelligence (ICACI), 2013.
    27. 27)
      • 30. Sivanandam, S.N.: ‘S.N.D., introduction to genetic algorithms’ (Springer, Heidelberg, 2008).
    28. 28)
      • 10. Chatterjee, N., Reddy, S., Reddy, S., et al: ‘A reliability aware application mapping onto mesh based network-on-chip’. 2016 3rd Int. Conf. on Recent Advances in Information Technology (RAIT), 2016.
    29. 29)
      • 20. Alikhah-Asl, E., Reshadi, M.: ‘Aspect and distance based Noc mapping (Adb)’. 2016 8th Int. Symp. on Telecommunications (IST), 2016.
    30. 30)
      • 14. Zhong, L., Sheng, J., Jing, M., et al: ‘An optimized mapping algorithm based on simulated annealing for regular Noc architecture’. 2011 9th IEEE Int. Conf. on ASIC, 2011.
    31. 31)
      • 25. Gebali, F.: ‘Computer communication networks analysis and design’ (Northstar Digital Design Inc, Canada, 2002).
    32. 32)
      • 2. Wu, C., Deng, C., Liu, L., et al: ‘An efficient application mapping approach for the Co-optimization of reliability, energy, and performance in reconfigurable Noc architectures’, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 2015, 34, (8), pp. 1264–1277.
    33. 33)
      • 27. Yan, J., Wu, X.: ‘A genetic based hyper-heuristic algorithm for the Job shop scheduling problem’. 2015 7th Int. Conf. on Intelligent Human-Machine Systems and Cybernetics, 2015.
    34. 34)
      • 8. Li, J., Pan, Y.: ‘A fast and energy efficient branch and bound algorithm for Noc task mapping’. Computer Design (ICCD), 2015 33rd IEEE Int. Conf. on, 2015.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2017.0156
Loading

Related content

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