A Survey of Meta-Heuristic Solution Methods for Mapping Problem in Network-on-Chips

Abstract:

Network on Chip (NoC) has been proposed as a new paradigm for designing System on Chip which supports high degree of scalability and reusability. Mapping the IP cores onto a given platform is an important phase of NoC design which can greatly affect the performance and energy consumption of the chip. Mapping which is an instance of the constrained quadratic assignment problem (QAP) belongs to the class of NP-hard problems. Due to the complexity of many of these problems, particularly those of large sizes encountered in most practical settings, meta heuristic algorithms are conspicuously preferable. These algorithms help us achieve optimal or near optimal solutions in large size applications with reasonable time. In this paper eight types of Genetic Algorithms (GA), Particle Swarm Optimization(PSO), Simulated Annealing(SA), Differential Evolution(DE) and Imperialist Competitive Algorithm (ICA) are applied in their basic frameworks for solving the mapping problem on two real core graphs Video Objective Plan Decoder and MPEG-4. The experimental results show the comparisons of these different meta heuristic algorithms with each other.

• Periodical: Advanced Materials Research (Volumes 403-408)
• Pages: 3994-4008
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.403-408.3994
• Online since: November 2011
• Authors: Majid Janidarmian, Atena Roshan Fekr
• Keywords: Differential Evolution, Genetic Algorithm (GA), Imperialist Competitive Algorithm, Mapping, Meta Heuristic Algorithms, Network-on-Chip (NoC), Particle Swarm Optimization Algorithm (PSO), Simulated Annealing (SA)

References

[1] A.V. De Mello, L.C. Ost, F.G. Moraes, N.L.V. Calazans, Evaluation of Routing Algorithms on Mesh Based NoCs, Faculdate Informatica Pucrs, Brazil, (2004).

[2] L. Benini, G. De Micheli, Network on Chips: A new SoC Paradigm, in the IEEE Computer, vol. 35, issue 1, Jan 2002, pp.70-78.

DOI: 10.1109/2.976921

[3] W.J. Dally and B. Towels, Route Packet, not Wires: on Chip Interconnection networks, " in the proceeding of design automation conference (DAC, 01), June 2001, PP. 684-689.

DOI: 10.1145/378239.379048

[4] S. Kmar, A. Jantsch, J.P. Soininen, M. Forsell, M. Millberg, J. Oberg, K. Tiensyrjs, and A. Hemani, a network on Chip Architecture and Design Methodology. " In the proceeding of the IEEE computer society annual symposium on VLSI (ISVLSI, 02), April 2002, PP. 105-112.

DOI: 10.1109/isvlsi.2002.1016885

[5] Saneei, M.;   Kakoee, M.R.;   Afzali-Kusha, A, COMRA: An efficient low-energy core mapping and routing path allocation algorithm for heterogeneous NoCs, Design and Test Workshop (IDT), 2009 4th International, Riyadh, Nov. 2009, PP. 1-6.

DOI: 10.1109/idt.2009.5404153

[6] J. C. Hu, Design Methodologies for Application Specific Network-onChip, PhD Thesis, Carnegie Mellon University, May. (2005).

[7] M. R. Garey, and D. S. Johnson, Computers and intractability: a guide to the theory of NP-completeness. Freeman and Company, (1979).

[8] Rafael Tomero, Juan M. Orduna, Maurizio Palesi, and Jose Duato, A Communication-Aware Task Mapping Technique, Parallel Processing Workshop, (2001).

[9] M. Janidarmian, A. Khademzadeh, M. Tavanpour, Onyx: A new heuristic bandwidth-constrained mapping of cores onto tile based Network on Chip, IEICE Electron. Express, Vol. 6, No. 1, pp.1-7, January (2009).

DOI: 10.1587/elex.6.1

[10] M. Gen, R. Cheng, Genetic Algorithm and Engineering Optimization, Copyright © 2000 John Wiley & Sons, Inc.

[11] Booker, L. Improving Search in genetic algorithms, in Davis, L., editor, Genetic Algorithms and Simulated Annealing, Morgan Kaufmann Publisher, San Francisco, (1987).

[12] Zhihua CUI, Xingjuan CAI, Jianchao ZENG, choatic performance-dependant particle swarm optimazation, International Journal of Innovative Computing, Information and Control (IJICIC) , Vol. 5, No. 4, pp.951-960, April (2009).

DOI: 10.1109/wcica.2004.1341974

[13] Franco Busetti, Simulated annealing overview.

[14] R. Storn, K. Price, Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, Volume 11, Issue 4, Sep. 1997, PP. 341-359.

DOI: 10.1023/a:1008202821328

[15] V. FEOKTISTOV, Differential Evolution in Search of Solutions, Springer, science + Business Media, (2006).

[16] E. Atashpaz Gargari, C. Lucas, Imperialist Competitive Algorithm: An Algorithm for Optimization Inspired by Imperialistic Competition, Evolutionary computation CEC2007, IEEE congress on , PP. 4661-4667.

DOI: 10.1109/cec.2007.4425083