Abstract Network-on-Chip (NoC) presents the interesting approaches to organize complex communications in many systems. NoC can also be used as one of the effective solutions to cover the existing problems in System-on-Chip (SoC) such as scalability and reusability. The most common topology used in NoC is mesh topology. However, offering the mapping algorithm for mapping applications, based on weighted task graphs, onto the mesh is known as a NP-hard problem. This paper presents an effective algorithm called ‘Boundary Mapping Algorithm’ (BMA), in terms of decreasing the priority of low weighted edges in the task graph to improved performance in the NoCs. A low complexity mapping algorithm cannot present the optimal mapping results for all applications. Then, adding an optimization phase to mapping algorithms can have a positive impact on their performance. So, this study presents an optimization phase based on Cellular Learning Automata to achieve this goal. For the evaluation mapping algorithm and optimization phase, we compared the BMA method with Integer Linear Programming (ILP), Nmap, CastNet and Onyx methods for six real applications. The mapping results indicated that the proposed algorithm can be useful for some applications. Also, optimization phase can be useful for the proposed and other mapping algorithms.

References

[1] Beigy H. and Meybodi M., “Asynchronous Cellular Learning Automata,” Automatica, vol. 44, no. 5, pp. 1350-1357, 2008.

[2] Beigy H. and Meybodi M., “A Mathematical Framework for Cellular Learning Automata,” Advances in Complex Systems, vol. 07, no. 3-4, 2004.

[3] Beigy H. and Meybodi M., “Open Synchronous Cellular Learning Automata,” Advances in Complex Systems, vol. 10, no. 4, pp. 527-556, 2007.

[4] Benini L. and Micheli G., “Networks on Chips: a New Soc Paradigm,” Computer, vol. 35, no. 1, pp. 70-78, 2002.

[5] FathyNavid A. and Bagheriaghababa A., Cellular Learning Automata and its Applications, IntechOpen, 2013.

[6] Garey M. and Johnson D., Computers and Intractability: A Guide to the Theory of NP- Completeness, W.H. Freeman and Co, 1979.

[7] Hu J. and Marculescu R., “Exploiting The Routing Flexibility for Energy/Performance Aware Mapping of Regular Noc Architectures,” in Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, Munich, pp. 688-693, 2003.

[8] Ijaz S., Munir E., Anwar W., and Nasir W., “Efficient Scheduling Strategy for Task Graphs in Heterogeneous Computing Environment,” The International Arab Journal of Information Technology, vol. 10, no. 5, pp. 486-492, 2013.

[9] Janidarmian M., Khademzadeh A., and Tvanpour M., “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, 2009.

[10] Moein-darbari F., Khademzade A., and Gharooni-fard G., “CGMAP: A New Approach to Network-on-Chip Mapping Problem,” IEICE Electron Express, vol. 6, no. 1, pp. 27-34, 2009.

[11] Murali S. and Micheli G., “Bandwidth- Constrained Mapping of Cores onto Noc Architectures,” in Proceedings Design, Automation and Test in Europe Conference and Exhibition, Paris, pp. 896-901, 2004.

[12] Pasricha S. and Dutt N., On-Chip Communication Architectures: System on Chip Interconnect, Morgan Kaufmann, 2008.

[13] Sahu P. and Chattopadhyay S., “A Survey on Application Mapping Strategies for Network-on- Chip Design,” Journal Systems Architecture, vol. 59, no.1, pp. 60-76, 2013.

[14] Srinivasan K., Chatha K., and Konjevod G., “Linear-Programming-Based Techniques for Synthesis of Network-on-Chip Architectures,” IEEE Transactions on Very Large Scale Integration Systems, vol. 14, no. 4, pp. 407-420, 2006.

[15] Stensgaard M. Sparso J., “ReNoC: A Network- on-Chip Architecture with Reconfigurable Topology,” in Proceedings of the 2nd ACM/IEEE International Symposium on Networks-on-Chip, Newcastle upon Tyne, pp. 55-64, 2008.

[16] Tosun S., Ozturk O., and Ozen M., “An ILP Formulation for Application Mapping onto Network-on-Chip,” in Proceedings of International Conference on Application of Information and Communication Technologies, Baku, pp . 1-5, 2009.

[17] Tosun S., “Cluster-Based Application Mapping Method for Network-on-Chip,” Advances in Engineering Software, vol. 42, no. 10, pp. 868- 874, 2011.

[18] Tosun S., “New Heuristic Algorithms for Energy Aware Application Mapping and Routing on Mesh-Based Nocs,” Journal of Systems Architecture, vol. 57, no. 1, pp. 69-78, 2011.

[19] Wolfram S., “Cellular Automata,” Los Alamos Science, vol. 9, pp. 2-21, 1983.

[20] Wolfram S., “Universality and Complexity in Cellular Automata,” Physica D: Nonlinear Phenomena, vol. 10, no. 1-2, pp. 1-35, 1984. 322 The International Arab Journal of Information Technology, Vol. 16, No. 2, March 2019 Mohammad Keley was born in Dezful. He received hir B.Sc. degree in Computer Engineering from Islamic Azad University, Dezfoul branch, Iran in 2003, and his M.Sc. degree in Computer Architecture Engineering from Science and Research Islamic Azad University, Tehran, Iran, in 2006. His research interests include design and analysis of reliable, fault tolerant and mapping in Network-on-Chips and 3- Dimentional Network-on-Chip interconnections. Ahmad Khademzadeh was born in Mashhad, Iran, in 1943. He received the B.Sc. degree in applied physics from Ferdowsi University, Mashhad, Iran, in 1969 and the M.Sc., Ph.D. degrees respectively in Digital Communication and Information Theory & Error Control Coding from the University of Kent, Canterbury, UK. He is currently the Head of Education & National Scientific and International Scientific Cooperation Department at ICT Research Institute (ITRC). He was the head of Test Engineering Group and the director of Computer and Communication Department at ITRC. He is also a lecturer at Tehran Universities & he is a committee member of the Iranian Electrical Engineering Conference Permanent Committee. Dr. Khadem-Zadeh has been received four distinguished national and international awards including Kharazmi International Award, and has been selected as the National outstanding researcher of the Iran Ministry of Information and Communication Technology. Mehdi Hosseinzadeh was born in Dezful in 1981. He received his B.Sc. degree in Computer Hardware Engineering from Islamic Azad University, Dezful branch, Iran in 2003. He also received his M.Sc. and Ph.D. degrees in Computer System Architecture from the Science and Research Branch, Islamic Azad University, Tehran, Iran in 2005 and 2008, respectively. He is currently an assistant professor in Department of Computer Engineering of Science and Research Branch of Islamic Azad University, Tehran, Iran. His research interests are computer arithmetic with emphasis on residue number system, cryptography, network security and e-commerce.