Improvement of Genetic Algorithm for Optimizing Routing and Power Consumption in Network on Chip

Document Type : Original Article

Authors

1 Faculty of Electrical Engineering, Sahand University of Technology (SUT), Tabriz, Iran

2 Faculty of Computer Science, University of the East, Manila, Philippines

3 Faculty of Electrical and Computer Engineering, Semnan University, Semnan, Iran

Abstract

Network on Chip (NoC) is a new structure that has attracted attention of researchers in electronics. Performance of routing in network on chip is an important task. Two problems are considered in this paper. First problem is finding an appropriate order for responsibilities of task graph. Position of tasks should be found on communication kip. Second problem is communicating and finding appropriate direction for NoC. Appropriate direction is a direction that contains minimum distance in mapped tasks and uses network bandwidth optimally. It also has less power consumption. In this paper, a combination of genetic algorithm (GA) and ant colony optimization (ACO) is utilized to map cores on NoC optimally. Also proposed algorithm is applied for finding directions on chip. Results show that proposed algorithm can do routing task in NoC well and decrease power consumption.

Keywords

References

Bjerregaard, T., & Mahadevan, S. (2006). A survey of research and practices of Network-on-chip. ACM Computing Surveys, 38(1), 1. doi:10.1145/1132952.1132953
Sahu, P. K., & Chattopadhyay, S. (2013). A survey on application mapping strategies for Network-on-Chip design. Journal of Systems Architecture, 59(1), 60–76. doi:10.1016/j.sysarc.2012.10.004
Mandelli, M., Amory, A., Ost, L., & Moraes, F. G. (2011). Multi-task dynamic mapping onto NoC-based MPSoCs. Proceedings of the 24th symposium on Integrated circuits and systems design - SBCCI ’11. Brazil. doi:10.1145/2020876.2020920
Weichslgartner, A., Wildermann, S., & Teich, J. (2011). Dynamic decentralized mapping of tree-structured applications on NoC architectures. Proceedings of the Fifth ACM/IEEE International Symposium on Networks-on-Chip - NOCS ’11. Pittsburgh, Pennsylvania. doi:10.1145/1999946.1999979
Ghosh, P., Sen, A., & Hall, A. (2009). Energy efficient application mapping to NoC processing elements operating at multiple voltage levels. 2009 3rd ACM/IEEE International Symposium on Networks-on-Chip. La Jolla, CA, USA. doi:10.1109/nocs.2009.5071448
Hu, J., & Marculescu, R. (2005). Energy-and performance-aware mapping for regular NoC architectures. IEEE Transactions on computer-aided design of integrated circuits and systems, 24(4), 551–562.
Lei, T., & Kumar, S. (2003). A two-step genetic algorithm for mapping task graphs to a network on chip architecture. Euromicro Symposium on Digital System Design, 2003. Proceedings. Belek-Antalya, Turkey. doi:10.1109/dsd.2003.1231923
Zhou, W., Zhang, Y., & Mao, Z. (2006). An application specific NoC mapping for optimized delay. In Design and Test of Integrated Systems in Nanoscale Technology. DTIS 2006. International Conference on (pp. 184–188). IEEE.
Ascia, G., Catania, V., & Palesi, M. (2004). Multi-objective mapping for mesh-based NoC architectures. Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis - CODES+ISSS ’04. Stockholm, Sweden. doi:10.1145/1016720.1016765
Jena, R. K., & Sharma, G. K. (2007). A multiobjective evolutionary algorithm-based optimisation model for network on chip synthesis. International journal of innovative computing and applications, 1(2), 121. doi:10.1504/ijica.2007.016793
Choudhary, N., Gaur, M. S., Laxmi, V., & Singh, V. (2011). GA based congestion aware topology generation for application specific NoC. 2011 Sixth IEEE International Symposium on Electronic Design, Test and Application. Queenstown, New Zealand. doi:10.1109/delta.2011.26
Sepúlveda, M. J., Chau, W. J., Gogniat, G., & Strum, M. (2012). A multi-objective adaptive immune algorithm for multi-application NoC mapping. Analog Integrated Circuits and Signal Processing, 73(3), 851–860. doi:10.1007/s10470-012-9869-9
Huida, L., Bingchen, F., Liheng, Y., & Yanan, L. (2012). RFID-based hazardous waste management platform establishment. Procedia Engineering, 29, 4–8. doi:10.1016/j.proeng.2011.12.658
He, T., & Guo, Y. (2013). Power consumption optimization and delay based on ant colony algorithm in network-on-chip. Engineering Review: Međunarodni časopis namijenjen publiciranju originalnih istraživanja s aspekta analize konstrukcija, materijala i novih tehnologija u području strojarstva, brodogradnje, temeljnih tehničkih znanosti, elektrotehnike, računarstva i građevinarstva, 33(3), 219-225.
Junior, L. S., Nedjah, N., & De Macedo Mourelle, L. (2013). Routing for applications in NoC using ACO-based algorithms. Applied Soft Computing, 13(5), 2224–2231.
Achballah, A. B., Othman, S. B., & Saoud, S. B. (2017). Problems and challenges of emerging technology networks− on− chip: A review. Microprocessors and Microsystems, 53, 1–20.
Transactions on Machine Intelligence
Volume 3, Issue 1
October 2020
Pages 14-22

Files

History

  • Receive Date: 20 May 2020
  • Revise Date: 10 June 2020
  • Accept Date: 22 August 2020

Share

How to cite

Statistics