康子扬，彭凌辉，周 干，林 博，王 蕾

(国防科技大学计算机学院,湖南 长沙 410073)

1 引言

在摩尔定律[1]驱动下，单位面积芯片可承载的晶体管数量不断增多，计算机的计算能力与存储能力呈指数级上升。基于冯·诺依曼体系结构的处理器时钟频率和性能不断上升，但是存储器访问速度却增长缓慢，导致处理器与存储器之间的鸿沟越来越大，造成“存储墙”瓶颈。因此，亟需新的计算模式及其体系结构来满足日益增长的计算性能需求。

类脑计算[2]没有沿用经典的冯·诺依曼体系结构，而是从全新的角度出发，探索更高效的计算方法。类脑计算以脑科学研究为基础，参考人类大脑皮层神经细胞的工作机制，并将其映射为实际的物理器件。

脉冲神经网络SNN(Spiking Neural Network)[3]的提出让类脑处理器的计算模式上升到了一个新的高度。在20世纪90年代，神经生物学家们发现，神经元细胞的轴突会发射出一系列电脉冲，这些脉冲通过轴突传递给其它的神经元，其它神经元在接收到脉冲后，或是被抑制，或是被激活，被激活的神经元照此继续向下传递脉冲。大脑通过这些突发的电脉冲，让神经元细胞相互激活和抑制，进行着复杂信息的传递。这种采用脉冲进行信息传递的模式被发现后，脉冲神经网络的概念被提出。这种网络模式具有更真实的生物特性，并能更好地凸显人脑低功耗的特点。

大部分类脑处理器上运行的是SNN[4]。一个路由器节点下面会挂载一个神经元核，而一个神经元核里面会包含数千个神经元。我们将成千上万的神经元进行实际的物理硬件映射，将通信量大的神经元放在一起封装成神经元核，从而尽可能地增加核内通信，减少核间通信。但是，神经元核并不能包含太多的神经元，否则单核内的布局布线互连会成为问题。所以，核间通信仍然大量存在。

对于类脑处理器，当有神经元被触发后，会向所有与它连接的神经元发送脉冲报文，类脑处理器会花费若干个逻辑时钟去处理当前时间步产生的事件，将所有的脉冲发送到目标神经元核并完成相应的计算。图1为不同时间步下神经元的放电行为统计。可以看出SNN有着短时猝发的通信特点。在这些时间步内，大量的神经元同时发出脉冲，核间通信出现短时猝发激增情况，使片上网络短时间内发生拥塞。所以，如何快速解决短时猝发情况是类脑处理器的片上网络NoC(Network on Chip)[5]设计亟待解决的问题。

Figure 1 Discharge behavior of neurons at different time steps图1 不同时间步下神经元的放电行为

本文针对类脑计算由于短时、猝发而导致片上网络拥塞的情况，提出了基于哈密尔顿路径[6]的拥塞感知自适应路由算法。相对于没有拥塞感知的哈密尔顿最短路径算法，在数量猝发模式和概率猝发模式下，本文提出的拥塞感知路由算法使得片上网络NoC的平均延迟分别降低了13.9%和15.9%，吞吐率分别提高了21.6%和16.8%。

2 背景

2.1 片上网络

SoC(System on Chip)即片上系统[7]，它是信息系统核心的芯片集成，将系统关键部件集成在一块芯片上。这样不仅能更加充分地利用芯片的资源，而且还能缩短组件之间的连线，从而降低系统的延迟，提高系统的稳定性。

一个系统里有许多组件，这些组件称为处理单元PE(Processing Element)。以高性能处理器为例，PE不仅指处理器核，还包括片上其它组件,如IO接口和内存接口。任意2个PE均有可能通信，比如处理器核就一定会和内存进行通信。若每一个核都与内存接口互连，那么将会使用大量的资源去连线，这是极不合理的。为了使SoC高效互连，片上网络NoC的通信模式被提出。NoC是片上专门负责PE之间通信的组件，将系统中所有的组件都挂载在NoC上，PE间再根据不同的通信协议进行通信。这样的通信模式，能极大地优化布局布线和减少功耗。

2.2 片上网络的设计空间

基本的NoC设计空间[8]包括拓扑结构、路由算法、流控机制和路由器微体系结构设计。

常用的拓扑结构有环网、二维Mesh和二维Torus[9]等，图2为二维Mesh结构。网络的拓扑结构决定了网络节点的实际物理分布和节点间的连接关系。为了使芯片能更好地布局布线，结构规整的二维Mesh网络被广泛应用在多核领域。

Figure 2 2D Mesh network图2 二维Mesh网络结构

路由算法[10]是根据网络上数据包所携带的信息及当前路由器坐标信息，对数据包进行路由计算，得到下一跳的路径。路由算法必须与网络结构相适应，否则容易产生死锁。路由算法包括确定性路由和自适应路由。确定性路由中当前节点到目的节点的路径是确定的。如XY路由，在二维Mesh的XY路由算法下，数据包先进行X方向传输，当X方向匹配时再进行Y方向传输。XY路由存在的问题也很明显[11],在网络规模较大时，网络一旦拥堵，边缘和角落节点的吞吐率大大降低，网络的负载大部分由中部区域承担，从而增大了延迟，且降低了吞吐率。与确定性路由相比，自适应路由的路径选择则不是固定的[12]，算法会根据当前网络节点的状态进行路径选择，但会更容易出现死锁问题。

流控机制为数据包分配资源。常用的流控机制包括虚通道、存储转发和虫孔路由[13]。

路由器微体系结构直接决定了路由器节点所需要的资源、面积、功耗和延迟等。图3为一个简单的片上网络节点路由器结构，其组成包括5个输入端口缓冲(分别连接东南西北4个方向的路由器，以及本地PE)、交叉开关和输出端口等部件。

Figure 3 Router structure of NoC图3 片上网络路由器结构

网络拓扑结构一旦确定，其物理连接和物理实现便不能再改变。所以，更灵活的路由算法能够使网络在相同的拓扑结构、不同的应用场景下都能取得更好的性能，以最小的代价获得相对最大的收益。

2.3 哈密尔顿最短路径路由算法

哈密尔顿路径[14]对网络中的每个节点只访问一次。如图4所示，每个节点都会有唯一的坐标Rnum(x，y)。对于m×n的网络，会给每一个节点都分配一个编号num。对于每个节点的num，我们可以根据坐标(x，y)计算获得。若y为偶数，则num=x+y×n;若y为奇数，则num=(y+1)×n-x-1。

Figure 4 Node coordinates and Hamilton labels图4 节点坐标与哈密尔顿标签

在二维Mesh NoC中，任意2个路由节点之间存在通信需求，可以按照哈密尔顿路径传输数据包。与此同时，任意2个路由节点通过双向链路连接，可以同时相互传递信息。因此，根据每个路由节点的编号，我们将网络分成2个子网，即高通道子网H和低通道子网L。在高通道子网中，数据包沿着节点编号严格增大的方向进行传输。在低通道子网中，数据包沿着节点编号严格减小的方向进行传输。

图5a中,R2到R9经过的路径可以是(2-3-4-5-6-7-8-9)。此时能清楚地看到，这样的传输路径并不是最短路径。R2到R9一共走了7跳，在XY路由中，只需要3跳,即(2-1-6-9)，显然该传输方法的效果不尽人意。于是按最小路径的决策，并且依然按照num严格增大的规则，便产生了“捷径路径”。如图5b的最短路径中，从R2到R9，捷径路径是(2-5-6-9),同样是3跳，且没有打破num严格增大的规则。捷径路径并不唯一，比如从R1到R11，就有3条捷径路径，分别是(1-2-3-4-11)、(1-2-5-10-11)和(1-6-9-10-11),都是4跳。低通道子网L同理。

Figure 5 Two transmission paths in high channel subnet图5 高通道子网中的2种传输路径

对于捷径的选择，本文按照某一方式来选择。本文采用先进行列匹配，再进行行匹配的方法。仍以R1到R11为例，数据包先从R1横向传输到R3，再纵向传输到R11。值得注意的是，基于这样的最短路径选择方法，并没有将网络约束为单纯的XY路由。以R2到R6为例，其捷径路径为(2-5-6)，是先进行Y方向路由，再进行X方向路由。本文按照以上最短路径的策略来设计路由算法，比不走捷径的策略效果要好，而且不同于传统的XY路由。

2.4 死锁

死锁[15]是片上网络设计必须解决的问题。死锁的本质问题，就是依赖关系产生了环。如图6所示，各个节点分别向箭头所指节点发送请求。R0的资源释放取决于R1的资源释放，R1的资源释放取决于R2，R2的资源释放取决于R3,R3的资源释放取决于R0，依次形成环路。当前资源无法释放导致下一级资源无法释放，导致网络出现死锁。

Figure 6 Deadlock图6 死锁

3 拥塞感知路由算法

本文基于哈密尔顿单播路由算法，研究拥塞感知的路由算法，优化类脑处理器片上网络的通信性能。

最短路径策略的路由算法以捷径为优先，在所有节点猝发的情况下，网络会在短时间内陷入拥塞。所以，如何在拥塞的情况下高效地进行传输，是本文要解决的问题。

本文以拥塞感知[16]为出发点，当前节点路由器会感知自己相邻节点路由器的链路buffer是否空闲。如图7所示，当前节点会获得相邻节点输入FIFO的full信号。然后路由算法会根据4个相邻方向full信号的情况，实时选择下一跳出口。路由算法会在符合算法策略的前提下选择full信号为0的方向进行传输。

Figure 7 Congestion-aware mechanism图7 拥塞感知机制

本文提出的拥塞感知路由算法是在哈密尔顿最短路径路由算法基础上进行了优化。传统的哈密尔顿最短路径路由算法严格按照节点标签增加或减少的方向进行数据传输。当网络产生拥塞时，路由器不能进行传输方向调整，限制了NoC的性能。为了提升数据包的传输效率，本文对这一规则进行了优化，允许路由器在选择最短路径时，根据网络状态及时调整传输方向。本文在算法优化后选择的路径也是最短路径。

上述优化是指一个通道到另一个通道的单向通信，即高通道进入低通道或者低通道进入高通道。若2个通道之间可以互相进行传输，则会产生死锁。

因此，本文的算法优化采用的是从低通道进入高通道的优化方案。以图5中R10到R6为例，数据包在R10，数据包目的地为R6，若按照本文提到的先列匹配，再行匹配的哈密尔顿最短路径路由算法，路径将是(10-9-6)。加入拥塞检测优化后，R10将对通向R9和R5的链路进行比较，当R10西面方向拥塞时，便将数据包向北传输,然后再由R5传输到R6。(10-5-6)的路径打破了严格增大或减小的规则，但是不会死锁，后面将会进行证明。同理，从R6到R2，R6根据东面方向和北面方向拥塞情况进行选择。路径原本应该是(6-5-2)，当东面方向拥塞时，则向北方向传输到R1，再到R2。当网络面对拥塞时，为了提高链路利用率，降低延迟，选择将数据包跳转到另一个子网进行路由，以缓解当前子网压力。

当网络不拥塞时，路由算法按照节点标签增加或减少的方向传输数据。当网络出现拥塞时，数据包从低通道进入高通道进行传输，以缓解当前子网的通信压力。因此，当路由器接收到数据包后，它会根据路由器的坐标的奇偶行，选择不同的路由算法确定其传输方向，以避免路由死锁的出现。具体的算法实现如算法1和算法2所示。

算法1拥塞感知路由算法(偶数行)Routing_even

输入:(Cx,Cy), (Dx,Dy),eastfull,westfull,southfull,northfull。/*(Cx,Cy)为当前节点坐标;(Dx,Dy)为目的节点坐标;eastfull,westfull,southfull,northfull为buffer满信号*/

输出:Dout。

1:Δx=Dx-Cx,Δy=Dy-Cy;

2://当前处于偶数行

3:ifCy==0then

4:ifΔy> 0then

5:ifΔx< 0then

6:ifsouthfull==1 ANDwestfull==0then

7:Dout=WEST;

8:else

9:Dout=SOUTH;

10:endif;

11:endif;

12:ifΔx> 0then

13:Dout=EAST;

14:endif;

15:ifΔx==0then

16:Dout=SOUTH;

17:endif;

18:endif;

19:ifΔy== 0then

把两种根本对立的角色放在一起进行描述，对比鲜明，好坏鲜明，使读者很容易分辨出好坏、分辨是非、明确立场。运用这种手法，有利于充分展示双方的矛盾立场，突现事物的本质特征，加强文章的艺术效果和感染力，有效地传递了人物的情感特点，从而把感情抒发得淋漓尽致，凸显人物特点。

20:ifΔx< 0then

21:Dout=WEST;

22:endif;

23:ifΔx> 0then

24:Dout=EAST;

25:endif;

27:Dout=LOCAL;

28:endif;

29:endif;

30:ifΔy< 0then

31:ifΔx< 0then

32:ifwestfull==1 ANDnorthfull==0then

33:Dout=NORTH;

34:else

35:Dout=WEST;

36:endif;

37:else

38:Dout=NORTH;

39:endif;

40:endif;

41:endif

算法2拥塞感知路由算法(奇数行)Routing_odd

输入:(Cx,Cy), (Dx,Dy),eastfull,westfull,southfull,northfull。/*(Cx,Cy)为当前节点坐标；(Dx,Dy)为目的节点坐标;eastfull,westfull,southfull,northfull为buffer满信号*/

输出:Dout。

1:Δx=Dx-Cx,Δy=Dy-Cy；

2://当前处于奇数行

3:ifCy==0then

4:ifΔy> 0then

5:ifΔx> 0then

6:ifsouthfull==1 ANDeastfull==0then

7:Dout=EAST；

8:else

9:Dout=SOUTH；

10:endif；

11:endif；

12:ifΔx< 0then

13:Dout=WEST；

14:endif；

15:ifΔx==0then

16:Dout=SOUTH；

17:endif；

18:endif；

19:ifΔy== 0then

20:ifΔx< 0then

21:Dout=WEST；

22:endif；

23:ifΔx> 0then

24:Dout=EAST；

25:endif；

26:ifΔx== 0then

27:Dout=LOCAL；

28:endif；

29:endif；

30:ifΔy< 0then

31:ifΔx> 0then

32:ifeastfull==1 ANDnorthfull==0then

33:Dout=NORTH；

34:else

35:Dout=EAST；

36:endif；

37:else

38:Dout=NORTH；

39:endif；

40:endif；

41:endif

4 无死锁证明

本文通过证明通道依赖图CDG(Channel Dependence Graph)是无环的[17]来证明优化算法是无死锁的。首先，将相邻的2个节点构建成2个通道，如0号节点和1号节点构建的通道为(0,1)和(1,0)。然后,再根据本文算法判断相邻的通道间是否存在通道依赖。例如，路径(10-5-6)符合算法策略，则通道(10,5)和通道(5,6)存在通道依赖；路径(6-9-8)不符合算法策略，则通道(6,9)和通道(9,8)不存在通道依赖。最后统计出所有的通道依赖得到算法的CDG。本文以4×4规模NoC为例构造了所提算法的CDG,如图8所示。可以看出，通道依赖图是无环的，即表明本文所提算法无死锁。

Figure 8 Channel dependence graph图8 通道依赖图

5 实验与结果

本文为了验证提出的拥塞感知的哈密尔顿单播路由算法的可行性和有效性，采用Verilog HDL搭建网络，NoC的设置如表1所示。

Table 1 Experimental setup

为了更好地模拟类脑计算应用中的短时猝发情况，本文模拟2种发包情况。第1种情况是数量猝发模式，以单节点注入数量为变量;第2种情况是概率猝发模式，以单节点注入概率为变量。在16×16的NoC上，分别测得哈密尔顿最短路径路由算法和实现拥塞感知哈密尔顿路由算法的平均延迟和吞吐率。

图9和图10是第1种情况下每个节点连续、随机发送100～2 000个数据包得到的优化前后平均延迟和吞吐率的结果。

Figure 9 Average delay comparison under different packet numbers图9 不同数据包数量下平均延迟对比

Figure 10 Throughput comparison under different packet numbers图10 不同数据包数量下吞吐率对比

图11和12是第2种情况下每个节点分别以相同的概率随机发送数据包得到的优化前后平均延迟和吞吐率的结果。

Figure 11 Average delay comparison under different probability burst modes图11 不同概率猝发模式下平均延迟对比

Figure 12 Throughput comparison under different probability burst modes图12 不同概率猝发模式下吞吐率对比

从图9～图12可以看出，随着网络注入压力的增大，拥塞检测机制能够提高链路利用率，从而有效缓解网络压力，减少平均延迟，增大网络吞吐率。

6 结束语

本文针对类脑处理器的片上网络报文猝发问题，研究了类脑处理器的片上网络拥塞控制方法，并基于哈密尔顿最短路径路由算法，提出了一种实时拥塞感知、无死锁的哈密尔顿路由算法，在网络猝发、短时间内陷入拥堵时更好地缓解了网络压力，提升了网络性能。最后，通过Verilog HDL建模，实现了路由算法，通过行为级仿真，与没有拥塞感知的情况进行了对比。实验结果表明，加入拥塞感知对网络性能会有较大提升。本文的研究成果能够应用到类脑计算等通信量大、通信模式较为复杂的通信场景，具有广泛的应用前景。由于SNN具有一到多的通信特点，单播路由算法能力有限，因此，在未来的工作中，将设计并实现拥塞感知的多播哈密尔顿路由算法，以进一步提升类脑处理器片上网络的性能。