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

access icon free Network-on-chip heuristic mapping algorithm based on isomorphism elimination for NoC optimisation

With the development of network-on-chip (NoC) theory, lots of mapping algorithm have been proposed to solve the application mapping problem which is an NP-hard (non-polynomial hard) problem. Most algorithms are based on a heuristic algorithm. They are trapped by iterations limited, not by the distance between iterations, because of the isomorphism of mapping sequence. In this study, the authors define and analyse the isomorphism with the genetic algorithm (GA) which is a heuristic algorithm. Then, they proposed an approach called density direction transform algorithm to eliminate the isomorphism of mapping sequence and accelerate the convergence of population. To verify this approach, they developed a density-direction-based genetic mapping algorithm (DDGMAP) and make a comparison with genetic mapping algorithm (GMA). The experiment demonstrates that compared to the random algorithm, their algorithm (DDGMAP) can achieve on an average 23.48% delay reduction and 7.15% power reduction. And DDGMAP gets better performance than GA in searching the optimal solution.

References

    1. 1)
      • 5. Tsai, W.-C., Lan, Y.-C., Hu, Y.-H., et al: ‘Networks on chips: structure and design methodologies’, J. Electr. Comput. Eng., 2012, 2012, pp. 22.
    2. 2)
      • 6. Khan, S., Anjum, S., Gulzari, U.A., et al: ‘Bandwidth-constrained multi-objective segmented brute-force algorithm for efficient mapping of embedded applications on NoC architecture’, IEEE Access, 2018, 6, pp. 1124211254.
    3. 3)
      • 9. Majd, A., Sahebi, G., Daneshtalab, M., et al: ‘Hierarchal placement of smart mobile access points in wireless sensor networks using fog computing’. 2017 25th Euromicro Int. Conf. on Parallel, St. Petersburg, Russia, 2017.
    4. 4)
      • 13. Hsin, H., Chang, E., Su, K., et al: ‘Ant colony optimization-based adaptive network-on-chip routing framework using network information region’, IEEE Trans. Comput., 2015, 64, pp. 21192131.
    5. 5)
      • 18. Kullu, P., Tosun, S.: ‘MARM-GA: mapping applications to reconfigurable mesh using genetic algorithm’. 2019 22nd Euromicro Conf. on Digital System Design (DSD), Kallithea, Greece, 2019, pp. 1318.
    6. 6)
      • 16. Morgan, A.A., Elmiligi, H., El-Kharashi, M.W., et al: ‘Multi-objective optimization for networks-on-chip architectures using genetic algorithms’. Proc. of 2010 IEEE Int. Symp. on Circuits and Systems, Paris, France, 2010, pp. 37253728.
    7. 7)
      • 23. 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, Hangzhou, China, 2015, pp. 161164.
    8. 8)
      • 25. Forrest: ‘Genetic algorithms: principles of natural selection applied to computation’, Science, 1993, 261, pp. 872878.
    9. 9)
      • 19. Gebali, F.: ‘Computer communication networks analysis and design’ (Northstar Digital Design Inc, Canada, 2002).
    10. 10)
      • 14. Xu, C., Liu, Y., Li, P., et al: ‘Unified multi-objective mapping for network-on-chip using genetic-based hyper-heuristic algorithms’, IET Comput. Digit. Tech., 2018, 12, pp. 158166.
    11. 11)
      • 15. Bhardwaj, K., Mane, P.S.: ‘C3map and ARPSO based mapping algorithms for energy-efficient regular 3-D NoC architectures’. 2014 Int. Symp. on VLSI Design, Automation and Test (VLSI-DAT), Hsinchu, China, 2014, pp. 14.
    12. 12)
      • 2. Patterson, D.A.: ‘Computer organization and design MIPS edition: the hardware/software interface’ (Morgan Kaufmann: CD Included, USA., 2013, 5th edn.).
    13. 13)
      • 12. Upadhyay, M., Shah, M., Bhanu, P.V., et al: ‘Multi-application based network-on-chip design for mesh-of-tree topology using global mapping and reconfigurable architecture’. 2019 32nd Int. Conf. on VLSI Design and 2019 18th Int. Conf. on Embedded Systems (VLSID), Delhi, NCR, India, 2019, pp. 527528.
    14. 14)
      • 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), Riyadh, Saudi Arabia, 2009, pp. 15.
    15. 15)
      • 24. 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), Zhangiiaijie, China, 2014, pp. 387390.
    16. 16)
      • 3. Dally, W.J., Towles, B.: ‘Route packets, not wires: on-chip interconnection networks’. Proc. of the 38th Design Automation Conf. (IEEE Cat. No.01CH37232), Las Vegas, NV, USA., 2001, pp. 684689.
    17. 17)
      • 10. Murali, S., Micheli, G.D.: ‘Bandwidth-constrained mapping of cores onto NoC architectures’. Proc. Design, Automation and Test in Europe Conf. and Exhibition, Paris, France, 2004, vol. 2, pp. 896901.
    18. 18)
      • 7. 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, Xiamen, China, 2011, pp. 389392.
    19. 19)
      • 20. Ye, T.T., Benini, L., Micheli, G.D.: ‘Analysis of power consumption on switch fabrics in network routers’. Proc. 2002 Design Automation Conf. (IEEE Cat. No.02CH37324), New Orleans, LA, USA., 2002, pp. 524529.
    20. 20)
      • 21. 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, pp. 12641277.
    21. 21)
      • 8. Shen, W., Chao, C., Lien, Y., et al: ‘A new binomial mapping and optimization algorithm for reduced-complexity mesh-based on-chip network’. First Int. Symp. on Networks-on-Chip (NOCS'07), Princeton, NJ, USA., 2007, pp. 317322.
    22. 22)
      • 1. International Roadmap for Devices and Systems, System and Architectures (IRDS™) 2017 Edition. Available at https://irds.ieee.org/editions/2017.
    23. 23)
      • 17. Ying, H., Heid, K., Hollstein, T., et al: ‘A genetic algorithm based optimization method for low vertical link density 3-dimensional networks-on-chip many core systems’. NORCHIP 2012, Copenhagen, Denmark, 2012, pp. 14.
    24. 24)
      • 4. Benini, L., Micheli, G.D.: ‘Networks on chips: a new SoC paradigm’, Computer, 2002, 35, pp. 7078.
    25. 25)
      • 11. Tang, L., Kumar, S.: ‘A two-step genetic algorithm for mapping task graphs to a network on chip architecture’. Euromicro Symp. on Digital System Design, 2003. Proc., Belek-Antalya, Turkey, 2003, pp. 180187.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2019.0212
Loading

Related content

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