有效地将神经网络映射到可编程逻辑设备的系统和方法

摘要

提供了用于将神经网络有效地映射到可编程逻辑设备(PLD)的系统和方法。用于将神经网络映射到FPGA的方法可以包括：接收定义所述PLD架构的数据结构；接收定义所述神经网络架构的数据结构；将所述PLD架构划分为多个层，每层具有与第一片外缓冲器相邻的起始原语和与第二片外缓冲器相邻的结束原语；将所述神经网络架构映射到多层中的一层或多层上，以使数据传输大小至少局部最小化；调度所述被映射的神经网络架构以在所述多个层中的一层或多层上执行；基于被调度和映射的神经网络架构输出执行序列。

说明书

相关申请的交叉引用

本公开要求于2018年10月12日提交的美国申请号16/159,580的优先权的权益，其全部内容通过引用合并于此。

背景技术

在用于神经网络的执行方面，现场可编程门阵列(FPGA)和其他可编程逻辑设备(PLD)通常比常规处理硬件(例如中央处理器(CPU)，图形处理单元(GPU)或类似器件)更为有效。但是，FPGA和其他PLD的架构通常互不相同，并且通常针对特定的神经网络进行定制设计。因此，无法在未专门为这些神经网络设计的现有FPGA和其他PLD上有效地实现神经网络。

发明内容

鉴于前述内容，本公开的实施例提供了用于将神经网络有效地映射到现有PLD的计算机实现的系统和方法。本公开的系统和方法可以为在现有的PLD架构上实现新的神经网络的技术问题提供技术解决方案。本公开的系统和方法可以导致在现有的PLD架构上神经网络的有效的空间和时间执行。

在一些实施例中，一种用于将神经网络映射到可编程逻辑设备(PLD)的系统可以包括被配置为存储指令的至少一个存储器和被配置为执行指令以执行操作的至少一个处理器。所述操作可以包括：接收定义所述PLD的体系结构的数据结构；接收定义神经网络架构的数据结构；将PLD的体系结构划分为多个层。每一层可具有与第一片外缓冲器相邻的起始原语和与第二片外缓冲器相邻的终止原语。该操作可以进一步包括将神经网络的体系结构映射到多个层中的一层或多层上，使得数据传输大小至少局部地最小化。调度被映射的神经网络架构以在多个层中的一个或多个层上执行；基于被调度和映射的神经网络结构输出执行序列。

在一些实施例中，一种用于将神经网络映射到可编程逻辑设备(PLD)的方法可以包括：接收定义所述PLD的体系结构的数据结构；接收定义神经网络架构的数据结构；将PLD的体系结构划分为多个层。每一层可具有与第一片外缓冲器相邻的起始原语和与第二片外缓冲器相邻的终止原语。该方法可以进一步包括将神经网络的体系结构映射到多个层中的一层或多层上，使得数据传输大小至少局部地最小化。调度被映射的神经网络架构以在多个层中的一个或多个层上执行；基于被调度和映射的神经网络架构输出执行序列。

在一些实施例中，非暂时性计算机可读存储介质可以存储可由一个或多个处理器执行的指令集，以使一个或多个处理器执行用于将神经网络映射到可编程逻辑的方法。设备(PLD)。该方法可以包括：接收定义PLD的体系结构的数据结构；接收定义神经网络架构的数据结构；将PLD的体系结构划分为多个层。每一层可具有与第一片外缓冲器相邻的起始原语和与第二片外缓冲器相邻的终止原语。该方法可以进一步包括将神经网络的体系结构映射到多个层中的一层或多层上，使得数据传输大小至少局部地最小化。调度被映射神经网络架构以在多个层中的一个或多个层上执行；基于被调度和映射的神经网络架构输出执行序列。

本公开的附加目的和优点将在下面的详细描述中部分地阐述，并且部分地从该描述中将是显而易见的，或者可以通过本公开的实践而获知。本公开的目的和优点将通过所附权利要求中具体指出的要素和组合来实现和获得。

应该理解，前面的概述和下面的详细描述仅是示例性和说明性的，并且不限制所公开的实施例。

附图说明

包括本说明书的一部分的附图示出了几个实施例，并且所述附图与描述一起用于解释所公开的实施例的原理和特征。在附图中：

图1是根据本公开的实施例的现场可编程门阵列(FPGA)中的原语的示意图。

图2是根据本公开的实施例的用于将神经网络映射到FPGA的示例性系统。

图3A是根据本公开的实施例的FPGA中的层的示意图。

图3B是根据本公开的实施例的FPGA中的另一层的示意图。

图4A是根据本公开的实施例的在将神经网络映射到FPGA之前的原语的变换的示意图。

图4B是根据本公开的实施例的在将神经网络映射到FPGA之前的原语的另一变换的示意图。

图4C是根据本公开的实施例的在将神经网络映射到FPGA之前的原语的又一变换的示意图。

图4D是根据本公开的实施例的在将神经网络映射到FPGA之前的原语的第四变换的示意图。

图4E是根据本公开的实施例的在将神经网络映射到FPGA之前的原语的第五变换的示意图。

图5是根据本公开的实施例的用于将神经网络映射到现场可编程门阵列(FPGA)的示例性方法的流程图。

图6是用于执行与本公开一致的方法的示例性计算机系统的示意图。

具体实施方式

公开的实施例涉及用于将神经网络映射到现场可编程门阵列(FPGA)并调度其执行的计算机实现的系统和方法。较佳的，与神经网络到FPGA上的常规加速相比，示例性实施例可以提供改进的效率。本公开的实施例还可以提供具有新的神经网络结构的FPGA的改进的重用。

本公开的实施例可以在各种可编程逻辑设备(PLD)中实现和使用。因此，尽管参考现场可编程门阵列(FPGA)进行了描述，但是其他PLD(例如可编程阵列逻辑(PAL)，可编程逻辑阵列(PLA)，复杂可编程逻辑器件(CPLD)等)可以执行根据本公开实施例的映射和调度的神经网络。

图1是FPGA(或其他PLD)的示例性流水线(pipeline)(或流水线的部分)100和150的示意图。如图1所示，原语105a可以连接到多个数据缓冲器，例如片外缓冲器103a和103b，和/或片上缓冲器101a和101b。如本文所使用的，“原语”是指FPGA的节点，该节点对一个或多个输入执行基本操作(无论是逻辑的，例如与、或、异或等，还是算术的，例如乘法、加法、减法、最大值、最小值等)以产生一个或多个输出。例如，在图1中，原语105a可以接受来自片外缓冲器103a和/或片上缓冲器101a的输入，并且可以输出到片外缓冲器103b和/或片上缓冲器101b。如本文所用，“缓冲器”是指用于通信数据的任何总线，例如电线，光缆等，以及耦合到该总线并用于存储(并因此“缓冲”)数据的任何存储器，和/或用于管理总线上传输的任何仲裁器或其他定时硬件。

类似于原语105a，原语105b可以接受来自片外缓冲器103c和/或片上缓冲器101b的输入，并且可以输出到片外缓冲器103d和/或片上缓冲器101c。因此，在图1的示例中，原语105a可以使用片上缓冲器101b将其输出作为输入提供给原语105b。因此，原语105a和原语105b可以被分组为从从原语105a执行的操作到由原语105b执行的操作的操作的子图。本公开的实施例可以将神经网络(或其他基于节点的应用)映射到FPGA(或其他PLD)的原语(例如原语105a和原语105b)，以(至少局部地)最大化诸如上述在原语105a和原语105b之间的芯片内传输，并且(至少局部地)最小化芯片外传输(例如，从原语105a到芯片外存储器和/或从原语105b到芯片外存储器)。

图2是根据本公开的实施例的用于将神经网络映射到FPGA的系统200的示意图。如图2中所示，H层查找器203(以下称为“层查找器”)接受FPGA设计201作为输入，例如，如下面在图5的方法500的步骤501中所述。例如，FPGA设计可以包括规范语言的一个或多个数据文件，诸如Verilog、impulse C、以下关于图5所描述的硬件规范语言(HSL)、其他硬件描述语言(HDL)。层查找器203因此可以确定由FPGA设计201定义的FPGA架构的层205(例如，如下面在图5的方法500的步骤503中所描述的)。如本文所使用的，“层”可以是指FPGA架构中从片外存储器附近开始的任何原语(也称为“节点”)序列。在一些实施例中，“层”也可以在片外存储器附近结束。邻近于层的开始的第一片外存储器可以包括与邻近于层的结束的第二片外存储器相同的片外存储器，或者可以包括不同的片外存储器。

如图2中进一步描述，H层映射器209(以下称为“层映射器”)接受层205以及神经网络模型207作为输入(例如，如下文在图5的方法500的步骤501中所述)。例如，层205可以包括定义由层查找器203确定的层(也称为“路径”)的数据结构(例如阵列等)。模型207可以包括数据结构，该数据结构包括定义神经网络的原语及其流。层映射器209因此可以将模型207的原语映射到由FPGA设计201定义的FPGA架构的层205，以使得用于FPGA架构的片外的数据传输量(至少局部地)最小化。例如，层映射器209可以确定模型207到层205上的所有可能的映射(例如，如下面在图5的方法500的步骤505中所解释的)，并且选择全局最小值。可替代地，层映射器209可以应用贪婪算法或其他算法以找到作为局部最小值的模型207到层205上的映射。

在一些实施例中，层映射器209可以输出映射模型207的原语到FPGA架构的节点的数据结构。附加地或替代地，由层映射器209生成的数据结构可以用作H层调度器211(以下称为“层调度器”)的输入。层调度器211可以进一步确定执行被映射的原语(例如，对应的层)的顺序。例如，层调度器211可以确定被映射的原语的所有可能的调度(例如，如下面在图5的方法500的步骤507中所解释的)，并且选择全局最小值。替代地，层调度器211可以应用贪婪算法或其他算法来找到作为局部最小值的映射原语的调度。

因此，层调度器211可以输出执行序列213，其定义模型207到FPGA架构的节点的映射以及模型207的原语将被执行的顺序。例如，执行序列213可以包括用于输入到FPGA芯片以配置FPGA芯片以执行模型207的指令的比特流。

图3A和3B描绘了可以从FPGA(或其他PLD)映射的示例性层300和350。在图3A的示例中，层300包括两个节点(其可以用作“原语”)，节点301和节点303。在层300中，对节点301的输入产生输出，该输出是对节点303的输入以产生最终输出。如上所述，输入可以从片外存储器(未示出)开始。附加地或替代地，输出可以在片外存储器(未示出)处结束。

在图3B的例子中，层350包括四个节点(其可以用作“原语”)，节点301、节点303、节点305和节点307。如图3A和3B所示，一些节点(例如，节点301和303)可以是多层的成员。在层350中，对节点301的输入产生输出，该输出是对节点303和对节点305的输入以产生输出，该输出是对节点307的输入以产生最终输出。如上所述，输入可以从片外存储器(未示出)开始。附加地或替代地，输出可以在片外存储器(未示出)处结束。

应当理解，FPGA的总层数不大于FPGA节点所有子集的部分组合之和。在大多数实施例中，FPGA的层总数将少于部分组合的总和，因为很少有FPGA的所有节点都相互连接。

如上所述，本公开的实施例可以在将神经网络映射到FPGA(或其他PLD)的层之前对神经网络(或其他节点计算图)执行一个或多个变换。图4A-4E描绘了可以在映射到FPGA之前在神经网络上执行的示例性变换400、410、420、430和440。可以理解的是，图4A至图4E仅是示例，并且除了4A-4E中的描述的变化之外，还可以执行类似的变换或替代上述变换。

在图4A中，变换400将后接矩阵乘法原语的连接原语改变为两个切片(slice)原语、两个矩阵乘法原语和加法原语。类似地，在图4B中，变换410将后接切片原语的矩阵乘法原语改变为后接矩阵乘法原语的两个切片原语。

图4C-4E描绘了更简单的变换。例如，图4C的变换420将后接切片原语的切片原语改变为单个切片原语。类似地，图4D的变换430将最大原语更改为线性整流函数(Relu)原语。图4E的变换440将后接切片原语的加法原语改变为后接一加法原语的两个切片原语。

可以使用规范语言来定义图4A-4E的变换。例如，可以使用以下语法定义的变换规范语言(TSL)定义转换：

TSL:

transforms::＝rule|rule transforms

rule::＝name id comp transform_to comp；

comp::＝val:value|variable begin end|primitive

value::＝any|int_var|(int_var*)

begin::＝any|int_var|(int_var*)

end::＝any|int_var|(int_var*)

name::＝string

id::＝integer

int_var::＝integer|string

variable::＝string

Keywords:

transform_to,val:,any,<>,primitive∈{dnn_compute_primitives}；

在以上规范中，每个变换规范都描述了源和目标计算模式(即，要替换的原始序列和替换原始序列)。每个计算模式都由一个或多个计算原语名称和相应的输入组成。如下图4A-4E所示，计算模式可以是嵌套的。例如，有效的计算模式可以包括add，C>，其中第二个加法(add)是第一个加法操作中的第0个输入。字段“变量”表示对原语的输入可以来自任何其他计算。

因此，使用如以上定义的TSL作为示例，图4A-4E的变换可以分别如下定义：

concat_eliminate 0mmW(0 0)(x n)>transform_to addmm>

slice_mm 1sliceval:(s t)val:(ss ts)>transform_to mmslice>

slice_slice 2sliceval:(s2t2)val:(ss2 ts2)>transform_to slice

max_eliminate 3maxtransform_to relu

slice_add 4sliceval:(s t)val:(ss ts)>transform_to addslice>

在上面的规范中，每个transform_to函数将在左侧(并且可能在神经网络或其他节点计算图内)定义的原语更改为在右侧定义的原语。

图5是用于将神经网络映射到现场可编程门阵列(FPGA)的示例性方法500的流程图。方法500可以由至少一个处理器(例如，图6的系统600的处理器601)执行。尽管使用FPGA来描述，但是方法500可以应用于任何可编程逻辑设备(PLD)，诸如PAL、PLA、CPLD等。

在步骤501，至少一个处理器可以接收定义FPGA架构的数据结构。例如，定义FPGA架构的数据结构可以包括规范语言。例如，所述语言可以包括Verilog，impulse C或任何其他HDL。在一些实施例中，数据结构可以包括由以下语法定义的硬件规范语言(HSL)：

HSL:

FPGAboard::＝kernel*mem*

kernel::＝name id(dnn_primitives*)InputBuffers OutputBuffers comp_constraints；

dnn_primitives::＝bp_primitive*|(dnn_primitives)|{dnn_primitives}

bp_primitive::＝primitive:bp|primitive:nbp

InputBuffers::＝(Input:id mem_name)*

OutputBuffers::＝(Output:id mem_name)*

comp_constraints::＝constraint|constraint comp_constraints

constraint::＝{input_id cons_category RELATION[typeVal|shapeVal|dataVal]}

cons_category::＝type|shape|data

typeVal::＝any|char|bool|int8|int16|int32|int64|float16|float32|float64

shapeVal::＝any|integer|(integer,integer)

dataVal::＝any|integer|(integer,integer)

mem::＝name id loc rw size(mem_name*)；

name::＝string

mem_name::＝string

input_id::＝integer

id::＝integer

loc::＝OnChip|OffChip

rw::＝R|W|RW

size::＝integer[B|KB|MB|GB|TB]

Keywords:

any,type,shape,data,R,W,RW,B,KB,MB,GB,TB,OnChip,OffChip,Input:,Output:,

:bp,:nbp,(),{},primitive∈{dnn_compute_primitives},RELATION∈{<,>,<＝,>＝,＝＝,！＝}；

在以上规范中，定义FPGA的数据结构由内核列表和存储器列表组成。每个内核对应于FPGA的计算逻辑(在上面也称为“节点”)。字段“名称”和“id”分别指示内核的名称和与其关联的唯一标识符。字段“dnn_primitives”包括一个或多个原语的列表，它们定义了可由内核执行的原语。原语的执行顺序可以是预先定义的，也可以是任意的。此外，内核可执行的原语可以是可避开的或不可避开的(分别由“：bp”或“：nbp”定义)。字段“InputBuffers”指示可以输入到内核的缓冲器，而字段“OutputBuffers”指示内核可以输出到的缓冲器。

一些内核可能对输入的大小和/或形状有要求。因此，字段“comp_constraints”可以包括描述输入要求的约束的列表。“input_id”字段标识哪个输入受到约束，“cons_category”字段定义约束的类别(例如，类型、形状、数据等)，“RELATION”字段表示输入与目标要求之间的关系，以及“typeVal|shapeVal|dataVal”字段定义目标要求。内核可能只对某些输入具有目标要求，或者对不同的输入可能具有不同的要求。从理论上讲，可以对不同输入施加约束的数量没有限制。

在一个示例中，可以使用HSL如下定义FPGA架构：

kernel0 0(mm:bp)(Input:0Buffer2)(Input:1Buffer3)；

kernel1 1({bias:bp add:bp}pooling:bp)(Input:0Buffer1)(Input:1Buffer2)(Input:2Buffer2)；

Buffer0 0OnChip RW 1MB{Buffer3}；

……

DDR 5OffChip RW 1GB{Buffer4 Buffer2}；

在以上规范中，FPGA具有至少两个内核，至少一个缓冲器和至少一个动态随机存取存储器(即片外双倍数据速率(DDR)存储器)。普通技术人员将认识到，以上规范仅是示例性的，并且FPGA(或其他PLD)可以包括任意数量的内核、缓冲器和片外存储器。另外，除片外存储器之外或可代替的片外存储器，FPGA(或其他PLD)可以包括任何数量的片上存储器。

此外，在步骤501，至少一个处理器可以接收定义神经网络的架构的数据结构。例如，定义神经网络架构的数据结构可以包括计算图。在这样的示例中，计算图可以包括多个原语和对其的输入。因此，计算图可以是节点。在一些实施例中，如上所述，计算图可包括至少一个嵌套模式。

在步骤503，至少一个处理器可以将FPGA架构划分为多个层。例如，每个层可以具有与片外缓冲器相邻的开始原语和与片外缓冲器相邻的结束原语。在一些实施例中，划分FPGA的架构可以包括应用Dijkstra的算法。例如，Dijkstra的算法可以提取通过FPGA节点的可能路径，并且可以应用于每个可能的起始节点(例如，与片外缓冲器相邻的节点)，以便提取从每个节点(或至少从有资格作为起始节点的每个节点)开始的可能路径。

另外地或可替代地，划分FPGA架构可以包括沿着FPGA的原语生成可能的路径，该可能的路径开始和结束于与片外数据传输的总线相邻，每个路径包括多个层中的一个。例如，可以应用Dijkstra的算法、Bellman-Ford算法或任何其他适合生成可能路径的算法。

因此，在一些实施例中，可以计算通过FPGA的节点的所有可能的路径。在其他实施例中，可以计算通过FPGA的节点的可能路径的子集。例如，可以应用每层的最大数量的节点，从而排除特定长度上的所有路径。另外地或可替代地，可以应用每层最小数量的节点，从而排除特定长度下的所有路径。

在步骤505，至少一个处理器可以将神经网络架构映射到多个层中的一层或多层上，使得数据传输大小至少局部地最小化。例如，至少一个处理器可以基于到FPGA的一个或多个片外存储器的输出和来自前述片外存储器的输入，来确定与每个映射相关联的数据传输大小。

将神经网络架构映射到多个层中的一个或多个上可以包括生成神经网络的原语到多个层上的可能的映射，并且选择具有数据传输大小的局部最小值的可能的映射。在一些实施例中，至少一个处理器可以确定神经网络的子图到FPGA的层的所有可能映射并选择全局最小值。在其他实施例中，至少一个处理器可以确定神经网络的子图到FPGA的层的可能映射的子集，并选择局部最小值。例如，至少一个处理器可以应用分支定界算法(branchand bound)或其他基于树的算法、Broyden-Fletcher-Goldfarb-Shanno(BFGS)算法或其他准牛顿算法，或前述算法的组合。

在步骤507，至少一个处理器可以调度被映射的神经网络架构，以在多个层中的一个或多个层上执行。例如，至少一个处理器可以基于到FPGA的一个或多个片外存储器的输出和来自其的输入来确定与每个调度相关联的数据传输大小。

调度被映射的神经网络架构以便执行可以包括选择用于多个层中的一个或多个层的执行序列，使得数据传输大小至少局部地最小化。例如，选择执行顺序可以包括生成多个层中的一个或多个层的可能的执行顺序，并选择具有数据传输大小的局部最小值的可能的执行顺序。在一些实施例中，至少一个处理器可以确定所有可能的调度并选择全局最小值。在其他实施例中，至少一个处理器可以确定可能的调度的子集并选择局部最小值。例如，至少一个处理器可以应用贪婪算法或其他算法来确定局部最大值。

在步骤509，至少一个处理器可以基于被调度和映射的神经网络架构输出执行序列。例如，所述执行序列可以包括用于输入到FPGA(或其他PLD)的比特流。因此，至少一个处理器可以将比特流直接输出到FPGA以相应地对其进行配置。另外地或可替代地，至少一个处理器可以输出比特流以进行存储。

如果片上存储器不足，则方法500可以允许执行对片外存储器的部分写入。因此，在一些实施例中，执行顺序的至少一个步骤可以包括对片外存储器的部分写入和对片上存储器的部分写入。

根据本公开，示例性方法500可以包括附加步骤。例如，在一些实施例中，方法500可以包括根据一个或多个变换规则将包括一个或多个原语的至少一个子图变换为至少一个其他子图。例如，可以使用图4A-4E中所描绘的任何或所有变换的另外地或替代的类似变换。在一些实施例中，可以在步骤505之前或步骤503之前执行变换。

图6描述了与本公开的实施例一致的用于将神经网络映射到FPGA的示例系统600。尽管在图6中系统600被描绘为服务器，但是，系统600可以包括被配置为执行例如图5的方法500的任何计算机，诸如台式计算机、膝上型计算机、平板电脑等。

如图6所示，服务器600可以具有处理器601。处理器601可以包括单个处理器或多个处理器。例如，处理器601可以包括CPU、GPU、可重新配置的阵列(例如，FPGA或其他ASIC)等。

处理器601可以与存储器603、输入/输出模块605和网络接口控制器(NIC)607可操作地连接。存储器603可以包括单个存储器或多个存储器。另外，存储器603可以包括易失性存储器、非易失性存储器或其组合。如图6所示，存储器603可以存储一个或多个操作系统609、层映射器611a和调度器611b。例如，层映射器611a可以包括用于将神经网络架构映射到FPGA架构的指令(例如，如图5的方法500的步骤505中所阐述的)，并且调度器611b可以包括用于调度映射的神经网络架构的执行的指令(例如，如图5的方法500的步骤507所阐述的)。因此，层映射器611a和调度器611b可以与图6的硬件协作，以执行图5的方法500。

输入/输出模块605可以从一个或多个数据库615存储和取出数据。例如，数据库615可以包括神经网络架构和/或FPGA架构，如上所述。

NIC 607可以将服务器600连接到一个或多个计算机网络。在图6的示例中，NIC607将服务器600连接到因特网。服务器600可以使用NIC 607通过网络接收数据和指令，并且可以使用NIC 607通过网络发送数据和指令。此外，服务器600可以使用NIC 607通过网络接收定义神经网络架构或FPGA架构的数据文件，如上所述。

为了通过使了用所公开的将神经网络映射到FPGA的技术来证明潜在的效率提高，开发和执行多种仿真。所述仿真使用了上述公开的变换以及用于下面的示例伪代码：

在上面的伪代码中，输入R包含变换规则，输入G包含神经网络的计算图，并且G根据R进行修改然后输出。具体而言，第1-6行创建了一个散列图，用于从图形模式(例如，在规则R中的输入子图)映射到另一个图(例如，规则R中的输出子图)。第8-22行以深度优先的方式遍历输入图形G。为了跟踪要遍历的下一个节点(即原语)，伪代码创建了一个工作表，该工作表最初仅包含图的根节点。在第10行，将访问工作表中的最后一个元素。第12-16行将当前节点控制的子图与所有转换规则进行比较。如果匹配其中一个规则，则将替换该子图，并将新子图的根节点的使用者节点添加到工作列表中进行访问(请参见第13行)。如果没有匹配任何转换规则，那么当前节点的使用者节点将被添加到工作列表中(请参见第17-22行)。

所述仿真还使用了如上所述的所公开的层查找器，并用于下面的示例伪代码中：

在上面的伪代码中，输入HSL包含定义FPGA架构的规范语言，输出流水线定义FPGA的层。特别是，第1行从HSL收集FPGA的基本存储器和内核组件。第4行使用Dijkstra的算法进行了一些修改，以将True或False填充二维数组MemReachable，以表明是否存在从一种类型的存储器到另一种类型的存储器的数据移动路径。第7-13行尝试收集所有具有来自片外存储器的输入数据的内核。这些StartKernels是计算管道(pipeline)中起始原语的候选项。第16-18行从StartKernels中的每个内核开始，并使用FindPipelines通过检查从一个内核写入的存储器到另一个内核从其中读取的存储器的可访问性，来查找设备上的所有内核并收集所有可能的管道。

所述仿真还使用了上述公开的层映射器，并用于下面的示例伪代码中：

在上面的伪代码中，输入G包括计算图(例如，按照上面的伪代码进行转换)，输入Pipelines定义了FPGA的层，输出Layers定义了映射到Pipeline上的图G。特别是，第2行的循环将就绪节点作为LayerMapper函数的起点进行迭代。在子例程LayerMapper()中，第1行调用的函数根据当前数据结构管道检查在一层中的当前节点是否可以是下一个节点。此检查的结果有四种状态：1)无效(INVALID)；2)继续(CONTINUE)；3)开始(START)；和4)两者都(BOTH)。INVALID表示当前节点不能在当前层或新层中，这意味着此映射无法继续进行。CONTINUE表示当前节点可以是一个或多个可能管道中的下一个节点。START表示当前节点可以是新管道中的起始节点。BOTH表示当前节点同时满足CONTINUE和START的条件。在上面的伪代码中，CONTINUE被用作代表，因为处理这种情况通常是最复杂的。第5行将当前节点添加到现有层，将进一步进行验证。第6行将当前节点设置为已访问，并将其从NextNodes中删除，该节点用于记录可以在下一步中遍历的节点。如果当前节点是要遍历的最后一个节点，则伪代码将检查最后一层的有效性，并在数据传输较少的情况下更新*MinLayers(请参见第7-8行)。否则，如果当前节点的使用者数量为1，则将当前节点添加到现有管道中(请参见第11行)，并将调用LayerMapper函数来处理当前节点的使用者。如果当前节点的使用者数量不为1，则伪代码将验证管道的有效性。如果有效，则伪代码然后将NextNodes中的每个节点迭代地设置为遍历中的下一个节点，并再次启动LayerMapper(请参见第21行)，以便遍历所有可能的路径。尽管以上使用递归进行了阐述，但是应当理解，除了递归之外或代替递归，可以使用迭代实现。

所有模拟都是使用Tensorflow平台和加速线性代数(XLA)编译器执行的。具体而言，使用本文公开的技术将XLA中间表示(IR)转换为FPGA指令流(以上也称为“比特流”)。

本文公开的技术在三个现有的深度神经网络(DNN)上进行了测试：广度和深度学习(WDL)DNN、稍作修改以使用两个基本单元作为循环体的长短期记忆(LSTM)DNN、以及残差神经网络(ResNet)。

本文公开的优化方法产生减少的数据传输至少高达81％的效果；但是，预计的效率是特定于网络的。表1显示了此示例的结果。表1包含了模型中原语的数量，包括转换前(N)和转换后(N')；设备上不受支持的但在模型中的原语的数量(转换前(UN)和转换后(UN'))；在转换之前(SG)和转换之后(SG')被不支持的原语划分的子图的数量；映射后的层数(HL)；每层平均原语数(APL)；具有常规加速(DT)的数据传输大小；应用本公开的技术之后的数据传输大小(Opt)；以及由于本公开的技术而导致的数据传输的减少(R)。

表1

由于数据传输的减少，WDL的性能得到了改善，与没有在相同的FPGA设计上应用本公开内容的映射的WDL的传统加速相比，产生4.8倍的加速(端到端)，而对于LSTM和ResNet，本公开的映射分别实现了1.5倍和2.5倍的加速。

其他模拟使用略有不同的算法映射到层。例如，不是像上述仿真中那样应用穷举搜索，而是其他仿真使用了贪婪算法。在下面描述的示例中，应用了一种三态贪婪算法。特别地，该系统首先确定每个原语是否具有(1)一个输入和单个使用者，(2)多个输入但一个使用者，或(3)多个使用者(和任意数量的输入)。对于情况(1)，仿真应用下面的公式1：

DT[i]＝min{DT[i-len]+PSeq[i-len+1].in_size，PSeq[i].out_size}；

{i∈(0，PSeq.siz)，j∈(0，HL.size)，len＝HL[j].len

公式1

在公式1的示例中，DT是与原语序列PSeq的特定组i相关联的数据传输，所有这些分类都在情况(1)内分类。HL是层的集合，j是层的索引。因此，公式1选择了具有最低关联DT的映射。

对于情况(2)，模拟首先将所有先前的原语确定为在情况(2)中分类的原语。如果一个以上的先前原语可能无法写入片外存储器，则将返回错误。另一方面，如果一个先前原语可能未写入片外存储器，则选择该先前原语的子图以包括被分类为情况(2)的原语。如果所有先前原语都可以写入片外存储器，则确定每个可能的映射的数据传输(例如，使用公式1)，并选择具有最低关联传输的映射。

对于情况(3)，模拟使用原语的每个使用者和多个使用者来启动一个新序列，将公式1应用于该序列以选择映射。此后，每个使用者序列都被相应地映射。尽管此三部分算法不一定总能找到最佳解决方案，但与使用算法相比，它在时间上通常没有那么复杂。

与映射算法类似，如上文关于步骤507所述，可以应用贪婪算法来调度映射的层。在以下呈现的仿真中，调度器按要求的顺序对任何层进行调度(例如，如果第1层仅取决于第2层的输出，则在第1层之前进行调度)。对于具有多个输入的层，首先将输入层分类为在或不在可用的片上存储器量之内。不在的任何层都将在在可用的片上存储器量之内的层之前调度。此外，在或不在的层每组中，任何较长的层都将在较短的层之前执行。

本文公开的这些在三个现有的深度神经网络(DNN)上进行了测试：广泛和深度学习(WDL)DNN、转换率(CVR)DNN和多层感知器残差网络(MLP-ResNet)。

本文公开的优化方法产生减少的数据传输至少高达81％；但是，预计的效率是特定于网络的。表2显示了此示例的结果。表2包括模型中原语的数量，包括转换前(N)和转换后(N')的数量；设备上不受支持但在模型中的原语的数量(转换前(UN)和转换后(UN'))；在转换之前(SG)和转换之后(SG')被不支持的原语划分的子图的数量；映射后的层数(HL)；每层平均原语数(APL)；具有常规加速(DT)的数据传输大小；应用本公开的技术之后的数据传输大小(Opt)；以及由于本公开的技术而导致的数据传输的减少(R)。

表2

由于减少了数据传输，因此WDL的性能得到了改善，与没有在相同FPGA设计上应用本公开的映射的WDL的常规加速相比，产生4.8倍的加速(端对端)。对于CVR和MLP-ResNet，本公开的映射分别实现了1.55倍和2.5倍的加速。

已经出于说明的目的给出了前面的描述。但它不是穷举性的，并且不限于所公开的精确形式或实施例。通过考虑所公开的实施例的说明书和实践，实施例的修改和变化将是显而易见的。例如，所描述的实施方式包括硬件，但是与本公开一致的系统和方法可以用硬件和软件来实施。另外，尽管已将某些组件描述为彼此耦合，但是这些组件可以彼此集成或以任何合适的方式分布。

此外，尽管本文已经描述了说明性实施例，但是范围包括具有基于本公开的等同要素、修改、省略、组合(例如，各个实施例的各个方面)、变化或替换的任何和所有实施例。权利要求中的元素将基于权利要求中使用的语言来广义地解释，并且不限于在本说明书中或在本申请进行期间描述的示例，这些示例应被解释为非排他性的。此外，可以以任何方式修改所公开的方法的步骤，包括重新排序步骤和/或插入或删除步骤。

根据详细的说明书，本公开的特征和优点是显而易见的，因此，所附权利要求旨在覆盖落入本公开的真实精神和范围内的所有系统和方法。如本文所用，不定冠词“一个”和“一种”表示“一个或多个”。类似地，除非在给定的上下文中明确使用复数形式，否则不一定使用复数形式。除非另外明确指出，否则诸如“和”或“或”之类的词表示“和/或”。此外，由于从研究本公开内容将容易发生许多修改和变形，因此不希望将本公开内容限制为示出和描述的确切构造和操作，并且，可以采用所有合适的修改形式和等同形式，这些均落入本发明的范围内。

如本文所用，除非另有明确说明，否则术语“或”涵盖所有可能的组合，除非不可行。例如，如果声明数据库可以包括A或B，则除非另有明确说明或不可行，否则数据库可以包括A、或B、或A和B。作为第二个示例，如果声明a数据库可能包含A、B或C，则除非另有说明或不可行，否则数据库可能包含A、或B、或C、或A和B、或A和C、或B和C、或A和B和C。

通过考虑本文公开的实施例的说明书和实践，其他实施例将是显而易见的。说明书和示例旨在仅被视为示例，所公开的实施例的真实范围和精神由所附权利要求指示。