随着集成电路技术的飞速发展，系统规模越来越大，时钟频率越来越高.传统总线时钟和功耗方面的问题越来越难以解决.片上网络(network-on-chip，NoC)可以很好地解决这些问题，已逐渐成为片上多核的标准通信架构.目前大多数片上网络采用同步通信机制，网络节点间的通信采用单一时钟驱动.只有少量片上网络采用异步通信机制，网络节点间的通信由局部握手协议控制.对异步片上网络的研究相对落后于同步片上网络，主要是由于异步电路设计较为复杂，且缺少成熟的工具支持[1].然而，这并不影响研究异步片上网络的重要性.异步片上网络与同步片上网络相比具有很多优势：异步电路无时钟偏斜、模块化程度高、功耗低、电磁兼容性强等[2,3].按国际半导体技术发展路线图估计，到2024年，49 % 的片上全局信号将由异步电路传递[4].
目前，典型的异步片上网络主要有：文献[5]提出的GALS (globally asynchronous and locally synchronous) NoC SpiNNaker是用于实时仿真生物神经网络的众核计算系统，采用树型拓扑结构.文献[6]提出异步片上网络ASPIN，采用全定制版图设计，路由器结构简单，适用于二维网状网拓扑结构.文献[7]提出的异步片上网络ANOC，使用虚拟通道VC(virtual channel).然而，已发表的异步NoC，大多数采用确定性路由算法(如源路由，X-Y路由)[7,8]，当发生阻塞时，可能会出现路由资源的浪费，而且会降低数据传输的效率.
针对确定性路由算法在异步片上网络实现中遇到的问题，本文提出了一种针对2D-Torus异步片上网络的自适应路由算法AA-XY路由算法(asynchronous adaptive X-Y routing algorithm). 该路由算法不再被动地执行路由策略，而是通过对路由环境中阻塞信息的监控，结合“最短路径策略”，动态地调整下一跳的路由节点，尽可能规避阻塞严重或出现故障的路由节点，减小路由延迟.在当前路由节点进行路由计算前，检测需要传输方向的局部阻塞信号，优先选择状态为空闲的路由节点.
1 AA-XY算法描述为解释算法，假设源节点为S(x_s,y_s)，目的节点为D(x_dst,y_dst)，当前节点为C(x,y)；路由开始时，C(x,y)=S(x_s,y_s)，同时每个路由节点具有9个方位，分别为E(东)，S(南)，W(西)，N(北)，O(本地)，NE(东北)，SE(东南)，SW(西南)，NW(西北)，如图1所示.
 |
图 1 2D-Torus结构异步NoC中节点方位示意图
Fig. 1 The diagram of the node positions in 2D-Torus asynchronous NoC |
2D-Torus结构异步片上网络的每行每列路由节点首尾相接，形成一个环形的结构，其路由方位并不是单纯的坐标上的大小关系.对于一个4×4的异步2D-Torus片上网络，假定(0,0)节点在网络的左下角，(3,3)节点在网络的右上角.算法中，等距离情况下优先判断为东/北方向的路径.即目的节点在x方向从东侧和从西侧距离当前节点的长度相同时，会优先判断为东向路径，y方向同理.
路由算法执行过程如下：
1) 若y_dst=y，x_dst=x，说明目标节点即为当前节点，路由计算模块会将数据发送到当前节点的本地端口O.
2) 若y_dst=y，x_dst=x-1，说明目标节点是当前节点的W方向第一个，此时路由节点路由计算模块将发送控制信息，将数据发送到西向输出端口W.
3) 若y_dst=y，x_dst=(x+1)或(x+2)，说明目标节点在当前的E方向，此时路由节点路由计算模块将发送控制信息，将数据发送到东向输出端口E.
4) 若y_dst=y-1，x_dst=x，说明目的节点是当前节点的S方向第一个，此时路由节点路由计算模块将发送控制信息，将数据发送到南向输出端口S.
5) 若y_dst=y-1，x_dst=x-1，说明目的节点在当前节点的SW方向，此时路由节点路由计算模块需要判断W方向和S方向输出路径的阻塞情况.阻塞情况由传输方向上的局部阻塞信号full给出，若W方向阻塞(full_W=1)而S方向不阻塞(full_S=0)，则路由计算模块发送控制信息，将数据发送到S方向输出端口；否则，发送数据到W方向输出端口.
6) 若y_dst=y-1，x_dst=(x+1)或(x+2)，说明目的节点是当前节点的SE方向，此时路由节点路由计算模块需要判断E方向和S方向的输出路径的阻塞情况，若E方向阻塞(full_E=1)而S方向不阻塞(full_S=0)，则路由计算模块发送控制信息，将数据发送到S方向输出端口；否则，发送数据到E方向输出端口.
7) 若y_dst=(y+1)或(y+2)，x_dst=x，说明目的节点是当前节点的N方向，路由计算模块发送控制信息，将数据发送到北向输出端口N.
8) 若y_dst=(y+1)或(y+2)，x_dst=x-1，说明目的节点是当前节点的NW方向，此时路由节点路由计算模块需要判断W方向和N方向输出路径的阻塞情况，若W方向阻塞(full_W=1)而N方向不阻塞(full_N=0)，则路由计算模块发送控制信息，将数据发送到N方向输出端口；否则，发送数据到W方向输出端口.
9) 若y_dst=(y+1)或(y+2)，x_dst=(x+1)或(x+2)，说明目的节点是当前节点的NE方向，此时路由节点路由计算模块需要判断E方向和N方向的输出路径的阻塞情况，若E方向阻塞(full_E=1)而N方向不阻塞(full_N=0)，则路由计算模块发送控制信息，将数据发送到N方向输出端口；否则，发送数据到E方向输出端口.
2 基于AA-XY算法的异步片上网络为了测试AA-XY算法的有效性，搭建基于AA-XY算法的异步片上网络.采用异步电路设计方法学，利用Petri网和异步有限状态机[9]进行电路的建模与设计.
2.1 路由节点设计本文研究的片上网络拓扑结构是4×4节点的2D-Torus结构，每个路由节点分为五个端口：北/东/南/西/本地(N/E/S/W/O)，各个端口的结构类似，都可以分为输入部分和输出部分.输入部分包含五个模块：输入端port_in、数据接收模块receiver、海明码解码模块ham_decode、路由计算模块analysis和交叉开关模块 split.输出部分包含四个模块：数据仲裁模块arbiter、海明码编码模块ham_encode、数据发送模块send和输出端port_out.其中海明码编解码模块，用于对传输的数据检错纠错.各个模块以端口名+模块名/输入端名/输出端名进行命名，例如西向端口的数据接收模块命名为Wreceiver，本地端口的输出端命名为Oport_out.
通过对路由节点进行数据流分析，并根据AA-XY路由算法和所选拓扑结构，对路由节点内部结构进行Petri网建模来描述允许的接口行为.文中列举西向端口和本地端口通信时的Petri网模型，具体如图2所示.
 |
图 2 异步NoC路由节点内部数据Petri网
Fig. 2 The Petri net model of the asynchronous NoC routing node |
由图2可知，在初始状态中，Wport_in准备好接收外部来的数据，节点内没有数据进行传输，每个变迁(Wreceiver/Wham_decode等)的前置集的库所都没有大于或等于1的标志.若变迁Wport_in的使能有效，则从节点外部接收数据到Wport_in的后置库所中；这时Wreceiver的前置集的库所中有为1的标志，Wreceiver使能有效，将前置集中的数据传输到后置集；依次下去，当Wsplit变迁使能有效时，会根据信息中携带的控制信息将数据发送到相应的输出端口的数据仲裁端口(本例中：Oarbiter)，经过变迁Oham_encode、Osend，发送到本地输出端口Oport_out.
2.2 路由计算模块设计路由计算模块analysis是异步片上网络功能的核心模块，用以实现路由算法.使用异步有限状态机的猝发模式(burst mode,BM)[10]来设计analysis模块，状态转换图如图3所示.
 |
图 3 路由计算模块状态转换图 Fig. 3 The state transition chart of the routing module |
BM机包含七个状态：
1) S0准备状态，复位后状态机进入此状态，等待由数据解码模块发送的数据请求信号req的来临.当该请求信号req有效，即req从低电平变为高电平后，将返回到数据解码模块的回应信号ack置为有效，即ack置为高电平，状态机转向数据接收状态S1.
2) S1数据接收状态，将数据缓存到路由计算模块analysis中，等待从数据解码模块发送的数据请求信号req置为无效，即req置为低电平.若该数据请求信号req从高电平变为低电平，将返回到数据解码模块的回应信号ack置为无效，即ack置为低电平，状态机转向信息存储状态S2.
3) S2信息存储状态，将从数据解码模块接收的数据中携带的目的地址信息、节点当前各个端口的数据传输状态、邻节点阻塞状态等信息进行锁存.为保证数据存储的正常进行，将保持S2状态至存储工作的完成，存储工作的时间取决于计算电路的最长路径长度，需要根据具体的电路设定S2保持的时间t_S2.S2保持时间达到t_S2(状态图中表示为cnt_t1由低电平变为高电平)后，状态机转向位移信息计算状态S3.
4) S3位移信息计算状态，根据S2状态中存储的地址信息计算数据传输的目的节点与当前节点间的位移信息.为保证信息计算的正常进行，将保持S3状态至信息计算的完成，信息计算工作的时间取决于计算电路的最长路径长度，需要根据具体的电路设定S3保持的时间t_S3.S3保持时间达到t_S3 (状态图中表示为cnt_t2由低电平变为高电平)后，状态机转向路由计算状态S4.
5) S4路由计算状态，根据路由位移信息、当前节点相应输出通道的状态和相邻节点的阻塞信息，使用AA-XY维序算法进行路由计算.为保证路由计算的正常进行，将保持S4状态至路由计算工作的完成，路由计算工作时间取决于计算电路的最长路径长度，需要根据具体的电路设定S4的保持时间t_S4.S4持续时间达到t_S4 (状态图中表示为cnt_t3+)后，状态机转向S5状态.
6) S5数据发送状态，若交叉开关模块的数据回应信号ack_data和控制信息回应信号ack_ctrl都为低电平，将路由计算后的有效数据和控制信息同时发送到交叉开关模块，同时将向交叉开关模块发送的数据请求信号req_data和控制信息请求信号req_ctrl置为高电平，状态机转向结束状态S6.
7) S6结束状态，等待交叉开关模块的数据回应信号ack_data和控制信息回应信号ack_ctrl都有效，若检测到该回应信号都为高电平，将向交叉开关模块发送的数据请求信号req_data和控制信息请求信号req_ctrl都置为低电平，本模块发送端的数据清零，状态机回到状态S0.
2.3 异步片上网络设计为了验证AA-XY路由算法，将16个异步路由节点以2D-Torus拓扑结构连接成异步片上网络，总体结构如图4所示.RPU为路由节点挂载的计算单元.
 |
图 4 2D-Torus结构异步NoC Fig. 4 The 2D-Torus asynchronous NoC |
该异步片上网路采用System Verilog语言，在Modelsim 10.0上实现并测试.
3.1 AA-XY算法测试及结果分析根据AA-XY算法，每个路由节点都会将东南西北四个方向输入端口的阻塞情况反馈给相邻节点，邻节点根据阻塞信息和本节点内数据需要输出路径上的阻塞情况决定路由方向.
测试中，连续的数据0x063cf6从西向输入端口进入路由节点，解码后得到原数据0x8e76.根据AA-XY算法，数据需要向东向节点发送.为了模拟阻塞情况，仿真时将东向节点的回应信号Eack_b置低，这样东向输出端口的数据发送模块接收不到有效的回应信号，会一直处于S3状态，不会返回S0状态，后续的数据也就没法进入Esend模块.依次下去，Eham_encode和Earbiter也会保持在结束状态，不会回到准备状态，不能接收新数据.不过由于测试数据中数据发送的速度比较慢，间隔时间足够数据通过节点内两个模块，所以在东向输出端口的三个模块Earbiter、Eham_encode和Esend刚处于阻塞状态时，Wsplit模块仍处于S0状态，还没有新的数据进入.此时Wanalysis模块根据输出端口的阻塞信息对数据进行路由判断，得出控制信号011000，然后发送到Wsplit模块.Wsplit将数据发送到北向输出端口的仲裁模块Narbiter，然后通过输出端口发送到上侧的邻节点(1,3).
根据仿真时得到的路由路径信息，说明节点在数据的输出通道遇到阻塞时，会主动避开阻塞通道.上述测试中，数据发送速度较慢，可以自适应检测阻塞来进行路由判断.假如数据发送速率较快，发送时间间隔小于让数据传输两个模块的时间，那么当有连续数据流进入片上网络，在输出端口阻塞的时候，输入端口的交叉开关内也会有有效数据，此时路由计算模块会将锁存的数据发送到空闲方向.由上述测试验证得知，路由节点可以自动检测输出端口的忙碌程度，较好地进行数据的分配传输，有效地减小路由延迟.
3.2 通信性能测试及结果分析测试中，在片上网络的(1,1),(2,1),(1,2)和(2,2)节点分别挂载一个4×4异步乘法器.以(0,0),(3,0),(0,3)和(3,3)节点为主节点，分别向这四个异步乘法计算单元进行访问，调用乘法器进行数据乘法运算，运算完成后，计算节点分别把计算结果返回给主节点.运算的数据分别是2×3,2×6,2×12和4×8.从本地发送的数据分别为0x0532,0x3662,0xc9c2和0xfa84.测试结果表明，设计的4×4节点2D-Torus异步片上网络具有多方向通信的功能，对从节点计算单元IP核进行访问调用的功能以及多节点并行传输通信的功能.
4 结 论
本文提出了一种针对2D-Torus异步片上网络的自适应路由算法AA-XY路由算法.并利用异步电路设计方法学，设计并实现了基于AA-XY算法的4×4节点2D-Torus结构片上网络.实验结果表明，AA-XY算法可以规避阻塞严重或出现故障的路由节点，减小路由延迟.基于该算法的异步片上网络，能够实现多方向通信，IP核调用以及多节点并行通信的功能.异步片上网络是下一代多核系统的优选片上通信架构，因此本文提出的面向异步电路的路由算法和基于该算法的异步片上网络具有较好的应用前景.
| [1] | 宋威,Doug Edwards.异步片上网络研究综述[J].计算机辅助设计与图形学学报,2012,24(6):699-709. ( 1)
|
| [2] | Naoya O,Tomoyoshi F.High throughput compact delay-insensitive asynchronous NoC router[J].IEEE Transactions on Computers,2014,63(3):637-649. (1)
|
| [3] | Gebhardt D,You J S,Stevens K.Design of an energy-efficient asynchronous NoC and its optimization tools for heterogeneous SoCs[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2011,30(9):1387-1399. (1)
|
| [4] | Li ITRS.International technology roadmap for semiconductor.chapter design[EB/OL].[2013-10-10].http://www.itrs.net/reports.html. (1)
|
| [5] | Plana L A,Furber S B,Temple S,et al.A GALS infrastructure for a massively parallel multiprocessor[J].IEEE Design & Test of Computers, 2007,24(5):454-463. (1)
|
| [6] | Sheibanyrad A.Asynchronous implementation of a distributed network-on-chip[D].Paris:University of Pierre et Marie Curie,2008. (1)
|
| [7] | Belgne E,Clermidy F,Vivet P,et al.An asynchronous NoC architecture providing low latency service and its multi-level design framework[C]// Proceedings of the 11th International Symposium on Asynchronous Circuits and Systems.Los A1amitos:IEEE Computer Society Press,2005:54-63. (1)
|
| [8] | Dobkin R R,Ginosar R,Kolodny A.QNoC asynchronous router[J].Integration,the VLSI Journal,2009,42(2):103-115. (1)
|
| [9] | Jens S,Steve F.Principles of asynchronous circuit design:a systems perspective[M].London:Kluwer Academic Publishers,2009. (1)
|
| [10] | Chris J M.Asynchronous circuit design[M].New York:Wiley-Interscience,2004. (1)
|