An Analytical Latency Estimation Approach in a Mesh Network in a Distributed Memory System on Chip
Abstract
We present an analytical latency model for a mesh Network-on-Chip with distributed memory in a system-on-chip, in which routers are modeled as M/M/1/N queues. The model accounts for collision probabilities arising at routing, at virtual-channel (VC) arbitration, and during wormhole transfer, and internal buffer-overflow probabilities. It supports comparison of routing schemes, number of VCs, buffer depth, and packet size, guiding early-stage decisions. Accuracy is validated against a cycle-accurate simulator: the error stays within 5% up to saturation while achieving ~100× speedup. Results are interpretable via decomposition of latency into contributions of input and output router buffers and into components associated with request and response traffic. Applying the model to routing, packet sizing, and capacity parameters yields three findings: (i) ADOR outperforms DOR due to the routing algorithm itself rather than added capacity (confirmed under equal hardware resources); (ii) packet-based transfer outperforms single-payload transfer, with an optimal packet size (two flits in our experiments); and (iii) when scaling capacity, increasing the number of VCs is more effective than increasing buffer depth.
Full Text:
PDF (Russian)References
Peccerillo, Biagio, et al. "A survey on hardware accelerators: Taxonomy, trends, challenges, and perspectives." Journal of Systems Architecture 129 (2022): 102561.
McKee, Sally A. "Reflections on the memory wall." Proceedings of the 1st conference on Computing frontiers. 2004.
Chen, Xiaowen. Efficient Memory Access and Synchronization in NoC-based Many-core Processors. Diss. KTH Royal Institute of Technology, 2019.
Gholami, Amir, et al. "Ai and memory wall." IEEE Micro 44.3 (2024): 33-39.
Milton, Jonathan, and Payman Zarkesh-Ha. "Impacts of topology and bandwidth on distributed shared memory systems." Computers 12.4 (2023): 86.
Jain, Arpit, et al. "Smart Communication Using 2D and 3D Mesh Network-on-Chip." Intelligent Automation & Soft Computing 34.3 (2022).
Kiasari, Abbas Eslami, Zhonghai Lu, and Axel Jantsch. "An analytical latency model for networks-on-chip." IEEE Transactions on Very Large Scale Integration (VLSI) Systems 21.1 (2012): 113-123.
Thomas, Marlin U. "Queueing systems. volume 1: Theory (leonard kleinrock)." SIAM Review 18.3 (1976): 512-514.
Lallas, Efthymios N. "An Evaluation of Routing Algorithms in Traffic Engineering and Quality of Service Provision of Network on Chips." Engineering 13.1 (2021): 1-17.
Khaidukov, Danila, and Alexandr Alekseev. "Routing Collision Mitigation Approaches in a Distributed Memory System on Chip". Nanoindustiya [Nanoindustry] 11s 18.135 (2025): 1298-1304.
Kavaldjiev, Nikolay, and Gerard JM Smit. "A survey of efficient on-chip communications for soc." (2003).
Uma, R., H. Sarojadevi, and V. Sanju. "Routing of flits in parallel input interface scenario in a generalized network-on-chip framework using wormhole flow control algorithm." Emerging Research in Computing, Information, Communication and Applications: ERCICA 2020, Volume 2. Singapore: Springer Singapore, 2021. 679-693.
Dananjayan, P., and Karunakar Reddy Vanga. "Low Latency NoC Switch using Modified Distributed Round Robin Arbiter." Journal of Engineering Science & Technology Review 14.3 (2021).
Kermani, Parviz, and Leonard Kleinrock. "Virtual cut-through: A new computer communication switching technique." Computer Networks (1976) 3.4 (1979): 267-286.
Duato, Jose, et al. "A comparison of router architectures for virtual cut-through and wormhole switching in a NOW environment." Journal of Parallel and Distributed Computing 61.2 (2001): 224-253.
Wang, Peng, et al. "A comprehensive comparison between virtual cut-through and wormhole routers for cache coherent Network on-Chips." IEICE Electronics Express 11.14 (2014): 20140496-20140496.
Tedesco, Leonel P., Ney Calazans, and Fernando Moraes. "Buffer sizing for multimedia flows in packet-switching NoCs." Journal of Integrated Circuits and Systems 3.1 (2008): 46-56.
Jin, Depeng, et al. "Evaluation and analysis of packet-length effect on networks-on-chip." Tsinghua Science & Technology 15.3 (2010): 288-293.
Zhou, Xinbing, Peng Hao, and Dake Liu. "Pccnoc: Packet connected circuit as network on chip for high throughput and low latency socs." Micromachines 14.3 (2023): 501.
Hao, Peng, et al. "PaCHNOC: Packet and Circuit Hybrid Switching NoC for Real-Time Parallel Stream Signal Processing." Micromachines 15.3 (2024): 304.
Liu, Shaoteng, Axel Jantsch, and Zhonghai Lu. "Analysis and evaluation of circuit switched NoC and packet switched NoC." 2013 Euromicro Conference on Digital System Design. IEEE, 2013.
Ghidini, Yan, et al. "Buffer depth and traffic influence on 3D NoCs performance." 2012 23rd IEEE International Symposium on Rapid System Prototyping (RSP). IEEE, 2012.
Parepalli, Ramanamma, Sanjeev Shama, and Mohan Kumar Naik. "Bufferless NoC router design for optical networks-on-chip." Journal of Optical Communications 0 (2024).
Mirza-Aghatabar, Mohammad, et al. "An empirical investigation of mesh and torus NoC topologies under different routing algorithms and traffic models." 10th Euromicro conference on digital system design architectures, methods and tools (DSD 2007). IEEE, 2007.
Nadi, M., M. H. Ghadiry, and M. K. Dermany. "The effect of number of virtual channel on NOC EDP." Journal of applied mathematics & informatics 2010 (2010): 539-551.
Rezazad, Mostafa, and Hamid Sarbazi-Azad. "The effect of virtual channel organization on the performance of interconnection networks." 19th IEEE international parallel and distributed processing symposium. IEEE, 2005.
Nicopoulos, Chrysostomos A., et al. "ViChaR: A dynamic virtual channel regulator for network-on-chip routers." 2006 39th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO'06). IEEE, 2006.
Shim, Keun Sup, et al. "Static virtual channel allocation in oblivious routing." 2009 3rd ACM/IEEE International Symposium on Networks-on-Chip. IEEE, 2009.
Fernandes, Ramon, et al. "OcNoC: Efficient one-cycle router implementation for 3d mesh network-on-chip." 2015 28th International Conference on VLSI Design. IEEE, 2015.
Poluri, Pavan, and Ahmed Louri. "An improved router design for reliable on-chip networks." 2014 IEEE 28th International Parallel and Distributed Processing Symposium. IEEE, 2014.
Papaphilippou, Philippos, and Thiem Van Chu. "Efficient deadlock avoidance for 2-D mesh NoCs that use OQ or VOQ routers." IEEE Transactions on Computers 73.5 (2024): 1414-1426.
Rao, Supriya, et al. "Vix: Virtual input crossbar for efficient switch allocation." Proceedings of the 51st Annual Design Automation Conference. 2014.
Seo, Daeho, et al. "Near-optimal worst-case throughput routing for two-dimensional mesh networks." 32nd International Symposium on Computer Architecture (ISCA'05). IEEE, 2005.
Shi, Zheng, and Alan Burns. "Real-time communication analysis for on-chip networks with wormhole switching." Second ACM/IEEE International Symposium on Networks-on-Chip (nocs 2008). IEEE, 2008.
Nikitin, Nikita, and Jordi Cortadella. "A performance analytical model for network-on-chip with constant service time routers." Proceedings of the 2009 International Conference on Computer-Aided Design. 2009.
Lai, Mingche, et al. "An accurate and efficient performance analysis approach based on queuing model for network on chip." Proceedings of the 2009 International Conference on Computer-Aided Design. 2009.
Ogras, Umit Y., Paul Bogdan, and Radu Marculescu. "An analytical approach for network-on-chip performance analysis." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 29.12 (2010): 2001-2013.
Qian, Zhiliang, et al. "A comprehensive and accurate latency model for network-on-chip performance analysis." 2014 19th Asia and South Pacific Design Automation Conference (ASP-DAC). IEEE, 2014.
Cohen, Itamar, Ori Rottenstreich, and Isaac Keslassy. "Statistical approach to networks-on-chip." IEEE Transactions on Computers 59.6 (2010): 748-761.
Matoussi, Oumaima. "Noc performance model for efficient network latency estimation." 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE). IEEE, 2021.
Mandal, Sumit K., et al. "Analytical performance models for NoCs with multiple priority traffic classes." ACM Transactions on Embedded Computing Systems (TECS) 18.5s (2019): 1-21.
Ben-Itzhak, Yaniv, Israel Cidon, and Avinoam Kolodny. "Delay analysis of wormhole based heterogeneous NoC." Proceedings of the Fifth ACM/IEEE International Symposium on Networks-on-Chip. 2011.
Bhattacharya, Debajit, and Niraj K. Jha. "Analytical modeling of the SMART NoC." IEEE Transactions on Multi-Scale Computing Systems 3.4 (2017): 242-254.
Levitin, Lev B., and Yelena Rykalova. "An analytical model for virtual cut-through routing." 2019 28th International Conference on Computer Communication and Networks (ICCCN). IEEE, 2019.
Qian, Zhi-Liang, et al. "A support vector regression (SVR)-based latency model for network-on-chip (NoC) architectures." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 35.3 (2015): 471-484.
Zhang, Xiaoyun, et al. "A survey of machine learning for Network-on-Chips." Journal of Parallel and Distributed Computing 186 (2024): 104778.
Catania, Vincenzo, et al. "Noxim: An open, extensible and cycle-accurate network on chip simulator." 2015 IEEE 26th international conference on application-specific systems, architectures and processors (ASAP). IEEE, 2015.
Refbacks
- There are currently no refbacks.
Abava Кибербезопасность ИТ конгресс СНЭ
ISSN: 2307-8162