AIRCC's International Journal of Computer Science and Information Technology

Open Access Open Access  Restricted Access Subscription Access

Applying Genetic Algorithm to Solve Partitioning and Mapping Problem for Mesh Network-On-Chip Systems


Affiliations
1 Faculty of Science University of Tripoli Tripoli, Libya
2 Faculty of Information Technology University of Tripoli Tripoli, Libya
 

This paper presents a genetic based approach to the partitioning and mapping of multicore SoC cores over a NoC system that uses mesh topology. The proposed algorithm performs the partitioning and mapping by reducing communication cost and minimizing power consumption by placing those intercommunicated cores as close as possible together. A program developed in C++ in which the provided specification of the multicore MPSoC system captures all data dependencies before any start of the design process. Experimental results of several multimedia benchmarks demonstrates that the genetic-based approach able to find different satisfied implementations to the problem of partitioning and mapping of MPSoC cores over mesh-based NoC system that satisfies design goals.

Keywords

Network-on-Chip, Multicore, Partitioning, Mesh Topology, Genetic Algorithm
User
Notifications
Font Size

  • Ahmed A. Jerraya, Wayne Wolf (editors) [2005]. Multiprocessor Systems-ON-Chips, Morgan Kaufmann Publishers, San Francisco, USA.

  • Resve Saleh, et al.: System-on-Chip: Reuse and Integration, Proceedings of the IEEE, Vol. 94, No. 6, June 2006.

  • Jantsch A, Tenhunen H., 2003. Networks on Chip. Kluwer Academic Publishers, USA.

  • De Michelli G, Benini L. Network on Chips. Morgan Kaufmann: Berlin, 2006.

  • Dally, W. J., and B. Towles, “Route packets, not wires: On-chip interconnection networks,” Proc. of the DAC'38 Conference, Las Vegas, June 2001.

  • T. Lei and S. Kumar. "A two-step genetic algorithm for mapping task graphs to a network on chip architecture", In Euromicro Symposium on Digital Systems Design, Sept. 1-6, 2003.

  • J. Teich, T. Blickle, L. Thiele: An Evolutionary Approach to System-Level Synthesis, In IEEE Proc. of Codes/CASHE’97 5th Int. Workshop on Hardware/Software Codesign, Braunschweig, Germany, March 1997, pp. 167-171.

  • J. Henkel, R. Ernst: High-Level Estimation Techniques for Usage in Hardware/Software Co-Design, In Proc. of IEEE/ACM Asia and South Pacific Design Automation Conference ASP-DAC’98, February Japan, 1998, pp. 353-360.

  • Amit Kumar Singh ; Muhammad Shafique ; Akash Kumar ; Jörg Henkel: Mapping on multi/many-core systems: Survey of current and emerging trends, In Design Automation Conference (DAC), 2013 50th ACM/EDAC/IEEE, NY, USA, May 2013.Page(s):1 - 10.

  • G. Ascia, V. Catania ; M. Palesi: An evolutionary approach to network-on-chip mapping problem, 2005 IEEE Congress on Evolutionary Computation, Sept. 2005, Edinburgh, Scotland, Vol.1, pp.112 – 119.

  • Glenn Leary, Krishnan Srinivasan ; Krishna Mehta ; Karam S. Chatha: Design of Network-on-Chip Architectures With a Genetic Algorithm-Based Technique, In IEEE Transactions on Very Large Scale Integration (VLSI) Systems ,Vol.17, Issue: 5) pp.674 – 687.

  • Tobias Bjerregaardand Shankar Mahadevan: A Survey of Research and Practices of Network-on-Chip, ACM Computing Surveys, Vol. 38, Article no.1, March 2006.

  • Kavaldjiev, Nikolay Krasimirov, and Gerardus Johannes Maria Smit, A survey of efficient on-chip communications for soc, Centre for Telematics and Information Technology, University of Twente, 2003.

  • Dally, W. J., and B. Towles. 2004. Principles and Practices of Interconnection Networks. Morgan Kaufmann Publishers, San Francisco, USA.

  • Duato J., S.Yalamanchili, L. Ni. 2002. Interconnection Networks–An Engineering Approach. Morgan Kaufmann Publishers, San Francisco, USA.

  • Azeddien M. Sllame, Amani Hasan: A Comparative Study between Fat Tree and Mesh Network-on-Chip Interconnection Architectures, In The 14th annual Middle Eastern Simulation and Modelling Conference (MESM’14), pp. 31-37, Muscat, Oman, 3-5 February 2014.

  • T. Baack: Genetic Algorithms in Theory and Practice. Oxford University Press, New York, Oxford, 1996.

  • D. Goldberg: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company, 1989.

  • J. Teich, T. Blickle, L. Thiele: An Evolutionary Approach to System-Level Synthesis, In IEEE Proc. of Codes/CASHE’97 5th Int. Workshop on Hardware/Software Codesign, Braunschweig, Germany, March 1997, pp. 167-171.

  • Azeddien M. Sllame, L. Sekanina: An Evolutionary-Based Algorithm to the Module Selection Process in High-Level Synthesis, In Proc. of 8th Int. Conference on Soft Computing Mendel’2002, Brno, Czech Republic, June 2002, pp. 87-92.

  • N.Janakiraman, P.ManoArunika, P.Nirmal Kumar, "An optimized Mapping of IP Core onto NoC using Multi-Objective Evolutionary Algorithms" , International Journal of Innovative Research in Science, Engineering and Technology Volume 3, Special Issue 3, March 2014.

  • Antoine Jalabert Srinivasan Murali Luca Benini Giovanni De Micheli: ×pipes Compiler: A tool for instantiating application specific Networks on Chip, Proceedings of the Design, Automation, and Test in Europe Conference and Exhibition (DATE’04), IEEE, 2004.

  • Fen Ge, Ning Wu, Xiaolin Qin and Ying Zhang: Clustering-Based Topology Generation Approach for Application-Specific Network on Chip, Proceedings of the World Congress on Engineering and Computer Science 2011 Vol II WCECS 2011, October 19-21, 2011, San Francisco, USA.

  • Ahmed A. Morgan, Haytham Elmiligi, M. Watheq El-Kharashi, and Fayez Gebali: Networks-on-Chip Architecture Customization using Network Partitioning: A System-Level Performance Evaluation, Int. J. Com. Dig. Sys. 4, No.1 (Jan-2015), ISSN (2210-142X).


Abstract Views: 445

PDF Views: 176




  • Applying Genetic Algorithm to Solve Partitioning and Mapping Problem for Mesh Network-On-Chip Systems

Abstract Views: 445  |  PDF Views: 176

Authors

WalidMoktharSalh
Faculty of Science University of Tripoli Tripoli, Libya
Azeddien M. Sllame
Faculty of Information Technology University of Tripoli Tripoli, Libya

Abstract


This paper presents a genetic based approach to the partitioning and mapping of multicore SoC cores over a NoC system that uses mesh topology. The proposed algorithm performs the partitioning and mapping by reducing communication cost and minimizing power consumption by placing those intercommunicated cores as close as possible together. A program developed in C++ in which the provided specification of the multicore MPSoC system captures all data dependencies before any start of the design process. Experimental results of several multimedia benchmarks demonstrates that the genetic-based approach able to find different satisfied implementations to the problem of partitioning and mapping of MPSoC cores over mesh-based NoC system that satisfies design goals.

Keywords


Network-on-Chip, Multicore, Partitioning, Mesh Topology, Genetic Algorithm

References