This paper proposes a multiobjective application mapping technique targeted for large-scale network-on-chip (NoC). As the number of intellectual property (IP) cores in multiprocessor system-on-chip (MPSoC) increases, NoC application mapping to find optimum core-to-topology mapping becomes more challenging. Besides, the conflicting cost and performance trade-off makes multiobjective application mapping techniques even more complex. This paper proposes an application mapping technique that incorporates domain knowledge into genetic algorithm (GA). The initial population of GA is initialized with network partitioning (NP) while the crossover operator is guided with knowledge on communication demands. NP reduces the large-scale application mapping complexity and provides GA with a potential mapping search space. The proposed genetic operator is compared with state-of-the-art genetic operators in terms of solution quality. In this work, multiobjective optimization of energy and thermal-balance is considered. Through simulation, knowledge-based initial mapping shows significant improvement in Pareto front compared to random initial mapping that is widely used. The proposed knowledge-based crossover also shows better Pareto front compared to state-of-the-art knowledge-based crossover. 1. Introduction The advancement in submicron technology allows more intellectual property (IP) cores to be integrated into a single chip which increases the system complexity. Multiprocessor system-on-chip (MPSoC) size will increase from several cores to hundreds of cores per chip in the future. Current on-chip communication architectures that utilize bus sharing or hierarchical bus architecture will become the performance bottleneck with the increasing number of cores. Implementation of large MPSoC needs more flexible communication resources. Network-on-chip (NoC) has emerged as a new communication architecture that provides modularity and flexibility for MPSoC. NoC architectures are based on traditional interconnection network concepts [1]. Each IP core is connected to one of the routers on the NoC network and messages are forwarded through routers to destination cores. However, a handful of NoC-based system design problems are still under research. The problems have been identified and categorized in [2]. A major challenge in NoC design is the placement of IP cores to the associated routers on the network. Application mapping determines the placement of IP cores to routers in the network such that the performance or cost metrics of interest are optimized [2]. In this paper, it
References
[1]
S. Tosun, “Cluster-based application mapping method for Network-on-Chip,” Advances in Engineering Software, vol. 42, no. 10, pp. 868–874, 2011.
[2]
R. Marculescu, U. Y. Ogras, L. Peh, N. E. Jerger, and Y. Hoskote, “Outstanding research problems in NoC design: system, microarchitecture, and circuit perspectives,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, no. 1, pp. 3–21, 2009.
[3]
B. Yang, L. Guang, T. Sntti, and J. Plosila, “Parameter-optimized simulated annealing for application mapping on Networks-on-Chip,” in Learning and Intelligent Optimization, Y. Hamadi and M. Schoenauer, Eds., Lecture Notes in Computer Science, pp. 307–322, Springer, Berlin, Germany, 2012.
[4]
C. Radu and L. Vintan, “Domain-knowledge optimized simulated annealing for Network-on-Chip application mapping,” in Advances in Intelligent Control Systems and Computer Science, L. Dumitrache, Ed., vol. 187 of Advances in Intelligent Systems and Computing, pp. 473–487, Springer, Berlin, Germany, 2013.
[5]
C. Radu, M. S. Mahbub, and L. Vin？an, “Developing domain-knowledge evolutionary algorithms for network-on-chip application mapping,” Microprocessors and Microsystems, vol. 37, no. 1, pp. 65–78, 2013.
[6]
M. Arjomand, S. H. Amiri, and H. Sarbazi-Azad, “Efficient genetic based topological mapping using analytical models for on-chip networks,” Journal of Computer and System Sciences, vol. 79, no. 4, pp. 492–513, 2013.
[7]
P. K. Sahu, T. Shah, K. Manna, and S. Chattopadhyay, “Application mapping onto mesh-based Network-on-Chip using discrete particle swarm optimization,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 22, no. 2, pp. 300–312, 2014.
[8]
B. Kazimipour, X. Li, and A. K. Qin, “Initialization methods for large scale global optimization,” in Proceedings of the IEEE Congress on Evolutionary Computation (CEC '13), pp. 2750–2757, June 2013.
[9]
C. Radu, Optimized algorithms for Network-on-Chip application mapping [Ph.D. thesis], University of Sibiu, 2011.
[10]
E. B. van der Tol and E. G. T. Jaspers, “Mapping of MPEG-4 decoding on a flexible architecture platform,” in Media Processors 2002, Proceedings of SPIE, pp. 1–13, San Jose, Calif, USA, January 2002.
[11]
P. K. Sahu and S. Chattopadhyay, “A survey on application mapping strategies for Network-on-Chip design,” Journal of Systems Architecture, vol. 59, no. 1, pp. 60–76, 2013.
[12]
J. Hu and R. Marculescu, “Energy-aware mapping for tile-based NoC architectures under performance constraints,” in Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC '03), pp. 233–239, IEEE, January 2003.
[13]
S. Murali and G. De Micheli, “Bandwidth-constrained mapping of cores onto NoC architectures,” in Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, pp. 896–901, February 2004.
[14]
C. Marcon, E. Moreno, N. Calazans, and F. Moraes, “Comparison of network-on-chip mapping algorithms targeting low energy consumption,” IET Computers and Digital Techniques, vol. 2, no. 6, pp. 471–482, 2008.
[15]
Z. Lu, L. Xia, and A. Jantsch, “Cluster-based simulated annealing for mapping cores onto 2D mesh networks on chip,” in Proceedings of the 11th IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems (DDECS '08), pp. 1–6, Bratislava, Slovakia, April 2008.
[16]
Z. Song, Y. Dou, M. Zheng, and W. Xu, “A quick method for mapping cores onto 2D-mesh based networks on chip,” in Computer Engineering and Technology, L. Xiao, P. Lu, J. Li, and C. Zhang, Eds., vol. 337 of Communications in Computer and Information Science, pp. 173–184, Springer, Berlin, Germany, 2013.
[17]
P. K. Sahu, N. Shah, K. Manna, and S. Chattopadhyay, “A new application mapping algorithm for mesh based network-on-chip design,” in Proceedings of the Annual IEEE India Conference (INDICON '10), pp. 1–4, Kolkata, India, December 2010.
[18]
A. A. Morgan, H. Elmiligi, M. W. EI-Kharashi, and F. Gebali, “Multi-objective optimization of NoC standard architectures using Genetic Algorithms,” in Proceedings of the 10th IEEE International Symposium on Signal Processing and Information Technology (ISSPIT '10), pp. 85–90, December 2010.
[19]
S. G. Ficici, “Multiobjective optimization and coevolution,” in Multi-Objective Problem Solving from Nature: From Concepts to Applications, J. Knowles, D. Corne, and K. Deb, Eds., Springer, New York, NY, USA, 2007.
[20]
G. Ascia, V. Catania, and M. Palesi, “Multi-objective mapping for mesh-based NoC architectures,” in Proceedings of the 2nd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS '04), pp. 182–187, September 2004.
[21]
A. A. Morgan, Networks-on-Chip: modeling, system-level abstraction, and application-specific architecture customization [Ph.D. thesis], University of Victoria, 2011.
[22]
R. K. Jena and G. K. Sharma, “Application mapping of mesh based-NoC using multi-objective genetic algorithm,” International Journal of Computers and Applications, vol. 30, no. 1, pp. 17–22, 2008.
[23]
N. Nedjah, M. Silva, and L. Macedo Mourelle, “Evolutionary IP mapping for efficient NoC -based system design using multi-objective optimization,” in Innovative Computing Methods and Their Applications to Engineering Problems, N. Nedjah, L. Santos Coelho, V. Mariani, and L. Macedo Mourelle, Eds., vol. 357 of Studies in Computational Intelligence, pp. 105–129, Springer, Berlin, Germany, 2011.
[24]
W. Jang and D. Pan, “A3MAP: architecture-aware analytic mapping for networks-on-chip,” in Proceedings of the 15th Asia and South Pacific Design Automation Conference (ASP-DAC '10), pp. 523–528, Taipei, Taiwan, January 2010.
[25]
H. Lin, L. Zhang, D. Tong, X. Li, and X. Cheng, “A fast hierarchical multi-objective mapping approach for mesh-based networks-on-chip,” Acta Scientiarum Naturalium Universitatis Pekinensis, vol. 44, no. 5, pp. 711–720, 2008.
[26]
A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing, Springer, 2003.
[27]
B. Hendrickson and R. Leland, The Chaco User’s Guide Version 2.0, 1995.
[28]
H. Maaranen, K. Miettinen, and A. Penttinen, “On initial populations of a genetic algorithm for continuous optimization problems,” Journal of Global Optimization, vol. 37, no. 3, pp. 405–436, 2007.
[29]
K. Skadron, M. R. Stan, K. Sankaranarayanan, W. Huang, S. Velusamy, and D. Tarjan, “Temperature-aware microarchitecture: modeling and implementation,” ACM Transactions on Architecture and Code Optimization, vol. 1, no. 1, pp. 94–125, 2004.
[30]
W. Liu, J. Xu, X. Wu et al., “A NoC traffic suite based on real applications,” in Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI '11), pp. 66–71, July 2011.
[31]
G. Karypis and V. Kumar, “Multilevel k-way hypergraph partitioning,” in Proceedings of the 36th Annual ACM/IEEE Design Automation Conference (DAC '99), pp. 343–348, New York, NY, USA, June 1999.
