Document Type : Original/Review Paper

Authors

Faculty of Computer Engineering, Shahrood University of Technology, Shahrood, Iran.

10.22044/jadm.2022.11518.2312

Abstract

With the advent of having many processor cores on a single chip in many-core processors, the demand for exploiting these on-chip resources to boost the performance of applications has been increased. Task mapping is the problem of mapping the application tasks on these processor cores to achieve lower latency and better performance. Many researches are focused on minimizing the path between the tasks that demand high bandwidth for communication. Although using these methods can result in lower latency, but at the same time, it is possible to create congestion in the network which lowers the network throughput. In this paper, a throughput-aware method is proposed that uses simulated annealing for task mapping. The method is checked on several real-world applications and simulations are conducted on a cycle-accurate network on chip simulator. The results illustrate that the proposed method can achieve higher throughput while maintaining the delay in the NoC.

Keywords

[1] P. Kansakar and A. Munir, “A design space exploration methodology for parameter optimization in multicore processors,” IEEE Transactions on Parallel and Distributed Systems, Vol. 29, No. 1, pp. 2–15, 2018.
 
[2] A. Balakrishnan and A. Naeemi, “Optimal global interconnects for networks-on-chip in many-core architectures,” IEEE Electron Device Letters, Vol. 31, No. 4, pp. 290–292, 2010.
 
[3] F. N. Sibai, “A two-dimensional low-diameter scalable on-chip network for interconnecting thousands of cores,” IEEE Transactions on Parallel and Distributed Systems, Vol. 23, No. 2, pp. 193–201, 2012.
 
[4] Y. Liu, S. Kato, and M. Edahiro, “Analysis of memory system of tiled many-core processors,” IEEE Access, Vol. 7, pp. 18964–18977, 2019.
 
[5] H. Jang et al., “Developing a multicore platform utilizing open risc-v cores,” IEEE Access, Vol. 9, pp. 120010–120023, 2021, doi: 10.1109/ACCESS.2021.3108475.
 
[6] A. Vijaya Bhaskar and T. Venkatesh, “Performance analysis of network-on-chip in many-core processors,” Journal of Parallel and Distributed Computing, Vol. 147, pp. 196–208, 2021.
 
[7] 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.
 
[8] M. J. Mohiz, N. K. Baloch, F. Hussain, S. Saleem, Y. B. Zikria, and H. Yu, “Application mapping using cuckoo search optimization with lévy flight for noc-based system,” IEEE Access, Vol. 9, pp. 141778–141789, 2021, doi: 10.1109/ACCESS.2021.3120079.
 
[9] P. Mazaheri Kalahroudi, E. Yaghoubi, and B. Barekatain, “IAM: An improved mapping on a 2-d network on chip to reduce communication cost and energy consumption,” Photonic Network Communications, Vol. 41, No. 1, pp. 78–92, Feb. 2021, doi: 10.1007/s11107-020-00911-x.
 
[10] W. Amin et al., “Performance evaluation of application mapping approaches for network-on-chip designs,” IEEE Access, Vol. 8, pp. 63607–63631, 2020, doi: 10.1109/ACCESS.2020.2982675.
 
[11] C. Marcon, A. Borin, A. Susin, L. Carro, and F. Wagner, “Time and energy efficient mapping of embedded applications onto nocs,” in Proceedings of the asp-dac 2005. asia and south pacific design automation conference, 2005, pp. 33–38. doi: 10.1109/ASPDAC.2005.1466125.
 
[12] 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 system design, 2003, pp. 180–187. doi: 10.1109/DSD.2003.1231923.
 
[13] W. Zhou, Y. Zhang, and Z. Mao, “An application specific noc mapping for optimized delay,” in International conference on design and test of integrated systems in nanoscale technology, 2006, pp. 184–188. doi: 10.1109/DTIS.2006.1708657.
 
[14] P. K. Sahu, P. Venkatesh, S. Gollapalli, and S. Chattopadhyay, “Application mapping onto mesh structured network-on-chip using particle swarm optimization,” in 2011 IEEE computer society annual symposium on VLSI, 2011, pp. 335–336. doi: 10.1109/ISVLSI.2011.21.
 
[15] I. Lang, N. Kapre, and R. Pellizzoni, “Worst-case latency analysis for the versal noc network packet switch,” in Proceedings of the 15th ieee/acm international symposium on networks-on-chip, 2021, pp. 55–60.
 
[16] E. Stergiou, “A study of multistage interconnection networks operating with wormhole routing and equipped with multi-lane storage,” International Journal of Parallel, Emergent and Distributed Systems, Vol. 36, No. 3, pp. 221–239, 2021.
 
[17] S. D. Chawade, M. A. Gaikwad, and R. M. Patrikar, “Review of xy routing algorithm for network-on-chip architecture,” International Journal of Computer Applications, Vol. 43, No. 21, pp. 975–8887, 2012.
 
[18] C. Chen and S. Cotofana, “Link bandwidth aware backtracking based dynamic task mapping in noc based mpsocs,” in Proceedings of the 2014 international workshop on network on chip architectures, 2014, pp. 5–10. doi: 10.1145/2685342.2685343.
 
[19] S. Tosun, O. Ozturk, and M. Ozen, “An ilp formulation for application mapping onto network-on-chips,” in 2009 international conference on application of information and communication technologies, 2009, pp. 1–5. doi: 10.1109/ICAICT.2009.5372524.
 
[20] S. Tosun, “Cluster-based application mapping method for network-on-chip,” Adv. Eng. Softw., Vol. 42, No. 10, pp. 868–874, Oct. 2011, doi: 10.1016/j.advengsoft.2011.06.005.
 
[21] S. D’souza, J. Soumya, and S. Chattopadhyay, “A constructive heuristic for application mapping onto an express channel based network-on-chip,” in 2015 19th international symposium on vlsi design and test, 2015, pp. 1–6. doi: 10.1109/ISVDAT.2015.7208147.
 
[22] E. Alikhah-Asl and M. Reshadi, “XY-axis and distance based noc mapping (xy-adb),” in 8th international symposium on telecommunications (ist), 2016, pp. 678–683. doi: 10.1109/ISTEL.2016.7881908.
 
[23] S. Murali and G. De Micheli, “Bandwidth-constrained mapping of cores onto noc architectures,” in Proceedings design, automation and test in Europe conference and exhibition, 2004, Vol. 2, pp. 896–901 Vol. 2. doi: 10.1109/DATE.2004.1269002.
 
[24] S. Khan, S. Anjum, U. A. Gulzari, F. Ishmanov, M. Palesi, and M. K. Afzal, “An optimized hybrid algorithm in term of energy and performance for mapping real time workloads on 2d based on-chip networks,” Applied Intelligence, Vol. 48, No. 12, pp. 4792–4804, Dec. 2018, doi: 10.1007/s10489-018-1246-7.
 
[25] S. Tosun, “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.
 
[26] P. K. Sahu, N. Shah, K. Manna, and S. Chattopadhyay, “A new application mapping algorithm for mesh based network-on-chip design,” in annual ieee india conference (indicon), 2010, pp. 1–4. doi: 10.1109/INDCON.2010.5712700.
 
[27] A. Tajary and E. Tahanian, “A routing-aware simulated annealing-based placement method in wireless network on chips,” Journal of AI and Data Mining, Vol. 8, No. 3, pp. 409–415, 2020, doi: 10.22044/jadm.2020.8964.2034.
 
[28] GNU Project, “GCC, the gnu compiler collection.” [Online]. Available: https://gcc.gnu.org/ (accessed Dec. 01, 2021).
 
[29] V. Catania, A. Mineo, S. Monteleone, M. Palesi, and D. Patti, “Improving the energy efficiency of wireless network on chip architectures through online selective buffers and receivers shutdown,” in 13th ieee annual consumer communications networking conference (ccnc), 2016, pp. 668–673. doi: 10.1109/CCNC.2016.7444860.
 
[30] Z. A. Khan, U. Abbasi, and S. W. Kim, “An efficient algorithm for mapping deep learning applications on the noc architecture,” Applied Sciences, Vol. 12, No. 6, 2022, doi: 10.3390/app12063163.
 
[31] G.-F. Fan, L.-Z. Zhang, M. Yu, W.-C. Hong, and S.-Q. Dong, “Applications of random forest in multivariable response surface for short-term load forecasting,” International Journal of Electrical Power & Energy Systems, Vol. 139, p. 108073, 2022.