A Survey on FPGA Electronic Design Automation Technology Based on Machine Learning
-
摘要: 随着后摩尔时代的来临,现场可编程门阵列(FPGA)凭借其灵活的重复可编程特性、开发成本低的特点,现已被广泛应用于物联网 (IoTs)、5G通信、航空航天以及武器装备等各个领域。作为FPGA设计开发过程中所必备的手段,FPGA电子设计自动化(EDA)技术的研究在各界得到了广泛的关注。尤其是在机器学习方法的推动下,FPGA EDA工具的运行效率和结果质量(QoR)得到了很大的提升。该文首先对FPGA EDA技术与机器学习技术的概念内涵进行了简要概述,随后综述了机器学习技术在FPGA EDA高层次综合(HLS)、逻辑综合、布局与布线等各个不同阶段应用的研究现状。最后,对基于机器学习的FPGA EDA技术的发展进行了展望。以期为本领域及相关领域的专家和学者提供参考,为后摩尔时代我国集成电路产业的发展提供技术支持。Abstract: With the advent of the post-Moore era, Field Programmable Gate Array (FPGA) is widely used in various fields such as Internet of Things (IoTs), 5G communication, aerospace, weapons and equipment because of its flexible repetitive programmable characteristics and low development cost. As a necessary means in the process of FPGA design and development, FPGA Electronic Design Automation (EDA) has received extensive attention from industry and academia. Especially driven by machine learning, the running efficiency and Quality of Result (QoR) have been significantly improved. A brief overview of the conceptual connotation of FPGA EDA and machine learning is presented at first, Then, the application of machine learning to different FPGA EDA stages such as High Level Synthesis (HLS), logic synthesis, placement and routing is summarized. Finally, the development of FPGA EDA technology based on machine learning is prospected. It is expected to provide reference for experts and scholars in this field and related fields, and provide technical support for the development of China’s integrated circuit industry in the post-Moore era.
-
1. 引言
随着硅工艺发展接近物理极限,用来刻画工艺演进速度的摩尔定律也开始被打破,半导体行业迎来了后摩尔时代[1,2]。然而集成电路芯片产业并没有因此而停滞发展,现场可编程门阵列(Field Programmable Gate Array, FPGA)由于所具有的高度灵活、可定制以及支持高并发等特性[3],被广泛应用于后摩尔时代的各个领域[4-8]。与此同时,为了能够适应更加复杂的电路系统,FPGA芯片的集成度也在不断增大,从最初只包含有几千个逻辑门的单功能芯片发展到了现今集成了数据信号处理(Digital Signal Processing, DSP)单元、块随机存取存储器(Block Random Access Memory, BRAM)以及多核微处理器的片上系统,FPGA芯片的集成度增加了数万倍。如此高的芯片集成度使得手动进行电路设计已经不现实,开发设计人员更加依赖于电子设计自动化(Electronic Design Automation, EDA)工具对FPGA数字集成电路进行设计[9,10]。但随着FPGA芯片规模的不断增大以及片上设计复杂度的不断提升,例如,AMD Xilinx发布的Virtex UltraScale+VU19P FPGA,其包含900万个逻辑单元以及近350亿个晶体管,而Intel发布的Stratix 10 GX 10M FPGA,更是包含了1020万个逻辑单元以及近430亿个晶体管,对FPGA EDA工具的可扩展性和工作效率提出了严峻的挑战[11,12],即便FPGA的可重复编程特性允许硬件设计的快速实现以及系统内调试,从而能够提高工作设计人员的工作效率,但如果EDA工具的运行时间过长或结果质量(Quality of Result, QoR)很差,这一优势就会被明显削弱。因此,FPGA EDA算法和软件工具亟需朝着更加高效、智能的方向进行演进[13]。
如今,机器学习在我们的生活中发挥着越来越重要的作用,已经在许多场景中得到了广泛的应用。机器学习方法在解决分类、检测和设计空间探索问题等方面展现了令人惊叹的性能[14]。此外,机器学习方法也显现出为许多非确定性多项式(Non-deterministic Polynomial, NP)完全问题生成高质量解决方案的巨大潜力,这些NP完全问题在FPGA EDA领域是非常常见的,而传统的解决方案常常由于缺乏知识积累,需要耗费大量的时间和资源从头解决所有问题[15]。相对应地,机器学习方法专注于提取可以在其他相关和类似情况下重用的高级特征或模型,避免重复的复杂分析。因此,应用机器学习方法是加速解决FPGA EDA问题的一个重要研究方向[13,16]。
可喜的是,国内外学者针对基于机器学习方法的FPGA EDA技术的研究已经取得了具有前瞻性的研究成果和进展。本文分析梳理了近年来应用机器学习解决FPGA EDA中一些关键问题的研究成果,对FPGA EDA和机器学习的背景知识进行了简要概述,调研了机器学习在FPGA EDA流程不同阶段应用的研究现状,即HLS、逻辑综合、布局以及布线,在此基础上对机器学习未来在FPGA EDA技术中的应用进行了展望。
2. FPGA EDA与机器学习技术概述
2.1 FPGA EDA技术概述
作为FPGA芯片设计、应用过程中不可或缺的重要组成部分,在过去的30余年中,FPGA EDA的设计流程变得越来越规范且复杂,具体包括高层次综合(High Level Synthesis, HLS)、逻辑综合、布局、布线以及码流生成[17,18],如图1所示。
HLS是指将高层次语言描述的逻辑结构自动转换成低抽象级语言描述的电路模型的过程,即HLS能够将C, C++, SystemC等具有较高的抽象度且不具备时钟或时序概念的高层次语言自动转化为Verilog, VHDL, SystemVerilog等低层次语言[19,20]。由于Verilog, VHDL, SystemVerilog能够用来描述时钟周期精确的寄存器传输级(Register Transfer Level, RTL)电路模型,是当前FPGA设计中最为普遍适用的电路建模与描述方式。HLS技术的应用可以提高设计速度、缩短设计周期,方便设计者在系统级进行设计方案的探索、在算法级对设计进行优化。
逻辑综合能够将HDL文件转换为描述指定FPGA器件上不同逻辑单元连接关系的网表文件,需要指出的是,网表中的连接关系只是逻辑连接,即逻辑综合工具只是给出了所需实现的设计的一个“草图”,这个“草图”最终需要由FPGA芯片中可用的逻辑资源来实现[21]。逻辑综合是一个非常复杂的过程,通常情形下只能通过启发式方法来得到一个次优的解决方案。
布局是指在一定的约束条件下(例如,线长、时延、功耗以及面积等),将逻辑综合过程得到的电路网表中的逻辑单元与实际FPGA芯片中的物理位置建立一对一映射的过程[22]。布局作为FPGA EDA流程中的关键环节,同时也是FPGA编译过程中最耗时的步骤之一。由于FPGA中的布线资源都是预置的且容量有限,一旦布局算法的解需要过多的布线资源,后续的布线过程将会失败或是需要很长的时间才会得到一个可行的布线解决方案,因此,一个好的布局解决方案对于FPGA EDA的工作流程至关重要。
布线能够在保证资源合法使用的前提下,通过配置FPGA芯片中的可编程开关,从而通过利用硬连线资源连通电路线网中所有的逻辑连接。与此同时,为了保证最终在FPGA芯片实现后的电路设计中的逻辑信号的正常传输,不同线网间的逻辑连接不能够共享相同的硬连线资源[23]。
执行完布线操作后,便可以生成二进制的码流文件,将其下载到芯片内部,最终完成FPGA的配置流程。
得益于学术界和工业界30余年的努力,FPGA芯片的设计流程得到了很好的发展。然而,随着FPGA芯片规模的不断增长,亟需引入更加高效的设计方法来降低设计成本、提升设计效率以及QoR。近年来,机器学习技术的飞速发展为解决上述问题提供了一个全新的视角。本文综述了机器学习技术在FPGA EDA HLS、逻辑综合、布局、布线等流程中的应用情况,并对发展趋势进行了总结,希冀为未来FPGA EDA技术的发展起到一定促进作用。
2.2 机器学习技术概述
机器学习技术是一种能够自动从数据集或是先验知识中提取有用信息的技术,通常情形下,基于机器学习技术的解决方案按照学习范式的不同可以分为监督学习、无监督学习、主动学习以及强化学习等几种类型[24,25]。监督学习与无监督学习的区别在于机器学习模型的输入数据事先是否被标记,通过监督学习或无监督学习,机器学习模型首先通过离线的方式在静态的数据集上进行训练,在模型的训练误差满足要求后,便可以用于在线部署。在利用一些传统的监督学习方法进行分类训练时,数据样本的规模越大,分类的效果便越好。但在实际的应用场景中,标记样本的获取往往是十分困难的,大多数情况下需要各领域的专家通过手工的方式进行标注,所耗费的时间成本和经济成本是无法负担的。为了降低数据标记过程所耗费的成本,进而能够使用较少的训练样本来获得性能较好的机器学习模型,主动学习的概念应运而生。主动学习是指机器学习模型能够从输入空间中查询得到最有用的未标记的样本,并交由专家进行标记,随后再利用上述已标记的样本来训练机器学习模型以提高模型的精确度,这样便能够降低海量数据标记所带来的成本浪费的问题。最后便是强化学习,强化学习事先不要求给定任何数据,强调决策体(Agent)如何通过采取行动(Action)-获取奖励(Award)的方式与环境(Environment)进行交互,以期获得最大的预期利益。上述方法均已被证明适用于FPGA EDA问题的求解过程。
机器学习模型是机器学习方法产出的结果,可以将其视为在给定输入情形下、输出一定结果的函数。机器学习模型并不是一个事先定义好的函数,而是利用历史数据归纳、推导出来的,即当输入不同的数据时,机器学习模型的输出会根据输入的不同而产生相应的变化,但机器学习模型本身并不会发生改变。传统的被应用于解决FPGA EDA问题的机器学习模型包括线性回归、随机森林(Random Forest, RF)以及人工神经网络(Artificial Neural Network, ANN)等。近年来,随着一些大型公共benchmark的公开、算法的突破以及硬件平台计算能力的提升,研究人员开始不断尝试将深度学习模型应用于FPGA EDA问题的求解当中,例如,卷积神经网络(Convolutional Neural Network, CNN)、递归神经网络(Recursive Neural Network, RNN)、生成对抗网络(Generative Adversarial Network, GAN)、深度强化学习(Deep Reinforcement Learning, DRL)以及图神经网络(Graph Neural Network, GNN)等,并取得了令人欣喜的研究成果[26,27]。
3. 研究进展
3.1 高层次综合技术
为了提高设计效率并向更广泛的用户群体推广FPGA,高层次综合工具应运而生。高层次综合工具接受高级语言(例如C, C++以及SystemC)作为输入,能够将其自动转换为Verilog或VHDL等形式的硬件描述语言。但随着片上设计复杂度的不断提升,如何在保证HLS工具输出结果质量的同时减少HLS所需花费的时间、提升设计空间的探索效率是现阶段迫切需解决的关键问题。机器学习技术的引入为解决上述问题提供了一种新的思路。机器学习技术在HLS中的应用主要包括性能评估以及设计空间的探索等两方面,接下来本文对两方面内容分别进行阐述。
3.1.1 高层次综合的性能评估
为了能够更好地评估利用HLS工具生成的寄存器传输级模型的性能,HLS工具会提供一组性能评估报告,用来定量的评估寄存器传输模型的时序以及资源使用情况等信息。上述信息可以用于指导后续流程的迭代优化,以获得所期望的结果质量。但评估报告中的许多参数往往是不正确的,特别是最终的资源占用以及时序信息往往取决于HLS的后续流程,例如逻辑综合、布局和布线等,因此即便是使用当前最先进的HLS工具也难以提供准确的性能评估报告。以AMD Xilinx商用Vivado HLS工具为例,它对查找表(Look-Up Table, LUT)使用数量评估的相对误差为125%,触发器评估的相对误差为98%[28]。这种对结果质量的不准确评估会阻止设计人员甚至工具本身应用合适的优化策略。为了获取更加准确的结果质量评估,设计人员需要在每一个设计点都花费大量的时间来迭代后续的操作流程(逻辑综合、布局和布线),但由于上述操作会抵消HLS所带来的设计效率上的优势,显然是不符合实际的。而机器学习技术可以通过学习真实的设计基准来提升HLS性能评估的准确性,因此,越来越多的研究学者开始关注于将机器学习应用到HLS的性能评估与预测中,主要可以划分为资源占用与时序信息评估以及跨平台的性能预测两大类。
(1) 资源占用与时序性能评估。资源占用与时序性能评估的整体工作流程如图2所示,该流程在文献[28]中被首先提出,流程的主要工作在于训练一个机器学习的模型,该模型会将HLS的评估报告作为输入,在无需执行后续逻辑综合、布局和布线等流程的条件下,输出一个关于资源占用与时序性能更加精准的评估结果。上述工作流程主要包括数据处理与模型训练两个步骤[28]。在数据处理阶段,首先需要针对不同的FPGA设备,在不同的时钟周期运行完整的C-to-Bitstream流程,以获取完整的数据集合。在此基础上,作者通过特征选择技术来系统地消除一些不重要的特征,以克服共线性的影响并降低数据维数。随后便可以将所选的特征应用到模型训练阶段。在模型训练阶段,通常使用相对绝对误差(Relative Absolute Error, RAE)与相对均方根误差(Relative Root Mean Squared Error, RRMSE)来评价性能评估的误差值。RAE可以表示为
RAE=|ˆy−y||y−ˆy| (1) 其中,
ˆy 表示模型预测值的向量集合,y表示数据集中真实值的向量集合,ˆy 表示向量y的所有元素的均值。RRMSE可以表示为RRMSE=√1N∑i∈N(ˆyi−yiyi)2×100% (2) 其中,N表示采样点的个数,
ˆyi 与yi 分别表示预测值与实际值的采样值。Makrani等人[29]同样基于如图2所示工作流程,将时序性能评估问题建模为回归问题,并利用深度学习训练平台[30]获得了由HLS工具生成的RTL代码的最大时钟频率等结果。随后,为了进一步提升评估的准确率,Makrani等人提出了一种结合了线性回归、支持向量机(Support Vector Machines, SVM)以及随机森林的训练模型,最终性能评估的准确率高达95%以上。此外,也有研究学者利用机器学习技术来减少HLS工具对操作延迟预测的误差,现有的HLS工具大多采用基于单个操作的预先表征的延迟的简单相加来执行延迟评估,但得到的结果可能并不准确。为此,Ustun等人[31]建立了一个定制的图神经网络(Graph Neural Network, GNN)模型以从数据流图中捕获各操作间的关联,并完成了模型的训练,最终的试验结果表明,该方法能够将Vivado HLS操作延迟预测的RRMSE降低72%。
(2) 跨平台性能预测。软硬件协同设计的出现使得开发人员能够利用一些新的混合平台,例如Zynq。然而,将应用程序分为两部分,一部分在CPU上运行,另一部分转换为在FPGA上实现的硬件加速器。但由于在不同的平台上实现的应用程序的性能存在显著的差异,使得开发设计人员在处理平台的选择上往往难以抉择,即哪部分要用可编程逻辑FPGA实现,哪部分要用微处理器实现。开发设计人员往往需要在不同的平台上完全实现设计方案,以此来评估最终的性能。当可用处理平台的数量较多时,上述过程是非常繁琐的。为了应对上述挑战,Makrani等人[32]设计了一种跨平台的性能评估系统XPPE,其具体工作流程如图3所示。
XPPE使用神经网络(Neural Network, NN)模型来预测ARM处理器上目标FPGA的应用程序的加速比。XPPE的输入包括目标FPGA上的可用资源、Vivado HLS工具生成的资源利用率报告以及提取到的应用程序的一系列特征。输出是ARM A9处理器上应用程序在目标FPGA上的加速比的估计结果。在此基础上,作者提出使用RRMSE来评估预测结果的准确性。最终的实验结果表明,所设计的体系架构的相对均方误差为5.1%。O’Neal等人[33]提出了一种与XPPE相类似的基于机器学习的跨平台的性能评估器HLSPredict。但与XPPE的不同之处在于HLSPredict仅将工作负载即应用程序作为输入,而不是HLS的报告、应用程序特性以及目标FPGA设备规格的组合。其次,HLSPredict所预测的目标平台必须与训练阶段的硬件平台保持一致。实验结果表明,对于一个应用程序,HLSPredict实现了9.08%的相对绝对百分比误差和43.78倍的运行时加速。
3.1.2 高层次综合的设计空间探索
本文3.1.1节综述了如何使用机器学习模型来预测HLS最终的QoR,机器学习方法在HLS中的另一个应用便是辅助进行设计空间的探索。在HLS中,可调整的综合选项跨越了非常大设计空间,在大多数情形下,设计空间探索的任务是找到帕累托前沿曲线,在该曲线上,每个点都不完全被其他点所支配。
经典的应用于HLS设计空间探索的算法包括模拟退火(Simulated Annealing, SA)以及遗传算法(Genetic Algorithm, GA)等,但上述方法的缺陷在于无法从已探索的设计数据库中学习到相关的经验信息。为此,许多研究学者探索了如何使用机器学习的预测模型来指导设计空间的探索过程。这些模型会根据已探索设计点的综合结果进行训练,并用于预测新设计的质量。例如,Liu等人[34]提出了一种专用的探索器来搜索针对于FPGA的帕累托最优的HLS设计。探索器会迭代地选择潜在的帕累托最优设计进行综合和验证,最优设计的选择是基于一组特征变量进行的,并且这些特征变量会在设计空间探索的过程中不断进行调整。最终实验结论表明,上述方法的搜索速度是穷举法的6.5倍、受限搜索方法的3倍,且最终的QoR也得到了明显的提升。文献[35]提出了一种基于转导实验设计(Transductive Experimental Design, TED)的方法,TED侧重于寻找能够准确描述设计空间的样本,其基本思想在于从设计空间中选择具有代表性的且难以推测的样本,而不是使用随机样本。TED的目标是使用最少的训练样本来最大化预测模型的准确性。为了达到上述目标,TED将寻找最佳策略的问题表述如下:假设旋钮设置(Knob Settings, KS)的总数为n,即
|κ|=n ,随后从中选取一个训练集˜κ ,即˜κ⊂κ ,使得|˜κ|=m 。因此,预测误差的最小化问题H(k)−˜H(k),∀k∈κ 便可以等效为如式(3)的问题进行求解max (3) 其中,H代表高层次综合工具,
\tilde H 表示高层次综合工具的学习模型,{\text{T}}\left[ \cdot \right] 表示矩阵迹的算子操作符,\mu 表示一个大于零的常量,I表示单位矩阵。与上述工作不同,为了进一步完善HLS中设计空间的探索过程,Meng等人[36]设计了一种自适应阈值的非帕累托消元法(Adaptive Threshold Non-Pareto Elimination, ATNE)来关注学习器的不准确度,而不是像上述工作那样主要关注模型如何对设计空间进行准确的描述。ATNE使用基于RF的方法来辅助HLS的设计空间的探索过程,在该文献中,Meng等人设计了一个帕累托识别阈值,并将其应用于RF回归器的误差估计,以此来逐步消除非帕累托最优设计。ATNE的重点不是提升学习器的准确度,而是评估并最小化因学习器不准确而导致失去“好”设计的风险,最终的实验结果也表明,ATNE能够获得比TED更好的性能。最后,本文对上述工作进行了总结,具体如表1所示。
3.2 逻辑综合技术
逻辑综合是一个具有复杂约束条件的优化问题,需要精确的求解才能够保证后续设计流程的准确性。使用机器学习算法来直接生成逻辑综合的解决方案是非常困难的,现阶段机器学习算法的主要应用是用来调度一些已有的优化策略。例如,Neto等人[37]提出了一种人工智能驱动的逻辑综合架构:LSOracle, LSOracle中集成了与非图(And-Inverter Graph, AIG)和表决器非图(Major-Inverter Graph, MIG)两种优化器,首先使用k划分的方法将电路的有向无环图(Directed Acyclic Graph, DAG)划分为k个部分,在此基础上,依靠深度神经网络(Deep Neural Network, DNN)来动态决定将哪个优化器应用于电路的不同部分。最终实验结果表明,与单独使用AIG优化器和DAG优化器相比较,LSOracle在面积-时延方面的性能平均提升了6.87%和2.70%。
当前的综合工具(例如,加州大学伯克利分校开发的ABC工具)中包含有许多逻辑转换的流程[38],为了选择一个合适的流程,Yu等人[39]提出了一种完全自动化的逻辑综合架构,该架构以待综合的HDL代码作为输入,输出为两组不同的逻辑综合流程:即“天使流程”(Angel-flows)和“魔鬼流程”(Devil-flows),它们分别对应了设计目标的最佳和最差的结果质量(QoR)。该问题被建模为一个多分类问题并使用基于卷积神经网络(Convolutional Neural Network, CNN)的分类器进行求解。其主要思想是用一小组经过标记的随机的逻辑综合的流程来训练一个CNN的分类器,此处所提到的不同的逻辑综合流程的标签是通过一个或多个不同QoR的指标进行标记的,例如时延、面积以及功率等。经过训练后的分类器便可以用来预测未被标记的逻辑综合的流程。最后,通过对预测置信度(即属于某个类别的概率)进行排序来生成“天使流”与“魔鬼流”。整个架构的具体流程如图4所示。Wu等人[40]提出了一种基于混合图神经网络的优化方法,针对逻辑综合的流程进行优化,以提升结果质量的评估以及优化方法的泛化能力。其关键思想在于同时利用来自硬件设计和逻辑综合流程的时空信息来预测不同设计上各种不同综合流程的性能指标,最终的实验结果也表明利用混合图神经网络的优化方法在误差精度是现有方法的7~15倍。
除了上述工作外,也有研究学者提出使用强化学习(Reinforcement Learning, RL)方法来优化逻辑综合的流程,即具有相同I/O行为的两个DAG之间的转换被建模为一个动作,随后通过设计不同的学习方式来完成动作的选择过程[41]。例如,在文献[42]中图卷积网络(Graph Convolutional Network, GCN)被用作策略函数来获取每个动作的概率。文献[43]则采用无监督的优势演员-评论家(Advantage Actor Critic, A2C)机制来搜索最佳的解决方案。宁波大学储著飞老师团队提出了一种基于强化学习的近端策略优化方法来训练调整优化序列[44],具体地,使用具有边缘特征聚合能力的图同构网络来学习电路表示,并将电路表示作为强化学习的智能体的状态,在此基础上,为了使智能体能够从历史的经验中学习到相关的知识,长短期记忆网络(Long Short-Term Memory, LSTM)被进一步嵌入到强化学习的模型中,与文献[43]相比较,面积指标优化了21.21%。
基于机器学习的逻辑综合技术虽然得到了大范围的研究,但上述方法要么需要大量标记数据进行训练,要么由于计算开销,在实际EDA工程的应用中受到了极大的限制。为了克服上述问题,Yu等人[45]提出了一种全新的适用于布尔逻辑优化的端到端的、高性能的、针对特定领域的Bandit计算架构,该架构能够同时对AIG、布尔可满足性的连接范式、标准单元技术映射后的静态时序分析以及6输入查找表(Look Up Table, LUT)架构的FPGA技术映射问题进行优化,最终的实验结果也表明,该方法的运算速度要优于文献[39]与文献[43]中所提出的方法。Grosnit等人[46]则是提出了一种基于贝叶斯理论的方法来解决样本复杂度过高的问题,实现了高效且可扩展的基于机器学习的逻辑综合的解决方案。
3.3 布局技术
布局作为FPGA EDA工作流程中的核心步骤之一,是典型的超大规模非确定性多项式(Non-deterministic Polynomial, NP)困难组合优化问题,对时延、线网可布通性、功耗等功能指标影响巨大。由于过去30余年FPGA架构的不断演进,现代FPGA拥有数以千计的DSP, RAM以及数百万个查找表(Look-Up Table, LUT)和触发器(Flip-Flop, FF)实例,这些异构资源通常完全分散在FPGA架构的离散位置,这种复杂性和异构性对现代FPGA布局器的运行效率和结果质量提出了严峻的挑战,将机器学习与传统布局方法相结合是解决上述问题的有效途径。
传统的布局方法大体上可以分为3类,基于启发式的布局方法、基于划分的布局方法以及基于解析式的布局方法。基于启发式的布局方法一般基于模拟退火技术[47,48],其本质上是一种基于概率的方法,能够在一个很大的空间内寻找全局最优解,在时间允许的情形下,能够得到全局最优解,并能够避免陷入局部最优解的陷阱,但其缺陷也同样明显,即算法的复杂度高且收敛效率低,对大规模电路的可扩展性极差。为了提高模拟退火算法的求解效率,有研究学者在模拟退火算法中引入了强化学习策略,以加快算法的收敛速度。2019年,Murray等人[49]使用单状态强化学习策略提出了一种自适应的FPGA布局方法,如图5所示,在每一次迭代的过程中,布局器agent能够自动地选取不同类型的逻辑单元执行逻辑单元的交换操作,节省了布局所需要的时间,与VPR工具相比较,能够获得2倍以上的加速比。在此项工作的基础上,2021年,Elgamma等人[50,51]做了进一步探索,使用多状态强化学习策略来优化模拟退火算法中直接过程的选取过程,使得基于模拟退火的FPGA布局器的性能得到了进一步的优化提升,运行效率以及结果质量都要优于已发布的VTR 8布局器,能够在更短的运行时间内得到更好的QoR布局解决方案。
基于划分的布局方法能够通过递归的方法对布局实例进行划分,直至所有布局实例均小于事先设定的阈值。但由于布局过程是递归求解,不恰当的划分会对后续的过程产生不可逆的伤害,导致回溯的最终解的质量产生较为严重的损失。因此,现阶段没有将机器学习技术应用于基于划分的布局方法的研究。
基于解析式的布局方法可将布局问题描述为更加复杂的优化问题,并基于丰富的梯度下降方法进行求解。根据目标函数的不同,可以将解析式方法分为二次方布局技术[42-55]以及非线性布局技术[56,57]。二次方布局技术的求解效率较高,但通常情形下,二次函数无法较为严格地逼近实际问题,且鲁棒性较差。非线性布局技术的目标函数基于高阶非线性方程组成,相比于二次函数更具有表现力,通过非线性布局技术得到的布局解的质量也要由于二次方布局技术。因此,现阶段较为优秀的FPGA布局器均采用了非线性布局技术,例如Meng等人[58]将基于静电场的布局方法ePlace[59]迁移至FPGA设计了一种全新的布局器elfplace,并实现了GPU加速,与UTPlaceF[60], RippleFPGA[61]以及Gplace3.0[62]等二次方或非线性布局器相比较,能够在运行时间大致相当的情况下,将线长指标分别减少13.5%、10.2%以及8.8%。随后,Rajarathnam等人[63]在此项工作的基础上,提出了一种基于开源深度学习工具的加速布局架构DreamPlaceFPGA,能够适应于大规模异构FPGA的布局工作,相比于elfPlace布局器[59],DreamPlaceFPGA能够在获得相同QoR的前提下,得到5.4倍的加速比。
机器学习在布局技术中的另一类应用便是在布局阶段进行布线拥塞的预测。布局的结果将直接决定物理实现后的线长、面积以及功耗等QoR指标,对于在FPGA芯片上实现的设计的性能具有很大的影响,不合理的布局将会使布线资源紧张,进而产生布线拥塞,导致布线迂回和较低的逻辑单元的利用效率,甚至在极端情况下的某些问题经过布线后仍无法修正,这样就会迫使设计人员重新调整布局,重复进行布局和布线的迭代,耗费大量的时间和资源。因此,在布局阶段进行布线拥塞的预测是极其重要的。正是认识到了上述问题,FPGA布线拥塞预测的研究成为近年来的研究热点,并且基于机器学习的布线拥塞预测方法也开始纷纷涌现。Pui等人[64]基于布局和全局布线的结果,通过提取的特征来实现布线拥塞的预测,该项工作提取了3类特征参数,并基于线性回归以及SVM模型对收集到的数据样本进行了训练。此项工作的缺点在于仍然需要执行全局布线操作才能够完成布线拥塞信息的预测,并且该方法的结果一致性仍需进一步考量。为了进一步提升预测的准确程度,Maarouf等人[65]在上述工作的基础上,提出了一种高效的机器学习模型来完成布线拥塞信息的精准预测,最终的实验结果表明,与文献[64]相比较布线拥塞信息预测的准确程度提升了25%。Yu等人[66]设计了一种基于条件生成对抗网络(Conditional Generative Adversarial Nets, CGAN)的布线拥塞预测方法,将布线拥塞预测问题建模为图像转换问题,仅利用布局阶段所提取的特征信息便能够进行布线拥塞信息的预测。但该方法却无法应用于大规模设计,其原因在于:首先,该方法对图像的处理能力被限制为256×256,无法对大规模的FPGA设计进行求解;其次,该方法在布局阶段所提取出的特征也无法应用于大规模的FPGA设计,尤其是该方法使用两个引脚间的飞线作为连接的特征信息,这只适合于小规模的电路,无法描述大规模的FPGA设计。为了克服上述问题,Alawieh等人[67]将布线拥塞预测问题转换为高清图像识别问题,能够面向大规模的FPGA设计进行求解。
除学术界外,工业界也在积极探索将机器学习应用到FPGA布局工作的流程当中,例如,AMD Xilinx在2021年最新发布的Vivado ML版本中便加入了基于机器学习的布线拥塞预测机制,据公开资料显示,其布线拥塞预测的准确率能够达到90%以上[68]。北京微电子技术研究所自研的国产FPGA EDA工具BFDS(BMTI FPGA Design Suit, BFDS)的布局流程中集成了强化学习模型,能够对布局的结果进行优化,现阶段能够支持7000万门级国产FPGA的应用开发。上述工作也是为数不多的将机器学习模型应用于FPGA布局实际工程应用中的尝试。表2是本文对上述工作的总结。
表 2 机器学习在FPGA EDA布局技术中的应用3.4 布线技术
作为FPGA EDA设计流程中的重要一环,布线直接决定了所设计的电路最终在FPGA芯片上实现后的性能。在布线时,EDA工具会首先将FPGA芯片内的硬件资源建模为一个有向的布线资源图(Routing Resource Graph, RRG)。RRG是布线方法与FPGA硬件间的纽带,通过RRG能够将FPGA布线问题转化为图论中的最短路径的求解问题,布线方法在RRG上直接对线网执行布线操作即可[69]。McMurchie等人[70]首次将拥塞协商的思想引入到FPGA的方案中,该方案允许FPGA中的布线资源在重复使用的情形下,对线网执行迭代布线操作,在每次迭代的过程中,会逐步增加对重复使用的布线资源的惩罚力度,直至将所有的拥塞全部消除。基于拥塞协商的FPGA布线方案的提出具有跨时代的意义,目前几乎所有的商业界或是学术界所使用的布线器,其基本思想都是基于拥塞协商的布线方案的改进。但随着FPGA电路规模的不断增大,布线所需花费的时间也越来越长,亟需探索新的解决方案以提升FPGA布线方法的运行效率和QoR。
机器学习技术的出现为人们指明了方向,例如,Farooq等人[71]提出了一种基于强化学习的FPGA布线解决方案,将FPGA的布线迭代流程转化为强化学习的训练过程,此项工作也是强化学习技术首次在FPGA布线任务中的尝试,最终的实验结果表明,在达到同等QoR指标的情形下,能够节约30%的系统运行时间。
4. 展望
基于机器学习的FPGA EDA技术虽然有了一定的发展,但仍存在一定的局限性,相关研究尚处于起步阶段。接下来将从这些局限性的角度出发,对基于机器学习的FPGA EDA技术进行展望。
(1)基于机器学习的FPGA EDA技术的基础是大型的数据集,但随着在FPGA EDA技术中所应用的机器学习模型的复杂度的不断攀升,现有的数据集已无法满足基于机器学习的FPGA EDA技术的发展需求。因此,构建数据量丰富、全面且通用的面向FPGA EDA技术的数据集对基于机器学习的FPGA EDA技术的发展至关重要。与此同时,弱监督与无监督方法可以在仅需要少量的标注数据和不需要标注数据的情况下完成机器学习模型的训练过程,可以显著地减少标注数据的时间成本,现阶段已在许多领域得到了广泛的应用[72]。随着基于机器学习的FPGA EDA技术研究的不断深入,数据的需求量在不断增大,数据的标注成为难题,弱监督或无监督的技术不仅能够解决基于机器学习的FPGA EDA的数据标注的难题,而且有望提升应用于FPGA EDA技术中的机器学习模型的精度与训练速度,是未来的研究方向之一。
(2)现有的机器学习在FPGA EDA领域的应用研究大多仍然是在效仿ASIC,例如,针对逻辑综合技术,最近的研究主要是通过预测传统尚需要进一步模拟的相关信息来提高下利率和准确性,具体而言,在机器学习模型的训练过程中,主要是通过调用abc工具,将布尔电路映射到工艺库,随后适用工艺库返回的信息(Area, Delay等)来设计相关的奖惩函数,最终得到一个相对最优的综合流程。但上述过程并没有考虑到FPGA自身的应用特性,对于综合过程而言,ASIC同FPGA最大的区别在于前者映射到了标准单元库,而后者却是查找表等FPGA上可用的逻辑资源,但已有的开源逻辑综合工具,例如前文所提到的学术界广泛适用的abc,现阶段只能简单地反馈出在综合的流程中所适用的查找表的数量以及相关层级关系等简单信息,缺少对FPGA异构逻辑单元库的支持,这就使得在机器学习模型的训练阶段得不到有用反馈的信息,这也正是阻碍机器学习模型在FPGA逻辑综合领域发展的一个至关重要的因素。因此,如何在现有研究的基础上使得逻辑综合工具能够支持详细的FPGA异构逻辑单元库,以便在逻辑综合的流程过后反馈出更加详尽的信息以供机器学习模型进行训练是未来机器学习技术在FPGA EDA领域研究的一个重要的研究方向。类似地,针对FPGA布局、布线技术,FPGA中包含有数量众多的异构逻辑单元,并且异构逻辑单元的摆放位置相对于ASIC而言要更加的整齐,但这却使得实际的布局、布线问题的约束条件变得更加的复杂多变,机器学习模型在训练的过程中越来越难以收敛到一个最优的解。因此,如何在考虑多种约束的条件下,实现基于机器学习技术的FPGA布局、布线问题的快速求解是未来需要重点关注的一个发展方向。
(3)目前,已有一些新兴的机器学习模型或方法(点云或图神经网络)被应用于专用集成电路(Application Specific Integrated Circuit, ASIC)EDA工具的设计与优化流程中,相关EDA工具的性能得到了大幅度的提升,但现阶段尚无将上述方法应用于FPGA EDA技术中的研究[13]。因此,将一些在ASIC EDA领域已被证明能够提升EDA工具性能的新兴的机器学习技术应用于FPGA EDA领域将是未来基于机器学习的FPGA EDA技术的研究方向之一。
5. 结束语
FPGA凭借其灵活的动态可重构功能,在工业界和学术界得到了越来越多的关注,现已成为后摩尔时代各应用领域的首选研究对象,FPGA EDA技术在FPGA的应用开发过程中扮演着不可或缺的角色。机器学习技术被证明能够显著提升EDA工具的性能,并且在ASIC电子设计自动化领域得到了广泛的应用。但机器学习技术在FPGA EDA领域的研究尚处于发展的初期,相关研究成果的数量也要明显少于ASIC。为了机器学习技术能够在FPGA EDA领域得到更好的应用,本文围绕基于机器学习的FPGA EDA技术,从机器学习在FPGA EDA流程中各不同阶段的应用情况对相关的研究进展进行了分析与总结。在此基础上,针对现有研究所存在的一些局限性,对未来发展趋势进行了展望,以期对未来基于机器学习的FPGA EDA技术的发展具有一定的启发意义。跟踪并研究基于机器学习的FPGA EDA技术是后摩尔时代我国芯片行业实现自主可控的重大机遇。
-
表 1 机器学习在FPGA EDA高层次综合技术中的应用
表 2 机器学习在FPGA EDA布局技术中的应用
-
[1] MEINDL J D. Beyond Moore's Law: The interconnect era[J]. Computing in Science & Engineering, 2003, 5(1): 20–24. doi: 10.1109/MCISE.2003.1166548 [2] YOSHIMURA C, HAYASHI M, OKUYAMA T, et al. FPGA-based annealing processor for ising model[C]. 2016 Fourth International Symposium on Computing and Networking (CANDAR), Hiroshima, Japan, 2017: 436–442. [3] MONMASSON E and CIRSTEA M N. FPGA design methodology for industrial control systems—a review[J]. IEEE Transactions on Industrial Electronics, 2007, 54(4): 1824–1842. doi: 10.1109/TIE.2007.898281 [4] FUJII N and KOIKE N. IoT remote group experiments in the cyber laboratory: A FPGA-based remote laboratory in the hybrid cloud[C]. 2017 International Conference on Cyberworlds (CW), Chester, UK, 2017: 162–165. [5] HUANG Hai, XIA Jingjing, and BOUMAIZA S. Parallel-processing-based digital predistortion architecture and FPGA implementation for wide-band 5G transmitters[C]. 2019 IEEE MTT-S International Microwave Conference on Hardware and Systems for 5G and Beyond (IMC-5G), Atlanta, USA, 2019: 1–3. [6] MEIER J and RAMESH T. Intelligent sensor fabric computing on a chip - a technology path for intelligent network computing[C]. 2007 IEEE Aerospace Conference, Big Sky, USA, 2007: 1–7. [7] CHEN Yingrui, WANG Teng, WANG Xin’an, et al. Implementation of an embedded dual-core processor for portable medical electronics applications[C]. The 10th International Conference on ASIC, Shenzhen, China, 2013: 1–4. [8] DONG Yang, YANG Aibing, and LI Zhuolun. Design of weapons training simulator of the audio transmission system based on FPGA platform[C]. 2011 International Conference of Information Technology, Computer Engineering and Management Sciences, Nanjing, China, 2011: 7–10. [9] HAMOLIA V and MELNYK V. A survey of machine learning methods and applications in electronic design automation[C]. The 11th International Conference on Advanced Computer Information Technologies (ACIT), Deggendorf, Germany, 2021: 757–760. [10] 涂开辉, 黄志洪, 侯峥嵘, 等. 基于配置模式匹配和层次化映射结构的高效FPGA码流生成系统研究[J]. 电子与信息学报, 2019, 41(11): 2585–2591. doi: 10.11999/JEIT190143TU Kaihui, HUANG Zhihong, HOU Zhengrong, et al. Research on efficient FPGA bitstream generation system based on mode matching and hierarchical mapping[J]. Journal of Electronics &Information Technology, 2019, 41(11): 2585–2591. doi: 10.11999/JEIT190143 [11] XILINX. VIRTEX UltraScale+ VU19P FPGA product brief[EB/OL]. https://www.xilinx.com/content/dam/xilinx/publications/product-briefs/virtex-ultrascale-plus-vu19p-product-brief.pdf, 2020. [12] INTEL. Intel® Stratix® 10 GX 10M FPGA product specifications[EB/OL]. https://www.intel.com/content/www/us/en/products/sku/210290/intel-stratix-10-gx-10m-fpga/specifications.html, 2020. [13] HUANG Guyue, HU Jingbo, HE Yifan, et al. Machine learning for electronic design automation: A survey[J]. ACM Transactions on Design Automation of Electronic Systems, 2021, 26(5): 40. doi: 10.1145/3451179 [14] LU Mei and LI Fanzhang. Survey on lie group machine learning[J]. Big Data Mining and Analytics, 2020, 3(4): 235–258. doi: 10.26599/BDMA.2020.9020011 [15] BABIC D and HU A J. Integration of supercubing and learning in a SAT solver[C]. The ASP-DAC 2005. Asia and South Pacific Design Automation Conference, Shanghai, China, 2005: 438–444. [16] ELFADEL I M, BONING D S, and LI Xin. Machine Learning in VLSI Computer-Aided Design[M]. Cham: Springer, 2019. [17] DHAR S, SINGHAL L, IYER M, et al. FPGA accelerated FPGA placement[C]. The 29th International Conference on Field Programmable Logic and Applications (FPL), Barcelona, Spain, 2019: 404–410. [18] DU Boyang, STERPONE L, and CODINACHS D M. A new EDA flow for the mitigation of SEUs in dynamic reconfigurable FPGAs[C]. The 21th IEEE European Test Symposium (ETS), Amsterdam, Netherlands, 2016: 1–2. [19] CONG J, LIU Bin, NEUENDORFFER S, et al. High-level synthesis for FPGAs: From prototyping to deployment[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011, 30(4): 473–491. doi: 10.1109/TCAD.2011.2110592 [20] NANE R, SIMA V M, PILATO C, et al. A survey and evaluation of FPGA high-level synthesis tools[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2016, 35(10): 1591–1604. doi: 10.1109/TCAD.2015.2513673 [21] SARKER A L and LEE M H. Synthesis of VHDL code for FPGA design flow using Xilinx PlanAhead tool[C]. The International Conference on Education and e-Learning Innovations, Sousse, Tunisia, 2012: 1–5. [22] AL-HYARI A, ABUOWAIMER Z, MAAROUF D, et al. An effective FPGA placement flow selection framework using machine learning[C]. The 30th International Conference on Microelectronics (ICM), Sousse, Tunisia, 2018: 164–167. [23] LUO Ruiqi, CHEN Xiaolei, and HA Yajun. Optimization of FPGA routing networks with time-multiplexed interconnects[C]. The 11th Latin American Symposium on Circuits & Systems (LASCAS), San Jose, Costa Rica, 2020: 1–4. [24] 姜园, 张朝阳, 仇佩亮, 等. 用于数据挖掘的聚类算法[J]. 电子与信息学报, 2005, 27(4): 655–662.JIANG Yuan, ZHANG Zhaoyang, QIU Peiliang, et al. Clustering algorithms used in data mining[J]. Journal of Electronics &Information Technology, 2005, 27(4): 655–662. [25] SUN Lili and WANG Xizhao. A survey on active learning strategy[C]. 2010 International Conference on Machine Learning and Cybernetics, Qingdao, China, 2010: 161–166. [26] CHEN Jingsong, KUANG Jian, ZHAO Guowei, et al. PROS: A plug-in for routability optimization applied in the state-of-the-art commercial EDA tool using deep learning[C]. 2020 IEEE/ACM International Conference on Computer Aided Design (ICCAD), San Diego, USA, 2020: 1–8. [27] LEE C K. Deep learning creativity in EDA[C]. 2020 International Symposium on VLSI Design, Automation and Test (VLSI-DAT), Hsinchu, China, 2020. [28] DAI S, ZHOU Yuan, ZHANG Hang, et al. Fast and accurate estimation of quality of results in high-level synthesis with machine learning[C]. The 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM), Boulder, USA, 2018: 129–132. [29] MAKRANI H M, FARAHMAND F, SAYADI H, et al. Pyramid: Machine learning framework to estimate the optimal timing and resource usage of a high-Level synthesis design[C]. The 29th International Conference on Field Programmable Logic and Applications (FPL), Barcelona, Spain, 2019: 397–403. [30] FARAHMAND F, FEROZPURI A, DIEHL W, et al. Minerva: Automated hardware optimization tool[C]. 2017 International Conference on ReConFigurable Computing and FPGAs (ReConFig), Cancun, Mexico, 2017: 1–8. [31] USTUN E, DENG Chenhui, PAL D, et al. Accurate operation delay prediction for FPGA HLS using graph neural networks[C]. The 39th International Conference on Computer-Aided Design, San Diego, USA, 2020: 87. [32] MAKRANI H M, SAYADI H, MOHSENIN T, et al. XPPE: Cross-platform performance estimation of hardware accelerators using machine learning[C]. The 24th Asia and South Pacific Design Automation Conference, Tokyo, Japan, 2019: 727–732. [33] O’NEAL K, LIU M, TANG H, et al. HLSPredict: Cross platform performance prediction for FPGA high-level synthesis[C]. 2018 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Diego, USA, 2018: 1–8. [34] LIU Dong and SCHAFER B C. Efficient and reliable High-Level Synthesis design space explorer for FPGAs[C]. The 26th International Conference on Field Programmable Logic and Applications (FPL), Lausanne, Switzerland, 2016: 1–8. [35] LIU H Y and CARLONI L P. On learning-based methods for design-space exploration with high-level synthesis[C]. The 50th Annual Design Automation Conference, Austin, USA, 2013: 50. [36] MENG Pingfan, ALTHOFF A, GAUTIER Q, et al. Adaptive threshold non-pareto elimination: Re-thinking machine learning for system level design space exploration on FPGAs[C]. 2016 Design, Automation & Test in Europe Conference & Exhibition (DATE), Dresden, Germany, 2016: 918–923. [37] NETO W L, AUSTIN M, TEMPLE S, et al. LSOracle: A logic synthesis framework driven by artificial intelligence: Invited paper[C]. 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Westminster, USA, 2019: 1–6. [38] BRAYTON R and MISHCHENKO A. ABC: An academic industrial-strength verification tool[C]. The 22nd International Conference on Computer Aided Verification, Edinburgh, UK, 2010: 24–40. [39] YU Cunxi, XIAO Houping, and DE MICHELI G. Developing synthesis flows without human knowledge[C]. The 55th ACM/ESDA/IEEE Design Automation Conference (DAC), San Francisco, USA, 2018: 1–6. [40] WU N, LEE J, XIE Yuan, et al. Hybrid graph models for logic optimization via spatio-temporal information[J]. arXiv: 2201.08455, 2022. [41] PERUVEMBA Y V, RAI S, AHUJA K, et al. RL-guided runtime-constrained heuristic exploration for logic synthesis[C]. 2021 IEEE/ACM International Conference on Computer Aided Design (ICCAD), Munich, Germany, 2021: 1–9. [42] HAASWIJK W, COLLINS E, SEGUIN B, et al. Deep learning for logic optimization algorithms[C]. 2018 IEEE International Symposium on Circuits and Systems (ISCAS), Florence, Italy, 2018: 1–4. [43] HOSNY A, HASHEMI S, SHALAN M, et al. DRiLLS: Deep reinforcement learning for logic synthesis[C]. The 25th Asia and South Pacific Design Automation Conference (ASP-DAC), Beijing, China, 2020: 581–586. [44] YANG Chenghao, XIA Yinshui, CHU Zhufei, et al. Logic synthesis optimization sequence tuning using RL-based LSTM and graph isomorphism network[J]. IEEE Transactions on Circuits and Systems II:Express Briefs, 2022, 69(8): 3600–3604. doi: 10.1109/TCSII.2022.3168344 [45] YU Cunxi. FlowTune: Practical multi-armed bandits in Boolean optimization[C]. The 39th International Conference on Computer-Aided Design, San Diego, USA, 2020: 130. [46] GROSNIT A, MALHERBE C, TUTUNOV R, et al. BOiLS: Bayesian optimisation for logic synthesis[C]. 2022 Design, Automation & Test in Europe Conference & Exhibition (DATE), Antwerp, Belgium, 2022: 1193–1196. [47] BETZ V and ROSE J. VPR: A new packing, placement and routing tool for FPGA research[C]. The 7th International Workshop on Field Programmable Logic and Applications, London, UK, 1997: 213–222. [48] CHEN Gang and CONG J. Simultaneous placement with clustering and duplication[J]. ACM Transactions on Design Automation of Electronic Systems, 2006, 11(3): 740–772. doi: 10.1145/1142980.1142989 [49] MURRAY K E and BETZ V. Adaptive FPGA placement optimization via reinforcement learning[C]. 2019 ACM/IEEE 1st Workshop on Machine Learning for CAD (MLCAD), Canmore, Canada, 2019: 1–6. [50] ELGAMMA M A, MURRAY K E, and BETZ V. Learn to place: FPGA placement using reinforcement learning and directed moves[C]. 2020 International Conference on Field-Programmable Technology (ICFPT), Maui, USA, 2020: 85–93. [51] ELGAMMA M A, MURRAY K E, and BETZ V. RLPlace: Using reinforcement learning and smart perturbations to optimize FPGA placement[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(8): 2532–2545. doi: 10.1109/TCAD.2021.3109863 [52] XU Yonghong and KHALID M A S. QPF: Efficient quadratic placement for FPGAs[C]. The International Conference on Field Programmable Logic and Applications, Tampere, Finland, 2005: 555–558. [53] GOPALAKRISHNAN P, LI Xin, and PILEGGI L. Architecture-aware FPGA placement using metric embedding[C]. The 43rd annual Design Automation Conference, San Francisco, USA, 2006: 460–465. [54] GORT M and ANDERSON J H. Analytical placement for heterogeneous FPGAs[C]. 22nd International Conference on Field Programmable Logic and Applications (FPL), Oslo, Norway, 2012: 143–150. [55] GESSLER F, BRISK P, and STOJILOVIČ M. A shared-memory parallel implementation of the RePlAce global cell placer[C]. The 33rd International Conference on VLSI Design and 2020 19th International Conference on Embedded Systems (VLSID), Bangalore, India, 2020: 78–83. [56] LIN T H, BANERJEE P, and CHANG Y W. An efficient and effective analytical placer for FPGAs[C]. The 50th Annual Design Automation Conference, Austin, USA, 2013: 10. [57] CHEN Yuchen, CHEN S Y, and CHANG Yaowen. Efficient and effective packing and analytical placement for large-scale heterogeneous FPGAs[C]. 2014 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), San Jose, USA, 2014: 647–654. [58] MENG Yibai, LI Wuxi, LIN Yibo, et al. elfPlace: Electrostatics-based placement for large-scale heterogeneous FPGAs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(1): 155–168. doi: 10.1109/TCAD.2021.3053191 [59] LU Jingwei, CHEN Pengwen, CHANG C C, et al. ePlace: Electrostatics based placement using Nesterov's method[C]. The 51st Annual Design Automation Conference, San Francisco, USA, 2014: 1–6. [60] LI Wuxi, DHAR S, and PAN D Z. UTPlaceF: A routability-driven FPGA placer with physical and congestion aware packing[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(4): 869–882. doi: 10.1109/TCAD.2017.2729349 [61] CHEN Gengjie, PUI C W, CHOW W K, et al. RippleFPGA: Routability-driven simultaneous packing and placement for modern FPGAs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37(10): 2022–2035. doi: 10.1109/TCAD.2017.2778058 [62] ABUOWAIMER Z, MAAROUF D, MARTIN T, et al. GPlace3.0: Routability-driven analytic placer for UltraScale FPGA architectures[J]. ACM Transactions on Design Automation of Electronic Systems, 2018, 23(5): 66. doi: 10.1145/3233244 [63] RAJARATHNAM R S, ALAWIEH M B, JIANG Zixuan, et al. DREAMPlaceFPGA: An open-source analytical placer for large scale heterogeneous FPGAs using deep-learning toolkit[C]. The 27th Asia and South Pacific Design Automation Conference (ASP-DAC), Taipei, China, 2022: 300–306. [64] PUI C W, CHEN Gengjie, MA Yuzhe, et al. Clock-aware ultrascale FPGA placement with machine learning routability prediction: (Invited paper)[C]. 2017 IEEE/ACM International Conference on Computer-Aided Design (ICCAD), Irvine, USA, 2017: 929–936. [65] MAAROUF D, ALHYARI A, ABUOWAIMER Z, et al. Machine-learning based congestion estimation for modern FPGAs[C]. The 28th International Conference on Field Programmable Logic and Applications (FPL), Dublin, Ireland, 2018: 4270–4277. [66] YU Cunxi and ZHANG Zhiru. Painting on placement: Forecasting routing congestion using conditional generative adversarial nets[C]. The 56th Annual Design Automation Conference 2019, Las Vegas, USA, 2019: 219. [67] ALAWIEH M B, LI Wuxi, LIN Yibo, et al. High-definition routing congestion prediction for large-scale FPGAs[C]. The 25th Asia and South Pacific Design Automation Conference (ASP-DAC), Beijing, China, 2020: 26–31. [68] XILINX. ML-based routing congestion and delay estimation in Vivado ML edition[EB/OL]. https://semiengineering.com/ml-based-routing-congestion-and-delay-estimation-in-vivado-ml-edition, 2021. [69] 田春生, 陈雷, 王源, 等. 面向FPGA的布局与布线技术研究综述[J]. 电子学报, 2022, 50(5): 1243–1254. doi: 10.12263/DZXB.20210637TIAN Chunsheng, CHEN Lei, WANG Yuan, et al. Review on technology of placement and routing for the FPGA[J]. Acta Electronica Sinica, 2022, 50(5): 1243–1254. doi: 10.12263/DZXB.20210637 [70] MCMURCHIE L and EBELING C. PathFinder: A negotiation-based performance-driven router for FPGAs[C]. The Third International ACM Symposium on Field-Programmable Gate Arrays, Napa Valley, USA, 1995: 111–117. [71] FAROOQ U, HASAN N U, BAIG I, et al. Efficient FPGA routing using reinforcement learning[C]. The 12th International Conference on Information and Communication Systems (ICICS), Valencia, Spain, 2021: 106–111. [72] 赵佳琦, 周勇, 何欣, 等. 基于深度学习的点云分割研究进展分析[J]. 电子与信息学报, 2022,, 44(12): 4426–4440. doi: 10.11999/JEIT210972ZHAO Jiaqi, ZHOU Yong, HE Xin, et al. Research progress analysis of point cloud segmentation based on deep learning[J]. Journal of Electronics &Information Technology, 2022,, 44(12): 4426–4440. doi: 10.11999/JEIT210972 -