一种张量运算加速芯片的自动设计方法

1.本发明涉及芯片设计自动化技术领域，具体涉及一种针对张量运算加速芯片的自动化设计方法。


背景技术：

2.张量运算加速芯片是一种针对类似矩阵乘法、二维卷积等张量运算的硬件加速芯片，广泛用于人工智能、大数据等领域。张量运算加速芯片往往采用空间式架构。空间式架构的主要部件是由大量的运算单元或处理单元(processing element,pe)组成的pe阵列，以及位于片上静态随机访存存储(sram)中的存储单元(memory bank)。为了描述不同的计算单元设计与它们之间的互联，通常采用一种名为数据流(dataflow)的中间表示形式(intermediate representation,ir)，并基于数据流进行分析和硬件自动生成。
3.目前，现有的张量运算加速芯片自动生成技术包括tensorlib(tensorlib:a spatial accelerator generation framework for tensor algebra》，liancheng jia等，dac 2021.)和tenet(tenet:a framework for modeling tensor dataflow based on relation-centric notation》，liqiang lu等，isca 2021.)。其中，tensorlib是一种基于数据流进行空间式架构自动生成的技术。在tensorlib中，数据流被表示为时空变换矩阵形式。根据对数据复用的分析，得到复用向量。针对每一类不同的复用向量，设计专用的pe模板，并将模板拼凑为完整的pe阵列，以实现硬件的自动生成。tensorlib的主要缺点是，数据流是由用户提供的，不能实现完全的自动化。并且，tensorlib仅分析了pe阵列的部分，并没有对存储行为进行分析。这些缺陷导致tensorlib并不能实现从张量运算到空间式架构的端到端自动硬件生成，硬件的性能依赖于用户直接提供的数据流。
4.tenet是一种对数据流进行复用性分析以及设计空间自动探索的技术。在tenet中，数据流被表示为一种映射关系。根据张量对数据的访问映射关系、硬件互联的映射关系，以及数据流映射关系，tenet提出了基于整数集运算的数据复用模型，从而实现了对计算延迟和通信开销的估计。tenet的主要缺点是，没有对数据流的硬件实现进行分析，因此其设计空间探索算法仅仅是对于映射关系的简单枚举，导致探索效率低下，且不支持硬件自动生成。


技术实现要素：

5.为了克服现有技术的补足，本发明提供一种张量运算加速芯片的自动设计方法，将芯片设计中的中间表示形式(数据流)分解为数据通路和数据访存，以有效实现芯片设计中数据流的自动探索与硬件生成。
6.张量运算加速芯片设计领域，通常采用数据流作为中间表示形式，用于表示芯片的不同计算单元之间的互联。本发明通过提出了两种新的中间表示形式，数据通路和数据访存，对数据流中间表示形式进行分解。将数据流中间表示形式分解为数据通路和数据访存两个中间表示形式；再基于数据通路和数据访存两个中间表示，实现张量运算加速芯片
空间式架构的设计空间自动探索与硬件自动生成。
7.本发明的技术方案：
8.一种张量运算加速芯片的自动设计方法，包括如下步骤：
9.1)将张量运算加速芯片设计中的数据流中间表示形式分解为数据通路和数据访存两个中间表示形式；数据访存用于表示张量数据从存储单元到运算单元pe的运动；数据通路用于表示数据在pe之间的运动；
10.本发明的数据流的分解过程表示为：
11.公式1：
12.公式2：
13.公式3：
14.公式4：
15.公式5：
16.其中，是数据流中间表示形式的逆映射，被分解为参与张量运算加速芯片中运算的各个张量(记为a，b等)的张量运动，如为张量a的张量运动，为张量b的张量运动，是访问函数的广义逆映射，为张量a的数据通路中间表示形式，为张量a的数据访存中间表示形式，表示位于的pe，表示pe的第周期，表示位于的接入点，表示接入点的第周期，表示张量a下标为的数据。公式1、2是本发明中数据流的分解式，公式3是本发明中张量运动的定义，公式4是本发明中数据通路中间表示形式的定义，公式5是本发明中数据访存中间表示形式的定义。
17.2)基于数据通路和数据访存两个中间表示，实现张量运算加速芯片空间式架构的设计空间自动探索与硬件自动生成；包括：
18.21)对于数据通路，对数据复用的方向向量基于线性代数进行排列组合，得到不同数据通路的完整设计空间；
19.22)对于数据访存，基于简单数据访存模式，采用转置访存模式变换运算与偏斜访存模式变换运算，得到数据访存的完整设计空间。
20.23)枚举不同的数据通路和数据访存的组合，并排除掉不能构成完整数据流以及硬件上难以实现的组合，从而组合出多个较为高效的数据流。
21.24)对于步骤23)中每一个找到的数据流，将其中数据通路中间表示的硬件模板拼在一起，得到pe阵列的硬件实现；将数据访存中间表示的硬件模板实现为地址生成器，与存储器一同构造片上存储单元。从而，自动生成了具有空间式架构的张量运算加速芯片。
22.与现有技术相比，本发明的有益技术效果：
23.本发明通过将张量运算加速芯片设计中的数据流中间表示形式，设计分解方法(分解公式)为两个低层次中间表示形式(数据通路和数据访存两种新的中间表示形式)，通
过数据通路的设计空间和数据访存的设计空间，基于数据通路和数据访存，实现张量运算加速芯片的自动设计，对芯片硬件的底层细节进行暴露，排除低效的芯片设计选择，从而提升了芯片设计自动探索效率，并实现高效的芯片硬件自动生成。
附图说明
24.图1为本发明提供的张量加速器自动生成方法的流程框图；
25.包括：用户输入张量表达式与限制条件、数据通路设计子空间，然后进行设计空间探索，通过枚举数据通路和数据访存，并进行组合与排除，得到高效的数据流，最后根据数据通路和数据访存硬件模板生成目标硬件。
26.图2、3、4为本发明方法中数据通路中间表示形式在二维运算单元阵列中的完整设计空间，共14种；每一个小图包括了一种映射关系、其硬件结构示例、型号，以及构成该数据通路的方向向量。
27.图5为本发明方法中数据访存中间表示形式的两种变换示例；
28.每一个小图包括了映射关系和访存顺序示例。在简单访存顺序的基础上，可以分别施加转置和偏斜变换，两种变换可以进行组合，以构造完整设计空间。其中空数据表示该周期的接入点不访问数据。
具体实施方式
29.下面结合附图，通过实施例，进一步阐述本发明。
30.本发明提供一种张量运算加速芯片的自动设计方法，将数据流中间表示形式分解为数据通路和数据访存两个中间表示形式；再基于数据通路和数据访存两个中间表示，实现张量运算加速芯片空间式架构的设计空间自动探索与硬件自动生成。具体包括如下步骤：
31.1)将张量运算加速芯片设计中的数据流中间表示形式分解为数据通路和数据访存两个中间表示形式；
32.将张量运算加速芯片设计中的数据流中间表示形式分解为不同张量的数据运动。对于每一个张量的数据运动，进一步被拆解为从存储单元到pe运动，以及在pe之间的运动，分别对应于数据访存中间表示形式，与数据通路中间表示形式。数据流被分解的过程，对应于单一映射关系被分解为多个映射关系的级联的过程。数据访存用于表示数据从存储单元到pe的运动；数据通路用于表示数据在pe之间的运动。
33.2)基于数据通路和数据访存两个中间表示，实现张量运算加速芯片空间式架构的设计空间自动探索与硬件自动生成；包括：
34.21)对于数据通路，对数据复用的方向向量基于线性代数进行排列组合，得到不同数据通路的完整设计空间；
35.对于数据通路中间表示形式，对数据复用的方向向量基于线性代数进行排列组合，得到不同数据通路的完整设计空间。用户可以进一步根据目标硬件平台，筛选出符合硬件特性的数据通路设计子空间。对于设计空间中的不同数据通路，预先实现针对目标硬件平台的硬件模板。
36.22)对于数据访存，基于简单数据访存模式，采用转置访存模式变换运算与偏斜访
存模式变换运算，得到数据访存的完整设计空间。
37.23)枚举不同的数据通路和数据访存的组合，并排除掉不能构成完整数据流以及硬件上难以实现的组合(即数据通路和数据访存不能组合为一个可逆的一一映射)，从而组合出多个较为高效的数据流。
38.24)对于步骤23)中每一个找到的数据流，将其中数据通路中间表示的硬件模板拼在一起，得到pe阵列的硬件实现；将数据访存中间表示的硬件模板实现为地址生成器，与静态随机访存存储器(sram)一同构造片上存储单元。
39.将得到的pe阵列和数据存储单元连接，即自动生成了具有空间式架构的张量运算加速芯片。
40.本发明具体实施时，用户根据目标硬件平台，选择限制条件与数据通路设计子空间，与所针对张量运算的张量表达式一起输入到本发明所提出的算法中，并从本发明输出的硬件设计中根据需求选择最终的加速芯片设计。
41.张量运算加速芯片包括数据单元和运算单元阵列；张量加速芯片存储张量数据的每一个数据单元包括了地址生成器和数据存储器件；数据流表示数据的移动方向；数据从存储了输入张量的数据单元中流出，经过接入点，进入处理单元阵列中。图1展示了芯片硬件的数据流中间表示形式是如何被分解为数据访存中间表示形式和数据通路中间表示形式的。在芯片空间式架构中，假定芯片的处理单元与数据存储单元之间，存在一个虚构的接入点。那么，每一个输入数据的运动，都可以被划分为在数据存储单元到接入点的运动，以及从接入点到处理单元的运动，输出数据则相反。为了描述具体分解方式，下文首先给出了符号定义，然后叙述分解方法，其中本发明设计了公式1、2、3、4、5，公式6、7是本领域相关概念在本发明中的符号定义。
42.基本概念的符号定义如下：
43.对于芯片硬件的一个常规的张量计算，可以用层叠循环的形式表示。给定一组循环变量如i,j,k等，每一个单位运算(如乘加)可以记为其中这些单位运算的集合称为迭代域ds，形如每一个多维张量的数据可以用张量下标的集合来表示，张量a的数据构成的集合称为张量a的张量域
44.每一个单位运算所访问的张量数据，构成了一个映射关系，称为访问函数。形如公式1，表示这个单位运算的操作数或结果来自于张量数据等。
45.公式6：
46.每一个单位运算必须在一个处理单元(pe)的一个周期上进行。在二维pe阵列中，一个pe根据坐标被标示为其中表示在第x行第y列。周期通常表示为多维时间的形式其中其中t1表示最内层循环，其他依此往外。两个多维时间的先后顺序按字典序进行比较。所有pe和周期的笛卡尔积所构成的集合，称为数据流时空域即的第周期。数据流则是从迭代域到数据流时空域的映射关系，形如公式2，表示单位运算发生在的第周期。
47.公式7：
48.本发明提出的分解过程如下：
49.首先，以公式1将数据流分解为不同张量的张量运动。然后以公式2将一个张量运动，分解为数据通路和数据访存。张量运动的定义为公式3，数据通路的定义为公式4，数据访存的定义为公式5。
50.公式5：
51.以下为对各个公式的解释。
52.公式1是将数据流分解为张量运动的公式，其中表示笛卡尔积，
×
表示映射的复合，左式是数据流的逆映射，是访问函数的广义逆映射。
53.公式2将张量运动分解为数据通路与数据访存的公式。其中，以接入点的位置和周期的笛卡尔积构成的集合称为接入点时空域的笛卡尔积构成的集合称为接入点时空域称为张量a的数据通路，称为张量a的数据访存。
54.公式3是张量运动的定义。对于单个张量a，仅考虑数据流中与a有关的部分，记为张量运动，是从数据流时空域到张量域的映射关系，表示的第周期访问了张量数据
55.公式4是张量a的数据通路的定义。表示运算单元的第周期访问的张量a的数据，来自于张量a的接入点的第个周期。
56.公式5是张量a的数据访存的定义。表示张量a的接入点的第个周期，访问了内存中的数据
57.图1展示了如何基于数据通路和数据访存，实现数据流的自动设计空间探索与硬件生成。分为以下步骤：
58.1)用户提供张量表示式。张量表示式包括张量域ds和访问函数
59.2)用户给定搜索限制条件，即内存空间限制等。
60.3)用户针对已有目标硬件平台(如asic或fpga等)，从后文描述的数据通路设计空间中，选定设计子空间。用户可以自定义选择性地提供适合于自身需求的数据通路硬件模板。
61.4)进行设计空间探索，在数据通路和数据访存设计空间中枚举数据通路和数据访存。根据公式1、2，将数据通路和数据访存组合为数据流。当数据通路和数据访存无法组合为数据流时，体现为公式1无法成立，即右式不能组合为一个可逆的一一映射，为错误的组合，排除该数据通路和数据访存组合。
62.5)对于设计空间探索得到的数据流，将其中的数据通路硬件模板进行拼合，得到运算单元阵列。将数据访存以有限状态自动机的形式，生成为地址生成器，与静态随机访存存储器(sram)拼合为数据存储单元。将运算单元阵列与数据存储单元连接后，得到空间式架构的核心部件，以产生张量运算加速芯片。
63.数据通路和数据访存分别有其设计空间。
64.对于数据通路，图3给出了在二维运算单元阵列中，限制数据运输的方向为向右、向下和向右下时，且运输距离为1或者整个阵列时，完整的设计空间。定义方向向量为(dx,dy|dt)，表示运算单元(x,y)的第t周期访问的数据和运算单元(x+dx,y+dy)的第t+dt周期访问的数据是同一个数据。由于局部性原理，这里的t仅指代最内层循环t1。限制dx,dy,dt为0或1，得到所有的方向向量(0,0|1),(1,0|0),(0,1|0),(1,1|0),(1,0|1),(0,1|1),(1,1,1)。这些方向向量再加以排列组合，去除线性空间重复的和可能导出反对角线方向的方向向量的组合，得到图3所示的14种数据通路。根据方向向量的特性，可以写出其数据通路映射关系。在硬件上，(0,0|1)方向向量对应于将数据局部存储在运算单元中，(1,0|0),(0,1|0),(1,1|0)方向向量对应于将数据在对应方向上复制给所有的运算单元，(1,0|1),(0,1|1),(1,1|1)方向向量对应于将数据以移位寄存器的方式传沿着对应的方向传播，因此根据其组合可以构造出相应的硬件模板。
65.对于数据访存，图4给出了两种变换，使得从任意一个简单访存开始，可以构造出完整得数据访存空间。简单访存指，将接入点时空域的维度，任意不加变换地映射到张量域的维度上。本发明中一共有两种变换。转置指的是交换映射的维度，如图2所示，图1的映射维度被交换后，每一个接入点由访问张量a的一列，变为访问张量a的一行，从而实现了转置。偏斜指的是让代表时间的维度减去将代表空间的维度，如图3所示，与图1相比，原本映射到t1的维度映射到了t
1-x上，使得第x个接入点需要等待x个周期，才能访问到合法的数据，等价于张量在存储空间内实现了偏斜。两种变换可以同时被应用，如图4所示。对于任意高维张量，这两种变换可以构造出一个完整的数据访存空间。
66.需要注意的是，公布实施例的目的在于帮助进一步理解本发明，但是本领域的技术人员可以理解：在不脱离本发明及所附权利要求的范围内，各种替换和修改都是可能的。因此，本发明不应局限于实施例所公开的内容，本发明要求保护的范围以权利要求书界定的范围为准。

技术特征：
1.一种张量运算加速芯片的自动设计方法，包括如下步骤：1)将张量运算加速芯片设计中的数据流中间表示形式分解为数据通路和数据访存两个中间表示形式；数据访存用于表示张量数据从存储单元到运算单元pe的运动；数据通路用于表示数据在pe之间的运动；将数据流的分解过程包括数据流的分解、张量运动的定义、数据通路中间表示形式的定义、数据访存中间表示形式的定义；分别表示为：公式1：公式2：公式3：公式4：公式5：其中，是数据流中间表示形式的逆映射，被分解为参与张量运算加速芯片中运算的各个张量的张量运动；为张量a的张量运动；为张量b的张量运动；是访问函数的广义逆映射，为张量a的数据通路中间表示形式，为张量a的数据访存中间表示形式，表示位于的pe，表示pe的第周期，表示位于的接入点，表示接入点的第周期，表示张量a下标为的数据；表示笛卡尔积，
×
表示映射的复合；2)基于数据通路和数据访存两个中间表示，实现张量运算加速芯片空间式架构的设计空间自动探索与硬件自动生成；包括：21)对于数据通路，对数据复用的方向向量基于线性代数进行排列组合，得到不同数据通路的设计空间；22)对于数据访存，基于简单数据访存模式，采用转置访存模式变换运算与偏斜访存模式变换运算，得到数据访存的设计空间；23)枚举不同的数据通路和数据访存的组合，并排除不能构成完整数据流以及硬件上难以实现的组合，得到多个数据流；24)对于步骤23)中得到的每一个数据流，将其中数据通路中间表示的硬件模板拼在一起，得到pe阵列的硬件实现；将数据访存中间表示的硬件模板实现为地址生成器，与存储器一同构造片上存储单元；通过上述步骤，实现自动生成具有空间式架构的张量运算加速芯片。2.如权利要求1所述张量运算加速芯片的自动设计方法，其特征是，步骤2)中实现数据流的自动设计空间探索与硬件生成的过程中，用户提供张量表示式和给定搜索限制条件，针对目标硬件平台；从数据通路设计空间中选定设计子空间；进行设计空间探索，在数据通路和数据访存设计空间中枚举数据通路和数据访存；将数据通路和数据访存组合为数据流；
所述张量表示式包括张量域和访问函数；给定搜索限制条件包括内存空间限制；目标硬件平台包括asic或fpga。3.如权利要求2所述张量运算加速芯片的自动设计方法，其特征是，进行设计空间探索具体是：根据公式1和公式2，将数据通路和数据访存组合为数据流；当公式1无法成立，即公式1的右式不能组合为一个可逆的一一映射时，表示数据通路和数据访存无法组合为数据流，即排除该数据通路和数据访存组合。4.如权利要求3所述张量运算加速芯片的自动设计方法，其特征是，对于设计空间探索得到的数据流，将其中的数据通路硬件模板进行拼合，得到运算单元阵列；将数据访存以有限状态自动机的形式生成为地址生成器，与静态随机访存存储器sram拼合为数据存储单元。5.如权利要求4所述张量运算加速芯片的自动设计方法，其特征是，将运算单元阵列与数据存储单元连接后，得到空间式架构的核心部件，以产生张量运算加速芯片。

技术总结
本发明公布了一种张量运算加速芯片的自动设计方法，通过提出了两种新的中间表示形式，数据通路和数据访存，将芯片设计中的中间表示形式(数据流)分解为数据通路和数据访存，基于数据通路和数据访存，实现张量运算加速芯片的自动设计，对芯片硬件的底层细节进行暴露，排除低效的芯片设计选择，从而提升了芯片设计自动探索效率，有效实现芯片设计中数据流的自动探索与硬件生成。的自动探索与硬件生成。的自动探索与硬件生成。


技术研发人员：梁云 罗梓璋
受保护的技术使用者：北京大学
技术研发日：2023.04.27
技术公布日：2023/8/14