面向非全互连3D NoC 的自适应单播路由算法

孙美东，刘勤让，刘冬培，燕昺昊

(国家数字交换系统工程技术研究中心，郑州450002)

(*通信作者电子邮箱137070845@qq．com)

0 引言

在3D集成系统中，使用垂直互连技术将多层晶片堆叠在一起［1］。因为硅通孔(Through Silicon Via，TSV)技术能提供最大的垂直互连密度和最小的层间距离，所以它是目前使用最普及的垂直互连技术［2］。虽然在集成系统中使用三维片上网络(three-Dimensional Network-on-Chip，3D NoC)架构可以提高网络性能，但TSV的使用仍面临3个问题:1)TSV的制造工艺还不够成熟，使得3D集成电路成品率较低［3］;2)在3D集成电路封装以及焊接TSV过程中，TSV可能出现短路导致故障［4］;3)相对于普通的2D水平链路，TSV有较大的面积消耗［5］。所以在保证正常通信的前提下，应使TSV的数量尽可能减少，这使得非全互连3D NoC架构得到广泛研究。

对于3D NoC，路由算法是十分关键的问题之一，前人在这一问题上已经作出相关的研究。如文献［6］提出LAFT(Look Ahead Fault Tolerant)算法，此算法分为三个阶段:第一阶段，读取微片(flit)，计算下一节点的地址;第二阶段，得到由故障模块发送的下一节点的故障信息并且获取其他三个方向的最短路径;第三阶段，做出路由方向的决定，其中最短路径的方向具有最高优先级。由于LAFT规定路径选择性为第二优先级，所以如果选取路径选择性多的方向，但此方向上的下一节点出现多处故障，此时会导致路径堵塞，使传输不能选择最短路径。针对上述现象，文献［7］提出HLAFT(Hybrid Look Ahead Fault Tolerant)算法，对于每一个到来的flit，该算法判断计算的方向是否导致路径堵塞。如果因为路径堵塞而选择非最短路径，则会根据当前节点和邻居节点的状态重新计算输出端口。HLAFT算法可以避免路径堵塞，然而只适用于全互连的3D NoC。DyXYZ(Dynamic XYZ)路由算法在X、Y、Z方向分别使用4、4、2个虚通道，将网络分成2个主网络，每个主网络又包含4个次网络［8］。因为每个次网络采用不同的虚通道，所以此算法不会死锁。当选择输出通道时，DyXYZ算法考虑输出方向上的缓存信息，进一步提高网络性能，但此算法同样也只适用于全互连的3D NoC架构且算法共采用10个虚通道，增加了网络的硬件开销。

文献［9］和文献［3］分别提出适用于非全互连不规则3D NoC架构的Elevator-First路由算法和路由器结构，该算法采用2个虚通道避免死锁。由于虚通道的使用过于耗费资源，文献［10］对Elevator-First算法进行改进，当选择“电梯”节点时，增加限制规则，使得不用虚通道就可以避免死锁。基于TSV上/下表的容错路由算法通过在每个路由器中添加TSV上/下表寻找最优的TSV进行层间传输;此外，为了高效地更新路由表，每个路由器会额外存储一张连接表［11］，但由于该算法中的TSV上/下表需要存储每层所有TSV的地址，且还要额外存储一张连接表，使得表开销过大，并且当扩大网络规模时，表的开销呈剧烈的增长。针对TSV上/下表开销过大的问题，低开销容错路由算法提出新的表策略，但此算法并未考虑垂直方向的拥塞信息［12］。因此，本文针对文献［11］表开销过大以及文献［12］出现的垂直拥塞问题，提出新的表结构和路由算法，该算法不仅能避让故障和拥塞节点，而且可以进行死锁恢复和免活锁，保证了有效的数据传输。

1 非全互连3D拓扑结构

非全互连3D拓扑结构层内采用2D mesh结构，且每层的规模相同，其与3D mesh结构不同的是TSV的分布是部分且随机的。该结构中具有两类路由器:三维路由器和平面路由器。含有TSV的路由器被称为三维路由器，具有7个端口，分别为本地、东、西、南、北、上、下方向的端口。其余的路由器称为平面路由器，具有五个端口，分别为本地、东、西、南、北方向的端口。上述的拓扑结构模型如图1所示，每个路由器的位置由三维笛卡尔坐标表示。

图1 非全互连3D拓扑模型Fig．1 Vertically partially connected 3D topology model

2 记录表的设计

在非全互连的3D NoC中，上/下层传输的数据包要选取最合适的垂直连接，所以记录垂直连接的位置信息显得尤为重要。本文与文献［11］和文献［12］中设计的表结构不同，此表将TSV上/下表整合到一个表中，不仅记录与当前路由器4个方向距离最近的TSV位置信息，也记录相邻节点的缓存占用和故障信息。在传输数据包时可以选择无故障且缓存占用少的端口，减少拥塞的情况和传输时间，提高网络性能。图1中(1，1，1)节点的记录表如表1所示。如果当前路由器连接的链路或路由器故障，在表中用信号0表示;如果可用，用信号1表示。本文设置路由器输入端口的缓存深度为8 flits。

表1 节点(1，1，1)存储的记录表Tab．1 Record table stored by node(1，1，1)

2．1 记录表的建立

记录表是由路由器发送广播数据包建立的，其中每个广播包会存储自身在网络中传输的跳数。表建立的过程分为两步:第一步是层间广播，由偶数层三维路由器向上/下层广播带有自身输入缓存占用信息的数据包，奇数层三维路由器收到数据包后会记录缓存信息同时向偶数层返回自身的输入缓存占用信息，此时三维路由器都具有邻近层的输入缓存占用信息。第二步是层内广播，三维路由器将缓存信息加入到数据包中向层内4个方向发送广播包，接收到的路由器会向其返回输入缓存信息。如果接收到的路由器记录表中没有TSV地址，则将包中的TSV地址和相应的缓存信息加入到记录表中;如果已有TSV地址，选择跳数比表中记录更小的广播包进行更新TSV地址和相应的缓存。为了减少数据包的重传，当收到两个相同的数据包会选择一个丢掉。

1) even layer 3D routers broadcast packets;

2) if(routers←packets) /*收到广播包*/

3) record and return buffer;

4) plane routers broadcast packets;

5) if(routers←packets)

6) record and return buffer;

7) if(record table is blank‖TSV address is smaller)

/*记录表的TSV地址为空或数据包中携带的TSV地址较小*/

8) update table;

9) end if

10) hop+1，broadcast packets;

/*广播包的跳数加1，继续向层内其他方向广播*/

11) end if

12) end if

2．2 记录表的更新

通常，三维片上网络系统中出现的故障分为短暂性故障和永久性故障［13］，当发生故障时，永久性故障相比短暂性故障会更大程度地影响系统性能，所以本文考虑的故障是永久性故障。在三维片上网络系统中出现的故障模型主要有以下两种:

1)路由器故障。三维路由器故障，如图1中的(3，3，1)路由器故障;平面路由器故障，如图1中的(2，1，1)路由器故障。

2)链路故障。层内链路故障，如图1中的(1，1，1)路由器西方向故障;层间链路故障，如图1中的(3，2，1)路由器下垂直连接故障。

当链路或路由器故障时，由检测到故障的路由器发送与建立记录表时相同的广播包进行记录表的更新。为达到增量更新减少更新开销，此过程只修改需要更新的表项。表更新过程与建立过程相似，这里不再赘述。

3 自适应单播路由算法

3D NoC中的路由算法是将数据包按照一定的路径从源节点准确无误地传输到目的节点，本文提出的层内和层间路由算法中主要符号和含义如表2所示。

表2 路由算法中主要符号及含义Tab．2 Main symbols and meanings in routing algorithm

3．1 层内路由算法

基于记录表中的信息，本文提出一种新的层内路由算法。首先根据当前节点和目的节点的地址确定最优方向，然后判断当前节点的故障信息，如最优方向故障则选取非最优方向，如果两个非最优方向的故障信息相同则进一步考虑端口的缓存信息，使得数据包可以选择无故障输出端口且避免拥塞。由于发生故障的连接会比发生拥塞的连接更易影响网络的性能，所以本文将判断故障信息的优先级设为最高，拥塞的优先级次之。

1) if(ΔX=0＆＆ ΔY=0)

2) local port←packet;

3) else if(ΔX=0)

4) N or S is available，N or S← packet;otherwise，check W and E;check W and E adjacent routers; /*N或S可用，选择相应端口;否则，检查W和E方向的故障，同时检查W和E可用方向邻近路由器的故障信息*/

5) if(one of W and E is faulty) /*两个方向其一故障*/

6) W or E←packet; /*选取无故障端口*/

7) else if(W and E are faulty)

8) N or S←packet; /*选择目标方向相反的端口*/

9) else(W and E aren’t faulty)

10) adjacent routers are available in target direction，less buffer W or E ← packet;otherwise，less faulty port← packet;/*两个邻近路由器在所需方向上可用，选择W或E缓存占用少的端口;两个邻近路由器在所需方向上故障不同，选择故障少的方向*/

11) else if(ΔY=0)

12) 处理方式同上;

13)else(ΔX≠0 ＆＆ ΔY≠0)

14) check 2 target direction and adiacent routers; /*检查与目标方向距离最近两个方向的故障信息，同时检查这两个方向邻近路由器的故障信息*/

15)if(one of them is faulty)

16) no faulty port←packet;

17)else if(they are faulty)

18) opposite port←packet;

19)else(they aren’t faulty)

20) adjacent routers are available， less buffer port← packet;otherwise， less faulty port← packet;

3．2 层间路由算法

当目的节点与源节点不在同层时，要先将数据包传输到目的节点层，然后再传输到目的节点。在层间传输时，选择最优的垂直连接是关键，所以在寻找最优垂直连接时，层间路由算法将拥塞和故障信息同时考虑。本文将目的节点映射到源节点所在层的节点称为映射节点。如果映射节点自身含有需要的TSV，那么选择此TSV进行传输;否则，根据映射节点的记录表，计算源节点与各个TSV的信息进而选择出最优的TSV，将数据包传输到邻近层，然后根据目的节点地址继续在层内传输。如果此层仍不是目的层，则采用同样的方法继续传输。源节点与各个TSV的信息计算方法为:

其中:dis表示源节点与映射节点记录表中各个TSV的距离，选择最小距离的TSV可以减少传输延时;interbuff表示TSV连接的邻近层路由器上/下输入端口的缓存占用信息，选择缓存占用最少的端口可以缓解网络的拥塞;Info值越小表示选择的TSV地址越优，可以作为最优的传输路径进行传输。

1) if(Zd＞Zc)

2) Xm=Xd;Ym=Yd;Zm=Zc;

3) if(M has TSV) /*映射节点含有需要的TSV*/

4) temporary address← TSV，inner-layer routing;/*选择此TSV，采用层内路由进行传输*/

5) else

6) calculate TSV，temporary address← TSV，inner-layer

routing;

7) else if(Zd＜Zc)

8) 处理方式同上;

9) else

10) intra-layer routing;

由上所述，本文提出的自适应单播路由算法在当前节点选择最佳的输出端口后，在接下来的路由器中循环执行判断逻辑，所以该算法的时间复杂度为O(N)，N为网络中每一维的节点数目。

3．3 死锁恢复与免活锁

在三维片上网络架构中采用自适应路由算法很可能会引起死锁。如图1 所示，当节点(1，0，1)向节点(1，0，0)发送数据包，同时节点(2，0，0)向节点(2，0，1)发送数据包，两条传输路径相互占用资源，形成死锁。本文采用RAB(Random-Access-Buffer)［7］进行死锁恢复。在没有死锁的情况下采用FIFO缓存管理机制，一旦检测到死锁，RAB会放弃缓存中正在执行的请求，寻找允许的请求进行缓存释放，进而打破死锁恢复网络状态。

因为本文考虑网络中的拥塞和故障信息，使得数据包在传输时，由于多次避免拥塞和故障的节点导致活锁现象发生。所以本文采用跳数限制避免活锁，具体方法是如果数据包记录的跳数超过设定的阈值，本文算法对路径的选择将只进行故障的判断，从而避免了活锁。

4 实验仿真

4．1 数据包设计

根据记录表中的内容和路由算法的特性，本文设计出对应的数据包结构，如图2所示。其中数据包分为两类:1)单播包，用来进行数据传输;2)广播包，用来建立和更新记录表。本文采用虫孔路由器，数据传输的最小单位是微片，微片大小为32 b。路由器根据前2 b进行头微片、体微片和尾微片的类型区分，其中头微片带有跳数和目的地址等信息，体微片和尾微片携带传输的数据。当网络出现故障时，及时更新记录表可以减少传输延时和功耗开销，所以用于更新记录表的广播包具有比单播包更高的优先级，因此用第3 b代表包的优先级(Pri):1代表高优先级;0代表低优先级。Temp字段为1代表数据包包含临时目的地址，Temp为0代表数据包包含真实目的地址。Hop字段记录数据包在网络中传输的跳数，大小为7 b。Xd、Yd、Zd分别代表目的地址的X、Y、Z轴坐标，因为设定拓扑结构为32×32×32，所以每一维的坐标需要用5 b表示。其中Hop和坐标地址所需的位数根据拓扑结构大小而相应地改变。Ext字段可供以后进行扩展来使用。

图2 数据包结构Fig．2 Packet structure

4．2 性能仿真分析

本文采用台湾大学开发的Access Noxim开源仿真器进行网络性能仿真，它将 Noxim和 HopSpot结合，使得 Access Noxim支持网络模型、功率模型和热模型的3D NoC仿真。

为了说明算法的性能，实验将算法应用到不同规模的网络结构，并且采用了两种流量模型进行目的地址的选择。由于文献［9］和文献［11］使用两个虚通道避免死锁，为了实验的公平起见，本实验使用RAB死锁恢复机制代替虚通道。

表3 实验参数设置Tab．3 Setting of experimental parameters

4．2．1 网络平均延时

在不同的数据包注入率下，4种算法在不同网络规模下的平均延时如图3和图4所示。单个数据包的延时是指数据包的头微片进入网络到目的节点接收尾微片的这段时间。平均延时是指多个数据包延时的平均值。数据包注入率是指每个IP核在每个时钟周期下向网络中注入数据包的速度。

在Random流量模型下，由于本文考虑到各输入端口的缓存占用信息，在传输数据包时会判断选择最优路径，所以在注入率较低时，平均延时高于文献［9］和文献［11］的算法。但在两种网络规模下，当注入率分别大于0．028和0．02时，由于文献［9］和文献［11］算法只考虑水平和垂直连接的故障，导致拥塞的情况发生，所以平均延时高于本文算法。文献［12］和本文的平均延时情况很接近，原因是它也同样考虑了层内缓存占用信息。

图3 4×4×4网络规模下的平均延时Fig．3 Average delay under 4×4×4 network size

图4 6×6×6网络规模下的平均延时Fig．4 Average delay under 6×6×6 network size

在Shuffle流量模型下，文献［9］和文献［11］算法在 4×4×4网络规模并且注入率大于0．015时，平均延时均高于本文算法。文献［12］算法在注入率小于0．016时依旧与本文有着接近的平均延时，但在注入率大于0．016后，平均延时高于本文。这是因为Shuffle流量模型以层间传输数据包为主，本文额外考虑了垂直方向的缓存占用信息，当注入过多的数据包时，可以减少层间传输的拥塞情况，使得平均延时低于文献［12］算法。6×6×6网络规模下的情况与上述类似，但因为网络规模的增加，所有算法的平均延时都有所增加。

4．2．2 网络吞吐率

吞吐率是指网络接收或发送消息的速率，实验以flit为网络中基本传输单位，所以吞吐率的大小可以用每个节点在每个时钟周期下传输的flit数量来衡量。吞吐率的理论计算公式如下:

其中:Throughput指网络吞吐率，吞吐率越高表明网络可以处理的数据包越多;Nrouter指网络中节点的数量，与网络规模有关;T指实验的仿真时间;PN指在T时间内成功到达目的节点的数据包总数;Lengthi指第i个数据包的大小(包含flit的数量)。

图5和图6为在两种网络规模下4种算法的吞吐率比较。

图5 4×4×4网络规模下的吞吐率Fig．5 Throughput under 4×4×4 network size

可以看出随着注入率的增加，本文算法比文献［9］、文献［11］和文献［12］算法都有优势，在Random流量模型下本文算法的优势并不明显，但在Shuffle流量模型下本文的吞吐率较其他三个算法有明显的优势。其原因是各节点的缓存使用率随着数据包注入率的增加而逐渐提高，对于以层间数据包传输为主的Shuffle流量模型，本文算法不会因为避让故障而导致某一层或某一节点发生拥塞。

另外由于文献［9］算法选择的TSV地址直接从寄存器中读取，当存储的TSV发生故障，即便有可用的TSV也无法进行层间传输，导致网络提前趋于饱和，在两种流量模型下的吞吐率均低于其他三个算法。

4．2．3 可靠性

数据包的丢弃是因为传输路径中的TSV故障或网络中的资源不足，因此可以用丢包率衡量算法的可靠性。本文计算了两种网络规模下算法的丢包率，结果如图7所示。

图6 6×6×6网络规模下的吞吐率Fig．6 Throughput under 6×6×6 network size

图7 两种网络规模下的丢包率Fig．7 Rate of losing packet under two network sizes

文献［12］和文献［11］算法由于没考虑垂直方向的缓存，当层间传输发生拥塞时，便会丢弃数据包。文献［9］算法在传输数据包时静态地选择TSV，所以当TSV发生故障，文献［9］算法不得不丢弃数据包，而且随着故障率的增加，数据包的丢弃变得越来越频繁。本文算法通过综合考虑记录表中的信息，躲避了故障的连接并缓解了拥塞的情况，在故障率为5%时，两种网络模型下的丢包率分别为2．4%和2．8%;在故障率为50%时，丢包率分别为25．5%和29．5%。

4．3 记录表的开销分析

根据本文记录表的结构，保存记录表所需寄存器大小的计算公式如下:

其中:Regbit表示寄存器的大小;fault表示链路或路由器是否故障，需要1 b;intrabuff表示层内邻节点缓存占用信息;interbuff已在式(1)中介绍;本文设置缓存深度为8 flit，所以intrabuff和interbuff均需要3 b;pc表示节点的坐标信息;hop表示当前节点到TSV的跳数，其中根据网络规模的不同，pc和hop需要的位数也不同。

表4给出了具体网络规模下保存记录表所需的硬件开销。在层内网络规模为N×N时，文献［11］的硬件开销为2N2;文献［12］的硬件开销为24 lb N+8;本文的硬件开销为24 lb N+48。由上述可知，随着网络规模的增加，文献［11］的表开销呈剧烈的增长，而文献［12］和本文的表开销增长缓慢。

表4 记录表的硬件开销Tab．4 Hardware overhead of record table

5 结语

本文主要针对非全互连3D NoC的拓扑结构提出基于记录表的自适应单播路由算法。该表不仅记录了TSV的位置信息也记录了缓存占用和故障信息，而且在较大的网络规模下比文献［11］算法的表开销要小得多;仿真实验结果表明，本文算法的可靠性优于其他三个算法，并且在平均延时和吞吐率性能指标上均有一定的优势。尤其在Shuffle流量模型下，当注入率高于0．02时，本文算法的网络还没有达到饱和，而其他两个算法的网络趋于饱和状态。当层内网络规模小于8×8时，本文算法的表开销过大，这是本文算法的不足。为了进一步提高非全互连3D NoC的网络性能，表结构的优化以及非全互连3D NoC的多播路由算法都是以后需要解决的问题。