0 概述

随着纳米技术的快速发展, 在单芯片上增加晶体管密度的多核架构得到广泛应用。然而, 日益增长的全局互联线延迟^[1]限制了多核架构潜在的性能改进, 导致片上网络(Network on Chip, NoC)向模块化^[2-4]和可扩展^[5-6]的分组交换方向发展^[7-9]。在单芯片上增加内核数量较难实现, 即使使用多个内核, 片上系统(System on Chip, SoC)架构通常也无法提供与内核数量相等的加速倍数。Amdahl定律表明, 并行计算所实现的加速效果取决于需要计算的串行运算量^[10-11]。

多数多核系统的运算速度受到片上网络I/O数量的影响。在单芯片上集成数十个甚至数百个内核, 需要复杂的NoC来提供高效可靠的片上通信。但是, NoC路由单元不是并发结构, 传统路由单元共享输入缓冲器, 如虚拟通道和交叉开关, 只允许连续的串行访问^[12]。这种设计导致片上通信的速度与效率较低。NoC路由单元将队列中的传输数据写入路由单元输入缓冲区, 或从路由单元输出缓冲区读出。每个数据块的每次写或读操作都会以串行方式更新路由单元缓冲区, 而同一个数据包中的其他数据则处于等待状态^[13-15]。交叉开关中也存在相同的串行操作。交换分配器协调输入通道和输出通道的使用, 每次只有一个输入通道可以将数据传输到一个输出通道, 来自其他输入通道的数据包必须等待并尝试在未来的周期中竞争交换机和输出通道^[16]。核心之间的大量通信使系统吞吐量大辐下降。有研究表明, 性能良好的并行策略能够更有效地利用多核系统^[17-18]。传统的路由单元遵循“推模式”规律^[4], 其中, 数据包从路由单元输入通道进入输出通道而不调查数据内容。因此, 路由速度受到限制。

本文提出一种基于虚拟冲突阵列^[19-20]的NoC路由单元架构。在路由单元缓冲区的输入处集成虚拟冲突阵列结构, 以消除对路由单元流水线的连续数据访问。数据请求不对路由单元输入缓冲区进行直接访问, 而在虚拟冲突阵列中被接收, 并与其相反请求实现中和。

1 基于虚拟冲突阵列的路由单元 1.1 传统虚拟通道路由单元传递途径

NoC通过多核系统在每个核心间传输数据。图 1所示为一个4×4环面拓扑的多核平台, 每个路由单元通过短暂的本地互连连接到核心和4个邻居路由单元。因此, 对于环形拓扑NoC, 每个路由单元具有5个输入/输出通道, 用于向东、南、西、北方向节点以及中心节点传输数据。

不同类型的路由单元有其独特的数据流控制机制。例如, 虚拟通道路由单元实现了高效的物理链路利用率和高吞吐量。如图 2所示, 每个输入端口的输入缓冲区由多个虚拟通道组成, 这些虚拟通道共享一个输入通道的相同物理链路。当一个虚拟通道的数据包由于某些未知原因而被阻塞时, 其余数据包可以通过其他虚拟通道的物理链路进行传输。

虚拟通道路由单元遵循“推模式”规律^[3], 其中, 数据包通过一跳或多跳从源端推送到目的端。在每一跳, 只要数据包的报头在路由单元输入通道可用, 如果虚拟通道有空间存储输入数据包, 则确认信号设置为“高”。在接收到该确认信号后, 输入缓冲器将接收写入请求以启动写入操作。当所有虚拟通道被占用并且没有更多空间来存储新的数据包时, 确认信号被设置为“低”, 写入操作停止。路由单元计算模块使用确定性逻辑来分析数据包的报头, 计算数据包的目的地并选择输出通道。如果输出通道可用, 并且授权信号被虚拟通道分配器和交换分配器设置为“高”, 则输入缓冲器将接收读请求并启动读操作, 直到授权信号被设置为“低”或虚拟通道变空。典型的路由单元流水线包含缓冲区写入和路由计算阶段、虚拟通道分配和交换分配阶段, 以及交换遍历阶段, 每个数据传递阶段都连续。假设T_p是数据包经过路由单元流水线的持续时间(数据包的延迟时间), 路由单元平均延迟T_r可以表示为:

$ {T_r} = H \cdot N \cdot {T_p} $

(1)

其中, H是跳数, N是数据包的总数。

1.2 冲突阵列结构

图 3所示为一个公共堆栈的冲突阵列结构, 其中, 有pop、push 2个操作与堆栈相关。在单核心多线程体系结构中, 每个线程都可能尝试访问此公共堆栈, 这种尝试被视为一个请求。如果有来自其他线程的请求争用堆栈导致该请求不能执行, 则其会退回到一个冲突阵列结构中, 并随机挑选阵列中的位置。如果有另一个请求已经存储在该位置, 且他们具有相反的操作, 则2个请求可能都被消除。例如, 一个请求想要弹出数据, 另一个请求想要推送数据。推送操作将其数据与弹出操作交换, 该过程称为请求消除。在这种情况下, 堆栈未被访问。如果一个请求不能与存储在所选位置中的请求交换数据(例如, pop不能与pop冲突, push不能与push冲突), 或者在所选位置找不到另一个请求, 则该请求会重新访问堆栈。

单核多线程架构可以大幅提高吞吐量。基于NoC的多核系统也具有共享结构, 例如路由单元中的输入缓冲区和交叉开关, Amdahl定律同样适用于这些情况。冲突阵列的概念不仅限于单核多线程架构, 本文将其扩展到片上路由单元, 以降低路由单元流水线的传输数据量。

2 NoC路由单元设计 2.1 虚拟通道路由单元的虚拟冲突阵列

本文提出一种新的NoC路由单元体系结构。

在传统虚拟通道路由单元的每个输入端口, 设置虚拟冲突阵列, 以消除对路由单元流水线的连续数据访问, 提高路由单元资源利用率与并行性。为说明数据不是直接访问输入缓冲区, 而是首先访问虚拟冲突阵列, 以潜在地与其他请求相冲突, 本文作如下定义:

定义1  虚拟冲突阵列是一种虚拟数据阵列(也称为消除阵列), 在访问共享结构之前可以消除数据请求。

定义2  冲突阵列的大小L为其长度, 表示可以同时存储在冲突阵列中的最大写请求数。

给定一个应用程序, 其包括任务流和相关任务。如图 4所示, 当在多核平台上处理任务流时, 任务T₁和T₂分配给内核A, 任务T₃和T₄分配给内核B。然后, 数据在T₁和T₃之间切换, 通过片上路由单元从核心A传输到核心B。任务流分区在路由过程之前被执行。通过任务流分割, 可以获取核心间通信数据包的源和目的信息。虚拟冲突阵列放置在每个路由单元输入端口中的路由单元虚拟通道之前。本文NoC路由单元体系结构包括随机地址生成器、计数器、状态分析器和L大小的虚拟冲突阵列。在任务流分区和任务调度阶段, 将任务分配给不同的核心并生成核心间的通信。

图 4所示为虚拟冲突阵列中的请求消除过程。当写入请求到达路由单元输入端口时, 随机地址生成器为其提供一个随机地址。如果此随机地址的关联阵列位置可用, 则数据请求将存储在此位置。如果这个位置被另一个数据请求占用, 随机地址生成器将为这个新的数据请求提供一个不同的地址。例如, 图 4中的写请求i首先被分配给虚拟冲突阵列中的一个位置。然而, 该位置已经被写请求b占用。因此, 写请求i从随机地址生成器获取新地址并进行存储。当读请求到达时, 随机地址生成器也在同一个虚拟冲突阵列中提供一个随机地址。状态分析器记录虚拟冲突阵列状态。如果存在与相同数据关联的写入请求, 则这2个相反的请求将发生冲突, 两者都被消除, 相关数据包将绕过路由单元管道, 直接到达目的地的输出通道。例如, 图 4中的读请求c在虚拟冲突阵列中的一个位置遇到写请求c, 这2个请求被消除, 数据包c将不再遍历路由单元流水线, 而直接从输入通道发送到输出通道。如果读请求不能满足其对应的相反请求, 则其退出并等待tb周期(定义将在下文给出), 以对下一个可用的虚拟冲突阵列进行访问, 而对应的数据分组仍存储在前一个路由单元的核心或缓冲区的存储器中(如图 4中的读请求d)。在上述过程中, 每个数据请求都可以独立访问虚拟冲突阵列。

通过上述分析可以看出, 提高访问次数可以增加数据冲突的可能性并缩短路由单元的延迟。本文路由单元结构允许回退并重新访问虚拟冲突阵列, 每个写请求存储在虚拟冲突阵列的随机位置。当计数器记录周期时, 如果数据请求仍未消除, 则它将离开虚拟冲突阵列并返回到输入缓冲区, 相关的数据包将在没有旁路的情况下穿过路由单元管道。例如, 图 4中的写请求a在虚拟冲突阵列中进行第n个循环后未被消除, 其将被发送到路由单元输入缓冲区。

定义3  写请求保持时间th表示虚拟冲突阵列可以存储每个写请求的最长时间。一旦持有时间到期, 未被消除的写请求必须离开虚拟冲突阵列, 而关联的数据包将在没有旁路的情况下穿过路由单元管道。

定义4  读请求回退持续时间tb表示读请求在重新访问虚拟冲突阵列之前必须等待的时间间隔。

图 5所示为本文基于虚拟冲突阵列的路由单元体系结构。

当需要通过路由单元进行核心间的通信时, 将数据包从前一个路由单元的核心或缓冲区的存储器注入路由单元输入端口之一。如果此输入端口中的虚拟冲突阵列具有存储数据请求的空间, 则状态分析器将确认信号设置为“高”, 并将其发送到输入通道。对于每个数据包, 发出写请求并将其发送到虚拟冲突阵列。同时, 路由计算模块在报头中提取数据包的目标地址, 并决定每个数据包的输出通道。如果输出通道可接收数据, 则它会发送一个确认信号回到输入端口, 并发出读请求, 该读请求将访问虚拟冲突阵列, 并尝试与已经在此处等待的写请求发生冲突。如果发生请求消除, 数据包将绕过路由单元管道到达输出通道。如果此输入端口中的虚拟冲突阵列存储空间已满, 则状态分析器将确认信号设置为“低”, 数据流将正常发送到路由单元流水线进行数据请求。在上述过程中, 新的虚拟冲突阵列消除了发送到路由单元流水线的数据请求。因此, 数据包可以绕过路由单元管道以节省路由时间和能量。消除速率、路由单元延迟可作为虚拟冲突阵列的关键性能评价指标。

2.2 消除率

为NoC路由单元引入虚拟冲突阵列, 可以在进入传统路由单元流水线之前消除数据请求。因此, 虚拟冲突阵列的消除率成为其性能评估的关键参数。对于L尺寸的虚拟冲突阵列, 为不失一般性, 假设一些写请求已经在其中。每个读请求可以访问任何位置的可能性为1/L。因此, 消除成功的概率是1/L, 消除失败的概率是1-1/L。th/tb的值表示一个读请求可能访问冲突阵列的上限。则消除率定义为:

$ E R=1-\left(\frac{L-1}{L}\right)^{t h / t b} $

(2)

与冲突阵列中失败的消除尝试相关联的数据包数量为:

$ {N_{{\rm{ fail }}}} = N \cdot {\left( {\frac{{L - 1}}{L}} \right)^{th/tb}} $

(3)

绕过路由单元管道的数据包数量为:

$ N_{\mathrm{succ}}=N \cdot\left(1-\left(\frac{L-1}{L}\right)^{t h / t b}\right) $

(4)

高消除率不一定缩短路由单元延迟。下文将进一步讨论如何设计虚拟冲突阵列以优化路由单元延迟。

2.3 路由单元延迟

式(1)定义N个数据包通过H跳传播的路由单元延迟, 式(3)给出使用路由单元流水线传输的

数据包数量。因此, 核心间通信的总路由单元流水线延迟, 可以表示为使用路由单元流水线传输的数据包数量和路由单元流水线延迟的乘积:

$ T_{\text { pipeline }}=N_{\text { fail }} \cdot T_{p} $

(5)

令k_i为第i个读请求的访问次数, 且1≤k_i≤th/tb。因此, 在虚拟冲突阵列中消除该读请求及其相应写请求的延迟是k_i·tb。成功消除虚拟冲突阵列中的请求所需的总延迟如下:

$ T_{\text { succ-e }}=\sum\limits_{i=1}^{N_{\text { succ }}} k_{i} \cdot t b $

(6)

虚拟冲突阵列中失败的请求消除花费的总延迟如下:

$ T_{\text { fail-e }}=N_{\text { fail }} \cdot t h $

(7)

综上, 虚拟冲突阵列的总延迟可以表示为:

$ T_{\text { array }}=\sum\limits_{i=1}^{N_{\text { suce }}} k_{i} \cdot t b+N_{\text { fail }} \cdot t h+N_{\text { succ }} \cdot t w $

(8)

其中, tw是一个数据包从路由单元输入通道传输到输出通道的线路延迟。

本文路由单元体系架构的总路由延迟可以计算为:

$ T_{\text { router }}=H \cdot\left(T_{\text { pipeline }}+T_{\text { array }}+T_{\text { overlap }}\right) $

(9)

其中, T_overlap是路由器流水线延迟和虚拟冲突阵列延迟的重叠。

2.4 硬件开销分析

在路由单元结构中引入虚拟冲突阵列, 可以提高路由单元的资源利用率, 但也会带来额外的硬件开销, 该开销表示如下:

$ Z=L /(V \cdot R) $

(10)

其中, V是每个输入端口拥有的虚拟通道数, R是每个虚拟通道所含的缓存区个数。

参考文献[21]对NoC的性能分析数据, 对于一个使用90 nm制程、含有16个缓存区的路由单元结构, 其硬件面积开销为81 407 μm²。以V=8、R=8、L=8为例, 根据式(10)的分析结果, 引入虚拟冲突阵列导致的新增面积约为10 176 μm², 开销比为12.5%。然而, 该虚拟冲突阵列配置能够消除55%的数据请求, 从而有效缩短了路由延迟。

3 实验结果与分析

本节在HNOCS平台上模拟4×4环形拓扑的NoC, 将基于虚拟冲突阵列的路由单元结构与现有虚拟通道路由单元结构在路由延迟方面进行比较。HNOCS是一个基于Omnet++平台的开源NoC模拟器, 其提供了一个开源、模块化、可扩展且完全可参数化的框架, 用于对NoC进行建模。所有计算机采用英特尔酷睿i7-6700 CPU, 频率为3.4 GHz, 配有16 GB内存和Microsoft Windows 10操作系统。图 6所示为消除率与th/tb值、L值之间的关系。由图 6可以看出, 使用更大的th/tb值和更小的L值, 可以实现更高的消除率。

图 7所示为虚拟冲突阵列延迟与th/tb值、L值之间的关系。其中, 核心间的通信具有5 000个数据包。由图 7可以看出, 在L达到8之前, 随着L的增加, 虚拟冲突阵列延迟急剧下降。当L达到8后, 该下降趋势变慢, 且当L超过10时开始平稳。当th/tb值达到6后, 在L=2时虚拟冲突阵列延迟为32 000个循环。而在L=16时, 虚拟冲突阵列延迟变为11 000个循环。对于不同的应用, 这些结论会有所不同, 但它们遵循相同的规律:如果一个写请求长时间存储在虚拟冲突阵列中, 则会剥夺其他请求的冲突机会。另外, 较高的th/tb值意味着每个写请求可以存储在虚拟冲突阵列中较长时间, 虚拟冲突阵列的延迟因此增加。另一方面, 更大的L值将在虚拟冲突阵列中提供更多的空间, 由于可以在虚拟冲突阵列中处理更多的请求, 因此延迟将缩短。

图 8所示为路由器流水线延迟、虚拟冲突阵列延迟与th/tb值的关系。其中, 核心间的通信具有5 000个数据包。由图 8可以看出, 随着th/tb值的增加, 路由单元流水线延迟减少, 虚拟冲突阵列延迟增加。原因是虚拟冲突阵列放置在路由单元虚拟通道之前, 当数据包由虚拟冲突阵列处理时, 先前的数据包被现有的路由单元流水线同时处理, 因此, 虚拟冲突阵列延迟和路由单元流水线延迟高度重叠。

为比较基于虚拟冲突阵列的路由单元与现有虚拟通道路由单元在路由延迟方面的性能, 模拟均匀数据业务模式, 在不同负载下得到的路由延迟对比结果如图 9所示。其中, L值设置为8。由图 9可以看出, 随着负载的增加, 与传统虚拟通道路由单元相比, 基于虚拟冲突阵列的路由单元具有较低的路由延迟, 且延迟增加较缓慢, 即其具有较好的路由延迟性能。

当L为8、负载为0.3时, 相比传统虚拟通道路由单元, 基于虚拟冲突阵列的路由单元延迟缩短了约70%, 代价仅为增加25%的硬件面积。当L值小于8时, 虽然消除率会减小, 延迟改进会降低, 但相应的硬件面积开销也会降低。

4 结束语

本文提出一种基于虚拟冲突阵列的路由单元结构, 以在数据进入路由单元流水线之前在虚拟冲突阵列中对其进行部分消除, 提高NoC的并行性。实验结果表明, 与传统虚拟通道路由单元相比, 该路由单元具有较短的路由延迟。本文路由单元结构目前只针对路由时延进行了优化, 下一步将研究并解决路由单元的能效优化问题。