快速累加器

摘要

本申请实施例提供的快速累加器，包括：多组依次相接的加法模块，每组所述加法模块至少包括一个加法单元，所述加法单元包括一个加法器和一个寄存器，所述加法器与所述寄存器的输入端、输出端循环相接；除了第一组和最后一组所述加法模块，其余每组所述加法模块包括第一进位、第二进位、第一出位及第二出位；所述第二进位通过一个寄存器直接与前一组加法模块的第二出位相接。通过在组间的进位链上插入寄存器，从而明显降低关键路径，提升系统的频率上限。

说明书

技术领域

本申请涉及数字信号处理技术领域，尤其涉及快速累加器。

背景技术

为了提升数字信号处理系统的吞吐率，一般通过插入流水线降低系统的关键路径，从而提升系统的运行频率，进而提高吞吐率，其中关键路径是指电路中不经过寄存器单元的所有路径中时延最长的逻辑计算路径。插入流水线，即在电路的前馈割集上插入寄存器（割集是一个图中边的集合，移去这些边之后，图会成为不相连的图。而前馈割集上的所有边都指着前向，即输入到输出的方向）是优化无环路电路关键路径的有效方法。

然而，很多数字信号处理系统中涉及到如图1所示的累加器，累加器中涉及的迭代运算引入了环路，在此部分环路中直接插入寄存器会破坏计算的正确性，故累加器的路径时延很难降低，很容易成为系统关键路径优化中的瓶颈。

发明内容

为了满足系统的关键路径时延要求，降低累加器的路径时延，本申请通过以下实施例提供了快速累加器。

本申请第一方面提供了一种快速累加器，包括：多组依次相接的加法模块，每组所述加法模块至少包括一个加法单元，所述加法单元包括一个加法器和一个寄存器，所述加法器与所述寄存器的输入端、输出端循环相接；

除了第一组和最后一组所述加法模块，其余每组所述加法模块包括第一进位、第二进位、第一出位及第二出位；所述第一进位用于接收并输入待累加数据中相应比特位的数据，所述第二进位通过一个寄存器直接与前一组加法模块的第二出位相接；

第一组所述加法模块包括第一进位、第一出位及第二出位，最后一组所述加法模块包括第一进位、第二进位及第一出位；

针对第一组所述加法模块，所述第一出位直接接至所述快速累计器的输出端口；针对其余组所述加法模块，所述第一出位及所述第二进位均接至合并加法器的输入端，所述合并加法器的输出端接至所述快速累加器的输出端口。

可选的，若每组所述加法模块包括两个及以上所述加法单元，则所有所述加法单元中的加法器依次相接。

可选的，若每组所述加法模块包括两个及以上所述加法单元，则所述合并加法器还包括插零进位。

本申请第二方面提供了一种快速累加器，包括：多组依次相接的加法模块，每组所述加法模块至少包括一个加法单元，所述加法单元包括依次相接的第一加法器、第二加法器和寄存器，所述寄存器的输出端接至所述第二加法器的输入端；

除了第一组和最后一组所述加法模块，其余每组所述加法模块包括第一进位、第二进位、第三进位、第一出位、第二出位及第三出位；

所述第一进位为每个所述加法单元中所述第一加法器的输入端，用于接收并输入待累加数据中的相应比特位的数据，所述第二进位为最低位的加法单元中所述第一加法器的输入端，所述第二进位通过一个寄存器直接与前一组加法模块的第二出位相接；所述第三进位为最低位的加法单元中所述第二加法器的输入端，所述第三进位直接接至前一个加法模块的第一出位；所述第一出位为最高位的加法单元中第一加法器的输出端，第二出位为最高位的加法单元中第二加法器的输出端，第三出位为每个加法单元中寄存器的输出端；

第一组所述加法模块包括第一进位、第一出位、第二出位及第三出位，最后一组所述加法模块包括第一进位、第二进位、第三进位及第三出位；

针对第一组所述加法模块，所述第三出位直接接至所述快速累计器的输出端口；针对其余组所述加法模块，所述第三出位及所述第二进位均接至合并加法器的输入端，所述合并加法器的输出端接至所述快速累加器的输出端口。

可选的，若每组所述加法模块包括两个及以上所述加法单元，则所有所述加法单元中的第一加法器依次相接，第二加法器依次相接。

可选的，若每组所述加法模块包括两个及以上所述加法单元，则所述合并加法器还包括插零进位。

本申请实施例提供的快速累加器，包括：多组依次相接的加法模块，每组所述加法模块至少包括一个加法单元，所述加法单元包括一个加法器和一个寄存器，所述加法器与所述寄存器的输入端、输出端循环相接；除了第一组和最后一组所述加法模块，其余每组所述加法模块包括第一进位、第二进位、第一出位及第二出位；所述第二进位通过一个寄存器直接与前一组加法模块的第二出位相接。通过在组间的进位链上插入寄存器，从而明显降低关键路径，提升系统的频率上限。

附图说明

图1为现有引入环路的累加器结构示意图；

图2为本申请实施例公开的累加器及其前后输入输出部分的运算示意图；

图3为本申请实施例公开的一种快速累加器的结构示意图；

图4为本申请实施例公开的又一种快速累加器的结构示意图；

图5为本申请实施例公开的又一种快速累加器的结构示意图；

图6为本申请实施例公开的又一种快速累加器的结构示意图；

图7为本申请实施例公开的快速累加器中，8位加法器的三级流水线处理示例图；

图8为本申请实施例公开的快速累加器中，采用的低位宽加法器的结构示意图；

图9为本申请实施例公开的一组通道数为C的输入特征图与通道数为C的卷积核进行卷积运算的示意图。

具体实施方式

为便于对申请的技术方案进行，以下首先在对本申请所涉及到的一些概念进行说明。

数字信号处理系统中，累加器及其前后输入输出部分的运算参见图2所示，可描述为如下过程：

从系统其他部分产生的输出先输入至加法器（∑），相加结果可概括为两类：一路临时和与两路临时和。参见图2中的（a），一路临时和即图中的TS（temporal sum），参见图2中的（b），两路临时和即图中的TS

假设累加器的累加输出不超过N位。设共有T组输入，则将这T组输入连续累加T个周期后，得到两个部分和（partial sum）：一是和位寄存器（即保留每一位加法器“和线”上值的寄存器）保存的部分和：S=s

对于一路临时和的输入TS，假设其N个比特分别表示为I

参见图3及图4，本申请第一实施例公开的一种快速累加器，包括：多组依次相接的加法模块，每组所述加法模块至少包括一个加法单元，所述加法单元包括一个加法器和一个寄存器，所述加法器与所述寄存器的输入端、输出端循环相接。

除了第一组和最后一组所述加法模块，其余每组所述加法模块包括第一进位Ⅰ、第二进位Ⅱ、第一出位Ⅰ’及第二出位Ⅱ’；所述第一进位Ⅰ用于接收并输入待累加数据中相应比特位的数据，所述第二进位Ⅱ通过一个寄存器直接与前一组加法模块的第二出位Ⅱ’相接。

第一组所述加法模块包括第一进位Ⅰ、第一出位Ⅰ’及第二出位Ⅱ’，最后一组所述加法模块包括第一进位Ⅰ、第二进位Ⅱ及第一出位Ⅰ’。

针对第一组所述加法模块，所述第一出位Ⅰ’直接接至所述快速累计器的输出端口；针对其余组所述加法模块，所述第一出位Ⅰ’及所述第二进位Ⅱ均接至合并加法器的输入端，所述合并加法器的输出端接至所述快速累加器的输出端口。

需要说明的是，图3及图4中，仅在某一个加法模块中标出了每个进位及出位的符号，但这些符号对每个加法模块都通用。图中的“+”表示加法器，“D”表示寄存器。

若每组所述加法模块包括两个及以上所述加法单元，则所有所述加法单元中的加法器依次相接。

若每组所述加法模块包括两个及以上所述加法单元，则所述合并加法器还包括插零进位。

每组加法模块中所包含的加法单元数量由系统的关键路径要求决定。

在一种实现方式中，假如系统的关键路径要求不超过1个全加器时延，则每组加法 模块中仅包括一个加法单元，即累加器中的N位加法器中每一位进位链上都插入寄存器，如 图3所示。T轮累加结束后，寄存器寄存了全部N-1位的进位组成的部分和C，C与部分和S的高 N-1位通过一个合并加法器（通常经过特殊设计，可满足累加器整体的关键路径要求，下文 有详细介绍）进行相加，相加结果与最低位的和

在另一种实现方式中，假如系统的关键路径要求不超过2个全加器时延，则每组加法模块中包括两个加法单元，即累加器中的N位加法器分为每两位一组，每组间的进位链上插入寄存器，如图4所示。T轮累加结束后，每两位加法只缓存一个进位，故C与S累加前需插入0，形成C=c

假如系统的关键路径可以更长，可以如上类推，以更多位加法器为一组，在各组加法器之间的进位线插入寄存器进行运算，对于未插入寄存器的位数，通过在部分和相加时的相应位上插入0来完成最后的加法运算。

对于二路临时和的输入TS

参见图5及图6，本申请第二实施例公开的一种快速累加器，包括：多组依次相接的加法模块，每组所述加法模块至少包括一个加法单元，所述加法单元包括依次相接的第一加法器、第二加法器和寄存器，所述寄存器的输出端接至所述第二加法器的输入端。需要说明的是，第一加法器和第二加法器中的“第一”及“第二”是按照输入数据的传输方向所界定，数据最初输入至第一加法器中，然后从第一加法器传输至第二加法器。

除了第一组和最后一组所述加法模块，其余每组所述加法模块包括第一进位Ⅰ、第二进位Ⅱ、第三进位Ⅲ、第一出位Ⅰ’、第二出位Ⅱ’及第三出位Ⅲ’。

所述第一进位Ⅰ为每个所述加法单元中所述第一加法器的输入端，用于接收并输入待累加数据中的相应比特位的数据，所述第二进位Ⅱ为最低位的加法单元中所述第一加法器的输入端，所述第二进位Ⅱ通过一个寄存器直接与前一组加法模块的第二出位Ⅱ’相接；所述第三进位Ⅲ为最低位的加法单元中所述第二加法器的输入端，所述第三进位Ⅲ直接接至前一个加法模块的第一出位Ⅰ’；所述第一出位Ⅰ’为最高位的加法单元中第一加法器的输出端，第二出位Ⅱ’为最高位的加法单元中第二加法器的输出端，第三出位Ⅲ’为每个加法单元中寄存器的输出端。

第一组所述加法模块包括第一进位Ⅰ、第一出位Ⅰ’、第二出位Ⅱ’及第三出位Ⅲ’，最后一组所述加法模块包括第一进位Ⅰ、第二进位Ⅱ、第三进位Ⅲ及第三出位Ⅲ’。

针对第一组所述加法模块，所述第三出位Ⅲ’直接接至所述快速累计器的输出端口；针对其余组所述加法模块，所述第三出位Ⅲ’及所述第二进位Ⅱ均接至合并加法器的输入端，所述合并加法器的输出端接至所述快速累加器的输出端口。

需要说明的是，图5及图6中，仅在某一个加法模块中标出了每个进位及出位的符号，但这些符号对每个加法模块都通用。图中的“+”表示加法器，“D”表示寄存器。

若每组所述加法模块包括两个及以上所述加法单元，则所有所述加法单元中的第一加法器依次相接，第二加法器依次相接。

若每组所述加法模块包括两个及以上所述加法单元，则所述合并加法器还包括插零进位。

每组加法模块中所包含的加法单元数量由系统的关键路径要求决定。

在一种实现方式中，假如系统的关键路径要求不超过2个全加器时延，则每组加法 模块中仅包括一个加法单元，即在每一位的两个加法器（即第一加法器和第二加法器，分别 用于完成本位结果的累加与临时和的相加）中，在用于本位累加的加法器进位链（即第一加 法器对应的第二进位）上插入寄存器，如图5所示。T轮累加结束后，寄存器寄存了所有N-1位 的进位组成的部分和C，与部分和S的高N-1位通过合并加法器进行相加，相加结果与最低位 的和

假如系统的关键路径要求不超过3个全加器时延，同样采用如图5所示电路，可以最小硬件成本满足不高于3个全加器时延的要求。

假如系统的关键路径要求不超过4个全加器时延，则每组加法模块中包括两个加法单元，即以每2位加法为一组，每组之间在用于本位结果累加的加法器进位链（即首个加法单元中第一加法器对应的第二进位）上插入寄存器。如图6所示，T轮累加结束后，每2位加法缓存1个进位，故C与S累加前需要在未缓存进位的位上插入0，再与S的高N-2位通过合并加法器进行相加。得到的和与s

需要说明的是，图3至图6中，加法器和线上的si和进位线上ci信号经过寄存器后的输出信号与对应输入信号的表示符号相同。而实际上，这些对应信号只是在时间上差了一个周期时才等价（等值）。

在上述第一实施例和第二实施例公开的快速累加器中，C与S两个部分和相加加法器的关键路径还可以按照如下几种方案进行优化，以确保累加器模块整体的关键路径可满足系统时钟要求。

一种方案是，在优化后的累加器中，用于部分和C与S相加的合并加法器位于环路外部，只涉及纯前向路径。为了适配关键路径延时约束，可以对这一合并加法器适当的插入多级流水线，例如，参见图7，对于8bit的部分和相加，可按照每3位加法器插入一级流水线，相邻两级流水线间的加法器可根据时序、面积等约束选择某种低位宽的快速加法实现。

另一种方案是，考虑到优化后的累加器引入了新的合并加法器会带来额外的硬件消耗，对于面积约束严格的电路，可以通过如下两种方式降低其硬件复杂度。

1)根据图3至图6中的快速累加器结构，输入合并加法器的部分和C中插入了0，据此，可以重新推导合并加法器的输出逻辑，从而简化设计。

2)合并加法器可以采用一个低位宽加法器，将加数分组，多次迭代相加来完成最后相加结果的输出。假设低位宽加法器为4位，待加的与两个部分和均为8位，则实现方案如图8所示，图8中，T

本申请关键点在于在数字信号处理系统中引入一种新的累加器实现方案，从而明显降低关键路径，提升系统的频率上限。主要的关键点在于：

一、通过分组后在组间的进位链上插入寄存器，结合每一位加法器和线上插入的寄存器，可将累加器输出的生成分为两步，第一步累加生成两个部分和，分别是：由各和线寄存器保存的S=s

二、基于关键点一，进位链寄存器的插入方案可以根据系统的关键路径要求进行调整，从而用最少的额外硬件消耗满足对累加器模块的关键路径约束。

三、基于关键点一，用于部分和相加的加法器可以适当的插入多级流水线，流水线之间可采用快速加法器（如进位选择加法器，提前进位加法器等），以满足对累加器模块的关键路径约束。

基于上述的主要关键点，可以从根本上解决因累加器中环路带来的关键路径瓶颈问题。累加器外的纯前向路径，可以通过插入流水线等常规方法实现系统频率的提升。

结合图9，以卷积神经网络（CNN）中，一组输入特征图和相应的卷积核进行卷积运算的典型示例进行说明。

图9中表示了一组通道数为C的输入特征图与通道数为C的卷积核进行卷积运算的示意图，虚线箭头表示系统模块和本申请中设计方案中模块的对应关系。图9中采用输入通道维度并行的方案进行乘法计算，为简单起见，选用的并行度为4。在一组四个像素值（像素值即输入特征图上一个点的值）和相应的权重值乘法运算结束后，其结果通过4to2压缩器阵列得到两路临时和（temporal sum），输入到改进的累加器进行累加。在常用卷积核3*3配置下，累加9C/4次后可得到下一组特征图的一个像素值。设置累加器的输入为32bit，按照如上图4、图5的架构分别对累加器进行实现，用SMIC 55nm库做时序分析，具体结果如下表所示：

表1 累积器优化前后关键路径对比图

通过综合分析，现有技术中经过EDA工具深度优化的32bit累加器路径时延为2.17ns，整个CNN加速器的系统可达到的最高频率为460.8MHz。通过本申请公开的快速累加器，可以将该模块路径时延降至1.10ns，同步搭配系统其他模块的流水线处理等方案，系统频率最高可提升至909.1MHz，吞吐率可提升最高1.97倍。