时钟及面积优化的可配置片上网络路由器

2022-05-28胡东伟尚德龙王力男

西安电子科技大学学报 2022年2期

胡东伟，尚德龙，张勇，王力男

(1.中国电子科技集团公司第五十四研究所，河北石家庄 050080；2.南京智能技术研究院，江苏南京 211100)

伴随着半导体工艺技术的飞速发展，在单芯片上能够集成的处理器数目越来越多，处理器与处理器之间的互连问题和数据交换需求，已不是传统的总线所能解决或达成。片上网络(Network-on-Chip，NoC)借鉴互联网的思维，采用数据包包交换的方式，实现处理器之间的互连和数据交换[1]。采用片上网络的芯片系统，可以实现成百上千处理器的集成[2-3]。

目前，片上网络技术的研究如火如荼，但在片上网络技术的各个方面，例如网络架构、路由算法、流量控制等问题，都未达到统一。因此，目前大量的片上网络技术研究，都停留在系统仿真层面[4-6]，电路实现方面的研究相对较少。

片上网络实现包括网络接口的实现和片上网络路由器的实现[7]。网络接口实现处理器和片上网络的数据交换，路由器实现数据包的远程交换和路由。片上网络实现的核心在于路由器的实现。首先，片上网络路由器的时钟，决定了整个网络的时钟；其次，片上网络路由器，直接实现了片上网络的路由算法和流量控制算法；最后，片上网络路由器的复杂度，决定了整个网络的复杂度[7]。

片上网络路由器主要由输入/输出缓冲器和交叉开关组成[8]。交叉开关包括仲裁器和多路选择器，其结构已经比较成熟。路由器的复杂度，主要由输入/输出缓冲器决定[9-10]。因此，路由器中缓存器的研究，引起了业界的极大重视。片上网络路由器的缓冲器，一般采用先进先出(FIFO)缓存器来实现。根据文献[9]，采用无缓存器的片上网络路由器，可以使得片上网络总面积消耗节约60%以上，功耗节约39%以上。根据文献[10]，缓存器面积占比达到75%，功耗占比达到22%。然而，无缓存的路由器增加了访问延时，降低了片上网络吞吐率[9]，这是所不希望的。因此，有必要寻求新的先进先出缓存器实现技术。

首先，介绍同步先进先出缓存器和异步先进先出缓存器的电路结构[11-12]和延迟特点，及片上网络组成的系统架构和片上网络路由器架构；然后，提出一种优化的时钟布线方案，并按照这种方案，重新设计了路由器，达到了减小复杂度及片上网络延迟的效果。在此基础上，笔者提出一种采用锁存器替代寄存器的方法，以降低路由器中同步或异步先进先出缓存器的复杂度，并提出单时钟寄存器写的解决方案，并进一步提出多个先进先出缓存器的共享实现方案。该方案建立在第3节先进先出锁存器实现方案的基础上。

1 基础知识

1.1 同步先进先出和异步先进先出缓存器

1.1.1 先进先出缓存器的接口信号

先进先出缓存器是一种非常常用的数字电路部件，在此对其功能不做过多的描述。图1(a)给出了一般形式的先进先出缓存器接口信号，图1(b)将接口信号重新命名，使得接口信号符合AXI总线形式。同步先进先出缓存器是指缓存器的写入时钟CLK 1和读出时钟CLK 2，采用同一个时钟。异步先进先出缓存器是指缓存器的写入时钟CLK 1和读出时钟CLK 2，采用两个不同的时钟。这两个时钟可以是频率相同、相位不同的两个时钟，也可以是既不同频、也不同相的两个时钟。

1.1.2 先进先出缓存器的电路实现

图2(a)给出了同步先进先出缓存器的电路实现。图2(a)中，在写入侧和读出侧，分别维持一个写地址寄存器和读地址寄存器，每写入一个数据包，或读出一个数据包，对应的地址加1。“DEC”和“MUX”分别是写地址译码器和读数据多路选择器。当写地址和读地址相同时，先进先出要么为“空”，要么为“满”状态。“空”和“满”状态分别由一个“FULL”寄存器来分辨。在复位状态下，先进先出只能为“空”，“FULL”被清零。此后，“FULL”寄存器可以跟踪“空”和“满”的状态变化。

图2(b)给出了异步先进先出缓存器的电路实现。与同步先进先出缓存器不同的是，由于读写地址位于不同的时钟域，需要对读写地址进行格雷编码，并在对方时钟域内进行两次采样，如此才能获得稳定的跨时钟域地址信号。此外，为区分缓存器“空”和“满”的状态，在读写时钟域内分别设置“EMPTY”和“FULL”寄存器，以此追踪缓存器的状态变化。“组合逻辑1”和“组合逻辑2”进行地址比较。需注意，这里1个地址为二进制编码，1个地址为格雷编码。

需要特别强调的是：① FIFO的数据流为单向的；② 根据图2所示的FIFO实现电路，当输入输出的READY都为高，且异步FIFO的两侧使用同一个时钟时，同步FIFO的输出相对输入延迟1个时钟，异步FIFO的输出相对输入延迟3个时钟，也就是，异步FIFO比同步FIFO具有更大的时延；③ 同步FIFO的最小深度为1，异步FIFO的最小深度为4；④ 通过FIFO与同步FIFO的级联，可构成4以上任意深度的异步FIFO，这种级联的异步FIFO输入输出延迟为4个时钟。

图2 先进先出缓存器的电路实现

1.2 片上网络及其路由器

1.2.1 片上网络架构

片上网络是用于多个处理器单元(Processing Element，PE)互连的一种电路，它由路由器和互连链路构成。在NoC之上，PE与PE之间以数据包的形式进行数据交换。文献[3]指出，在一个路由器上连接一个处理器簇的分层架构，较一个路由器上连接单个PE的全网络架构，能更好地利用处理器簇内的本地存储器，从而具有更高的多处理器并行加速比，并且，簇内PE数目以4至8个为宜。因此，考虑图3所示的片上网络架构。图3中，NoC路由器(R)与R由L1链路相连，每一个R上连接1个处理器簇，每个簇内包含4个PE。R与PE由L2链路相连。簇内4个PE之间，每两两由L3链路相连(图3中未示出PE0与PE2、PE1与PE3之间的L3)。图3示出了1个4×4的NoC，每一个R具有X和Y两个坐标，可用于R(对应处理器簇)的寻址。每一个PE可通过对应的R和簇内PE编号来寻址。

显然，在图3所示的架构中，每一个L1链路，至少承担两个处理器簇(即8个PE)的互连，因此L1的带宽要求较高。考虑图4所示的数据包格式。图4中，数据包由包头、地址段和数据段构成。包头内包括了数据包类型(读请求、写请求、读响应、写响应)、源、目标PE地址和数据段的大小指示，地址段给出了数据段内数据的起始地址，数据段承载PE间需要交换的数据。由于L1的带宽要求较高，设计数据段的位宽较宽(例如128、192或256位)，且整个数据包在一个时钟周期内传输[13]，因此，图4所示数据包格式，与总线有一定的相似性。

以XY静态路由算法为例[5]。XY静态路由对数据包首先进行X(Y)方向的路由，再进行Y(X)方向的路由，直至到达目的R(PE)。采用XY路由，从源PE到目的PE只有1条路径，具有路由简单、无死锁的优点，因而被广泛采纳。此外，由于R内采用先进先出缓存器(见2.2.2节)，从源PE到目的PE整个路径上数据包的先后顺序得以保持，这也类似于总线。

图3所示的4×4 NoC连接了64个PE，但该架构具有向更大规模伸放的可行性。

图3 片上网络架构示意图

1.2.2 路由器架构

根据图3所示的NoC架构，路由器R的接口信号如图5(a)所示。图5(a)中，一个路由器上有4个相邻NoC(即东e、南s、西w、北n 4个方向)输入、4个PE输入，这分别对应图3中4个L1和4个L2的输入方向；相应地，路由器有4个相邻NoC输出和4个PE输出，这分别对应图3中4个L1和4个L2的输出方向。图5(b)给出了路由器的电路实现框图。图中，每个输入数据包，首先进入对应的先进先出进行缓存，8个先进先出缓存器的输出，连接到8个仲裁及多路选择器，每个仲裁及多路选择器选择出一个有效输出，输出到输出端口的先进先出缓存器。

仲裁及多路选择器由仲裁器和多路选择器构成，其个数与输出端口数目相同，且每个仲裁及多路选择器都相互独立。所有仲裁及多路选择器的输入通道数目，与路由器输入先进先出通道数目相同。输出端口的FIFO连接到下一个路由器(或PE)的输入FIFO，因此可以与下一个路由器(或PE)的输入FIFO合并。因此文中后面路由器将不再有输出FIFO。路由器输入FIFO可以是同步FIFO，也可以是异步FIFO，2.1节将详细讨论FIFO的时钟要求。

图5 路由器架构

1.2.3 虚通道和3D NoC

可以将每个物理输入通道的数据包，根据不同的标记排列到不同的先进先出队列中，由此形成虚通道。此标记即为虚通道识别号。图6示出了每个物理通道分为2个虚通道的示意图。虚通道方法增加了先进先出的个数，从而增加了同时从先进先出中输出的数据包个数，提高了数据包输出的并行性，由此对吞吐率有一定的提升；但另一方面，仲裁及多路选择器的输入通道数目增多，增大了仲裁及多路选择器的复杂度。假如仲裁及多路选择器的输入通道数目过多，则需要流水实现，这又增加了路由器的延迟，因此，对虚通道的使用需谨慎对待[5，9]。

图6 基于虚通道的路由器架构

这里需要强调的是，倘若采用虚通道方案，则仲裁及多路选择器的优先级，需要与时间相关，不可使仲裁器长时间驻留在某个优先级。例如，假如某个输出端口的数据包阻塞(由于它对应的下一级先进先出满导致)，且较长时间无法发送出去，此时，如果本地优先级轮转，则仲裁及多路选择器会尝试发送与这个数据包并行的其他数据包(隶属于其他虚通道)，这会在一定程度上减小阻塞。要使优先级与时间关联，也是很容易实现的，只要设置一个计数器，当仲裁器驻留在某一优先级超过该计数器阈值时，仲裁器跳转到下一优先级。

3D NoC在图5(a)所示的架构上，增加了上下方向NoC的输入输出。同样，这也增加了仲裁及多路选择器的输入通道数目，可流水实现仲裁及多路选择器。

2 片上网络对FIFO的时钟要求及优化方案

2.1 时钟要求及优化方案

如图3所示，由片上网络路由器构成的整个芯片，连接的PE较多，面积往往较庞大，因此，倘若整个芯片采用同步时钟，则从芯片的东南角到芯片的西北角，时钟的延迟构成一个环路，由于布线的延迟，时钟布线将很难收敛，或时钟速率很难提高。此外，由于这样的芯片功耗往往较高，需要对每个PE进行动态电压频率伸缩，这又需要各个PE的时钟独立。因此，最简单的办法是，对图5(b)所示的输入先进先出，采用异步先进先出[7，13]。这可以实现：① 各个PE的时钟解耦合；② 相邻NoC路由器的时钟解耦合。

但是，如2.1.2节所示，异步先进先出的缺陷是，异步先进先出两端的延迟较大，这将导致整个NoC上数据传输时的延迟较大。因此，笔者提出如下优化方案：

(1) PE与R之间，依旧采用异步先进先出，以实现各个PE时钟独立。

(2)对所有的R，从R到R，采用两个独立的时钟，从西到东、从北到南为CLK1，从东到西、从南到北为CLK2。

(3)对所有的R，从R到R的先进先出，采用同步先进先出。

图7为以上时钟方案的示意图。按照此时钟方案，NoC路由器R将涉及到多个时钟域，图8给出了此时路由器的总体架构。

图7 优化的NoC时钟方案

图8中，PE到R的数据包，首先分路为2路，一路将向东、南NoC端口输出，因此需要通过异步先进先出转换到CLK 1时钟域；另一路将向西、北NoC端口输出，因此需要通过异步先进先出转换到CLK 2时钟域。CLK 1和CLK 2都只是沿平面的一个方向推进，即东南方向或西北方向推进，时钟的延迟可以在这个方向逐渐递增，因此，时钟布线时，较易做到时钟收敛。为减小复杂度，在同一个R内，将不再支持由PE到PE路由。由PE到PE的访问，将全部通过图3中L3链路实现。因此，图8中，CLK 1时钟域下的仲裁及多路选择器阵列和CLK 2时钟域下的仲裁及多路选择器阵列，每个时钟域下均为4个2选1(至PE)，和2个6选1(至NoC)的仲裁和多路选择，这样仲裁及多路选择器的复杂度大大降低。需强调的是，图8中的PE到R的异步先进先出，和R到PE的异步先进先出，分成了2个，但相应地，它们的数据包流量也减半，因此每一个异步先进先出的深度亦减半，先进先出的复杂度并没有较图5(b)方案增加。

2.2 实验及结果

2.2.1 NoC路由器的实现实验

分别按照图5(b)所示的架构和按照图8所示的架构，对NoC路由器R进行设计实践。实践中图5(b)只有输入异步先进先出，没有输出异步先进先出，先进先出深度选取为8。图8所示异步先进先出深度为4。为尽量保证比较的公平性，图8的左侧增加4个分路器，将每个PE输入的数据包由1路分成2路；图8的右侧亦没有输出异步先进先出。

表1给出了实现的综合结果。实验中先进先出采用寄存器实现，工艺为TSMC 28nm HPC，9Track，RVT。从表1可以看到，采用图8所示结构，组合逻辑明显减小，时序逻辑与图5(b)的相当。这与前面的分析是一致的。

表1 不同结构下的NoC路由器面积对比 μm2

图9 不同跳数下的链路延迟

2.2.2 延迟仿真实验

为检验图7所示的时钟优化结果，按照图3所示架构，从源PE往目的PE发送数据包，检验不同跳数(通过1个NoC路由器R，记为1跳)下链路的延迟。仿真中，所有的时钟都设置为同一个时钟，以该时钟的时钟计数来评估链路延迟。图9给出了不同跳数下按照图5所示R和图8所示R实现时的链路延迟结果。从图9可以看到，在所有的跳数下，优化的时钟方案，都减小了链路延迟；当跳数为7时，全异步FIFO方案时，链路延迟为24个时钟，优化后，链路延迟只有12个时钟，只有原来的50%。

3 使用锁存器构建FIFO的存储阵列

如前所述，数据包的位宽较宽，这导致NoC路由器R内的先进先出占用较多资源。一般情况下，先进先出的深度不够深，其存储阵列不足以使用现成的SRAM宏单元，需采用定制电路实现。但定制电路的设计需耗费较长时间，在很多情况下很不方便。此时，最简单的办法是采用寄存器实现。如表1所示，此时寄存器占据了整个R内最大部分的面积开销。

为进一步减小先进先出的实现代价，推荐使用锁存器来替代寄存器，构建同步或异步先进先出。锁存器的模型如图10(a)所示。图10中，当使能信号EN为高时，输入数据D将贯通到锁存器输出端Q；当EN为低时，锁存器的输出值Q将保持不变。当EN、D都是由时钟CLK驱动时，数据D的延迟有可能比EN大，也可能比EN小，如图10(b)所示。这将导致锁存器内锁存不同时钟下的数据(D12和D21)，导致错误。此外，倘若错误地址上的EN信号产生毛刺，则有可能将数据写到错误的地址上。因此，针对锁存器的写数据，最简单的办法是，数据保持3个时钟，只在中间时钟打开EN信号，如图10(c)所示。

图10 锁存器模型及锁存器写存在的问题

但NoC路由器内的先进先出需要高吞吐率，使用3个时钟来完成写，是不可以接受的。笔者推荐图11的锁存器写方法。图11(a)示出了锁存器写的时序。图中，锁存器使能信号只是在时钟低电平的半周期内有效。锁存器的输入数据，是原始输入数据(见图10(b))延迟半个时钟周期。这延迟半个时钟周期，可以通过一个下降沿采样的寄存器来实现，如图11(b)所示。这样，使用图11(b)所示电路对先进先出的输入数据进行处理后，先进先出的存储阵列即可使用锁存器来实现。

图11 单周期锁存器写方法

此方法要求，在时钟的前半个周期内，地址译码已经稳定，这样不至于在锁存器使能信号打开时，数据写到错误的地址上。由于NoC路由器内的先进先出深度都很小(几个到几十个)，地址位宽很小，半个时钟周期内实现稳定译码，是很容易达到的。

需要强调的是，图11(a)的虚线处，锁存器可能暂时锁存前一个数据D10或D20，但由于在锁存器使能信号的下降沿前后，数据稳定为D11和D21，因此锁存器能保证锁存到正确数据。因此，使能信号上升沿的数据振荡，只是造成轻微的功耗损失，不影响锁存数据的正确性。

表2给出了图5(b)和图8的NoC路由器，使用寄存器和使用锁存器时的面积对比。综合时使用的工艺同前。从表2中可以看到，使用锁存器，大大减小了NoC路由器的面积消耗。

表2 寄存器和锁存器下的NoC路由器面积对比 μm2

4 可配置的共享先进先出

在图8中，CLK 1和CLK 2域，分别有两个同步先进先出，且它们的深度为图8中异步先进先出深度的2倍。本节进一步提出，将CLK 1域和CLK 2域的4个同步先进先出(FIFO 1、FIFO 2、FIFO 3和FIFO 4)深度进行共享。也就是，FIFO 1可以从FIFO 2借用若干条目(entry)的FIFO单元，FIFO 2可以从FIFO 1、FIFO 3借用若干条目的先进先出单元，FIFO 3可以从FIFO 2、FIFO 4借用若干条目的FIFO单元，FIFO 4可以从FIFO 3借用若干条目的先进先出单元[14]。

图12(a)给出了两个先进先出共享的原理框图。

(a) 两个FIFO共享存储陈列示意图

图12中有一个大的、基于锁存器的存储阵列，它的上半部分为FIFO 1，下半部分为FIFO 2。上半部分和下半部分的分界，由一个寄存器Addr1_E/Addr2_S来指示，该寄存器可配置。倘若FIFO 1和FIFO 2在同一个时钟域内，则很容易实现存储阵列同时写两个数据、读两个数据。这时，存储阵列相当于多端口寄存器文件。倘若FIFO 1和FIFO 2不在同一个时钟域内，则由于锁存器无需时钟，只有分界地址在两个时钟域内都使用，需保证使用该分界地址时，两个时钟域内的分界地址都有效。这有很多办法可实现，例如，可以在一个时钟域内写入，在另一个时钟域内读出，并等待两个时钟域内写入和读出的数值相同来保证；也可以在CLK 1域写入，传到CLK 2域，然后又从CLK 2域传回CLK 1域，比较传回的数值与写入的数值。

以上方法可实现静态的先进先出共享。如果设置一个寄存器，记录分界地址前后(即wr_addr1或rd_addr1到Addr1_E/Addr2_S，和Addr1_E/Addr2_S到wr_addr2或rd_addr2)，先进先出内容是否为空，则可以判断是否可以进行分界地址的动态修改。只有分界地址前后先进先出内容都为空时，则分界地址的修改方可进行。如此可实现先进先出的动态共享。同样，分界地址更改后，需保证修改后的地址，在相关时钟域内都稳定后，相关时钟域内的读写方可继续。

图12(b)给出了4个同步先进先出共享的原理框图。FIFO 2和FIFO 3的分界地址，涉及到跨时钟域问题。该分界地址前后的状态，也处于不同的时钟域。

也可考虑异步先进先出的共享。但非级联异步先进先出的地址涉及到格雷编码，地址需连续变化为宜。此外，图8中的异步先进先出深度只有4，已是异步先进先出的最小深度，共享的意义不大。倘若需要更大深度的异步先进先出共享，则笔者主张以级联的方式实现：通过深度为4的异步先进先出实现写到读时钟域的转换，只对读时钟域内的同步先进先出实现共享。

在图8所示NoC路由器实现中，仿真及综合验证了这种共享先进先出方法的可行性。综合时采用的工艺库同前。表3给出了采用这种共享先进先出和不采用这种共享先进先出的复杂度对比。可以看到，采用共享先进先出的方法，先进先出的组合逻辑复杂度有所增加。这是由于共享先进先出后，所有先进先出的地址位宽都需要加宽，输入数据地址译码器和输出数据多路选择器的复杂度将变大。表3中从比例上看，共享先进先出复杂度的提高还较显著。这在面积容忍度较大，而对数据灵活性要求较高的场合[15-17]，是可以接受的，有较大的现实意义。