-
摘要:
稀疏线性方程组求解等高性能计算应用常常涉及稀疏矩阵向量乘（SpMV）序列Ax，A2x, …, Asx的计算. 上述SpMV序列操作又称为稀疏矩阵幂函数MPK（matrix power kernel）. 由于MPK执行多次SpMV且稀疏矩阵保持不变，在缓存（cache）中重用稀疏矩阵，可避免每次执行SpMV均从主存加载A，从而缓解SpMV访存受限问题，提升MPK性能. 但在cache数据重用会导致相邻SpMV操作之间的数据依赖，现有MPK优化多针对单次SpMV调用，或在实现数据重用时引入过多额外开销. 提出了cache感知的MPK（cache-aware MPK，Ca-MPK），基于稀疏矩阵的依赖图，设计了体系结构感知的递归划分方法，将依赖图划分为适合cache大小的子图/子矩阵，通过构建分割子图解耦数据依赖，根据特定顺序在子矩阵上调度执行SpMV，实现cache数据重用. 测试结果表明，Ca-MPK相对于Intel OneMKL库和最新MPK实现，平均性能提升分别多达约1.57倍和1.40倍.
Abstract:Many high performance computing (HPC) applications such as solving sparse linear systems involve the calculation of sequences of Sparse Matrix-Vector Multiplications (SpMV) like Ax, A2x, …, Asx, which is known as the sparse Matrix Power Kernel (MPK). Since MPK calls SpMV using the same sparse matrix, reusing the matrix elements in cache, instead of repeatedly loading them from main memory, can potentially alleviate the memory-constrained problem for SpMV and enhance the performance of MPK. However, reusing the matrix introduces data dependencies between subsequent SpMVs. Prior work mainly either focus on optimizing an individual SpMV invocation, or introduce significant overheads for cache data reuse in MPK. This paper proposes a Cache-aware MPK (Ca-MPK) to optimize MPK via cache data reuse. Based on the dependency graph of a sparse matrix, an architecture-aware recursive partitioning of the graph is designed to obtain subgraphs/submatrices which are fit into cache. Separating subgraphs (i.e., separators) are constructed to decouple data dependencies among subgraphs. Then cache data reuse is achieved by executing sequences of SpMVs on subgraphs with a specified order. Performance evaluation demonstrates that Ca-MPK outperforms the MPK implementations based on the Intel OneMKL library and the state-of-the-art approach, with an average speedup of up to about 1.57 times and 1.40 times, respectively.
-
目前，人工智能和深度学习发展迅猛，取得了显著的技术突破和应用成果. 深度学习算法在图像识别、自然语言处理、语音识别和自动驾驶等领域表现出卓越的性能，推动了智能产品和服务的普及. 尽管取得了巨大成就，人工智能和深度学习仍面临挑战，包括对大数据和高性能计算资源的依赖、能效和并行处理能力的限制、在复杂任务中的泛化能力不足等. 人类大脑由大约1 000亿个神经元组成，每个神经元平均有7 000个突触，形成了一个错综复杂的巨大网络 [1-2]. 尽管中枢神经系统内的神经元之间有着复杂的联系，大脑仍然通过其高效的事件驱动通信实现了显著的能量效率. 可见，大脑和深度学习架构之间存在着巨大的能效差距和并行处理能力的差距[3].
许多国家已经开始从人类大脑的连接模式和计算模型中寻求灵感，通过探索生物神经网络的机制，模拟大脑处理和存储信息的方式，旨在设计受大脑启发的高能效计算平台——神经形态平台（neuromorphic platforms）. 脉冲神经网络（spiking neural network， SNN）作为神经形态平台的基本计算范式，使用离散的脉冲来传递信息，这使得它们在信息处理和能耗效率方面更接近于生物神经系统，并在模式识别、感知系统等应用中表现出色[4-6]. 为模拟大脑的操作动力学，神经形态平台通常包含数千个并行核心. 例如，IBM在其深蓝超级计算机平台上使用了近150 000个CPU来模拟猫的大脑皮层模型[7]. SpiNNaker项目[8]已经实现了一个具有惊人的1 036 900个ARM 内核的大规模神经形态系统，这就导致网络中充斥着海量的数据包. 因此，在神经形态平台上运行SNN的一个关键挑战是如何在数千个核心之间分配大量的数据包流量. 传统的芯片通信架构使用总线结构，其中所有模块共享一个通信总线. 随着芯片集成度的增加和系统规模的扩大，总线架构面临着通信带宽瓶颈、延迟增加和功耗上升等问题. 片上网络（network-on-chip， NoC）应运而生，为这些问题提供了一种有效的解决方案. NoC是一种在芯片级别上实现高度集成的通信架构，可以提供更高的吞吐量、更低的延迟以及良好的可扩展性、可重构性、灵活性. 这些特性使得NoC成为目前神经形态平台常采用的一种互连体系结构.
目前神经形态平台NoC的设计还面临着一些挑战. 首先在传输模式方面，一个神经元的脉冲信号常常需要传递给多个有突触连接的目标神经元. 要处理这种一对多的传输模式，多播技术比传统的单播技术更加适合[9]. 多播技术可以一次性将脉冲信号发送给所有目标神经元，而不需要逐个发送，这显著提高了数据传输的效率，减少了通信开销和延迟. 此外，多播更逼真地再现了生物神经网络的并行处理能力和信息传播方式[10]. 然而之前的很多神经形态平台，如TrueNorth[11]、Loihi[12]、天机芯[13]等，只支持单播路由策略. 这种通过多次点对点传输来完成多播的方式会导致额外的功耗开销和低传输效率. 除了路由器的传输模式以外，NoC及其路由策略的可扩展性和存储信息开销也是满足未来神经形态计算需求的关键之处. 部分工作[14-15]基于目的驱动的路由方式，将所有的目的地路由信息以分组报头的形式嵌入到数据包中. 这种方式会严重影响NoC的可扩展性，当目的地数量增多时，数据包将会呈线性膨胀；还有一些工作[16-18]基于源驱动的路由方式，将所有可能的路由路径提前计算好，并保存在本地存储器中，数据包中只传输其源地址. 这种方式存在的一个问题是经过每个中间节点都需要查路由表的延迟和功耗代价过大.
为了解决这些问题，本文针对大规模神经形态平台的通信需求，提出了一个脑启发的NoC设计. 本文的主要贡献包括3个方面：
1）借鉴大脑的小世界网络特性，提出了自适应、无死锁的区域广播 （region-broadcast，ReB）路由方案，通过统一的数据包格式和路由策略将单播、多播和广播融合起来，以更加通用简洁的方式适应神经形态平台的各种数据通信模式，并且设计了支持多种脉冲传输模式的路由器. ReB利用脉冲发放的空间局部性，获得了更加均衡的链路负载和更低的峰值流量；
2）设计了一个突触连接索引方法用来替换传统的路由表，将神经元之间的突触连接信息存储起来，从而使NoC获得良好的可扩展性和较低的传输功耗；
3）在合成流量、4个SNN应用以及脑皮质柱网络上对ReB和其他相关工作进行了链路负载、延迟、吞吐量和功耗等方面的对比，展示了在神经形态平台NoC的设计中，我们的ReB路由策略和突触连接索引方法会更加具有优势.
实验表明，与现有工作相比，ReB路由方案将峰值脉冲流量和链路负载标准差分别降低了11.5%和20.4%，并且有效提升了网络的延迟、吞吐量和功耗等方面的性能. 同时，所提出的ReB路由器的带宽达到0.24 spike/cycle， 硬件实现面积仅为0.014 mm2.
1. 背景及相关工作
本节将介绍大脑网络和神经元之间通信相关的背景知识，以及概述一些已有的神经形态平台NoC和专用NoC设计.
1.1 大脑的小世界网络特性
随着从人类神经影像数据中重构网络技术的发展，Latora等人[19]的工作表明人类大脑网络有小世界特性，具有高度聚集的结构和全局性的高效率——神经元倾向于形成紧密联系的群体，而且具有较短的特征路径长度. 图1展示了大脑区域之间的连接模式.
由于连接远距离神经元的昂贵布线成本，大脑网络的进化倾向于将连接的神经元尽可能靠近，这有助于提高大脑网络的拓扑效率和鲁棒性[2].
真实生物神经元的平均放电速率为10 Hz. 在人类大脑中，1011个神经元的集体活动导致每秒产生多达1012数量的脉冲信号. 尽管中枢神经系统内的神经元之间存在大量的尖峰信号，但大脑仍然通过其模块化结构实现了显著的能量效率. 这种非凡的效率赋予大脑在认知和感知等复杂任务中强大的学习和记忆能力. 大脑网络通信成本有3个方面[20]：延迟、能量和信息成本. NoC的通信模型在这3个方面之间实现良好的平衡，有可能构成生物学意义上更加合理的神经通信策略.
1.2 神经形态平台NoC及专用NoC
在大规模神经形态平台研究领域，已经涌现了大量的片上网络设计. 2014年IBM发布的大规模仿人脑芯片TrueNorth[11]含4 096个核心，基本计算核通过2D mesh路由形成可拓展的大规模神经形态网络. 2019 年清华的异构融合类脑芯片天机芯[13]具有高速度、高性能、低功耗的特点，“天机芯I”采用了2D mesh路由结构，每块芯片含有6个FCore，片内的 6 个 FCore 呈 2×3 矩形 2D 排列，每个FCore 的路由节点可以与东南西北4个方向的 FCore 交换信息，同时也可以将信息发送至本地 FCore. Intel的多核类脑芯片Loihi [12] 实现了异步片上网络，用于核间通信，网络拓扑结构为2D mesh，由于与芯片间消息事务相关的死锁保护的原因，Loihi 的NoC使用2个独立的物理路由器网络. 斯坦福大学研制的Neurogrid[21]数模混合系统中每个256×256的神经元阵列组成一个神经核，16个神经核通过树形的拓扑连接结构形成分级网络. Neurogrid采用多播树的片上路由策略，通过分2个阶段（向上阶段和向下阶段）进行路由，并将数据包的分流限制到向下阶段，从而避免死锁. 但这种路由方法与其独特的神经核树形拓扑连接方式相适应，不具备通用性. SpiNNaker[22]是一种专门设计用于支持大脑中各种通信的计算机，它的关键创新是通信架构，路由系统采用基于2D triangular mesh的轻量级多播包路由机制，并提出了增强的最短路径路由（enhanced shortest path routing，ESPR）和邻居探索路由（neighbour exploring routing，NER）这2种源驱动的路由方式来完成SpiNNaker的通信需求. 2021年复旦大学设计的负载感知多播路由（load-aware multicast routing，LAMR）策略[16]主要采用源驱动的基于树的多播路由机制. LAMR通过宽度优先搜索来寻找拥塞较小的路由路线，并且尽可能合并多播路径，实现了较高的通信效率.
此外，近年来还出现了许多专用的NoC设计. 2017 年Akbari 等人[23]设计了一种用于神经形态结构的高性能片上网络拓扑——Dragonfly，以解决传统拓扑结构具有高直径、低平分带宽和较差的 集体通信支持. 2023 年Yazdanpanah[14]提出了基于2层 2D mesh 拓扑结构的 TLAM路由方法，采取了混合树/路径的多播路由策略. 它将片上网络划分成4个分区，每个分区有一个中心节点，并且通过4条新增链路将中心节点连接起来. 单播数据包采用基于转向的无死锁XY路由，多播数据包在每个本地分区采用哈密顿路径进行路由. 杨智杰等人[24]设计的类脑处理器异步片上网络架构 NosralC采用异步链路和同步路由器实现，在资源和性能开销不大的前提下，实现了延迟的降低和能效的提升.
目前大多数神经形态平台NoC只支持单播路由策略，通过多次单播来实现多播. 专用NoC设计虽然在一定程度上解决了传输模式单一的问题，但路由策略仍然存在不够灵活高效的问题，在支持多播方面，对于网络的死锁避免问题也没有很好的解决办法. 此外，路由信息存储方法仍然存在着可扩展性低和功耗开销过大的问题.
2. 脑启发的NoC设计
在本节中，我们主要介绍针对大规模神经形态平台片上互连通信所设计的NoC架构，包括整体的设计方案、详细的路由策略、路由器架构和突触连接索引方法，并对NoC的可扩展性进行了分析讨论.
2.1 整体设计方案及路由策略
受人脑小世界网络特性的启发，本文提出了一种用于大规模神经形态平台上脉冲数据包传输的无死锁ReB路由策略. ReB路由策略可以支持单播、多播和广播的并行路由计算和传输. 路由算法的整体思路如图2所示.
详细的流程解释如下：
1）根据SNN模型中神经元的互连情况，将连接紧密的神经元尽可能划分到一个计算核心，完成神经元到片上网络的映射.
2）针对每个源神经元的目标神经元，我们通过算法（如层次聚类算法）对目标神经元进行聚类，得到一些簇集. 对每个聚类簇用矩形框起来，并用一条 对角线的2个坐标点表示：A（x1，y1），B（x2，y2），其中A是矩形的左上角顶点，B 是右下角顶点.
3）将每个聚类簇矩形信息，即A和B这2个坐标点存储到与源神经元相对应的存储单元中. 当神经元产生脉冲事件时，它会访问本地存储器得到与该神经元相对应的聚类簇矩形，并将数据包发送到目标矩形区域的边界节点. 当到达目标区域后，数据包在该区域进行广播，区域内的节点访问突触连接信息以确定该数据包是否被接收.
在单播模式的情况下，矩形区域是1个点；在具有多个目的神经元的情况下，表示多播模式，支持多个目的地和矩形区域；当目的神经元分布在NoC的所有核心上时，表示广播模式，矩形区域包含整个2D mesh片上网络. 图2（c）展示了ReB路由策略的大致过程，它具有自适应和无死锁的特性. 通过ReB路由第1次到达矩形区域的节点，我们称之为过渡节点. 首先，ReB路由在区域内进行广播的方式为：对于过渡节点，它会向所有方向（除去传入和边界方向）发送数据包；对于区域内的其余节点，从X方向进入的数据包在所有方向上（除去传入和边界方向）进行传输；从Y方向进入的数据包只沿着相同的Y方向发送. 其次，从源节点发往目标区域的过程中是基于西向优先转向模型[25]进行路由，我们将其扩展以支持目的地不是单个节点而是一个矩形区域的情况：当源节点在矩形区域左边界的东边并且在区域的上方或下方时，数据包需要先向西传输到矩形区域的左边界的延长线上，再以最短距离传输到矩形区域. 使用这种方法的原因在于避免从区域外的单播切换到区域内的广播时，发生违背转向规则的传输，正如图3所示.
在NoC中，数据包需要在各个处理单元之间不断传输. 死锁情况会导致数据包在某个节点或路径上无法前进，从而阻塞整个网络的通信. 随着片上核心数量的增加，通信路径变得更加复杂. 如果网络中存在死锁风险，系统的扩展会变得更加困难. ReB路由策略通过禁止由南向西和由北向西2个方向的转向，使得在NoC上不会形成环路依赖. 即使对于多播数据包的传输，也可以避免在NoC上发生死锁的现象.
本文提出的路由机制还实现了拥塞感知的路径选择. 如图2（c）所示，路由器在收到东向链路上的full信号时，会将数据包向南发出，而不是阻塞在当前节点，这种自适应的路径选择发生在图4中的位置1和位置2.
![]()
图 4 在不同情况下ReB策略允许的路由方向Figure 4. Routing directions allowed by ReB strategy in different situations对于源节点在位置1的情况，可以根据相邻节点输入信道的full信号，选择向东或者向南传输；源节点在位置2的情况同理，选择向东或向北传输. 对于源节点在位置3和4的情况，数据包直接沿X方向传输到目的矩形区域即可. 由于这些情况都是以最短路径传输到目的区域的过渡节点上，因此也不存在活锁的发生. 具体路由算法的伪代码见算法1.
算法1. ReB路由算法.
输入：当前节点坐标（x，y），目标区域的左上顶点坐标（XL，YL），右下顶点坐标（XR，YR），数据包传入方向inport；
输出：数据包的所有输出方向outs.
① /* 在目标矩形区域内*/
② if（x，y）在目标区域内
③ if 数据包是第1次到达目标矩形区域或者 inport==east or west
④ outs←除去inport和边界方向的其他所有 方向；
⑤ else if inport==north or south
⑥ outs←inport的反方向；
⑦ endif
⑧ else /* 在目标矩形区域外*/
⑨ if x > XL
⑩ outs←west;
⑪ else
⑫ if YL ≤ y ≤ YR 或者东边没有传来满信号
⑬ outs←east;
⑭ else if y < YL
⑮ outs←south;
⑯ else if y > YR
⑰ outs←north;
⑱ endif
⑲ endif
⑳ endif
2.2 路由器的硬件设计
本文还实现了支持ReB策略的路由器，用于混合模式的脉冲数据包传输. 图5展示了路由器的硬件整体架构. 为了进一步减少面积开销，我们不使用虚通道技术，也不为输出端口配备缓冲区. 当数据包到达输入端口时，它会被写入相应的先进先出（first in first out，FIFO）存储器. 然后，ReB逻辑执行路由计算，以确定此数据包的输出端口. 路由输出端口根据来自相邻路由器输入信道的full信号自适应地改变，这可以有效地减少片上网络中的拥塞. 接下来，数据包将进入开关分配阶段，它会仲裁开关的输入输出端口. 一旦分配到输出端口，单播数据包就会从缓冲区中读出并进行到开关传输阶段. 最后，数据包经过链路传输到下游路由器. 对于多播或者广播数据包，它可能会请求多个输出端口，数据包将被复制到多个输出端口. 只有当数据包被成功传输到所有的目的端口后，它才会从FIFO中被移除.
数据包大小统一为64 b，最高的2 b表示数据包类型，包括单播（00），多播（01）和广播（10）. 接下来的2个8 b字段分别表示目的矩形区域的左上坐标（XL，YL）和右下坐标（XR，YR）. 标签tag和索引index字段用于判断矩形区域中的节点是否接收该数据包，在目标区域之外不发挥作用. 最后一个字段表示数据有效载荷. 图5还展示了所提出ReB路由策略的硬件电路设计. 该电路由基本门电路、比较器和多路选择器组成. 比较器用于将当前路由器地址与目标地址进行比较，比较的结果和邻居路由器传来的full信号综合起来作为输出方向的判定条件. 多路选择器根据当前路由器位于矩形区域内外的情况对输出方向进行一个选择.
2.3 突触连接索引方法
在本文中，我们部署了一种突触连接索引方法来配合ReB路由策略并替换掉多播路由表，使得NoC 的信息传输可以覆盖每个核心的所有神经元，相当于模拟真实神经元之间的突触连接. 当神经元发放脉冲时，神经元ID将用于查找目的地信息. 具体流程如图6所示. 源神经元ID被用作访问发送端第1级存储器的索引，以获得多播区域的基地址和区域数量. 然后根据基地址和区域数量访问发送端第2级存储器的相应条目. 每个条目都包括目标区域的左上坐标、右下坐标、标签和索引字段. 条目中字段的含义与数据包格式中相应字段的含义一致. 最后，这些与目的神经元相关的基本信息被组装成数据包并由路由器发送到网络中. 当脉冲数据包到达目的节点处的路由器时，数据包的索引字段用于检索接收端第1级存储器，将脉冲数据包中的标签字段与索引条目中的标签进行比较，如果它们匹配，则认为该数据包有资格由当前核心接收. 接着，路由器使用基地址和索引条目中的神经元数量来检索接收端第2级存储器中所有的目标神经元ID和树突ID. 这些ID用于访问核心数据区中的突触权重，为神经元计算做准备. 发送端和接收端的多级存储器构建了不同神经元之间突触连接的桥梁. 图6还展示了一个在NoC上的不同核心之间神经元互连通信的示例，核心0中的1个神经元分别与核心1中的神经元1、核心2中的神经元2、核心3中的神经元3和4存在突触连接. 当源神经元发送脉冲数据包时，它通过发送端的2级存储器获取目的区域的路由信息，按照ReB路由策略传输到核心1，2，3所组成的目的区域. 当核心3收到该脉冲数据包时，它会访问接收端的多级存储器，通过索引和标签字段判断出当前核心可以接收该数据包，进而获取要传输到的具体神经元ID，即神经元3和4.
![]()
图 6 突触连接索引方法的示意图Figure 6. An Illustration of the synaptic connections indexing method2.4 可扩展性分析
所提出NoC具备良好的可扩展性. 一方面，数据包采用统一的格式来完成混合模式的脉冲数据传输. 多播目的地以矩形区域的形式嵌入到大小为O(log N)的single-flit数据包中，其中N表示为片上网络的核心数. 由于数据包无需存储所有的目的地路由信息，这大大节省了信息传输开销. 矩形区域的编码长度随着片上核心数目增加呈对数变化，这对于大规模神经形态平台的扩展具有很大的优势. 此外，mesh拓扑结构本身就具备灵活扩展的特性，这种扩展不会显著增加整体复杂度或影响网络性能.
另一方面，目的驱动的路由方式在传输路径上不需要路由表. ReB 路由只需要在源节点和目的区域索引突触连接关系来发送和接收数据包，而不是路径上的每一跳都要访问路由表. ReB路由访存功耗与源驱动的路由方式所产生的访存功耗的比值推导如下：
PReBP源驱动=(1+k)×e(1+h)×e=(1+k)(1+h)， (1) 其中e表示一次访存所产生的能耗，k表示多播的目的地数量，h表示传输的总跳数. 如图7所示，以基于源驱动的维序路由[18]为例，我们统计了不同NoC拓扑大小下源驱动路由的平均总跳数，并计算了式（1）中访存功耗的比值. 当2D mesh的拓扑变大时，对于随机产生目的地的方式来说，该比值会随之变小. 主要原因是ReB路由的访存功耗与拓扑规模大小无关，仅与多播目的地数量相关，而源驱动路由中的总跳数h与网络拓扑大小呈正相关.
![]()
图 7 不同NoC规模下的访存功耗比值Figure 7. Memory access power consumption ratio under different sizes of NoCReB路由策略的良好可扩展性对于大规模神经形态平台至关重要，它能够确保系统在面对不断增加的计算需求时，可以灵活地增加计算核心或存储资源，并且仍然保持高效的性能和较低的功耗，以应对更大规模的复杂神经网络任务.
3. 实 验
本节分析讨论了所提出的ReB路由策略对链路负载、网络延迟和吞吐量的影响，以及所提出的突触连接索引方法对功耗的影响. 这些都是衡量NoC性能的关键指标. 本节将基于PAT-Noxim[26]仿真器展开实验. 它是基于SystemC开发的周期精确的 NoC 模拟器，可以进行延迟、吞吐量等数据的分析，也可以根据有关功耗的细粒度统计数据进行性能的评估. 此外，我们选取了一些经典的路由策略以及最近一些NoC工作中所采取的路由策略作为对比，包括UNICAST，XY[25]，ESPR[18]，LAMR[16]. 其中UNICAST算法通过多次的单播来完成多播，作为对比的基线策略，以衡量多播技术所带来的性能提升；XY多播路由优先往X方向传输数据包，遇到Y方向上存在多播目的地时复制数据包并产生路由分支；增强最短路径路由（enhanced shortest path routing，ESPR）是SpiNNaker神经形态平台所提出的片上多播路由策略，它通过尽可能合并多播的路由路径来减少链路负载；负载感知多播路由（load-aware multicast routing，LAMR）是复旦大学团队设计的基于树的多播路由机制，它通过宽度优先搜索来寻找拥塞较小的路由路线. 这些策略都在仿真器上进行了部署和实现. 为了使实验结果更加具有可靠性，我们进行重复实验计算性能指标的平均值. 具体的仿真实验参数配置如表1所示.
表 1 仿真实验参数配置Table 1. Simulation Parameters Setting参数 值 mesh大小 10×10 FIFO深度 8 微片大小/b 64 数据包长度 signle-flit 交换机制 虫洞 路由器流水线长度 4级 合成流量模式 random，transpose，hotspot 多播目的地数量 10，20，30 注入率/(packet/(cycle·node)) 0.01~0.055 热身时间/cycle 1 000 运行时间/cycle 20 000 此外，为了更好地发挥所提出ReB策略的自适应路由的优势和减少由于西向优先产生的额外跳数，我们对ReB的多播随机目的地映射进行调整，将源节点尽量放置在图4中相对目的区域的位置1~4，这种方式命名为ReB-MA （mapping adjustment）.
3.1 合成流量模式下的性能评估
为了评估ReB和其他路由策略的链路负载、延迟和吞吐量等性能指标，我们使用了多种合成通信流量模式，包括随机（random）、翻转（transpose）、热点（hotspot）.
3.1.1 链路负载
图8（a）为各种路由方案下所有链路流量分布的盒图，可以看出由于更好地利用了目的地位置的局部趋向性，ReB和ReB-MA策略的流量分布更加集中均衡. 与LAMR算法相比，ReB-MA的峰值流量降低了11.5%. UNICAST通过多次单播来完一次多播的数据包传输，这种方式显著地增加了网络流量，并且降低了传输效率. ESPR和LAMR策略通过一些方法来合并不同数据包的多播路径，从而减少了传输过程中的多播路由分支. 因此，相比于没有路径合并机制的XY多播来说，平均链路流量和峰值负载都得到了很大程度的降低. 此外，由于映射调整后的ReB-MA可以更多地利用路由的自适应拥塞感知策略去改变数据流量的传输路径，网络流量相比于ReB也会更好地分散在不同的链路上，从而进一步降低链路的峰值负载.
如图8（b）所示是所有链路负载标准差的对比实验结果. 标准差δ可以通过式（2）（3）得到：
δ=√m∑i=1(xi−μ)2m， (2) μ=m∑i=1xim， (3) 其中，i表示链路编号，xi是链路i的数据流量数，m是有效链路的总数. 在这个例子中，对于10×10大小的2D mesh NoC来说，m为360. 我们从图8（b）中可以发现，采用ReB路由的链路负载的标准差减少了20.4%，获得了更加均衡的负载流量，可以在很大程度上缓解网络上的拥塞.
3.1.2 吞吐量
如图9所示，我们研究了在不同多播目的地数量和不同拓扑大小下的网络饱和吞吐量，以表征系统的整体数据传输能力. 其定义如下：
![]()
图 9 不同多播目的地数量和拓扑大小下的饱和吞吐量Figure 9. Saturation throughput for different destination numbers and topology size吞吐量=接收的数据包总数仿真运行时间×节点数. (4) 我们逐渐增加注入率，直到网络吞吐量不再增加，此时的吞吐量被定义为饱和吞吐量. 从图9（a）可以看到，从10个多播目的地到30个多播目的地，ReB和ReB-MA策略的网络饱和吞吐量逐渐增加，相对于其他路由策略，始终保持较大的饱和吞吐量. 在30个多播目的地时，ReB-MA策略下每个路由器的饱和吞吐量可以达到0.16 数据包/周期. 我们设计的无死锁机制使得在注入率较大时，网络依然可以连续不断地对数据包进行传输. ESPR和LAMR路由策略由于没有相应的死锁避免机制，相比于无死锁的XY多播路由，并没有取得吞吐性能上的优势.
片上网络的拓扑大小取决于具体的神经形态规模需求，较大的片上网络会带来传输跳数和延迟的增加，较小的片上网络会导致系统支持的神经元数量减少. 图9（b）展示了在不同拓扑规模下的网络饱和吞吐量，可以看到随着拓扑规模的变大，平均传输路径变长，UNICAST单播方式的吞吐量下降趋势尤为明显，其他几种多播算法也出现不同程度的下降. ReB策略在不同拓扑大小下保持相对较高的网络吞吐量，在20×20的拓扑大小下，吞吐量仍然达到0.08 packet/(cycle·node).
3.1.3 平均延迟
图10展示了在不同数据包注入率下的平均延迟并在random，transpose，hotspot这3种不同的合成流量模式下将不同的路由策略进行对比. 延迟被定义为数据包到达目的地被接收的时间戳与数据包产生的时间戳之间的差值. 注入率被定义为单位周期内每个节点产生的数据包数量.
可以看到，对于不同的流量模式，ReB和ReB-MA在轻到中等流量负载下都表现出相对较低的延迟. 相较于完全单播的方式，ReB路由在0.01注入率下，平均延迟减少了约20.7%~30.8%. 此外，在random和hotspot的流量模式下，我们提出的路由方案可以支持更高的数据流量注入率，并且在NoC上不会产生死锁和活锁的现象，这对于大规模神经形态平台中的信息传输具有重要意义. 虽然在transpose流量模式下，LAMR路由表现较为出色，但其在高注入率下很容易发生死锁，导致系统运行被阻塞，需要重复运行很多次仿真来获取实验结果.
3.2 真实SNN应用下的性能评估
SNN作为神经形态平台的基本计算范式，将其进行映射部署到NoC上进行仿真验证是有意义的. 本实验使用了4种不同类型的SNN应用，它们具有不同的连接模式和数据集，如表2所示. 表中 4C3 表示卷积通道数为 4、卷积核大小为 3×3，MP2 表示步长为2的最大池化层，10FC 表示输出维度为 10的全连接层，36H表示SRNN网络结构里的36个隐藏层神经元，{K}×3表示有3个K结构.
表 2 SNN应用程序Table 2. SNN ApplicationsQTDB 和 Ev-object数据集对应的SNN网络结 构都只有全连接，因此多播比例是100%. 除了全连 接外，MNIST和DVS-Gesture对应的SNN网络还有 卷积层和池化层. 图11展示了在不同SNN应用下的归一化运行时间和功耗开销.
ReB路由策略利用神经元高度聚集结构的特性，在更短的运行时间内处理完所有输入的脉冲信号. 突触连接索引方法节省了在路由路径上查找路由表所产生的功耗，而只需要在源节点和目的区域内对突触连接的存储信息进行访问. 这对于网络中较长的传输路径来说，具有很大的能效优势.
3.3 脑网络仿真
目前人类对大脑的认知程度还十分有限，但已经涌现了大量的脑仿真建模工作. 为了更加全面地评估ReB NoC架构的性能，我们基于Potjans等人[31]所提出的分层皮质微环路模型开展仿真验证实验，如图12所示. 皮质柱被认为是大脑的基本功能块，第2/3，4，5，6层分别由模型神经元的兴奋性（三角形）和抑制性（圆形）群体表示，群体的输入由丘脑皮层输入靶向层4和6以及所有群体的其他外部输入表示，模型尺寸对应于1mm2表面下的皮质网络.
图13（a）统计了该脑网络模型中每个神经元群的脉冲发放频率，L5层的脉冲发放较为频繁，意味着会输出更多的数据包到网络中. 各个神经元群的平均脉冲发放率不超过10 spike/s，每个计算核心可以容纳
2048 个神经元，因此一个计算核心的最大发放率为20 Kspike/s. 本文提出的NoC路由器带宽可达0.24 spike/cycle，在100 MHz条件下每秒可以处理24 M 的脉冲，因此满足脑网络仿真的吞吐需求，并且可以将脑网络的仿真时间缩短约原来的1/1 000倍.![]()
图 13 分层皮质网络模型下的性能评估Figure 13. Performance evaluation under layered cortical networks models我们基于该模型生成了5 015个神经元的小网络和38 586个神经元的大网络用于仿真实验. 图13（b）统计了2种脑网络规模下的延迟和能耗数据，并与其他几种多播NoC进行比较. 得益于ReB路由的脑启发多播特性和突触连接索引方法，它在不同规模的分层皮质网络下都具有较低的传输延迟和能耗开销，可以有效支持脑网络应用下的脉冲信息传输.
3.4 与相关先进工作的比较
本文提出的路由器通过Verilog HDL进行实现，并基于SMIC 28nm CMOS工艺完成综合. 表3显示了ReB NoC与其他先前工作中NoC的比较. 表3的上半部分列出了一些专用的NoC设计，它们通常用于一般片上系统（system on chip，SoC）中的数据传输需求，典型的应用场景包括处理器间的同步信号、缓存一致性协议等；表3的下半部分展示了一些用于神经形态平台的NoC设计，它们专注于满足神经网络计算的特定需求，通常包括SNN和ANN这2种应用场景，比如清华的异构融合类脑芯片Tianjic[13]在硬件上融合这2种神经网络的实现. 神经形态平台NoC上传输的数据类型包括脉冲数据和非脉冲数据，其设计核心在于高效的数据并行传输和多种数据类型的支持. 本文的ReB 路由器的带宽可以达到0.24 spike/cycle， 硬件实现面积仅为0.014 mm2. 此外，只有ReB路由策略支持混合模式的脉冲数据传输，并且具备无死锁和拥塞感知的自适应路由机制.
表 3 ReB与相关先进工作对比Table 3. Comparison of ReB and related advanced workNoC 类型 工艺/nm 拓扑结构 路由算法 有无死锁避免 带宽/(spike/cycle) 面积/mm2 MC-3DR（2019）[17] 专用NoC设计 45 3D mesh 混合模式，固定路由 × 0.250 0.031 TLAM（2023）[14] 45 分层结构 混合模式，固定路由 √ 0.086 0.070 Tianjic（2019）[13] 神经形态平
台的NoC设计28 2D mesh 单播，固定路由 √ - 0.008 LAMR（2022）[16] 28 2D mesh 混合模式，自适应路由 × 0.016 - MerLin（2023）[32] 55 Fullerene-60 混合模式，自适应路由 × 0.200 0.013 ReB（本文） 28 2D mesh 混合模式，自适应路由 √ 0.240 0.014 4. 结 论
本文提出了一种针对大规模神经形态平台设计的脑启发NoC方案. 所提出的无死锁ReB路由策略支持混合模式的传输和拥塞感知的路径选择. 突触连接索引方法为NoC架构提供了更好的可扩展性和更低的功耗. 实验结果表明，ReB NoC在延迟、吞吐量、信息成本和功耗之间实现了良好的平衡，为神经形态平台提供了一种更具生物学合理性的神经通信策略. 在未来，我们将基于该NoC研究更大规模的多层次众核互联架构和通信协议，能够容纳多种神经网络并支持任意神经元之间互联.
作者贡献声明：王智超负责方案设计、实验验证、论文撰写；陈亮负责理论指导、架构设计和论文修改；李千鹏负责论文修改，设计代码撰写；陈奥新负责论文修改，实验数据记录；刘昕负责设计代码；宋文娜负责实验验证.
-
![]()
图 1 （a）稀疏矩阵A；（b）矩阵A的CSR存储格式(上)及依赖图(下)；（c）MPK中的数据依赖
Figure 1. (a) Sparse matrix A; (b) The CSR format (top) and the dependency graph for A (bottom)； (c) Data dependencies in MPK
![]()
图 2 （a）Aix和Ai+1x之间的数据依赖; （b）对应于图3（b）的树数据结构.
注：其中方括号内数字为子矩阵行索引，[16, 24]和[24, 24]分别是第一次和第二次递归的分割子图.
Figure 2. (a) Data dependencies between Ai and Ai+1x; (b) The tree data structure. Numbers in the brackets indicate the starting and ending indices for matrix rows. [16, 24] and [24, 24] are the separators for the first and second recursions, respectively
![]()
图 3 (a)划分为4个子图及1个分割子图（未重排序）；(b)第二次递归后（含重排序）
Figure 3. (a) A graph partitioned into four subgraphs and one separator (without reordering)； (b) After two recursive partitions (with reordering)
![]()
图 4 以图3（b）为例给出了次幂s=5时Ca-MPK执行顺序的示意图
注：每个框代表一个子矩阵，框中数字为执行顺序，同一数字子矩阵可并行执行. 长方形虚框表示其中的子矩阵可在cache中重用
Figure 4. Diagram illustrating the execution of Fig.3(b) in Ca-MPK with the power s=5. Numbers in boxes indicate the execution order. Subgraphs with the same numbers are executed concurrently. Boxes in the same dotted rectangles indicate that subgraphs are reused in cache
![]()
图 5 不同MPK实现s=5（a）, s=10（b）and s=15（c）时302个矩阵在Intel 6258R CPU上时的性能对比
Figure 5. Performance comparison of different MPK implementations with s=5 (a), s=10 (b) and s=15 (c) using 302 sparse matrices on the Intel 6258R CPU
![]()
图 6 不同MPK实现s=5（a）, s=10（b）and s=15（c）时302个矩阵在Kunpeng 920 CPU上时的性能GFLOPS对比
Figure 6. Performance in GFLOPS for different MPK implementations s=5 (a), s=10 (b) and s=15 using 302 sparse matrices on the Kunpeng 920 CPU
![]()
图 7 不同MPK实现s=5（a）和s=15时（b）12个矩阵在Intel 6258R CPU上时的详细性能对比
注：右侧y轴给出了CG和BiCGStab求解器采用不同MPK实现时相对于基于MKL实现的加速比
Figure 7. Detailed performance comparison for different MPK implementations with s=5(a) and s=15(b) using 12 matrices on the Intel 6258R CPU. The right Y-axis indicates the speedup for solvers compared to MKL-based baseline
![]()
图 8 不同MPK实现s=5（a）和s=15（b）时12个矩阵在Kunpeng 920 CPU上时的详细性能对比
注：右侧y轴给出了CG和BiCGStab求解器采用不同MPK实现时相对于基于CSR实现的加速比
Figure 8. Detailed performance comparison for different MPK implementations with s=5(a) and s=15(b) using 12 matrices on the Kunpeng 920 CPU. The right Y-axis indicates the speedup for solvers compared to CSR-based baseline
![]()
图 9 Freescale1矩阵X86上主存和cache数据访问量(s=15)
Figure 9. Data traffic of memory and cache for Freescale1 on X86 (s=15)
表 1 12个代表性稀疏矩阵的详细性能分析
Table 1 Twelve Represented Sparse Matrices for Detailed Performance Analysis
编号 矩阵名称 行数 非零元数 对称正定 1 ASIC 320k 321 821 1 931 828 no 2 ASIC 320ks 321 671 1 316 085 no 3 ASIC 680ks 682 712 1 693 767 no 4 Freescale1 3 428 755 17 052 626 no 5 FullChip 2 987 012 26 621 983 no 6 G2 circui 150 102 726 674 yes 7 G3 circuit 1 585 478 7 660 826 yes 8 memchip 2 707 524 13 343 948 no 9 nxp1 414 604 2 656 177 no 10 pre2 659 033 5 834 044 no 11 rajat30 643 994 6 175 244 no 12 transient 178 866 961 790 no 
下载: 导出CSV
-
[1] Zhang Yichen, Li Shengguo, Yuan Fan, et al. Memory-aware optimization for sequences of sparse matrix-vector multiplications[C]//Proc of 2023 IEEE Int Parallel and Distributed Processing Symposium (IPDPS). Piscataway: IEEE, 2023: 379−389
[2] Alappat C, Hager G, Schenk O, et al. Level-based blocking for sparse matrices: sparse matrix-power-vector multiplication[J]. IEEE Transactions on Parallel and Distributed Systems, 2022, 34(2): 581−597
[3] Gurhem J, Vandromme M, Tsuji M, et al. Sequences of sparse matrix-vector multiplication on fugaku’s a64fx processors[C]//Proc of 2021 IEEE Int Conf on Cluster Computing (CLUSTER). Piscataway, NJ: IEEE, 2021: 751−758
[4] Saad Y. Numerical Methods for Large Eigenvalue Problems: Revised Edition[M]. Philly: SIAM, 2011
[5] Filippone S, Cardellini V, Barbieri D, et al. Sparse matrix-vector multiplication on gpgpus[J]. ACM Transactions on Mathematical Software, 2017, 43(4): 1−49
[6] Barrett R, Berry M, Chan T F, et al. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods[M]. Philly: SIAM, 1994
[7] Vuduc R W. Automatic Performance Tuning of Sparse Matrix Kernels[M]. Berkeley: University of California, 2003
[8] Buluç A, Fineman J T, Frigo M, et al. Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks[C]//Proc of the 21st Annual Symp on Parallelism in Algorithms and Architectures. New York: ACM, 2009: 233−244
[9] Demmel J, Hoemmen M, Mohiyuddin M, et al. Avoiding communication in computing krylov subspaces[R]. Berkeley: University of California, 2010
[10] Hoemmen M. Communication-Avoiding Krylov Subspace Methods[M]. Berkeley: University of California, 2007
[11] Carson E C. Communication-Avoiding Krylov Subspace Methods in Theory and Practice[M]. Berkeley: University of California, 2015
[12] Dongarra J, Tomov S, Luszczek P, et al. With extreme computing, the rules have changed[J]. Computing in Science & Engineering, 2017, 19(3): 52−62
[13] Mohiyuddin M, Hoemmen M, Demmel J, et al. Minimizing communication in sparse matrix solvers[C]//Proc of the Conference on High Performance Computing Networking, Storage and Analysis. New York: ACM, 2009: 1−12
[14] Morlan J, Kamil S, Fox A. Auto-tuning the matrix powers kernel with SEJITS[C]//Proc of 10th Int Conf High Performance Computing for Computational Science-VECPAR 2012. Berlin: Springer, 2013: 391−403
[15] Muranushi T, Makino J. Optimal temporal blocking for stencil computation[J]. Procedia Computer Science, 2015, 51(1): 1303−1312
[16] Huber D, Schreiber M, Schulz M. Graph-based multi-core higher-order time integration of linear autonomous partial differential equations[J]. Journal of Computational Science, 2021, 53(4): 101−139
[17] Alappat C, Basermann A, Bishop A R, et al. A recursive algebraic coloring technique for hardware-efficient symmetric sparse matrix-vector multiplication[J]. ACM Transactions on Parallel Computing, 2020, 7(3): 1−37
[18] Qiu Haozhong, Xu Chuanfu, Fang Jianbin, et al. Towards scalable unstructured mesh computations on shared memory many-cores[C]//Proc of the 29th ACM SIGPLAN Annual Symp on Principles and Practice of Parallel Programming. New York: ACM, 2024: 109−119
[19] Naumov M. S-step and communication-avoiding iterative methods[R]. Santa Clara: NVIDIA, 2016
[20] Karypis G, Kumar V. A fast and high quality multilevel scheme for partitioning irregular graphs[J]. SIAM Journal on scientific Computing, 1998, 20(1): 359−392 doi: 10.1137/S1064827595287997
[21] Intel Corporation. Intel oneapi math kernel library (onemkl)[EB/OL]. Santa Clara: Intel Corporation, 2024[2024-03-25]. https://www.intel.com/content/www/us/en/developer/tools/oneapi/onemkl.html.
[22] Davis T A, Hu Y. The university of florida sparse matrix collection[J]. ACM Transactions on Mathematical Software, 2011, 38(1): 1−25
[23] Treibig J, Hager G, Wellein G. Likwid: A lightweight performance-oriented tool suite for x86 multicore environments[C]//Proc of 2010 39th Int Conf on Parallel Processing Workshops. Piscataway, NJ: IEEE, 2010: 207−216
计量
- 文章访问数: 9
- HTML全文浏览量: 4
- PDF下载量: 3
