基三众核架构中基于同步哈密顿环的无死锁策略  

Deadlock-Free Strategies Based on Synchronized Hamiltonian Ring in Triplet-Based Many-Core Architecture

作　　者：李春峰 Karim Soliman 计卫星 石峰[1] Li Chunfeng;Karim Soliman;Ji Weixing;Shi Feng(School of Computer Science&Technology,Beijing Institute of Technology,Beijing 100081;School of Artificial Intelligence,Beijing Normal University,Beijing 100875)

机构地区：[1]北京理工大学计算机学院,北京100081 [2]北京师范大学人工智能学院,北京100875

出　　处：《计算机研究与发展》2025年第4期930-949,共20页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60973010)。

摘　　要：确保片上网络(network-on-chip,NoC)中的数据传输无死锁,是NoC为多处理器片上系统(multi-processor system-on-chip,MPSoC)提供可靠通信服务的前提,决定了NoC甚至MPSoC的可用性.现有的通用防死锁策略难以发挥出特定拓扑结构的自身特点和优势,甚至可能会增加网络延迟、功耗以及硬件复杂性.另外,由于路由级和协议级死锁存在显著差异,现有无死锁方案较难同时解决这2类死锁问题,影响了MPSoC的可靠性.利用基三众核架构(triplet-based many-core architecture,TriBA)中拓扑结构自身具有的哈密顿特性提出了基于同步哈密顿环的无死锁策略,该策略依据拓扑结构自身的对称轴和哈密顿边对数据传输进行分类,预防了协议级死锁并提高了数据传输速度;同时使用循环链表技术判断同一缓冲区内数据同步传输方向,消除了路由级死锁并降低了数据传输延迟.在优化前瞻路由算法基础上,设计了基于同步哈密顿环的无死锁路由机制HamSPR(Hamiltonian shortest path routing).GEM5仿真结果表明,与TriBA现有方法相比,HamSPR在合成流量下的平均数据包延迟和功耗分别降低了8.78%~65.40%和6.94%~34.15%,吞吐量提高了8.00%~59.17%;在PARSEC测试集下的应用运行时间和平均数据包延迟分别最高实现了16.51%和42.75%的降低.与2D-Mesh架构相比,TriBA在PARSEC测试集下的应用性能实现了1%~10%的提升.Ensuring deadlock-free data transmission in the network-on-chip(NoC)is a prerequisite for providing reliable communication services for multi-processor system-on-chip(MPSoC),directly determining the availability of NoC and even MPSoC.Existing general-purpose deadlock-free strategies are oriented to arbitrary topologies,making it challenging to utilize the features and advantages of a specific topology.Moreover,these strategies may even increase network latency,power consumption,and hardware complexity.In addition,due to significant differences in the regular network between routing-level and protocol-level deadlocks,existing solutions struggle to simultaneously address both types of deadlock issues,affecting MPSoC reliability.We propose a deadlock-free strategy with synchronous Hamiltonian rings based on the inherent Hamiltonian characteristics of the triplet-based many-core architecture(TriBA).This method uses the topology’s symmetric axes and Hamiltonian edge to allocate independent store-and-forward buffers for data transmission,preventing protocol-level deadlocks and improving data transfer speed.Additionally,we design a directional determination method for data transmission within the same buffer using cyclic linked-list technology.This method ensures data independence and synchronous forward transmission,eliminates routing-level deadlocks,and reduces data transfer latency.Based on optimizing redundant calculations in look-ahead routing algorithms,we propose a deadlock-free routing mechanism called Hamiltonian shortest path routing(HamSPR)based on a synchronous Hamiltonian ring.GEM5 simulation results show that,compared with existing solutions in the TriBA,HamSPR reduces average packet latency and power consumption in synthetic traffic patterns by 18.78%−65.40%and 6.94%−34.15%,respectively,while improving throughput by 8.00%−59.17%.In the PARSEC benchmark,HamSPR achieves maximum reductions of 16.51%in application runtime and 42.75%in average packet latency,respectively.Moreover,compared with 2D-Mesh,

关 键 词：众核处理器 片上网络 基三众核架构 哈密顿特性 路由算法 死锁预防 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]