FPGA硬件加速器中非乘加类计算操作的优化方法和优化系统

技术领域

本公开涉及硬件加速器领域，更具体地说，涉及FPGA硬件加速器中非乘加类计算操作的优化方法和优化系统。

背景技术

近年来，由于数据量和可访问性的快速增长，人工智能算法的重要性逐渐被工业界所认知。其中，基于深度神经网络的人工智能算法在图片、语音和视频处理等方面展现出了较高的准确率，受到了业界的极大关注。然而，这些深度神经网络往往参数量巨大，结构复杂，需要大量计算资源来进行训练和推理，这使得传统的算力架构显得处处捉襟见肘。而随着深度神经网络在无人驾驶、医疗、教育等关键领域深入落地，这些多样化的场景中高并发、实时性的需求又进一步对计算深度神经网络所需的算力提出了更高的要求。

具体地，深度神经网络常常包含多种计算操作，例如，乘加类和非乘加类的计算操作。乘加类的计算操作在批量计算时往往可以转化为矩阵乘法，在硬件实现中经由高效的乘加器阵列进行运算。而对于非乘加类的计算操作，由于其种类多样、计算各异，在硬件加速中往往需要实现多种不同的电路以进行加速计算。现有解决方案或是无法支持多种网络，或是计算性能有限，无法满足不断涌现的新型网络和日益增长的算力需求。

发明内容

本公开的示例性实施例可至少解决上述问题，也可不解决上述问题。

根据本公开的一方面，提供一种FPGA硬件加速器中非乘加类计算操作的优化方法，包括：通过将非乘加类计算操作拆解为多个基础运算，生成第一计算图；通过将第一计算图中的连续基础运算合并，获得至少一个合并运算；基于第一计算图和所述至少一个合并运算，生成第二计算图；按照第二计算图在所述FPGA硬件加速器中执行运算；其中，所述按照第二计算图在所述FPGA硬件加速器中执行运算，包括：利用流水线优化执行所述至少一个合并运算的每个合并运算。

可选地，所述将第一计算图中的连续基础运算合并，获得至少一个合并运算，可包括：基于FPGA硬件加速器的资源总量和所述多个基础运算所需的第一资源使用量，利用贪心算法探索能够合并的连续基础运算的组合；将探索到的能够合并的连续基础运算的组合合并为合并运算。

可选地，所述基于FPGA硬件加速器的资源总量和所述多个基础运算所需资源使用量，利用贪心算法探索能够合并的连续基础运算的组合，可包括：循环执行以下操作，直到结束探索：(1)搜索第一计算图中所有的连续基础运算的候选组合；(2)计算所有候选组合的用于反映加速效果的加速因子；(3)根据计算出的加速因子对所有候选组合进行排序；(4)获取排序结果中加速因子最大的候选组合所需的第二资源使用量；(5)判断第一资源使用量和第二资源使用量之和是否超过所述资源总量；(6)当第一资源使用量和第二资源使用量之和未超过所述资源总量时，将所述加速因子最大的候选组合确定为能够合并的组合，并基于该候选组合，更新第一计算图和第一资源使用量；(7)当第一资源使用量和第二资源使用量之和超过所述资源总量时，判断是否存在其它未探索的候选组合，如果存在，则将排序结果中加速因子仅次于当前候选组合的候选组合更新为所述排序结果中加速因子最大的候选组合并跳转至操作(4)，如果不存在，则结束探索。

可选地，所述计算所有候选组合的用于反映加速效果的加速因子，可包括：针对每个候选组合，计算候选组合在第一计算图中的平均所需运算时间周期数、平均计算数据项数量、出现次数，并将这三者相乘，作为该候选组合的加速因子。

可选地，所述更新第一资源使用量，可包括：将第一资源使用量更新为第一资源使用量与第二资源使用量之和。

可选地，利用流水线优化执行所述至少一个合并运算中的每个合并运算，可包括：针对每个合并运算，将合并运算的计算过程分解为不同的流水线阶段，在每个时钟周期并行执行不同的流水线阶段。

可选地，所述FPGA硬件加速器可为深度神经网络加速器。

根据本公开的另一方面，提供一种FPGA硬件加速器中非乘加类计算操作的优化系统，包括：计算图生成装置；运算执行装置；其中，计算图生成装置被配置为：通过将非乘加类计算操作拆解为多个基础运算，生成第一计算图，通过将第一计算图中的连续基础运算合并，获得至少一个合并运算，基于第一计算图和所述至少一个合并运算，生成第二计算图；其中，运算执行装置被配置为：按照第二计算图在所述FPGA硬件加速器中执行运算；其中，运算执行装置利用流水线优化执行所述至少一个合并运算中的每个合并运算。

可选地，计算图生成装置可被配置为：基于FPGA硬件加速器的资源总量和所述多个基础运算所需的第一资源使用量，利用贪心算法探索能够合并的连续基础运算的组合；将探索到的能够合并的连续基础运算的组合合并为合并运算。

可选地，计算图生成装置可被配置为：循环执行以下操作，直到结束探索：(1)搜索第一计算图中所有的连续基础运算的候选组合；(2)计算所有候选组合的用于反映加速效果的加速因子；(3)根据计算出的加速因子对所有候选组合进行排序；(4)获取所述候选组合列表中第一个候选组合所需的第二资源使用量；(5)判断第一资源使用量和第二资源使用量之和是否超过所述资源总量；(6)当第一资源使用量和第二资源使用量之未超过所述资源总量时，将所述加速因子最大的候选组合确定为能够合并的组合，并基于该候选组合，更新第一计算图和第一资源使用量；(7)当第一资源使用量和第二资源使用量之和超过所述资源总量时，判断是否存在其它未探索的候选组合，如果存在，则将排序结果中加速因子仅次于当前候选组合的候选组合更新为所述排序结果中加速因子最大的候选组合并跳转至操作(4)，如果不存在，则结束探索。

可选地，计算图生成装置可被配置为：针对每个候选组合，计算候选组合在第一计算图中的平均所需运算时间周期数、平均计算数据项数量、出现次数，并将这三者相乘，作为该候选组合的加速因子。

可选地，计算图生成装置可被配置为：将第一资源使用量更新为第一资源使用量与第二资源使用量之和。

可选地，运算执行装置可被配置为：针对每个合并运算，将合并运算的计算过程分解为不同的流水线阶段，在每个时钟周期并行执行不同的流水线阶段。

可选地，所述FPGA硬件加速器可为深度神经网络加速器。

根据本公开的另一方面，提供一种包括至少一个计算装置和至少一个存储指令的存储装置的系统，其中，所述指令在被所述至少一个计算装置运行时，促使所述至少一个计算装置执行由计算图生成装置执行的操作。

根据本公开的另一方面，提供一种存储指令的计算机可读存储介质，其中，当所述指令被至少一个计算装置运行时，促使所述至少一个计算装置执行由计算图生成装置执行的操作。

根据本公开的示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化方法和优化系统，将非乘加类计算操作拆分为多个基础计算，并在所述多个基础计算的基础上采用合并计算结合流水线优化的方案，不仅提高非乘加类计算的运算性能，还增加硬件加速器的可通用性和可扩展性。

此外，根据本公开的示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化方法和优化系统，基于FPGA器件可重复擦写的特性，有效地探索计算图中多次重复出现的连续计算组合，从而提高硬件资源的使用率，以提升FPGA上深度神经网络加速性的性能。

附图说明

通过结合附图，从实施例的下面描述中，本公开这些和/或其它方面及优点将会变得清楚，并且更易于理解，其中：

图1是根据本公开的示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化方法的流程图。

图2是示出根据本公开的示例性实施例的合并运算的示意图。

图3是示出根据本公开的示例性实施例的流水线优化的示意图。

图4是示出根据本公开的示例性实施例的探索合并运算的方法的流程图。

图5是根据本公开的示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化系统的框图。

具体实施方式

提供参照附图的以下描述以帮助对由权利要求及其等同物限定的本公开的实施例的全面理解。包括各种特定细节以帮助理解，但这些细节仅被视为是示例性的。因此，本领域的普通技术人员将认识到在不脱离本公开的范围和精神的情况下，可对描述于此的实施例进行各种改变和修改。此外，为了清楚和简洁，省略对公知的功能和结构的描述。

在此需要说明的是，在本公开中出现的“若干项之中的至少一项”均表示包含“该若干项中的任意一项”、“该若干项中的任意多项的组合”、“该若干项的全体”这三类并列的情况。例如“包括A和B之中的至少一个”即包括如下三种并列的情况：(1)包括A；(2)包括B；(3)包括A和B。又例如“执行步骤一和步骤二之中的至少一个”，即表示如下三种并列的情况：(1)执行步骤一；(2)执行步骤二；(3)执行步骤一和步骤二。

深度神经网络是一类包含多种计算操作的神经网络结构，输入的数据需要依次通过神经网络中各种计算操作的运算，以获得网络所需要的运算结果。目前流行的深度神经网络中不同层与层之间的结构往往各不相同，其包含的计算操作也各有差异，需要使用不同的计算步骤以及计算方法进行计算。

传统算力构架大多基于中央处理器。但由于中央处理器是一种通用型硬件，为了满足其通用性的需求，中央处理器芯片上的大量硬件资源被用来实现复杂的调度设计和控制系统。这些硬件资源的占用不仅降低了计算的性能，也增加了计算时的额外功耗。为了追求更高的性能及更低的功耗，更多的设计开始采用以ASIC、FPGA等专用硬件为基础的解决方案。通过降低通用能力，这些专用硬件芯片能够有针对性的对深度神经网络计算中的瓶颈部分进行优化和算力提升，提供了一种通往处理能力和高能效的坦途。

在深度神经网络加速器的硬件实现中，我们往往需要在硬件上实现不同结构的硬件电路以进行加速。这些深度神经网络常常包含大量的乘加类计算操作，这些乘加类计算操作以乘加计算为基本运算单元，在批量计算时往往可以转化为矩阵乘法进行运算。常见的深度网络硬件加速器均会在片上实现独立的矩阵乘法器单元，得以高效快速的执行这些矩阵乘法运算。

与此同时，常见的深度神经网络中也包含着众多不以乘加计算为基础的计算操作。由于这些操作的基础计算单元并不是乘加器，使得我们无法使用深度神经网络加速器中常见的乘加器阵列(例如矩阵乘法计算器)来进行加速运算。但这些非乘加类计算操作往往穿插串联在乘加类计算操作之间，共同构成了整个神经网络的脉络。对于深度神经网络这类的网络计算结构，输入的数据需要依次通过网络中各种计算操作的运算，才能获得最后所需要的结果，这也使得我们难以跳过或者延迟这些非乘加类计算。根据所选深度神经网络的不同，这些非乘加类计算操作往往数量各异，计算结构也不尽相同，用以加速计算它们所需的计算电路也不尽相同，这大大提高了通用型深度神经网络硬件加速器的设计难度。此外，随着人们对深度神经网络研究的深入，以及各种新型深度神经网络结构不断涌现，这些非乘加类计算操作的种类、多样性也日渐增加。由于这些不同的非乘加类计算操作往往需要不同的硬件加速实现，这对通用型深度神经网络硬件加速器的设计实现也带来了更多的难度与挑战。

在现有的FPGA深度神经网络硬件加速方案中，解决这一问题往往应用以下几种方案。

这种方案在设计时需要考虑所选网络中所有可能出现的计算操作，通过为每一种可能出现的计算操作设计他们专用的硬件加速电路，来实现对于所选深度神经网络的支持。这种解决方案的优点在于：由于网络中每种计算操作都由定制设计的硬件电路进行加速，往往可以达到理想的性能与功耗指标。但是这种方案也有以下缺点：1、由于硬件片上资源的限制，加速器中可以实现的计算操作类型有限。2、由于无法穷举实现所有的计算操作，使用这种方案的硬件加速器往往只能支持有所选择的网络或者常见标准网络。3、这类实现往往无法支持新开发的网络。

这种方案利用了软硬一体设计中软硬件协同工作的优势，将硬件加速器中没有实现的计算操作分配至中央处理器进行运算。由于中央处理器是一种通用型的计算设备，理论上这种方案可以支持任何计算操作。同时由于许多深度神经网络中大量的运算集中于乘加类计算操作，分配到中央处理器的运算量可能不大，所以不一定会带来过高的性能损失。然而，由于深度神经网络具有依次计算的特性，在这种方案下，我们不可避免的需要将运算数据在硬件加速器和中央处理器中进行相互传输。根据通信架构的不同，这种方案将可能会产生巨大的额外通信开销，影响总体性能。

这种方案在软件侧将非乘加类计算操作拆分为类似于加、减、乘、取大小之类的基础运算，然后通过依次执行这些基础运算，来完成原有计算操作所需的计算功能。由于基础运算的类型有限，根据这种方案设计的硬件加速器可以在硬件上实现所有需要的基础运算，以支持绝大多数的深度神经网络。同时，由于这些基础运算的电路的实现相对简单，这种方案也不需要大量的片上硬件资源。这种方案的缺点是：由于每个非乘加计算操作往往都需要经过多个基础运算来依次执行，这种运算方式的计算性能较弱。一旦非乘加类计算操作在整个网络中占比较高，这种方案将大大降低所实现硬件加速器的加速性能。

本公开为了提高非乘加类计算的运算性能，同时又增加硬件加速器的可通用性和可扩展性，在将非乘加类计算操作拆分为多个基础计算的现有方案的基础上，通过采用合并计算结合流水线优化的方案，提出了一种FPGA硬件加速器中非乘加类计算操作的优化方法和优化系统，从计算图运算执行层面优化加速器性能，可应用于一个或多个FPGA设备中对于深度神经网络的加速。此外，本公开基于FPGA中硬件资源的限制和合并运算在计算图中重复出现的特性，提出了完整的对非乘加类计算操作进行合并优化的探索流程，通过平衡资源利用以及优化效果，有效地提升基于FPGA的深度神经网络加速器的加速性能。此外，本公开提出的FPGA硬件加速器中非乘加类计算操作的优化方法和优化系统不仅可用于深度神经网络的FPGA硬件加速器，还可用于任何在乘加类计算操作的同时还需要较大量的不同类型的非乘加类计算操作的任何网络或模型的FPGA硬件加速器。

下面，将参照图1至图5详细地描述根据本公开的示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化方法和优化系统。

图1是根据本公开的示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化方法的流程图。

参照图1，在步骤101，通过将非乘加类计算操作拆解为多个基础运算，生成第一计算图。在步骤102，通过将第一计算图中的连续基础运算合并，获得至少一个合并运算。在步骤103，基于第一计算图和所述至少一个合并运算，生成第二计算图。下面将详细描述步骤101至步骤103。

在工程实践中，可在软件解析中把非乘加类计算操作拆解为诸如加、减、乘、取大小等的基础运算，从而生成第一计算图。如果在硬件加速器上按照拆解后的基础运算依次执行运算，第一计算图中将产生大量新的基础运算，这些基础运算往往穿插在矩阵乘法计算之间。由于硬件加速器需要依次执行这些基础运算，其加速性能将收到影响。由于这些基础运算在计算图中连续执行，可以尝试将其合并成为一组操作，并应用流水线优化，由于流水线优化能够给大大提升组合运算的性能，通过这种方法，可以有效提升硬件加速器的性能。

由于这些组合后的“合并运算”具有其独立的运算顺序和运算逻辑，这些新生成的合并运算往往无法复用之前基础运算的硬件电路进行计算。也就是说，需要在硬件加速器上部署新的运算电路来进行执行这些合并运算。同样的，由不同顺序、类型的基础运算所合成的合并运算之间也无法复用相同的计算电路。如果在应用合并优化后生成了多种合并运算，如合并运算A、合并运算B、合并运算C……，则需要在硬件优化器中为每一种合并运算生成其对应的运算电路。

例如，图2是示出根据本公开的示例性实施例的合并运算的示意图。其中，图2中的(a)示出将非乘加类计算操作拆解为多个基础运算而生成的第一计算图，图2中的(b)示出通过合并运算而生成的第二计算图。

根据本公开的示例性实施例，可将第一计算图中的重复多次出现的连续基础运算合并以获得合并运算，并基于第一计算图和获得的合并运算，重新生成新的计算图，即，第二计算图。例如，如图2所示，在第一计算图中，运算2和运算3是连续的基础运算，重复多次出现，且运算种类和运算顺序都一致，因此，可将第一计算图中的运算2和运算3合并，以获得合并运算A，从而生成第二计算图。对于这样重复的合并运算A，可复用相同的硬件电路进行加速运算。

根据本公开的另一示例性实施例，可将第一计算图中的任何在合并后基于流水线优化能够提高加速性能的连续基础运算合并以获得合并运算，并基于第一计算图和获得的合并运算，重新生成新的计算图，即，第二计算图。将在后面描述合并优化的探索流程。

返回参照图1，在步骤104，按照第二计算图在所述FPGA硬件加速器中执行运算，其中，利用流水线优化执行所述至少一个合并运算的每个合并运算。

流水线优化是硬件实现中一种常见的优化方法。流水线优化通过在不同步骤上重叠操作，使得多个操作可以并行地加以执行，从而大大的提升了整体程序的运行速度，也能够有效提高硬件资源的利用效率。例如，在有限状态机类的传统计算执行方式下，硬件加速器完成一组操作往往需要多个时钟周期。假设每个操作需要1个时钟周期，对N个数据项执行一组M个操作则需要N×M个时钟周期。在应用流水线优化之后，对N个数据项执行一组M个操作现在只需要N+M-1个时钟周期。因此，在硬件加速器的设计中，大量应用了流水线优化，提高了计算的性能。对于连续基础运算，虽然每种运算所需的时钟周期不同，但可以将这些连续基础运算合并成为一组操作(即，合并运算)，通过在细分步骤中重叠操作，应用流水线优化，能够大大提高计算性能。

根据本公开的示例性实施例，针对每个合并运算，可将合并运算的计算过程分解为不同的流水线阶段，在每个时钟周期并行执行不同的流水线阶段。例如，图3是示出根据本公开的示例性实施例的流水线优化的示意图。其中，图3中的(a)示出针对各数据项执行连续基础运算的周期图，图3中的(b)示出在将连续基础运算合并后应用流水线优化执行运算的周期图。

参照图3，假设连续基础运算包括计算1、计算2和计算3，计算1需要6个时钟周期、计算2需要4个时钟周期，计算3需要7个时钟周期。如图3中的(a)所示，在按照原计算图(例如，第一计算图)执行运算的情况下，完成3个数据项的运算总共需要(3×(6+4+7)＝51)个时钟周期。如图3中的(b)所示，在将计算1、计算2和计算3合并成合并运算以生成新的计算图(例如，第二计算图)，在按照第二计算图执行运算时利用流水线优化对该合并运算进行优化，完成同样的计算则只需要(3+6+4+7-1＝19)个时钟周期，这大大提升了加速器的性能。

下面将具体描述获得合并运算的探索流程。

根据本公开的示例性实施例的获得合并运算的探索流程基于FPGA器件可重复擦写的特性，有效地挖掘出计算图中多次重复出现的连续计算组合进行合并。在FPGA片上可用资源的范围内，尽可能提高硬件资源的使用率，以提升FPGA上深度神经网络加速性的性能。

根据本公开的示例性实施例，基于FPGA硬件加速器的资源总量S和第一计算图中包括的多个基础运算所需的第一资源使用量U，利用贪心算法探索能够合并的连续基础运算的组合，并将探索到的能够合并的连续基础运算的组合合并为合并运算。这里，FPGA硬件加速器的资源总量S可基于FPGA硬件的相关参数表中指示的资源总量来确定。第一计算图中包括的多个基础运算所需的第一资源使用量U可基于在FPGA硬件加速器中按第一计算图执行运算所占用的资源来确定。

下面将参照图4具体描述根据本公开的示例性实施例的探索能够合并的连续基础运算的组合的方法。图4是示出根据本公开的示例性实施例的探索合并运算的方法的流程图。

参照图4，在步骤401，可搜索第一计算图中所有的连续基础运算的候选组合。例如，可通过穷举法搜索第一计算图中所有的可能合并的连续基础运算作为候选组合。当然，本公开不限于此，还可根据用户需求使用任何可行的搜索方法。

在步骤402，可计算所有候选组合的用于反映加速效果的加速因子。

根据本公开的示例性实施例，对于计算图中的一组能够合并的连续运算组合，假设其平均所需运算时间周期数为T、平均计算数据项个数为N，出现次数为R，则对其合并且采用流水线优化后所减少的时钟周期数为R(T×N-N-T+1)，这里，T，N＞＞1。因此，可将加速因子定义为F＝R×T×N。加速因子越大，表明优化后减少的时钟周期数最大，加速效果也越好。也就是说，针对每个候选组合，计算候选组合在第一计算图中的平均所需运算时间周期数、平均计算数据项数量、出现次数，并将这三者相乘，作为该候选组合的加速因子。当然，本公开不限于此，还可使用任何可行的方案来定义用于反映加速效果的加速因子。

在步骤403，可根据计算出的加速因子对所有候选组合进行排序。例如，可按加速因子的降序对所有候选组合进行排序以生成候选组合列表，也就是说，在该候选组合列表中，加速因子越大的候选组合排在越前面。当然，本公开不限于此，还可使用任何可行的方案来对所有候选组合排序。

在步骤404，可获取排序结果中加速因子最大的候选组合所需的第二资源使用量A。这里，第二资源使用量A可基于在FPGA硬件加速器中利用流水线优化执行该候选组合所占用的资源来确定。例如，当在按加速因子的降序排列的候选组合列表中，可获取候选组合列表中第一个候选组合所需的第二资源使用量。

在步骤405，可判断第一资源使用量U和第二资源使用量A之和是否超过FPGA硬件加速器的资源总量S。即，判断是否U+A>S。

在步骤406，当第一资源使用量U和第二资源使用量A之和未超过FPGA硬件加速器的资源总量S，即，U+A≤S时，可将该加速因子最大的候选组合(例如，在按加速因子的降序排列的候选组合列表中的第一个候选组合)确定为能够合并的组合，并基于该候选组合，更新第一计算图和第一资源使用量U。

这里，当U+A≤S时，说明该FPGA硬件加速器有能力运行更新后的计算图(即，以原硬件电路运行原计算图+以新硬件电路运行该候选组合)，则可将该候选组合确定为能够合并的组合，引入该候选组合作为新的合并运算。每当引入新的合并运算，都需要基于当前第一计算图和新的合并运算，来重新生成新的第一计算图，即，更新第一计算图，并且还需要将第一资源使用量更新为当前第一资源使用量与第二资源使用量之和，即，U＝U+A。然后，才进入下一次探索。

在步骤407，当第一资源使用量U和第二资源使用量A之和超过FPGA硬件加速器的资源总量S，即，U+A＞S时，可判断是否存在其它未探索的候选组合。如果存在，则在步骤408，可将排序结果中加速因子仅次于当前候选组合的候选组合更新为排序结果中加速因子最大的候选组合(例如，在按加速因子的降序排列的候选组合列表中，当前候选组合的下一个候选组合)并跳转至步骤404。如果不存在，则在步骤409，可结束探索。

这里，当U+A＞S时，说明该FPGA硬件加速器没有能力运行更新后的计算图(即，以原硬件电路运行原计算图+以新硬件电路运行该候选组合)，则可放弃该候选组合，并探索下一个加速因子次优的候选组合，即，针对下一个候选组合，执行步骤404至406或者步骤404、405、407和408或者步骤404、405、407和409。以此类推。

此外，当在步骤406，第一计算图被更新后，需要重新搜索并排序更新后的第一计算图中的所有可能的候选组合，并执行相同的探索方案。也就是说，可循环地执行步骤401至409，直到结束探索。

图5是根据本公开的示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化系统的框图。

参照图5，根据本公开的示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化系统500(下面，简称为优化系统500)包括计算图生成装置501和运算执行装置502。

计算图生成装置501可通过将非乘加类计算操作拆解为多个基础运算，生成第一计算图，通过将第一计算图中的连续基础运算合并，获得至少一个合并运算，并基于第一计算图和所述至少一个合并运算，生成第二计算图。根据本公开的示例性实施例，计算图生成装置501可包括第一计算图生成单元(未示出)、合并运算获取单元(未示出)和第二计算图生成单元(未示出)，其中，第一计算图生成单元用于通过将非乘加类计算操作拆解为多个基础运算，生成第一计算图，合并运算获取单元用于通过将第一计算图中的连续基础运算合并，获得至少一个合并运算，第二计算图生成单元用于基于第一计算图和所述至少一个合并运算，生成第二计算图。下面将详细描述计算图生成装置501(例如，第一计算图生成单元、合并运算获取单元和第二计算图生成单元)的操作。

在工程实践中，计算图生成装置501(例如，第一计算图生成单元)可在软件解析中把非乘加类计算操作拆解为诸如加、减、乘、取大小等的基础运算，从而生成第一计算图。如果在硬件加速器上按照拆解后的基础运算依次执行运算，第一计算图中将产生大量新的基础运算，这些基础运算往往穿插在矩阵乘法计算之间。由于硬件加速器需要依次执行这些基础运算，其加速性能将收到影响。由于这些基础运算在计算图中连续执行，可以尝试将其合并成为一组操作，并应用流水线优化，由于流水线优化能够给大大提升组合运算的性能，通过这种方法，可以有效提升硬件加速器的性能。

由于这些组合后的“合并运算”具有其独立的运算顺序和运算逻辑，这些新生成的合并运算往往无法复用之前基础运算的硬件电路进行计算。也就是说，需要在硬件加速器上部署新的运算电路来进行执行这些合并运算。同样的，由不同顺序、类型的基础运算所合成的合并运算之间也无法复用相同的计算电路。如果在应用合并优化后生成了多种合并运算，如合并运算A、合并运算B、合并运算C……，则需要在硬件优化器中为每一种合并运算生成其对应的运算电路。

根据本公开的示例性实施例，计算图生成装置501(例如，合并运算获取单元)可将第一计算图中的重复多次出现的连续基础运算合并以获得合并运算，并计算图生成装置501(例如，第二计算图生成单元)可基于第一计算图和获得的合并运算，重新生成新的计算图，即，第二计算图。例如，如图2所示，在第一计算图中，运算2和运算3是连续的基础运算，重复多次出现，且运算种类和运算顺序都一致，因此，可将第一计算图中的运算2和运算3合并，以获得合并运算A，从而生成第二计算图。对于这样重复的合并运算A，可复用相同的硬件电路进行加速运算。

根据本公开的另一示例性实施例，计算图生成装置501(例如，合并运算获取单元)可将第一计算图中的任何在合并后基于流水线优化能够提高加速性能的连续基础运算合并以获得合并运算，并计算图生成装置501(例如，第二计算图生成单元)可基于第一计算图和获得的合并运算，重新生成新的计算图，即，第二计算图。将在后面描述合并运算获取单元合并优化的探索流程。

运算执行装置502可按照第二计算图在所述FPGA硬件加速器中执行运算，其中，利用流水线优化执行所述至少一个合并运算的每个合并运算。

流水线优化是硬件实现中一种常见的优化方法。流水线优化通过在不同步骤上重叠操作，使得多个操作可以并行地加以执行，从而大大的提升了整体程序的运行速度，也能够有效提高硬件资源的利用效率。例如，在有限状态机类的传统计算执行方式下，硬件加速器完成一组操作往往需要多个时钟周期。假设每个操作需要1个时钟周期，对N个数据项执行一组M个操作则需要N×M个时钟周期。在应用流水线优化之后，对N个数据项执行一组M个操作现在只需要N+M-1个时钟周期。因此，在硬件加速器的设计中，大量应用了流水线优化，提高了计算的性能。对于连续基础运算，虽然每种运算所需的时钟周期不同，但可以将这些连续基础运算合并成为一组操作(即，合并运算)，通过在细分步骤中重叠操作，应用流水线优化，能够大大提高计算性能。

根据本公开的示例性实施例，运算执行装置502针对每个合并运算，可将合并运算的计算过程分解为不同的流水线阶段，在每个时钟周期并行执行不同的流水线阶段。

下面将具体描述计算图生成装置501(例如，合并运算获取单元)获得合并运算的探索流程。

根据本公开的示例性实施例的计算图生成装置501(例如，合并运算获取单元)获得合并运算的探索流程基于FPGA器件可重复擦写的特性，有效地挖掘出计算图中多次重复出现的连续计算组合进行合并。在FPGA片上可用资源的范围内，尽可能提高硬件资源的使用率，以提升FPGA上深度神经网络加速性的性能。

根据本公开的示例性实施例，计算图生成装置501(例如，合并运算获取单元)可基于FPGA硬件加速器的资源总量S和第一计算图中包括的多个基础运算所需的第一资源使用量U，利用贪心算法探索能够合并的连续基础运算的组合，并将探索到的能够合并的连续基础运算的组合合并为合并运算。这里，FPGA硬件加速器的资源总量S可基于FPGA硬件的相关参数表中指示的资源总量来确定。第一计算图中包括的多个基础运算所需的第一资源使用量U可基于在FPGA硬件加速器中按第一计算图执行运算所占用的资源来确定。

计算图生成装置501(例如，合并运算获取单元)可执行如图4所示的根据本公开的示例性实施例的探索能够合并的连续基础运算的组合的方法。即，计算图生成装置501(例如，合并运算获取单元)可执行以下步骤：

在步骤401，可搜索第一计算图中所有的连续基础运算的候选组合。例如，可通过穷举法搜索第一计算图中所有的可能合并的连续基础运算作为候选组合。当然，本公开不限于此，还可根据用户需求使用任何可行的搜索方法。

在步骤402，可计算所有候选组合的用于反映加速效果的加速因子。

根据本公开的示例性实施例，对于计算图中的一组能够合并的连续运算组合，假设其平均所需运算时间周期数为T、平均计算数据项个数为N，出现次数为R，则对其合并且采用流水线优化后所减少的时钟周期数为R(T×N-N-T+1)，这里，T，N＞＞1。因此，可将加速因子定义为F＝R×T×N。加速因子越大，表明优化后减少的时钟周期数最大，加速效果也越好。也就是说，针对每个候选组合，计算候选组合在第一计算图中的平均所需运算时间周期数、平均计算数据项数量、出现次数，并将这三者相乘，作为该候选组合的加速因子。当然，本公开不限于此，还可使用任何可行的方案来定义用于反映加速效果的加速因子。

在步骤403，可根据计算出的加速因子对所有候选组合进行排序。例如，可按加速因子的降序对所有候选组合进行排序以生成候选组合列表，也就是说，在该候选组合列表中，加速因子越大的候选组合排在越前面。当然，本公开不限于此，还可使用任何可行的方案来对所有候选组合排序。

在步骤404，可获取排序结果中加速因子最大的候选组合所需的第二资源使用量A。这里，第二资源使用量A可基于在FPGA硬件加速器中利用流水线优化执行该候选组合所占用的资源来确定。例如，当在按加速因子的降序排列的候选组合列表中，可获取候选组合列表中第一个候选组合所需的第二资源使用量。

在步骤405，可判断第一资源使用量U和第二资源使用量A之和是否超过FPGA硬件加速器的资源总量S。即，判断是否U+A>S。

在步骤406，当第一资源使用量U和第二资源使用量A之和未超过FPGA硬件加速器的资源总量S，即，U+A≤S时，可将该加速因子最大的候选组合(例如，在按加速因子的降序排列的候选组合列表中的第一个候选组合)确定为能够合并的组合，并基于该候选组合，更新第一计算图和第一资源使用量U。

这里，当U+A≤S时，说明该FPGA硬件加速器有能力运行更新后的计算图(即，以原硬件电路运行原计算图+以新硬件电路运行该候选组合)，则可将该候选组合确定为能够合并的组合，引入该候选组合作为新的合并运算。每当引入新的合并运算，都需要基于当前第一计算图和新的合并运算，来重新生成新的第一计算图，即，更新第一计算图，并且还需要将第一资源使用量更新为当前第一资源使用量与第二资源使用量之和，即，U＝U+A。然后，才进入下一次探索。

在步骤407，当第一资源使用量U和第二资源使用量A之和超过FPGA硬件加速器的资源总量S，即，U+A＞S时，可判断是否存在其它未探索的候选组合。如果存在，则在步骤408，可将排序结果中加速因子仅次于当前候选组合的候选组合更新为排序结果中加速因子最大的候选组合(例如，在按加速因子的降序排列的候选组合列表中，当前候选组合的下一个候选组合)并跳转至步骤404。如果不存在，则在步骤409，可结束探索。

这里，当U+A＞S时，说明该FPGA硬件加速器没有能力运行更新后的计算图(即，以原硬件电路运行原计算图+以新硬件电路运行该候选组合)，则可放弃该候选组合，并探索下一个加速因子次优的候选组合，即，针对下一个候选组合，执行步骤404至406或者步骤404、405、407和408或者步骤404、405、407和409。以此类推。

此外，当在步骤406，第一计算图被更新后，需要重新搜索并排序更新后的第一计算图中的所有可能的候选组合，并执行相同的探索方案。也就是说，计算图生成装置501(例如，合并运算获取单元)可循环地执行步骤401至409，直到结束探索。

根据本公开的示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化方法和优化系统可用于深度神经网络加速器中非乘加类计算操作。然而，本公开不限于此，根据本公开的示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化方法和优化系统还可用于任何在乘加类计算操作的同时还需要较大量的不同类型的非乘加类计算操作的任何网络或模型中非乘加类计算操作。

根据本公开的示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化方法和优化系统，将非乘加类计算操作拆分为多个基础计算，并在所述多个基础计算的基础上采用合并计算结合流水线优化的方案，不仅提高非乘加类计算的运算性能，还增加硬件加速器的可通用性和可扩展性。

此外，根据本公开的示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化方法和优化系统，基于FPGA器件可重复擦写的特性，有效地探索计算图中多次重复出现的连续计算组合，从而提高硬件资源的使用率，以提升FPGA上深度神经网络加速性的性能。

以上已参照图1至图5描述了根据本公开示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化方法和优化系统。

图5所示出的FPGA硬件加速器中非乘加类计算操作的优化系统中的计算图生成装置可被配置为执行特定功能的软件、硬件、固件或上述项的任意组合。例如，各个单元可对应于专用的集成电路，也可对应于纯粹的软件代码，还可对应于软件与硬件相结合的模块。此外，各个单元所实现的一个或多个功能也可由物理实体设备(例如，处理器、客户端或服务器等)中的组件来统一执行。

此外，参照图5所描述的计算图生成装置执行的操作方法可通过记录在计算机可读存储介质上的程序(或指令)来实现。例如，根据本公开的示例性实施例，可提供存储指令的计算机可读存储介质，其中，当所述指令被至少一个计算装置运行时，促使所述至少一个计算装置执行根据本公开的由计算图生成装置执行的操作。

上述计算机可读存储介质中的计算机程序可在诸如客户端、主机、代理装置、服务器等计算机设备中部署的环境中运行，应注意，计算机程序还可用于执行除了上述步骤以外的附加步骤或者在执行上述步骤时执行更为具体的处理，这些附加步骤和进一步处理的内容已经在参照图5进行的由计算图生成装置执行的相关方法的描述过程中提及，因此这里为了避免重复将不再进行赘述。

应注意，根据本公开示例性实施例的FPGA硬件加速器中非乘加类计算操作的优化系统中的计算图生成装置的各个单元可完全依赖计算机程序的运行来实现相应的功能，即，各个单元在计算机程序的功能架构中与各步骤相应，使得整个系统通过专门的软件包(例如，lib库)而被调用，以实现相应的功能。

另一方面，图5所示的计算图生成装置的各个单元也可以通过硬件、软件、固件、中间件、微代码或其任意组合来实现。当以软件、固件、中间件或微代码实现时，用于执行相应操作的程序代码或者代码段可以存储在诸如存储介质的计算机可读介质中，使得处理器可通过读取并运行相应的程序代码或者代码段来执行相应的操作。

例如，本公开的示例性实施例还可以实现为计算装置，该计算装置包括存储部件和处理器，存储部件中存储有计算机可执行指令集合，当计算机可执行指令集合被处理器执行时，执行根据本公开的示例性实施例的由计算图生成装置执行的操作。

具体说来，计算装置可以部署在服务器或客户端中，也可以部署在分布式网络环境中的节点装置上。此外，计算装置可以是PC计算机、平板装置、个人数字助理、智能手机、web应用或其他能够执行上述指令集合的装置。

这里，计算装置并非必须是单个的计算装置，还可以是任何能够单独或联合执行上述指令(或指令集)的装置或电路的集合体。计算装置还可以是集成控制系统或系统管理器的一部分，或者可被配置为与本地或远程(例如，经由无线传输)以接口互联的便携式电子装置。

在计算装置中，处理器可包括中央处理器(CPU)、图形处理器(GPU)、可编程逻辑装置、专用处理器系统、微控制器或微处理器。作为示例而非限制，处理器还可包括模拟处理器、数字处理器、微处理器、多核处理器、处理器阵列、网络处理器等。

根据本公开示例性实施例的由计算图生成装置执行的操作中所描述的某些操作可通过软件方式来实现，某些操作可通过硬件方式来实现，此外，还可通过软硬件结合的方式来实现这些操作。

处理器可运行存储在存储部件之一中的指令或代码，其中，存储部件还可以存储数据。指令和数据还可经由网络接口装置而通过网络被发送和接收，其中，网络接口装置可采用任何已知的传输协议。

存储部件可与处理器集成为一体，例如，将RAM或闪存布置在集成电路微处理器等之内。此外，存储部件可包括独立的装置，诸如，外部盘驱动、存储阵列或任何数据库系统可使用的其他存储装置。存储部件和处理器可在操作上进行耦合，或者可例如通过I/O端口、网络连接等互相通信，使得处理器能够读取存储在存储部件中的文件。

此外，计算装置还可包括视频显示器(诸如，液晶显示器)和用户交互接口(诸如，键盘、鼠标、触摸输入装置等)。计算装置的所有组件可经由总线和/或网络而彼此连接。

根据本公开示例性实施例的由计算图生成装置执行的操作方可被描述为各种互联或耦合的功能块或功能示图。然而，这些功能块或功能示图可被均等地集成为单个的逻辑装置或按照非确切的边界进行操作。

因此，参照图5所描述的由计算图生成装置执行的操作可通过包括至少一个计算装置和至少一个存储指令的存储装置的系统来实现。

根据本公开的示例性实施例，至少一个计算装置是根据本公开示例性实施例的用于执行辅助人工文本标注的方法的计算装置，存储装置中存储有计算机可执行指令集合，当计算机可执行指令集合被至少一个计算装置执行时，执行由计算图生成装置执行的操作。

以上描述了本公开的各示例性实施例，应理解，上述描述仅是示例性的，并非穷尽性的，本公开不限于所披露的各示例性实施例。在不偏离本公开的范围和精神的情况下，对于本技术领域的普通技术人员来说许多修改和变更都是显而易见的。因此，本公开的保护范围应该以权利要求的范围为准。