research-article

NoC Application Mapping Optimization Using Reinforcement Learning

Authors:

Samala Jagadheesh,

Soumya J.Authors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 27, Issue 6

Article No.: 55, Pages 1 - 16

https://doi.org/10.1145/3510381

Published: 27 June 2022 Publication History

Abstract

Application mapping is one of the early stage design processes aimed to improve the performance of Network-on-Chip. Mapping is an NP-hard problem. A massive amount of high-quality supervised data is required to solve the application mapping problem using traditional neural networks. In this article, a reinforcement learning–based neural framework is proposed to learn the heuristics of the application mapping problem. The proposed reinforcement learning–based mapping algorithm (RL-MAP) has actor and critic networks. The actor is a policy network, which provides mapping sequences. The critic network estimates the communication cost of these mapping sequences. The actor network updates the policy distribution in the direction suggested by the critic. The proposed RL-MAP is trained with unsupervised data to predict the permutations of the cores to minimize the overall communication cost. Further, the solutions are improved using the 2-opt local search algorithm. The performance of RL-MAP is compared with a few well-known heuristic algorithms, the Neural Mapping Algorithm (NMA) and message-passing neural network-pointer network-based genetic algorithm (MPN-GA). Results show that the communication cost and runtime of the RL-MAP improved considerably in comparison with the heuristic algorithms. The communication cost of the solutions generated by RL-MAP is nearly equal to MPN-GA and improved by 4.2% over NMA, while consuming less runtime.

References

[1]

Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio. 2017. Neural combinatorial optimization with reinforcement learning. arXiv abs/1611.09940. Retrieved from https://arxiv.org/abs/1611.09940.

[2]

L. Benini and G. De Micheli. 2002. Networks on chips: A new SoC paradigm. Computer 35, 1 (2002), 70–78. https://ieeexplore.ieee.org/document/976921/.

Digital Library

[3]

Navonil Chatterjee, Sheshivardhan Reddy, Shilpa Reddy, and Santanu Chattopadhyay. 2016. A reliability aware application mapping onto mesh -based network-on-chip. In Proceedings of the 3rd International Conference on Recent Advances in Information Technology (RAIT’16). 537–542. 10/gjskvr

[4]

Qingkun Chen, Wenjin Huang, Yuze Peng, and Yihua Huang. 2021. A reinforcement learning-based framework for solving the IP mapping problem. IEEE Trans. VLSI Syst. 29, 9 (2021), 1638–1651.

Digital Library

[5]

Q. Chen, W. Huang, Y. Zhang, and Y. Huang. 2020. An IP core mapping algorithm based on neural networks. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 29, 1 (2021), 189–202.

[6]

Michel Deudon, Pierre Cournut, Alexandre Lacoste, Yossiri Adulyasak, and Louis-Martin Rousseau. 2018. Learning heuristics for the TSP by policy gradient. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Willem-Jan van Hoeve (Ed.). Springer International Publishing, Cham, 170–181.

[7]

R. P. Dick, D. L. Rhodes, and W. Wolf. 1998. TGFF: Task graphs for free. In Proceedings of the 6th International Workshop on Hardware/Software Codesign (CODES/CASHE’98). 97–101. 10/bsqt2m

[8]

Sandeep D’souza, J. Soumya, and Santanu Chattopadhyay. 2015. A constructive heuristic for application mapping onto an express channel based network-on-chip. In Proceedings of the 19th International Symposium on VLSI Design and Test. 1–6. 10/gjsgdt

[9]

Matthias Englert, Heiko Röglin, and Berthold Vöcking. 2014. Worst case and probabilistic analysis of the 2-opt algorithm for the TSP. Algorithmica 68, 1 (2014), 190–264.

[10]

Juan Fang, Huan Zong, Haoyan Zhao, and Huayi Cai. 2019. Intelligent mapping method for power consumption and delay optimization based on heterogeneous NoC platform. Electronics 8, 8 (2019).

[11]

Max Farias, Edna Barros, Abel Filho, André Araújo, André Silva, and João Melo. 2013. An ant colony metaheuristic for energy aware application mapping on NoCs. In Proceedings of the IEEE 20th International Conference on Electronics, Circuits, and Systems (ICECS’13). 365–368.

[12]

Pavel Ghosh, Arunabha Sen, and Alexander Hall. 2009. Energy efficient application mapping to NoC processing elements operating at multiple voltage levels. In Proceedings of the 3rd ACM/IEEE International Symposium on Networks-on-Chip. 80–85. 10/dmq44m

Digital Library

[13]

Lei Guo, Yifan Ge, Weigang Hou, Pengxing Guo, Qing Cai, and Jingjing Wu. 2018. A novel IP-core mapping algorithm in reliable 3D optical network-on-chips. Optical Switching and Networking 27 (2018), 50–57.

Digital Library

[14]

Jingcao Hu and R. Marculescu. 200. Energy- and performance-aware mapping for regular NoC architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 24, 4 (2005), 551–562.

Digital Library

[15]

Sergey Ioffe and Christian Szegedy. 2015. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd International Conference on International Conference on Machine Learning (ICML’15). 448–456.

[16]

Diederik P. Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv:1412.6980. Retrieved from https://arxiv.org/abs/1412.6980.

[17]

Santanu Kundu and Santanu Chattopadhyay. 2008. Network-on-chip architecture design based on mesh-of-tree deterministic routing topology. International Journal of High Performance Systems Architecture 1, 3 (2008), 163–182.

Digital Library

[18]

Santanu Kundu, J. Soumya, and Santanu Chattopadhyay. 2012. Design and evaluation of mesh-of-tree based network-on-chip using virtual channel router. Microsyst 36, 6 (Aug 2012), 471–488.

Digital Library

[19]

C. Marcon, A. Borin, A. Susin, L. Carro, and F. Wagner. 2005. Time and energy efficient mapping of embedded applications onto NoCs. In Proceedings of the Asia and South Pacific Design Automation Conference (ASP-DAC’05), Vol. 1. 33–38.

[20]

Radu Marculescu, Jingcao Hu, and Umit Y. Ogras. 2005. Key research problems in NoC design: A holistic perspective. In Proceedings of the 3rd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS’05). 69–74. 10/cnkxvg

[21]

S. Murali and G. De Micheli. 2004. Bandwidth-constrained mapping of cores onto NoC architectures. In Automation and Test in Europe Conference and Exhibition Proceedings Design, Vol. 2. 896–901 Vol.2. 10/b45bpr

[22]

Pradip Kumar Sahu and Santanu Chattopadhyay. 2013. A survey on application mapping strategies for network-on-chip design. Journal of Systems Architecture 59, 1 (2013), 60–76.

Digital Library

[23]

Pradip Kumar Sahu, Tapan Shah, Kanchan Manna, and Santanu Chattopadhyay. 2014. Application mapping onto mesh-based network-on-chip using discrete particle swarm optimization. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 22, 2 (2014), 300–312.

Digital Library

[24]

Pradeep Kumar Sharma, Santosh Biswas, and Pinaki Mitra. 2019. Energy efficient heuristic application mapping for 2-D mesh-based network-on-chip. Microprocess. Microsyst. 64 (2019), 88–100.

[25]

K. Srinivasan, K. S. Chatha, and G. Konjevod. 2006. Linear-programming-based techniques for synthesis of network-on-chip architectures. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 14, 4 (2006), 407–420.

Digital Library

[26]

Suleyman Tosun, Ozcan Ozturk, and Meltem Ozen. 2009. An ILP formulation for application mapping onto network-on-chips. In Proceedings of the International Conference on Application of Information and Communication Technologies. IEEE, 1–5.

[27]

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS’17). Curran Associates Inc., Red Hook, NY, USA, 6000–6010.

[28]

Xinyu Wang, Tsan-Ming Choi, Xiaohang Yue, Mengji Zhang, and Wanyu Du. 2020. An effective optimization algorithm for application mapping in network-on-chip designs. IEEE Transactions on Industrial Electronics 67, 7 (2020), 5798–5809.

[29]

Xiaojun Wang, Feng Shi, and Hong Zhang. 2019. KLSAT: An application mapping algorithm based on kernighan-lin partition and simulated annealing for a specific WK-recursive noc architecture. In Proceedings of the 16th IFIP WG 10.3 International Conference on Network and Parallel Computing (NPC’19),Lecture Notes in Computer Science, Vol. 11783, Xiaoxin Tang, Quan Chen, Pradip Bose, Weiming Zheng, and Jean-Luc Gaudiot (Eds.). Springer, 31–42.

Digital Library

[30]

Ronald J. Williams. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach. Learn. 8, 3-4 (May 1992), 229–256.

Digital Library

[31]

Chen Wu, Chenchen Deng, Leibo Liu, Jie Han, Jiqiang Chen, Shouyi Yin, and Shaojun Wei. 2017. A multi-objective model oriented mapping approach for NoC-based computing systems. IEEE Transactions on Parallel and Distributed Systems 28, 3 (2017), 662–676.

Digital Library

[32]

Chen Wu, Chenchen Deng, Leibo Liu, Jie Han, Shouyi Chen, and Shaojun Wei. 2015. An efficient application mapping approach for the co-optimization of reliability, energy, and performance in reconfigurable noc architectures. IEEE Trans. Comput.-Aid. Des. Integr. Circ. Syst. 34, 8 (2015), 1264–1277.

Digital Library

[33]

Changqing Xu, Yi Liu, Peng Li, and YinTang Yang. 2018. Unified multi-objective mapping for network-on-chip using genetic-based hyper-heuristic algorithms. IET Computers & Digital Techniques 12, 4 (2018), 158–166.

[34]

Lei Yang, Weichen Liu, Weiwen Jiang, Mengquan Li, Juan Yi, and Edwin Hsing-Mean Sha. 2016. Application mapping and scheduling for network-on-chip-based multiprocessor system-on-chip with fine-grain communication optimization. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 24, 10 (2016), 3027–3040.

Digital Library

Cited By

Perumal DAlagarsamy AMahilmaran SCardarilli GKo S(2024)Probability-based mapping approach for an application-aware networks-on-chip architecturesNano Communication Networks10.1016/j.nancom.2024.10052641(100526)Online publication date: Sep-2024
https://doi.org/10.1016/j.nancom.2024.100526
Xu CShi XYang HWang Y(2024)3D network-on-chip data acquisition system mapping based on reinforcement learning and improved attention mechanismMicroelectronics Journal10.1016/j.mejo.2024.106323151(106323)Online publication date: Sep-2024
https://doi.org/10.1016/j.mejo.2024.106323
Asadi Y(2024)A comprehensive study and holistic review of empowering network-on-chip application mapping through machine learning techniquesDiscover Electronics10.1007/s44291-024-00027-w1:1Online publication date: 24-Oct-2024
https://doi.org/10.1007/s44291-024-00027-w
Show More Cited By

Index Terms

NoC Application Mapping Optimization Using Reinforcement Learning

Recommendations

Application mapping onto mesh-based network-on-chip using constructive heuristic algorithms

Application mapping is an important part of network-on-chip (NoC) design, it tries to map the application onto a NoC-based platform. Because mapping an application onto the mesh architecture is NP-hard, there is no known algorithm for solving this ...
Cluster-based application mapping method for Network-on-Chip

Network-on-Chip (NoC) is a newly introduced paradigm to overcome the communication problems of System-on-Chip architectures. Mapping applications onto mesh-based NoC architecture is an NP-hard problem and several heuristic methods have been presented to ...
Combining mapping and partitioning exploration for NoC-based embedded systems

Networks on Chip (NoC) have emerged as the key paradigm for designing a scalable communication infrastructure for future Systems on Chip (SoC). An important issue in NoC design is how to map an application on this architecture and how to determine the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 27, Issue 6

November 2022

285 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/3544939

Editor:
X. Sharon Hu
University of Notre Dame, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 27 June 2022

Online AM: 18 February 2022

Accepted: 01 January 2022

Revised: 01 November 2021

Received: 01 September 2021

Published in TODAES Volume 27, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

Indo-Austrian joint

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
950
Total Downloads

Downloads (Last 12 months)319
Downloads (Last 6 weeks)55

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Perumal DAlagarsamy AMahilmaran SCardarilli GKo S(2024)Probability-based mapping approach for an application-aware networks-on-chip architecturesNano Communication Networks10.1016/j.nancom.2024.10052641(100526)Online publication date: Sep-2024
https://doi.org/10.1016/j.nancom.2024.100526
Xu CShi XYang HWang Y(2024)3D network-on-chip data acquisition system mapping based on reinforcement learning and improved attention mechanismMicroelectronics Journal10.1016/j.mejo.2024.106323151(106323)Online publication date: Sep-2024
https://doi.org/10.1016/j.mejo.2024.106323
Asadi Y(2024)A comprehensive study and holistic review of empowering network-on-chip application mapping through machine learning techniquesDiscover Electronics10.1007/s44291-024-00027-w1:1Online publication date: 24-Oct-2024
https://doi.org/10.1007/s44291-024-00027-w
Srinivasan SBoutros AMahmoudi FBetz V(2023)Placement Optimization for NoC-Enhanced FPGAs2023 IEEE 31st Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)10.1109/FCCM57271.2023.00014(41-51)Online publication date: May-2023
https://doi.org/10.1109/FCCM57271.2023.00014
Saleem SHussain FAmin WAhmed RZikria YIshmanov FYu H(2023)A Survey on Dynamic Application Mapping Approaches for Real-Time Network-on-Chip-Based PlatformsIEEE Access10.1109/ACCESS.2023.332923311(122694-122721)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3329233
Choudhary JSudarsan CJ. S(2023)A performance-centric ML-based multi-application mapping technique for regular Network-on-ChipMemories - Materials, Devices, Circuits and Systems10.1016/j.memori.2023.1000594(100059)Online publication date: Jul-2023
https://doi.org/10.1016/j.memori.2023.100059
Raj RJoseph AH. AKalady SB. J(2023)SpecMap: An efficient spectral partitioning based static application mapping algorithm for 2D mesh NoCsConcurrency and Computation: Practice and Experience10.1002/cpe.783835:26Online publication date: 17-Jun-2023
https://doi.org/10.1002/cpe.7838
Shammasi MBaharloo MAbdollahi MBaniasadi A(2022)Turn-aware Application Mapping using Reinforcement Learning in Power Gating-enabled Network on Chip2022 IEEE 15th International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)10.1109/MCSoC57363.2022.00061(345-352)Online publication date: Dec-2022
https://doi.org/10.1109/MCSoC57363.2022.00061

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents