FPGA设计空间探索综述

A Review of Spatial Exploration of FPGA Design

摘要: 设计空间探索(DSE)问题一直是一个具有挑战性的问题，因为设计空间大小呈指数倍增长，仿真时间非常长，并且DSE存在多个目标。由于人工探索的局限性促使了许多自动探索的算法的提出，于是设计师们希望通过一种自动化的方法来解决这个问题，从而加快探索过程。本文旨在通过对设计空间探索技术进行的调查，以便为研究人员提供有关未来研究方向的见识。

Abstract: The Design Space Exploration (DSE) problem has always been a challenging one, because the size of the design space is exponentially increasing, the simulation time is very long, and DSEs have multiple targets. Because the limitations of human exploration have led to the introduction of many algorithms for automatic exploration, designers hope to solve this problem through an automated method to speed up the exploration process. This paper aims to provide researchers with insights into future research directions through the investigation of spatial exploration techniques for design.

1. 引言

现场可编程门阵列(FPGA)是一种可重新配置的数字逻辑设备，有助于快速进行原型设计和设计验证，从而使设计人员能够开发强大的硬件和软件解决方案。近年来，FPGA系统已在许多应用中获得普及，例如数字信号处理、高性能计算、生物应用等。FPGA显示出在硬件专业化方面的巨大潜力，为了获得高质量的结果(QoR)，CAD工具需要大量的人工来配置大量的设计和工具参数。由于CAD映射流程的每个步骤通常都是NP-complete，因此有必要使用试探法在合理的时间内生成FPGA比特流。现代FPGA支持数百万个LUT，数千个DSP和片上Block RAM，以及各种奇特的硬件功能，导致编译时间增加到数小时或数天。当处理设计流程中的时序约束时，通常会反复使用FPGA CAD工具来提供时序收敛，而长时间运行时间和复杂的配置选项的结合使开发人员越来越难以管理此设计过程。FPGA编译流程可以分解为一系列连续的CAD阶段，比如高层次综合、逻辑综合、工艺映射、逻辑单元打包和布局布线等。在每个阶段进行设计空间探索(DSE)都有可能影响下面阶段的选择。DSE中存在多个目标，从而产生了一组最优解，也称为Pareto最优解，而不是单个最优解。在没有任何进一步信息的情况下，这些Pareto最优解都不能被认为比其他解更好。因此，非常需要一种自动方法来尽快找到尽可能多的Pareto最优设计。

本文调查发现对相关技术进行分类时，使用不同的技术主要区别所探索的问题不同，导致输入的数据类型不同。输入的数据主要分成无序的，有序的和不规则的。如果探索的是组合优化问题即输入的数据是无序的，通常使用的是传统的机器学习方法或是本地搜索技术，如果输入的数据是有序的(图片类型)通常用深度学习的方法，而不规则结构(比如图)会使用图学习的方法。

本文其余部分安排如下：第二节讨论了先前设计空间探索技术相关的工作，详细的阐述了针对设计空间探索提出的不同类型的算法，第三节对基准进行总结，讲述了高层次综合常见的基准测试，第四节介绍了DSE常用的评估指标，第五节是结论。

2. 设计空间探索技术

2.1. 高层次综合

高层次综合(High level Synthesis, HLS)通过允许此类任务以更高的抽象级别进行(以C/C++或system C等高级语言作为输入综合到优化的低级实现(例如RTL或门级网表))，HLS技术已被广泛研究了二十多年，并且到目前为止，不仅在学术界而且在工业中已经开发了许多HLS工具，从而简化了硬件设计和验证。在HLS中进行有效的设计空间探索是一项重要的研究任务，现代HLS工具中会提供一些可用的循环优化的设置，比如展开，流水线，数组拆分，内联等设置，组合的方式呈指数增长。

2.2. 基于学习的方法

基于学习的方法，通过在运行实际模拟/合成之前预测解决方案质量来指导DSE过程，与本地搜索技术相比，基于学习的方法可以产生更好的解决方案质量，并且需要较短的仿真/综合运行时间，使用基于机器学习算法的算法比较如表1所示。

Table 1. Comparison of algorithms using machine learning algorithms

表1. 使用机器学习算法的算法比较

我们知道机器学习训练模型是一个非常耗时的过程，以如今计算力而言要想将每种可能的参数组合都实验一遍(即网格搜索)明显不现实，所以一般就是事先限定若干种可能，机器学习方法主要理论是通过仅对感兴趣的一部分进行采样，学习了采样组合的特性，企图去减少设计空间。即使不能找到Pareto最优解，但是可以从概率上找到一个“相对最优”。比如以下基于传统机器学习算法的模型，Mahapatra和Schafer [1] 提出了一种基于决策树机器学习算法的快速模拟退火算法(FSA)，在初始阶段生成决策树，以决定哪些属性有助于最大化成本函数，然后固定这些属性，很大程度减少了设计空间，可以在HLS中进行有效的多目标设计空间探索。Liu和Carloni [2] 提出了基于随机森林的学习模型以解决监督设计空间探索，且在初始阶段引入了转导实验设计，它可以对具有代表性和难以预测的微体系结构选择进行抽样，并将其用于训练学习模型。同样是基于随机森林机器学习分类的方法，Zacharopoulos等 [3] 提出的方法着眼于Loop Unrolling指令，能够预测目标应用程序中所有循环的最佳循环展开因子。Lo和Chow在文章 [4] 使用基于贝叶斯优化方法来自动选择HLS指令设置，以及在文章 [5] 采用了多保真度优化方法，对HLS CAD流程中可用的多个度量的组合用高斯过程(GP)回归方法进行建模。以上是使用单个机器学习算法建模的，还有集合了多种算法进行建模。比如Makrani等 [6] 采用的方法是基于集成学习提出了一个称为Pyramid的框架来准确估计HLS设计的最佳性能和资源利用率。

基于神经网络的模型可映射任意复杂的非线性关系，且具有高速寻找优化解的能力。Hsiao和Anderson [7] 提出了基于卷积神经网络(CNN)的预测器，它可以预测由于减少位宽而带来的合成后区域节省，并为用户提供程序变量及其区域影响的排名，实现较高的区域预测精度，并能够快速探索节省区域的机会。算法比较如表2所示。

Table 2. Comparison of algorithms using neural network algorithms

表2. 使用神经网络算法的算法比较

其它基于学习的方法，Zhao等 [8] 提出了COMBA，这是一个基于模型的综合分析框架，相当于一个Vivado HLS工具。它能够使用可插拔分析模型，递归数据收集器(RDC)以及度量指导的设计空间探索算法(MGDSE)来分析与设计描述中的功能，循环和数组有关的多种编译指示的影响。Xydis等 [9] 开发了一种名为SPIRIT的新型HLS探索框架，该框架利用响应面模型(RSMs)来预测设计点的质量，并且使用频谱技术来指导迭代细化。Liu等 [10] 发现原以为当重新合成(HLS)时，导致ASIC情况下导致Pareto最优设计的综合指令的相同组合，当以FPGA为目标时，这也将导致Pareto最优设计，实验结果并非如此。引入基于预测模型的方法以快速进行，而无需重新探索，找到给定ASIC的探索结果的FPGA Pareto最优设计。算法比较如表3所示。

Table 3. Comparison of algorithms using other learning-based algorithms

表3. 使用其他基于学习的算法比较

2.2.1. 群智能优化算法

由于解决方案空间很大，很多的DSE问题依赖于本地搜索技术，例如，像遗传算法和PSO这些经典黑盒优化算法，我们归类为群智能优化算法。但是，当与CAD工具一起使用时，这些算法在每一步都需要实际的仿真/综合来获得解决方案的质量，因此要经历长时间的仿真/综合运行时间。群智能优化算法主要模拟了昆虫、鸟群和鱼群的群集行为，这些群体按照一种合作的方式寻找食物，群体中的每个成员通过学习它自身的经验和其他成员的经验来不断地改变搜索的方向。群智能优化算法的突出特点就是利用了种群的群体智慧进行协同搜索，从而在解空间内找到最优解，比如 [11] - [20]。我们主要研究以下几篇，Ferrandi等 [11] 与Schafer和 Wakabayashi [12] 提出了一种基于遗传算法的高层次综合设计空间探索方法，而Liu等 [13] 同样提出了基于遗传算法进行搜索，并且指出了用机器学习进行建模，该方法首先针对给定的HLS多个行为描述，针对ASIC生成各种数据流配置，然后基于成分预测模型，映射到FPGA时自动重新优化数据流。与以上工作有所差异的是，Sarkar等 [14] 提出一种基于自适应遗传算法的解决方案，用于在HLS期间对控制数据流图的数据路径资源配置和循环展开因子(UF)进行综合探索，以实现最佳调度。Sengupta和Bhadauria [15] 提出用粒子群优化算法驱动DSE，除了在探索过程中将功耗和执行时间(或延迟)作为设计目标之外，还考虑了最佳数据路径生成过程中的多周期瞬态故障约束。

2.2.2. 其它DSE算法

除了以上方法外，还有以下其他高层次综合DSE算法。比如论文 [21] [22] [23] [24] [25] 主要通过对高级语言程序修改或插入指令实现设计空间探索。Silva和Bampi [21] 提出了一种迭代，递归和多平台的方法，有效地探索了设计空间。Schafer在论文 [22] 中提出了对knobs进行分类并顺序进行探索来加快设计空间探索(DSE)的速度，在论文 [23] 中介绍了一种分层方法，分别探索每个功能，然后执行合并阶段以获得总体优势结果。Gao等 [24] 介绍了第一个开源程序优化器，用于自动重写给定程序以优化延迟，同时控制准确性和面积。

根据衡量设计空间探索算法性能的常用方法，可看出时序是评估算法好坏的重要指标，但是对于精准的时序信息提取存在不小的难度。在Liu等 [25] 提到缓慢的CAD运行时间和繁琐的低级寄存器传输级设计一直困扰着FPGA开发，所以设计离线表征工具，以生成校准路径并使用RapidWright提取FPGA互连资源的时序延迟。

2.3. RTL

当前的技术主要集中在设计流程的单个阶段，例如高级综合(HLS)，从而错过了重要的跨界优化机会。现有的方法通常使用pre-PnR甚至是pre-synthesis报告来评估设计点的质量，虽然这可以缩短执行时间，但仅依靠早期设计阶段的粗略估计可能DSE无法达到高质量的设计点。为了解决上述缺陷，以下是基于多阶段设计空间搜索。

这类文章也用了各式各样的方法进行设计空间探索。Kapre等 [26] 介绍了一种基于智能，机器学习和云计算的方法，可有效地自动选择参数，以最大程度地降低计时成本。 [27] [28] [29] 用的都是InTime插件。Kapre等 [27] 建议在贝叶斯学习和分类框架的支持下在云上并行评估多个CAD运行，以生成最有可能有助于实现时序收敛的多个CAD参数组合。虽然InTime对于FPGA设计的时序收敛很有用，但是有可能需要在2-3天的探索中以完全自动化的方式实现定时收敛，于是Yanghua等 [28] 人通过将特定于设计的特征选择与分类相结合，这些分类方法可提高模型质量并减少交付时序收敛所需的迭代次数。同样为了提供具有高分类器准确性的时序收敛，从而减少时序收敛的迭代次数。在Yanghua等 [29] 又专注于选择合适的机器学习算法和技术，以识别和调整最有前途的解决方案。此外Xu等 [30] 也专注于选择合适的机器学习算法，设计了一种高效的并行化方案，该方案使多个基于multi-armed bandit (MAB)的自动调谐器能够同时探索设计空间，具体来说是OpenTuner (一个开源自动调整框架)使用的MAB算法将每种搜索方法视为一条手臂。同样Ustun等 [31] 也是基于OpenTuner构建学习辅助FPGA自动调整框架，具体来说，LAMDA选择了OpenTuner提出的一组看不见的配置，XGBoost回归器用于根据工具和特定于设计的功能估算时序。以上的论文多数是针对时序的，Mametjanov等 [32] 提出基于机器学习的方法来自动调整FPGA设计参数可以大大降低功率要求，同时仍然满足时序约束。

同样为了提高了预测准确性并降低了过多的仿真成本，与传统的蛮力DSE方法相反，Guo等 [33] 提出了Co-Training Model Tree (COMT)方法，该方法可以利用未标记的设计配置来改进模型。除了提高了预测精度外，由于使用了可理解的模型树，COMT还可以指导微处理器的设计。

我们知道准确地预测任何配置的性能是一个难题，它需要大量的训练模拟来达到不错的精度，所以回归模型大都集中于预测任何给定体系结构配置的性能，而Chen等 [34] 认为架构师在DSE流程中最需要的信息是，给定的配置在存在设计约束的情况下是否会比另一个配置表现更好，还是比目前为止看到的任何其他配置都更好，而不是精确地估计该配置的性能。ArchRanker采用了一种称为RankBoost的代表性学习排名算法来构建排名模型，以预测两种架构配置中哪一种效果最佳。

2.4. 布局布线

在2.1和2.2中所解决的问题主要是组合优化问题(属于无序的数据)，所以主要使用的是机器学习方法，人们尝试过用深度学习解决组合优化问题但效果不明显，但人们仍希望使用深度学习解决问题，于是把问题转移到布线性预测上。早期的可布线性预测有助于设计人员和工具执行预防措施，从而可以主动避免违反设计规则的情况。对于大型设计，物理设计过程通常要花费数小时至数天的时间，而布线是最关键的步骤，而布局布线过程不能分开，特定的位置可能根本无法布线，而稍微不同的位置可能会产生高质量的布线。

使用深度学习意味着数据的读取是以图片的形式的，即将布局信息认为是一张图片的信息。我们知道，设计一个既准确又快速的布线预测器是一个巨大的挑战，Xie等 [35] 利用卷积神经网络来应对这一挑战，提出了称为RouteNet的方法可以在不进行全局布线的情况下评估单元布局解决方案的总体可布线性，或者预测DRC (设计规则检查)热点的位置。Yu和Zhang [36] 在 [35] 的基础上提出了一种基于条件生成对抗网络(conditional GAN)的方法，该方法通过给定的解决方案来估计详细的布线拥塞。所提出的方法使用条件生成对抗网络模型完全预测了布线拥堵热图。在Yu和Zhang的基础之上，Alawieh等 [37] 使用高分辨率图像，加快FPGA布局和布线的闭合速度。

2.5. IP设计空间探索

IP核心是逻辑或数据块，用于制造产品的FPGA或ASIC。设计人员可以通过利用通常由第三方开发的现有IP模块来构建整个芯片或其一部分，而不是从头开始设计芯片中的每个组件。这种做法极大地减少了较大芯片中各个子模块的开发时间和成本。作为设计重用的基本要素，IP内核是不断重复使用以前设计的组件的不断发展的电子设计自动化(EDA)行业趋势的一部分。Papamichael等 [38] 提出了一种在IP生成器中内置扩展遗传算法(GA)来执行自动IP参数调整的方法，并且做了一些扩展，使IP作者可以嵌入相关的设计知识，在IP作者知识的帮助下，Nautilus指导的GA可以进一步加速GA搜索过程。Papamichael是基于进化算法进行IP设计空间搜索，如今HLS工具供应商已经开始提供保护行为IP，允许BIP用户以编译指示的形式将综合指令插入源代码，所以Wang和Schafer [39] 提出了一种通过对BIP的不同部分进行加密来选择性地控制搜索空间的方法。

2.6. 其它

前面讨论过对于有序和无序数据所常用的技术，而对于不规则结构主要使用图学习。我们知道如果使用深度学习可以将输入视为图像，以便在使用DL进行图像处理的先前工作的基础上进行构建。但是，当书投入的是一个网表，如果用深度学习处理网表，估计电路中的性能需要考虑很多的偏置，比如图片放大放小或是旋转都会产生不必要的影响，所以Ma [40] 考虑使用图学习。Ma为了处理逻辑电路的不规则图表示，提出了一种高性能的图卷积网络(GCN)模型，该方法适用于识别网表中难以观察的点，与最新的商业工具相比，基于GCN模型和迭代观察点插入流程，在工业设计上实现了更好的可测试性。

除此之外现代VLSI同样面临着DSE复杂问题，比如 [41] [42] [43] [44] [45]。主要详细介绍一下几篇， [41] [42] [43] 使用SynTunSys使设计人员的决策过程中的关键部分自动化，来控制综合参数调整过程，SynTunSys包含有决策引擎算法组件，决策引擎解决的一般问题可以描述为黑盒调整或搜索，并且也已使用多种技术来解决，例如机器学习和贝叶斯优化等。此外还有Kwon等 [45] 提出了一种LSPD参数推荐器系统，该系统通过张量分解和回归学习协作预测模型。

对于专用多处理器片上系统(MPSoC)的设计，也可以调整各种可自定义参数，以根据选定的品质因数找到最佳折衷方案。比如论文 [46] 提出了结合了实验设计(DoE)和响应面建模(RSM)技术，用于管理系统级约束。

3. 基准

FPGA十分依赖于基准来评估其硬件和软件解决方案的性能，并且标准基准套件对于研究人员定量评估其算法至关重要。因此，必须使用标准和公平的基准测试实践来评估FPGA系统并确定其支持目标应用程序的潜力。例如，最终用户可以研究各种FPGA供应商发布的基准测试结果，以选择适合于预期应用的FPGA器件。因此，FPGA社区开发了许多基准，以评估实现这些系统的硬件和软件解决方案。这项调查也探索了基准测试的使用，以评估包含FPGA器件及其相关软件设计工具链的系统。

这段讨论的是，不同的基准是基于不同的语言的基准程序，针对的目标也不同。虽然有几篇论文选用了相同的基准套件，但是其真正选用的基准或是数量都有所不同，对于评估指标也有差异。比如在论文 [5] 使用CHStone套件中10个基准，主要针对减少位宽而带来的合成后区域节省，生成了约7000个位宽减少的电路，其目标是估计自适应逻辑模块(ALM)的面积消耗，其中ALM是具有两个触发器的双输出6-LUT。论文 [6] 只使用CHStone套件中的ADPCM基准，ADPCM设计空间大小为17024，这篇论文将LUT的使用，最坏情况下的估计周期数和时钟周期视为相关的设计指标。论文 [7] 的估计目标为LUT，FF，DSP和BRAM的资源使用情况，以及Minerva报告的最大时钟频率。

总结上述列举的论文，下面介绍几个DSE中比较常见的基准。

3.1. CHStone

CHStone [47] 是一套基于C的高级综合的基准程序，CHStone套件包含从各种应用程序领域中选择的12个程序，包括算术，媒体处理，安全性和微处理器等。CHStone包含12个基准测试aes，blowfish，dfadd，dfdiv，dfmul，dfsin，gsm，mips，motion，sha，adpcm，jpeg (四个算术程序，四个媒体应用程序，三个加密程序和一个处理器)。CHStone基准套件非常易于使用，CHStone基准测试程序使用有限的标准的C语言编写，不使用大多数现有HLS工具不支持的以下数据类型和构造：浮点数据，诸如struct的复合数据类型，动态内存分配和递归。此外CHStone基准测试套件未使用此类特定于工具的扩展，因此CHStone具有高度的可移植性。使用CHStone的论文有 [5] [6] [7]。

3.2. S2CBench

S2CBench [48] 是用于高层次综合的SystemC基准套件，不仅包括不同大小的应用程序，而且这些应用程序通常来自HLS中使用的各个领域(例如，加密，图像和DSP应用程序)，而且还测试了每种应用程序中的特定优化技术。S2CBench包括12+1针对HLS中通常使用的各种应用的程序。12个基准符合最新的SystemC可综合子集，而一种设计(FFT)是不可综合的，因为它包含三角和浮点运算(qsort, Sobel, aes_cipher, kasumi, md5C, snow3G, adpcm, fft, fir, decimation, interpolation, idct, disparity)。CHStone基准套件与S2CBench的工作类似，它以HLS为目标，并包含一组ANSI-C程序，使用ANSI-C的主要缺点是某些主要的商用HLS工具不支持ANSI-C，而所有主要的HLS工具都支持一种通用语言：SystemC。使用S2CBench的论文有 [1] [6] [10] [13] [22] [23] [39]。

3.3. MachSuite

高级综合和与加速器相关的体系结构显示了工作负载选择方面的巨大差异。为了提高加速器研究社区的标准化，MachSuite [49] 设计目的便是用于评估高级综合工具和以加速器为中心的体系结构。MachSuite是一组涵盖12个不同内核的19个基准测试，旨在涵盖各种应用程序域并结合不同的算法选择(AES/AES，BFS/BULK，BACKPROP/BACKPROP，BFS/QUEUE，FFT/STRIDED，FFT/TRANSPOSE，GEMM/NCUBED，GEMM/BLOCKED，KMP/KMP，MD/KNN，MD/GRID，NW/NW，SORT/MERGE，SORT/RADIX，SPMV/CRS，SPMV/ELLPACK，STENCIL/STENCIL2D，STENCIL/STENCIL3D，VITERBI/VITERBI)。与CHStone相比，CHStone被设计为HLS工具的评估机制，它专注于少量的低级计算，虽然对于评估较旧的HLS框架的功能很有用，但在现代CAD工具链所处理的复杂设计以及许多架构师正在考虑和构建的扩展系统设计的背景下，有些不足。使用MachSuite的论文有 [4] [5]。

3.4. PolyBench

PolyBench [50] 是一个包含30个数值计算的基准套件，具有静态控制流，并从各个应用程序域的操作中提取(线性代数计算，图像处理，物理模拟，动态规划，统计信息等)。使用PolyBench的论文有 [8] [24]。

3.5. IPSD2015

上面提及的都是高层次综合相关的基准，ISPD 2015布线性预测相关的基准 [51]。ISPD 2015是Fence Regions和Routing Blockages的基准。时序约束和区域布局约束是实际工业设计中常见的特征。布局质量的最终衡量标准是其时序性能及其详细的可布线性，尽管这里描述的基准仍然缺乏时序约束，但它们的可布线性和区域约束相当完整。

4. 评估指标

衡量设计空间探索算法性能除了需要有基准测试外，还需要有作为评估或比较的标准。比较不同的多目标函数优化方法时的主要问题是如何衡量结果的质量：与Pareto front的接近程度，下面列出了一些用于衡量设计空间探索算法性能的常用方法：1) 距参考集的平均距离(ADRS)：ADRS表示Pareto-front与reference-front的距离。值越小，说明所获得的approximate-front和reference-front越接近。2) Cardinality：基数表示每种方法找到的主要设计的数量。基数高表明有很多可供选择的解决方案，但是需要与其他数据一起仔细解释。3) IPC (Instruction-per-Cycle)：表示每个时钟周期执行的平均指令数。

5. 结论

本文调查了设计空间探索的不同技术，以及高层次综合所使用的基准测试以及DSE评估指标。可以看出近年来人们对于DSE关注度越来越高，仔细对比各种方法的基准测试或是评估指标会发现有很大的不同，没有一个通用的基准供各种方法使用，所以无法做到客观的比较，以至于现有的技术始终无法达到对实施成本的精确预估。