粗粒度可重构阵列（coarse-grained reconfigurable array，CGRA）是一种可空域并行、时域扩展的新型领域定制加速器架构. 通过组织不同粒度和不同功能的计算资源，具有运行时可配置数据通路的特征. 在运行时，CGRA可根据数据流的特点，让可配置的硬件资源互连形成相对固定的数据通路，以接近“专用电路”的方式进行计算；当算法和应用变换时，CGRA可通过重复配置，形成不同的数据通路去执行不同的任务. 因此，CGRA是一种很有潜力的计算平台，可以在灵活性、性能和功耗之间提供良好的平衡. 由于CGRA具有粗粒度处理单元（processing element，PE）和稀疏的PE间互连，与细粒度现场可编程门阵列（field programable gate array， FPGA）相比，CGRA的配置开销要小得多. 因此CGRA可以为广泛的应用提供高能效的解决方案^[1-3].

如图1所示，一个典型的CGRA通常由主控制器、多bank存储器，DMA（direct memory access）和2D mesh网络连接的处理单元阵列（processing element array，PEA）组成. 每个PE主要由支持定点操作的功能单元（function unit，FU）、本地寄存器堆（local register file，LRF）、输出寄存器和配置缓存组成. 通过2组多路复用器（multiplexer，MUX），每个PE可以为其FU选择来自邻居PE或访存单元（load-store unit，LSU）的数据. PE和PE之间、PE和LSU之间往往通过mesh网络互连，实现局部数据的交换. 通过LSU，PE可以和多bank存储器进行数据交换. LSU通过全互连的交叉选择开关，可以访问多bank存储器中的任何一个bank. 如果PE之间发生访存冲突，即不同的PE需要同时访问数据存储器中的同一个bank，则会发生数据访存冲突. 冲突的访存请求将会被分配到多个时钟周期，这将严重影响CGRA的流水执行性能.

图  1  CGRA基础架构

Figure  1.  The basic CGRA architecture

下载: 全尺寸图片 幻灯片

类似于图1的CGRA结构我们也称为访存-计算解耦的CGRA架构. 因为在这种架构中，存在专用的LSU来确定内存访问的地址. 不需要在PE阵列上进行访问地址的计算，这使得这种架构可以进一步提升PE执行计算任务的效率. 这种访存-计算解耦的架构已经在许多加速器架构^[4-5]上得到了应用，并且在性能上取得了不错的提升. 在CGRA上，这种访存-计算解耦也已经开展了多项研究^[6-8]. 因此本文将侧重于访存-计算解耦的CGRA目标架构^[9].

为了加速执行CGRA上的循环内核，通常会使用模调度^[10]来使循环内核对应的数据流图（data-flow graph，DFG）以流水的方式执行. 通过最小化迭代间的启动间隔（initiation interval，II），改善循环执行的性能. 但是较小的启动间隔会引起更多的并发内存访问操作. 当循环内核包含具有对单个数组的多个引用时，对该数组的内存访问操作数量很容易超过bank的端口数量（通常每个bank为单端口或者双端口）. 在多bank结构中，甚至会超过bank的数量，这将导致访存冲突，造成性能损失.

为了打破bank端口的限制，存储划分通常将原始数组拆分存放到多个bank中. 常用的存储划分方法可以分为3类^[11]：块划分、循环划分以及块循环划分. 例如：文献[12]提出了一种基于线性变换（linear transformation based，LTB）的多维数组存储划分方法. 但是这种方法仅限于循环划分的方式，在某些情况下只能找到次优解. 并且由于其变换公式中包含较多的除法、乘法等复杂计算，导致其访存地址计算的开销较大. 为了简化访存地址计算的复杂性，文献[13]提出了一种访存-计算解耦的CGRA存储划分方法（CASCADE），该方法支持将1维数据划分到多bank中. 对于多维数据而言，CASCADE首先通过专用硬件将其展平为1维数组，然后对展平的数组进行块循环划分. 虽然这种方法简化了地址计算的复杂性，但是数组展平之后的划分结果具有不稳定性和次优性，其结果取决于原始数据的大小和尺寸. 对于不同的数组大小，会生成不同的划分方案，其中许多方案是次优的.

考虑到现有的方法无法在地址计算的复杂度和划分质量之间取得较好的平衡，我们提出了一种基于访存图案变形的粗粒度可重构计算架构存储划分优化方法. 本文的主要贡献有2点：

1）提出了一种基于访存图案变形的存储划分算法，该算法仅需要全“1”系数超平面来进行存储划分，并能在访问地址生成开销和划分结果质量之间取得良好的平衡.

2）实现了一种高面积效率和高能量效率的CGRA架构，以精简的地址生成单元来支持上述基于访存图案变形的存储划分结果.

实验结果表明，与目前最先进的架构相比，我们的架构具有平均1.25倍的能量效率提升.

1.   相关工作

如引言所述，在多bank存储结构中，单个bank存在端口的限制. 因此为了打破这种限制，存储划分通常选择将同一个数组中的元素存放到多个bank中，以实现对同一个数组的并行数据访问. 在FPGA的高层次综合^[14]中，存储划分已经得到了比较好的研究. 例如：文献[15]中的工作尝试在同一个循环迭代中以循环划分的方式将一个数组的多个内存访问划分到多个bank中. 文献[16]提出了对循环体内核中不同迭代的内存访问进行调度，以找到接近最优的存储划分方式. 尽管这些工作为循环流水中的高效存储划分迈出了第一步，但它们仅限于1维数据. 然而实际应用程序中通常包含具有多维数据的嵌套循环. 在文献[17]中，一种通用存储划分（generalized memory partitioning，GMP）方法被提出用来支持多维数组的块循环划分，以便在大多数情况下都能找到最优值，但是这种方法具有较大的地址计算开销. 在文献[18]提出通过数据重用的方法来消除一些对内存的访问操作，减少并行访存数量，但是这种方法会消耗额外的寄存器资源. 文献[19]提出了基于晶格的存储划分方法，具有较少的硬件和能量开销. 文献[20]提出了一种存储划分算法来支持仿射和非仿射访存图案. 文献[21]提出了一种基于图论的存储划分（GMB）方法来实现最优bank数量. 现有的这些方法，包括基于超平面的和基于图论的，都是针对给定形状的访存图案来寻找最优的bank数量，失去了同时最小化bank数量和硬件开销的机会.

在CGRA上，存储划分变得更具有挑战性，这是因为在CGRA上bank的数量十分有限（例如4~8个），同时复杂的地址生成对CGRA不太友好. 为此，迫切地需要一种能够以较低的地址生成代价来实现（近）全局最优（即最小化bank的数量）的划分策略. 为了能够解决上述挑战，已经存在多种关于CGRA的存储划分的方案. 文献[22–23]考虑存储管理和CGRA映射2方面因素下，提出了一种无冲突的循环内核映射算法. 文献[24]提出了基于LTB存储划分和模调度的无冲突的循环映射算法. 然而该方法由于仅考虑了迭代内的内存访问并且忽略了块划分，导致可能无法找到最优解. 此外，如果基于LTB算法来实现地址生成单元，那么芯片面积和功耗开销会显著增大. 为了简化地址生成的复杂性，文献[13]提出了CASCADE. 尽管这种方法很大程度上简化了地址生成，但是由于受到原数组尺寸大小的影响，导致划分结果在多数情况下并非最优解，甚至在某些情况下，解的质量十分糟糕.

从上面的分析中，我们注意到现有的CGRA存储划分工作无法在地址生成开销和划分质量之间取得良好的平衡. 为了能在控制地址生成的开销条件下，进一步提高划分结果的质量，本文提出了一种基于访存图案变形的CGRA存储划分优化方法. 由于访存图案的形状对划分结果至关重要，并且它与循环流水线中内存访问操作的调度密切相关，因此本文方法试图形成一种划分友好的访存图案，以在地址计算开销和划分质量之间达到良好的平衡. 尽管在这之前已经有人研究过存储划分和调度协同优化，但是他们仅限于1维数据或专注于迭代内的内存访问. 而本文的方法可以针对2维数组进行算子调度和内存划分的协同优化.

2.   存储划分的相关定义

在本节中我们主要介绍存储划分方法中的一些概念和定义.

在存储划分中，通常用向量的形式来表示数据在数组中的位置. 例如，对于一个2维数组，其数据元素的位置就可以用一个2维向量$({x}_{0},{x}_{1})$来表示. 在正式描述我们的算法之前，我们先给出一些基本的符号解释和定义.

定义1. 数据空间^[25]. 给定一个n维数组A，该数组的数据空间M被定义为所有存储元素的集合. M中数据元素$\boldsymbol{\phi }$的坐标可以表示为$\boldsymbol{\phi }={({x}_{0},{x}_{1},… ,{x}_{n-1})}^{\mathrm{T}}$，对于$0\le i\le n$都有${x}_{i}\in [0,{d}_{i}-1]$，其中${d}_{i}$表示数组在第i维度的宽度.

定义2. 访存图案^[25]. 由数组A的m个相邻数据元素组成的访存图案定义为$P=\{{\boldsymbol{\phi }}_{1},{\boldsymbol{\phi }}_{2},… ,{\boldsymbol{\phi }}_{m}\}$，其中${\boldsymbol{\phi }}_{i}={({x}_{0}^{i},{x}_{1}^{i},… ,{x}_{n-1}^{i})}^{\mathrm{T}}$.

定义3. 存储划分^[25]. 数组的存储划分表示为一对映射函数$(f\left(\boldsymbol{\phi }\right),g(\boldsymbol{\phi }\left)\right)$，其中$f\left(\boldsymbol{\phi }\right)$计算数据映射到bank号，$g\left(\boldsymbol{\phi }\right)$ 用于计算对应的bank内偏移地址.

定义4. 有效存储划分. 数据空间为M的数组的有效存储划分是指找到一对映射函数（$f\left(\boldsymbol{\phi }\right),g\left(\boldsymbol{\phi }\right)$），使得对于任意的 ${\boldsymbol{\phi }}_{1},{\boldsymbol{\phi }}_{2}\in M$，式（1）成立.

定义5. 基于线性变化的存储划分（LTB）. LTB是仅支持循环划分的存储划分方法. 给定一个n维数组的访问索引$\boldsymbol{\phi }={({x}_{0},{x}_{1},… ,{x}_{n-1})}^{\mathrm{T}}$，LTB执行线性变换$\boldsymbol{\phi }\to \boldsymbol{\alpha }\cdot \boldsymbol{\phi }$，其中$\boldsymbol{\alpha }=({\alpha }_{0},{\alpha }_{1},… ,{\alpha }_{n-1})$且${\alpha }_{i}\in \mathbb{Z}$. 假设N是表示bank数量的划分参数，则对于2维数组该映射函数可以表示为

定义6. 通用存储划分（GMP）. GMP是同时支持循环划分和块划分的存储划分方法. 假设N和B分别是划分参数和分块大小参数，则GMP在2维数组上的映射函数可以描述为

定义7. 基于扁平化存储划分（flatten-based memory partition，FMP）. FMP首先将一个d维的数据数组展平为1维数据数组，然后对1维数据数组执行块循环划分. 对于一个2维数据数组，其展平函数被描述为$x={d}_{1}{x}_{0}+{x}_{1}$. 在2维数组上，FMP的映射函数可以描述为

基于以上这些不同的策略，存储划分的主要任务是对$(\boldsymbol{\alpha },N)$，$(\boldsymbol{\alpha },N,B)$，或者$(N,B)$进行空间上的探索，以在使用的bank数量、存储开销和寻址复杂度之间进行权衡. 由于GMP在上述3种划分策略中具有最大的搜索空间，因此可以在大多数情况下达到最优解.

3.   动机示例及问题定义

在本节中，我们以一个例子来演示所提出的方法和其他方法的不同，并给出在CGRA存储划分中需要解决的问题.

3.1   动机示例

在图2（d）中展示了2维去噪算法的循环内核，该算法包括对数组C的4个取数据操作（L1，L2，L3，L4），其中${d}_{0}$和${d}_{1}$分别表示数组C第0维和第1维的宽度. 图2（a）中展示了该循环内核对应的原始DFG在启动间隔$II=1$的情况下流水线执行的场景，可以看到在同一个时刻，会同时执行同一迭代中的4个取数操作. 图2（b）表示数据空间中这种执行方式下的数组访存图案，这种访存图案用GMP方法进行求解，可以用4个bank进行划分，其中参数$\boldsymbol{\alpha }=\left(\mathrm{1,3}\right)， B=2$. 如图2（c）所示，为了实现GMP方法对应的划分函数（$f\left(\boldsymbol{\phi }\right),g\left(\boldsymbol{\phi }\right)$），生成了一个具有11个节点的DFG，包含4个乘法、2个除法、2个模运算和6个常数. 这样的DFG对应的电路将会比较复杂，同时也会导致较大的配置缓冲区. 即使将N和B的取值限制为2的n次幂（一些乘法、除法和模运算可以被简化为移位运算和与运算），但仍然有3个乘法无法消除. 因此，GMP是以复杂的地址生成为代价来得到最优或者接近最优的划分结果.

图  2  动机示例

Figure  2.  The motivating example

下载: 全尺寸图片 幻灯片

对于CASCADE^[13]中的方法，如图2（e）所示，它首先将2维数组平坦化为1维数组，然后对1维数组进行块循环划分. 在这个例子中，其划分参数 $B=2， N=5$，即需要5个bank. 如图2（f）所示，为了实现其对应的划分函数，我们生成了一个包含8个节点的DFG，其包括2个乘法、2个除法和2个模运算. 如果使用累加器^[13]实现数组平坦化，并且将划分参数的取值都限制为2的n次幂，则所有的复杂运算（乘法、除法和模运算）都可以被简化为移位运算和与运算. 因此这种平坦化的方法以较低的地址生成开销实现了次优的划分结果.

以上2种方法都无法在较低的地址生成开销的前提下，达到最优的划分方案，所以我们引入了基于访存图案变形的存储划分方法. 如图2（g）所示，DFG被重新调度了（L2和L4的执行时间步相较之前延后1个单位），来自不同迭代的访存操作将会同时执行. 重新调度之后，在数组的数据空间中，其访存图案如图2（h）所示变成了阶梯图案，因此当$\boldsymbol{\alpha }=\left(\mathrm{1,1}\right)$时，执行循环划分可以达到bank数量为4的最优划分. 当 $\boldsymbol{\alpha }$ 固定为$\left(\mathrm{1,1}\right)$时，其地址生成的DFG如图2（i）所示，只需要进行5次操作，其中包括1个乘法、1个除法和1个模运算. 同样地，如果将划分参数N的取值限制为2的n次幂，那么就只会存在1个复杂运算（乘法）. 这种方法相比GMP和CASCADE而言，既保证了划分结果的质量又减小了地址生成的开销. 因此基于访存图案变形的存储划分方法可以在适中的地址生成开销情况下找到最优或接近最优的划分结果.

3.2   问题定义

从3.1节的例子中，我们可以看到虽然GMP可以达到最优的解，但是其地址生成比较复杂，包含多个除法、乘法、加法运算. 而CASCADE虽然减小了地址生成的复杂度，但是其划分结果的质量是次优的. 这里我们将给出本文方法中关于阶梯图案及算法中重要变量的定义，并证明阶梯图案可以实现最佳划分结果，并在最后对CGRA存储划分问题进行定义.

定义8. 全“1”系数超平面. 如果LTB中的划分超平面的变换系数构成全“1”向量，即$\boldsymbol{\alpha }=(\mathrm{1,1},… ,1)$，则称之为全“1”超平面. 如图2（h）所示，法向量为$\left(\mathrm{1,1}\right)$的虚线表示全“1”超平面. 在启动间隔为II的流水线执行时，如果全“1”超平面恰好覆盖该访存图案的II个数据元素，则称完全全“1”超平面. 例如在图2（h）中，我们令 $\boldsymbol{\alpha }=\left(\mathrm{1,1}\right)$，在数据空间中，得到了若干条斜率为–1的直线，这些斜率为–1的直线就组成了全“1”系数超平面.

定义9. 阶梯图案. 给定一个由一组连续的全“1”超平面H覆盖的访存图案P，对于任意的$\boldsymbol{h}\in {H}$，如果h穿越不超过II个数据元素，则称P为阶梯图案. 例如在图2（h）中，L1，L2，L3，L4在数据空间可以被全“1”超平面覆盖，对于每一个超平面（虚线）都只穿越了访存图案中的1个数据元素，因此图2（h）中的访存图案为可视为一个阶梯图案.

定义10. 严格阶梯图案. 给定一个由一组连续的全“1”超平面H覆盖的访存图案P，对于除最后1个之外的任意$\boldsymbol{h}\in {H}$，如果h正好穿越II个数据元素，则称P为严格阶梯图案. 例如在图2（h）中，通过将L2和L4提前一步执行，数据空间中对应的2个元素（竖线纹理和点状纹理）各自向右移动1个单位. 在II=1时，4个全“1”超平面恰好都只穿越该访存图案的1个元素，此时的访存图案就称为严格阶梯图案.

定理1. 如果P是一个由数组中m个元素构成的严格阶梯访存图案，其对应的循环流水启动间隔为II. 使用全“1”超平面对该访存图案进行循环划分，可以达到最小的bank数量.

证明. 如定义10，一组连续的全“1”超平面中除最后1个以外，其他超平面能够覆盖整个图案P，且恰好穿越II个元素. 因此，需要$\left\lceil m/II\right\rceil$个连续的全“1”超平面来覆盖该图案，即仅需要最小的bank数（$\lceil m/ II\rceil$）来实现无冲突的存储划分. 证毕.

由于全“1”超平面的系数为常数1，并且不涉及块划分（B=1），其存储划分的映射函数可以简化为

定义11. 转移矩阵. 转移矩阵TranA的元素A_i,j表示访存图案中的第i个数据元素在移动j$-$m步之后（j$\in [0,\mathrm{ }2m]$，m为访存图案大小），经过全“1”超平面的划分，该数据元素被分配的bank序号. 由于j的取值范围在[0, 2m]，因此该转移矩阵的元素不仅能够表示数据元素的向右移动（j$-$m>0），还能表示数据元素的向左移动（j–m<0）. 为减少搜索空间，我们约定数据元素向左移动不能超过原始访存图案中最左侧的元素点. 对于不满足该约定的移动，其对应转移矩阵元素取值为–1.

针对如图2（b）中的原始访存图案，我们可以得到如下矩阵：

由于L2为该图案中的最左侧元素，其他几个元素向左移动后的位置不能超过L2的位置. 由于该限制，L1最多左移1步，转移矩阵中第0行的第1个非“$-$1”值出现在j=3（j$-$m=3$-$4=$-$1）的列中. 当L1左移1步时，会被划分到第1个bank，因此TranA[0][3]取值为1.

如动机示例所示，对内存访问操作的算子进行调度可以实现访存图案变形，并且通过严格阶梯图案可以达到最优存储划分. 因此我们将给出基于访存图案变形的存储划分问题的定义：

问题1. 给定循环内核的流水执行启动间隔II，其访存图案P包含m个元素，通过对该循环DFG的算子调度来实现访存图案变形使得：

1）在同一个全“1”超平面上的访存算子必须被调度到不同的控制步骤；

2）在调度形成的新访存图案中，最大化能够覆盖II个访存算子的全“1”超平面的数量.

对于第1项而言，由于同一个超平面上的元素将会存放在同一个bank中，因此需要将这些元素的访问操作分开调度，从而避免访存冲突. 对于第2项来说，？？最大化覆盖II个元素的全“1”超平面的数量意味着全“1”超平面的数量就越少，即所需要的bank数量越少.

4.   基于回溯的访存图案变形算法

由3.1节的动机示例可知，访存算子的调度可以改变访存图案. 本节详细介绍通过算子调度算法来改变访存图案实现存储划分. 该算法分为2个步骤，首先根据定义11计算出该访存图案的转移矩阵，然后据此转移矩阵进行回溯搜索得到最终的调度结果.

如算法1所示，我们首先对各个变量进行初始化，然后计算出访存图案P的转移矩阵TranA. 在得到转移矩阵之后，通过while循环来寻找在当前II下的解，如果当前II下无法找到可用的解，那么就增大II继续寻找，直到找到解. 在算法1的行⑩~⑯，我们根据访存图案中每个元素的移动距离、最小距离（minDis）和II来确定该元素对应的控制步. 确定了所有的访存算子的控制步之后，利用整数线性规划^[26]对剩下的非访存算子进行调度，从而生成最终的调度结果CS.

算法1. 基于回溯的访存图案变形算法.

输入：访存图案P，访问图案元素个数M，bank最大数量 N，DFG 算子集合 OP；

输出：使用bank数量N_used，调度结果CS.

① bankInfo ←$N\times M\;zeros；$

② minDis,selected_values ← 0；

③ dis[N] ← INT_MIN；

④ TranA = get_transfer_matrix(P)；

⑤ II$=\max(\lceil |P|\rceil /N, \lceil |OP|\rceil /PEA)$；

⑥ while(! find_solution(row=0,II))

⑦　II = II + 1；

⑧ end while

⑨ minDis = min(dis)；

⑩ for each bank_i in bankInfo

⑪　step ← 0；

⑫　for each p in bank_i

⑬　　CS[p] ← (dis[p]$-$minDis) II+step；

⑭　　step ← step + 1；

⑮　end for

⑯ end for

⑰ ILPScheduling(otherOperators)；

⑱ N_used←getUseBanks(bankInfo).

算法2通过回溯的方式来寻找转移矩阵TranA中符合条件的值. 首先从转移矩阵的第0行开始（即访存图案中的第1个元素），在第0行中搜索值不为$-$1且不会造成启动间隔大于给定II的值. 当在第0行中找到符合条件的值后，就更新bank分配列表和元素移动信息列表，再遍历TranA的下一行. 如果下一行找不到满足要求的值，那么就回溯到之前的状态. 当遍历完转移矩阵的所有行之后，就可以得到满足要求的bank分配列表和元素移动信息.

算法2. 函数find_solution.

输入：当前待处理行row，启动间隔II；

输出：bank分配信息bankInfo，元素移动距离dis.

① if row == M

②　return selected_values == M；

③　for col from 0 to 2M;

④　　value ← TranA[row][col]；

⑤　　if value ≠$-$1 && bankInfo[value]. size < II

⑥　　　bankInfo[value]. add(row)；

⑦　　　dis[row] ← col$-$M；

⑧　　　if (find_solution(row+1, II))

⑨　　　　return true；

⑩　　　end if

⑪　　　bankInfo[value]. remove(row)；

⑫　　　dis[row] ← INT_MIN；

⑬　　end if

⑭　end for

⑮ end if

⑯ return false.

5.   硬件架构以及编译流程

在本节中，我们首先介绍了适配以上存储划分结果的高效CGRA架构，然后再给出了总体的编译流程.

5.1   高效CGRA架构

在传统CGRA的基础之上，我们首先为所有的LSU单元添加了共享的时钟分频器（divider，DIV），然后对每个LSU单元的内部结构进行了精简化设计. 由于在模调度中仅在每II个周期执行1次特定的存储器访问操作，因此DIV 模块仅在每II个周期向特定LSU产生使能信号. 如图3（d）所示，时钟分频器由累加器（Acc）和II_max个比较器组成，其中II_max表示硬件允许的最大循环流水II. 由于LSU上的存储器访问操作在高度为II的时间窗口中任意一个时间步执行，因此比较器可以用于为工作在不同控制步的LSU生成II个使能信号.

图  3  本文提出的硬件架构

Figure  3.  Our proposed hardware architecture

下载: 全尺寸图片 幻灯片

在图3（b）中列出了精简的LSU的结构. 它主要由加载寄存器（load register，LDR）、存储寄存器（store register，STR）、地址生成器（address generator，AG）和配置缓冲区组成. 精简之后的AG如图3（e）所示，AG首先接收来自时钟分频器的信号来启用累加器${ACC}_{{x}_{1}}$，通过给定步长stride₁和初始值start₁来生成内存访问坐标的低维分量${x}_{1}$. 如果${x}_{1}$达到最大值，则${ACC}_{{x}_{1}}$将重置为start₁. 同时，启用另一个累加器${ACC}_{{x}_{0}}$，使用步长stride₀和初始值start₀生成内存访问坐标的高维分量${x}_{0}$. 然后，根据式（8）（9），使用2个加法器、1个乘法器、1个移位器和1个与门来计算产生bank号和偏移地址. 为了简化电路，bank数量N的取值也仅限于2的n次幂. 因此，除法操作被简化为右移位器，求模运算简化为与运算. 在这样的架构实现中，由于存储划分超平面的系数为常数1，其地址生成的开销被大幅度降低了.

5.2   整体编译流程

图4展示了我们编译框架的总体流程. 首先，使用LLVM^[27]前端工具将输入循环内核转换为中间表式（IR）；然后基于IR生成DFG，其中记录着相应的访存图案；接下来调用算法1执行访存图案变形，并生成调度结果和划分结果；最后基于调度结果执行基于最大团算法^[10]的DFG映射，并生成配置信息.

图  4  整体编译流程

Figure  4.  Overall flow of compilation

下载: 全尺寸图片 幻灯片

6.   实验结果

在本节中，为了评估我们提出的方法，我们进行了一系列实验并比较了在硬件资源无约束情况和有约束情况下的结果. 在硬件资源无约束的情况下，存储划分可以达到最优解. 在资源受限情况下，存储划分只能在目标架构中找到次优解.

6.1   实验设置

由于FMP^[13]和GMP^[17] 这2种存储划分方法与我们所提出的方法都是基于线性变换，并且不像其他方法（例如基于图^[21]或者基于晶格^[19]的存储划分）需要额外的存储空间，我们采用FMP和GMP作为主要的比较对象. FMP将多维数组平坦化成1维数组进行存储划分，并采用CASCADE^[13]简化的LSU进行地址生成. 由于FMP方法对数组的宽度敏感，因此在执行FMP时，我们在第1维上提供了d₁=30，32，34这3种可变宽度. 为简单起见，我们使用FMP-30，FMP-32，FMP-34分别表示d₁=30，32，34时FMP的实验结果. GMP直接针对多维数组进行线性划分，需要如图2（c）所示的复杂地址生成单元来支持复杂参数的线性划分. 我们提出的基于访存图案变形的存储划分方法PMM（access pattern-morphing-based memory partitioning）首先采用算法1进行存储划分，并使用如图3（e）所示的精简地址生成器来实现全“1”系数的存储划分. 为了屏蔽硬件差异带来的影响，我们还将算法1的存储划分的结果映射到GMP的目标硬件架构上（简称为PMM^*）进行比较.

为了公平比较，所有架构都包括一个由8个bank组成的4 KB存储空间以及4$\times$4的PE阵列，每个PE中的LRF包含4个寄存器，支持多周期数据依赖路由. 为了硬件的高效实现，约定所有方法的划分参数N和块大小B的取值均为2的n次幂. 因此，一些乘法、除法和模运算可以简化为移位器和逻辑门. 所有方法的相应编译均采用RAMP^[10]进行后端映射，该映射算法运行在频率为2.1 GHz、内存为64 GB的Intel 16核CPU上.

实验中所有用例都来自真实应用^[28]（包括医学图像处理和H.264运动补偿等）中的12个循环内核. 如图5所示，这些内核在2维数据中具有不同的访存图案，其中访问元素的数量范围为4~25.

图  5  12个基准访存图案

Figure  5.  Access patterns of the 12 benchmarks

下载: 全尺寸图片 幻灯片

6.2   无约束情况下的比较

为了验证FMP，GMP，PMM^*这3种方法的存储划分质量，我们首先在无资源约束的情况下进行了实验，其可用bank的数量是无限的，参数N和B可以是任何正整数. 在这种情况下，由于所有的存储器访问操作都可以在单个周期内执行，它相当于II=1的完全流水执行.

图6展示了在无约束情况下各个方法占用的bank数量情况. 平均而言，FMP-30，FMP-32，FMP-34，GMP和本文算法PMM^*分别使用9.83，10.33，10.58，9.00，8.67个bank. 与GMP相比，PMM^*可以在所有12个内核上达到最少的bank数量，而GMP无法在sobel和median这2个例子中上求得最优划分结果. 在这2个例子中，访存图案的几何形状是造成GMP失败的主要原因. 对于有sobel而言（具有8个访问元素，N初始化为8），按照文献[17]中的方法遍历整个搜索空间后，GMP仍然无法找到无冲突的解决方案. 于是，N将会被增加到9，最终得到一个无冲突的解. 对于median这个用例，GMP必须将N增加到10，以获得无冲突的解. 利用访存图案变形，PMM^*可以形成存储划分友好的图案，从而使这些内核占用的bank数量最少. 对于FMP，对于初始化的N，它在展平数组上的搜索空间非常有限，并且容易出现访存冲突，因此它更容易得到次优解. 从图6中我们还注意到FMP的划分结果对数据数组的维度宽度非常敏感，而GMP和PMM^*对不同宽度的数据都很稳定.

图  6  无约束条件下的bank使用数量

Figure  6.  Number of used banks in the unconstrained situation

下载: 全尺寸图片 幻灯片

此外，为了能够得到正确的bank内地址，在划分之后需要对数组进行填充，将低维度的数组宽度扩充至N$\times$B的整数倍. 图7展示了具有不同宽度（d₁）下3种方法的填充数据大小. 当d₁=30时，平均而言，PMM^*的填充大小分别是FMP和GMP的86.7%和98.1%. 随着宽度的增加，PMM^*仍然优于FMP和GMP. 由于我们使用的是循环划分（即B=1），并且N可以达到最小值，所以PMM^*更容易使得N$\times$B的值较小. 因此，平均而言，PMM^*只需要较少的数据进行填充，可以进一步减少内存的开销.

图  7  不同d₁取值下的数据填充大小比较

Figure  7.  Data padding size comparison over different d₁ values

下载: 全尺寸图片 幻灯片

6.3   硬件频率、面积、功耗的比较

为了比较硬件开销，我们首先使用Verilog HDL分别实现了GMP的访存-计算解耦的CGRA架构、面向FMP的CASCADE架构和本文提出的如图3所示的CGRA架构；然后使用Synopsys Design Compiler在FreePDK 45 nm工艺库上评估了它们的频率、面积和功耗；最后使用Cadence innovus完成布局布线. 这3种架构之间的主要区别在于LSU中的AG不同. 对于面向GMP的访存-计算解耦的CGRA架构，其AG实现根据式（4）（5）.

如表1所示，CASCADE和CGRA具有相同的频率，而GMP架构的频率较低. 这是因为GMP的CGRA架构中复杂的AG成为关键路径. 与CASCADE相比，CGRA的面积为0.549 mm²，平均功耗为120.523 mW，面积仅增加了5.78%，功耗仅增加了8.48%. 由于GMP的目标架构在AG中使用了更多的乘法器和用于超平面参数的配置缓存， GMP的目标架构在面积和功耗方面都有更大的开销.

表  1  频率、面积、功耗的比较

Table  1.  Comparison of Frequency, Area and Power

架构	频率/MHz	面积/mm2	功耗/mW
GMP-解耦架构	452.49	0.607	137.128
CASCADE	462.96	0.519	111.101
PMM（本文架构）	462.96	0.549	120.523

下载: 导出CSV 

| 显示表格

6.4   资源有限情况下的比较

当将12个内核映射到CGRA时，存储划分受到最大bank数量（N$\le$8）和N的取值为2的n次幂的约束. 图8展示了12个内核的归一化的流水执行性能（II/II_min）和归一化的吞吐量（频率/II_mapped）的比较，其中II_min是理论上能达到的最小II，II_mapped 是实际映射成功的II. 为了简单起见，该图仅显示了d₁=30，32，34时的FMP平均值. 如图8所示，相比其他2种方法，PMM^*由于屏蔽硬件差异，在所有测试用例中均达到了最好的流水执行性能. 由于FMP需要更多的bank完成存储划分，在资源有限的情况下，其流水执行性能最差. 对于GMP而言，在大多数测试用例中，它都表现较好. 但是在sobel和median这2个测试用例中，由于其无法做到最优存储划分，因此需要更大的II才能在8个bank的限制下完成无冲突访存，从而造成其流水执行性能下降. 平均而言，PMM^*相比于FMP和GMP在流水执行性能上分别可以获得平均 1.54倍和1.09 倍的加速比. 再考虑到算法和硬件的综合影响，PMM的目标硬件相比于GMP的目标硬件具有更高的频率. 因此，如图8所示，经过算法和硬件的联合优化，相比于FMP，GMP，PMM^*，PMM 在吞吐量上分别获得平均1.74倍、1.15倍、1.02倍的加速比.

图  8  映射的II和吞吐量的比较

Figure  8.  Comparison of the mapped II and throughput

下载: 全尺寸图片 幻灯片

6.5   能量效率的比较

为了考虑包括功耗、频率、流水性能等因素的综合影响，我们进一步采用能效指标（吞吐量/功耗）进行比较. 如图9所示，与FMP和GMP相比，PMM可以分别实现平均1.67倍和1.25倍的能效提升. 在motion-LH用例中，由于FMP的硬件功耗最低，且这3种方法在这个用例中的映射II均为1. 因此，FMP在motion-LH这一用例中达到了最高的能效. 在其他的用例中，由于FMP得到的映射II均高于其他2种方法，因此FMP的能效较低. 而对于GMP而言，虽然其映射II基本接近理论最小值，但是由于其硬件结构的能耗较大，因此其能效相对较低. 屏蔽硬件影响之后，我们发现PMM^*相比于FMP和GMP 依然有平均1.51和1.14 倍的能效加速. 因此，相比于FMP和GMP，PMM^*分别贡献了76%和56%力量，而硬件优化分别贡献了24%和44%的力量.

图  9  能效的比较

Figure  9.  Energy efficiency comparison

下载: 全尺寸图片 幻灯片

6.6   编译时间的比较

图10给出了FMP，GMP，PMM在存储划分算法上的编译运行时间比较. 其中FMP为${d}_{1}=32$时的编译时间. 由于不同测试用例的耗时差异较大，为方便展示，我们选取了对数坐标轴. 由于PMM在图案变形之后仅需全“1”超平面，不需要穿越整个迭代空间去寻找划分超平面，也不需要对数组进行平坦化，所以用于超平面的搜索时间较少. 另外，虽然我们的图案变形使用了回溯算法，但是该算法仅运行在问题规模并不大的访存图案上. 因此，PMM的平均编译时间仅为GMP和FMP的 13.07% 和 45.57%.

图  10  存储划分编译时间的比较（d₁=32）

Figure  10.  Banking compilation time comparison (d₁=32)

下载: 全尺寸图片 幻灯片

由于存储划分的复杂性远低于DFG后端映射^[10]，因此不同方法在总编译时间上并没有明显的差距. 如图11所示，PMM和GMP获得了几乎相同的编译时间. 这是因为这2种方法在所有内核都获得了相同的II，因此映射算法几乎具有相同的复杂度. 至于FMP，对于某些测试用例它的存储划分结果需要更大的II. 由于更大的II下硬件资源约束更加宽松，FMP的后端映射更容易找到合法的映射结果. 平均而言，PMM在总体编译时间上相比于FMP和GMP具有平均1.92 倍和1.02 倍的时间消耗.

图  11  总体编译时间的比较

Figure  11.  Total compilation time comparison

下载: 全尺寸图片 幻灯片

7.   结　　论

本文提出了一种针对2维数组的存储划分和CGRA硬件的协同优化方法. 在算法上，我们通过访存图案的变形不仅能找到（近）全局最优的划分结果，还能简化用以存储划分的超平面的参数. 在硬件架构上，我们根据简化的超平面参数设计了精简的地址生成单元. 实验结果表明本文方法不仅能取得较好的存储划分方案，并且能够减少硬件开销，最终能够提升整体能效. 目前本文方法只能针对2维数组进行存储划分. 未来，我们将把存储划分方法扩展至高维数组.

作者贡献声明：潘德财提出了求解算法、实验设计，分析数据并撰写论文；牟迪协助部分实验设计；尚家兴对论文撰写提出指导意见；刘大江提出研究思路并对论文的实验和撰写提出指导意见.