一种用于片上网络的拥塞感知哈密尔顿最短路径路由算法

A congestion-aware Hamilton shortest pathrouting algorithm for network on chip

类脑处理器能够支持多种脉冲神经网络SNN的部署来完成多种任务。片上网络NoC能够用较少的资源和功耗解决片上复杂的互连通信问题。现有的类脑处理器多采用片上网络来连接多个神经元核,以支持神经元之间的通信。SNN在时间步内瞬时突发的通信会在短时间内产生大量的脉冲报文。在这种通信行为下,片上网络会在短时间内达到饱和,造成网络拥塞。片上网络中非拥塞感知路由算法会进一步加剧网络拥塞状态,如何在每一个时间步内有效处理这些数据包,从而降低网络延迟,提高吞吐率,成为了目前需要解决的问题。首先对SNN的瞬时猝发通信特性进行了分析;然后提出一种拥塞感知的哈密尔顿路径路由算法,以降低NoC平均延迟和提高吞吐率;最后,使用Verilog HDL实现该路由算法,并通过模拟仿真进行性能评估。在网络规模为16×16的2D Mesh结构的片上网络中,相对于没有拥塞感知的路由算法,在数量猝发模式和概率猝发模式下,所提出的拥塞感知路由算法的NoC平均延迟分别降低了13.9%和15.9%;吞吐率分别提高了21.6%和16.8%。

Spiking neural networks(SNN)can be deployed on neuromorphic processors to complete various tasks.Network on Chip(NoC)can solve the complex interconnection and communication problems with less resources and power consumption.NoC is widely adopted in neuromorphic processors to support communication between neurons.The instantaneous burst communication patten of SNN gene-rates a large number of spikes at each time step.At this time,NoC reaches its saturation rapidly,causing network congestion.Meanwhile,non-congestion-aware routing algorithms further aggravates the congestion state of NoC.How to effectively process these spikes at each timestep,reduce the delay of the network,and increase the throughput has become the problem we need to solve at present.The paper first analyzes the instantaneous burst communication characteristics of SNN.Then,a congestion-aware Hamilton path routing algorithm with the shortest path length is proposed to reduce the average latency and increase the throughput of NoC.Finally,the routing algorithm is implemented in Verilog HDL,and performance evaluation is conducted by simulation.The results show that,compared with the non-congestion-aware routing algorithms,the proposal reduces the average delay by 13.9%and 15.9%respectively,and increases the throughput by 21.6%and 16.8%,respectively under the two experimental scenarios(different packet count,and different packet inject rate)in a 16×162D mesh NoC.