CIE 最前沿 | 面向FPGA的布局与布线技术研究综述

论文信息：

面向FPGA的布局与布线技术研究综述

田春生, 陈雷, 王源, 王硕, 周婧, 张瑶伟, 庞永江, 周冲, 马筱婧, 杜忠, 薛钰. 面向FPGA的布局与布线技术研究综述[J]. 电子学报, DOI:10.12263/DZXB.20210637

全文二维码:

内容简介

现场可编程门阵列（Field Programmable Gate Array, FPGA）又被称为集成电路领域的“变形金刚”，作为一种半定制电路，一经面世便被广泛应用于现代数字系统的设计中。随着各种新兴技术的不断涌现，FPGA的应用范围也在逐步从普通的消费电子向物联网、高性能运算、人工智能以及航空航天等领域不断拓展。作为制约FPGA发展的关键因素，电子设计自动化（Electronic Design Automation, EDA）技术的研究显得至关重要，如图画家之笔、渡河之舟，没有EDA，FPGA的发展将寸步难行。FPGA EDA工具的设计流程主要包括设计输入、行为综合、逻辑映射、打包、布局、布线以及二进制码流生成。其中，布局与布线作为FPGA EDA工具设计流程中至关重要的环节，同时也是设计流程中最耗时的步骤，其最终结果直接决定了所设计的电路在FPGA芯片上实现后的性能。因此，布局和布线技术的研究对于FPGA的健康可持续发展具有重大的意义。

文章《面向FPGA的布局与布线技术研究综述》从方法论的角度探讨了FPGA的布局与布线方法，结合基于划分的布局、基于启发式的布局、基于解析式的布局、FPGA串行布线和FPGA并行布线等关键技术对近年来国内外研究人员做出的努力进行了回顾，并由此对FPGA布局与布线技术的发展趋势进行展望。

1 FPGA布局关键技术

FPGA中包含有数量众多的数字信号处理（Digital Signal Processing, DSP）、随机存取存储器（Random Access Memory, RAM）、可配置逻辑块（Configurable Logic Block, CLB）和输入输出（Input and Output, I/O）等异构逻辑单元（如图1（a）所示），其中，CLB占据了的FPGA芯片布局的绝大部分比例。每个CLB包含多个基本逻辑单元（Basic Logic Element, BLE）,每个BLE又进一步包含多个查找表（LookUp Table, LUT）与触发器（Flip-Flop, FF），通过一定的打包规则，能够将LUT与FF打包进CLB（如图1（b）所示）。上述异构逻辑单元全部分散在FPGA芯片结构的离散位置上。使用HDL语言设计的电路在经过行为综合、逻辑映射和打包等操作后，会被转化为一个电路网表，FPGA布局就是指根据线长、时延、功耗以及面积等约束条件，将电路网表中的异构逻辑单元与实际FPGA芯片中的物理位置建立一一映射的过程。现有的FPGA布局技术主要可以分为以下3类：基于划分的布局技术、基于启发式的布局技术以及基于解析式的布局技术。

1.1 基于划分的布局技术

基于划分的布局技术是指根据已知的布局约束关系，在最原始的布局实例的基础上，通过不断的递归迭代对布局实例进行划分，直至所有的布局实例均小于事先设定的阈值为止。基于划分的布局技术的优点在于通过对较大规模的电路或网表执行递归划分的操作，将原始布局问题转化为相互正交的不同的子问题进行求解，对于较大规模的电路的适应能力较强，收敛到最终布局结果的速度较快，但缺点也同样明显，通过使用基于划分的布局技术得到的布局结果，不能保证布局解的最优性，容易陷入到局部最优解当中。

1.2 基于启发式的布局技术

基于启发式的布局技术以现有科学领域中的一些自然现象为设计原理，对FPGA异构逻辑单元的布局过程进行建模。典型的包括遗传算法、蚁群算法和模拟退火算法等，其中又以模拟退火算法的研究最为广泛。现阶段学术界较为流行的FPGA通用布局布线（Versatile Placement and Routing, VPR）工具，其布局器的基础框架正是基于模拟退火算法。模拟退火算法的本质是一种基于概率的算法，能够在一个很大的空间内寻找近似最优解，在时间允许的情形下，能够得到全局最优解，并且能够有效避免陷入到局部最优陷阱。其缺陷在于当电路规模较大时，算法收敛的时间较长，因此现有的研究大多是针对模拟退火算法的收敛时间进行优化。

1.3 基于解析式的布局技术

基于解析式的布局技术能够将FPGA布局问题建模为一个连续优化问题，最终通过梯度下降的方法得到布局问题的最优解。根据目标函数的不同，基于解析式的布局技术又能够被划分为二次方布局技术以及非线性布局技术。二次方布局技术是指通过二次函数来逼近最终的布局解，而非线性布局技术是指利用更加具有表现力的高阶方法来完成对布局结果的近似。基于解析式的布局技术其布局结果的可接受度以及系统运行时间要优于基于划分的布局技术与基于启发式的布局技术。然而，为了更加高效地利用FPGA芯片资源，基于解析式的布局技术在一些具体的布局细节方面仍需进一步优化，这些具体的布局细节通常以低温模拟退火方法或是一些基于贪婪思想的启发式方法的方式来实现。

与此同时，在FPGA EDA流程中，打包过程与布局过程间的关系是密不可分的，图2对他们间的关系做了总结。早期，打包-布局-合法化（Packing-Placement-Legalize）（图2蓝线）方法无论是在学术界亦或是工业界都占据着统治性地位。在这种操作流程中，打包工具首先根据逻辑单元间的连接关系将逻辑单元进行打包，随后的布局以及合法化操作依次执行，最终能够得到一个合法的布局解。尽管打包-布局-合法化方法的执行效率很高，但这种方法在将逻辑单元打包的过程中并没有将逻辑单元的空间位置信息与连接关系联合起来进行考虑，因此得到的布局解的质量相对较差。为了解决上述问题，布局-打包-布局-合法化（Placement-Packing-Placement-Legalize）（图2橙线）方法应运而生。首先由布局器执行扁平化的初始布局（Flat Initial Placement, FIP）操作，随后在打包阶段将逻辑单元的连接关系与空间位置信息同时进行考虑，最后执行布局与合法化操作。同时，也有部分研究学者提出了一种布局-半打包-合法化（Placement-SemiPacking-Legalize）（图2红线）的方法，在这种方法中，打包与布局的界限相对模糊，首先由布局器执行布局操作，得到一种FIP，在此基础上进一步将LUT与FF打包成逻辑单元簇（BLEs），最后执行合法化操作完成整个布局流程。

表1总结了基于划分的布局技术、基于启发式的布局技术与基于解析式的布局技术的优势与不足。

2 FPGA布线关键技术

FPGA布线问题是指通过对芯片中的可编程互连开关进行配置，从而完成对电路逻辑单元间的连接。同时，为了确保电路中的信号能够被正确传输，在布线过程中，需要保证所有的互连资源都不能被重复使用。1995年，McMurchie 等人首次提出了基于拥塞协商思想的FPGA布线方法PathFinder，它能够在允许FPGA中互连资源被重复使用的情况下执行线网的布线操作，随后迭代地对电路中的线网进行“拆线-重布”，每次迭代时PathFinder会以协商的方式确定各线网间互连资源的分配。随着迭代次数的增加，PathFinder会逐渐增加对重复使用的互连资源的惩罚力度，以此来逐步消除互连资源的重复使用。PathFinder拥塞协商方法起到了引路者以及奠基人的角色，它是目前大部分FPGA布线算法的基础，学术上通用的VPR工具在布线阶段也是使用PathFinder方法，现阶段几乎所有的FPGA厂商都在使用基于拥塞协商的PathFinder布线方法，或是在这个方法基础上引申出来的其他布线方法，迄今为止，还未出现其他更好的方法能够代替PathFinder方法在FPGA布线领域的主导性地位。但随着电路规模的增大，PathFinder布线方法耗时越来越长，这一问题随着FPGA的发展将愈发突出。因此，亟需探索新的解决方案或是对现有解决方案进行优化以适应FPGA不断发展的需求。现有的解决方案可以分为FPGA串行布线与FPGA并行布线两种类型。

2.1 FPGA串行布线技术

PathFinder拥塞协商方法的本质使得它只能够被串行执行，现有的FPGA串行布线技术大多是基于PathFinder方法的改进。例如，将FPGA电路中常用的逻辑单元打包成宏并提前进行编译或是简化FPGA布线结构，但由于应用条件的限制，上述方法的应用范围十分有限。与此同时，改变PathFinder布线策略同样是一种非常有效的改进手段，例如，有研究学者提出基于连接（Connection-Based）的布线策略或是基于自适应增量的布线策略，都能够大幅度提升布线方法的运行效率，减少布线所需耗费时间。

2.2 FPGA并行布线技术

随着多核CPU与图形处理器（Graphics Processing Unit, GPU）的普及，越来越多的研究学者将并行计算应用到FPGA布线领域以减少FPGA在布线时所需花费的时间。根据并行化方式的不同，又可以将FPGA并行布线技术分为粗粒度FPGA并行布线技术、细粒度FPGA并行布线技术以及两种不同并行布线技术的混合。粗粒度FPGA并行布线技术通过将线网划分为不同的分区，在每个分区内执行独立的布线操作。最终布线后的性能参数取决于线网的划分方式、并行运算过程中数据的同步模式以及冲突的回避方式等多种因素。细粒度FPGA并行布线技术能够对单个线网的布线过程实现并行加速，最终的性能参数取决于并行布线过程中的并行度以及共享数据的同步方式等诸多因素。此外，评判某一FPGA并行布线方法的性能还需将布线方法的可扩展性与确定性等问题联合起来进行考虑。表2对不同的FPGA并行布线技术进行了分析总结。

3 未来发展趋势

迄今为止，国内外科研人员对FPGA布局与布线技术有了较为深入的研究，并提出了一些具有代表性的研究成果。从当前的研究成果可以得出：关于FPGA布局技术，主要可以分为基于划分的布局技术、基于启发式的布局技术以及基于解析式的布局技术三种类型，三种类型的FPGA布局技术具备各自的优缺点，在应用的过程中可根据需求进行选择。关于FPGA布线技术，均是以基于拥塞协商的PathFinder布线技术为根基，在此基础上又能够细分为 FPGA 串行布线技术与 FPGA并行布线技术。相比较于串行布线技术，并行布线技术能够获得更高的加速比，但在布线的过程中也面临着资源竞争、布线方法的确定性以及可扩展性等诸多问题。通过上述分析可知，对FPGA布局和布线技术的研究仍然任重而道远，基于现有的研究基础，布局与布线技术未来的发展趋势可以归纳为以下几个方面：

（1）利用人工智能技术优化FPGA布局和布线的流程。FPGA电路规模越大，对布局与布线技术的要求就越高，系统运行时间便越长。FPGA布局与布线问题属于典型的启发式探索问题，变量空间大，难以寻找全局最优解，而人工智能技术是非常适合于此类高维数据空间问题求解的 。但现阶段却鲜有将人工智能技术应用于FPGA布局与布线领域的研究。因此，随着人工智能技术与相关工具的发展，可以尝试突破现有方法的架构，将人工智能等方法应用到FPGA布局与布线的流程中，在不影响收敛速度前提下，提升 FPGA 布局与布线解的质量。

（2）探索多驱动的布局和布线策略。随着FPGA应用领域的不断拓展，在布局与布线的过程中仅考虑线长、时序等信息是远远不够的。例如，现阶段在航空、航天等各重要核心领域的电子系统中，FPGA在正扮演一个其它芯片无法替代的角色。但随着 FPGA 的大规模使用，其在空间应用中的辐照问题也越来越突出。宇宙空间中存在着大量的高能粒子，这些高能粒子会对FPGA 电子器件的功能造成影响，产生软错误。但如果在布局与布线的过程中就考虑到了软错误的影响，便有可能将软错误产生的概率降至最低。因此，在实际应用的过程中，需要将线长、时延、软错误、拥挤度、功耗等诸多因素联合起来进行考虑，以满足未来FPGA全方位发展的需求，同时这也是在今后研究中需要进一步探索的方向。

（3）研究更加简单可行的FPGA并行布局与布线方法。通过并行计算的方法能够显著提升 FPGA 布局和布线的速度，减少使用 EDA 工具将 FPGA 电路编译为二进制码流所需要的时间 。但随着 FPGA 电路的规模越来越大，现有的并行布局与布线方法的执行难度也在不断加大，并行方法的确定性以及可扩展性等问题越来越突出。在未来的工作中，可以尝试研究更加简单可行的FPGA并行布局、布线方法，从而加大布局、布线方法在执行过程中的并行度，进一步减少 FPGA EDA工具在布局和布线阶段所需花费的时间。

4 结论

随着科技的不断发展，现代工业中所使用的FPGA电路的规模也在不断增大，对FPGA布局和布线技术提出了更高的要求。论文围绕着FPGA布局与布线问题展开，从FPGA布局关键技术与布线关键技术2个方面对研究进展做了分析与总结。在此基础上，对未来的发展趋势进行了展望，以期对未来本领域的研究具有借鉴意义。我们坚信，随着研究人员对布局与布线技术的不断探索，终将满足未来FPGA发展的需求，为FPGA更加普遍的应用提供有力支撑。

作者简介

田春生，1993年2月出生，中共党员，2020年博士毕业于吉林大学，现为北京大学与北京微电子技术研究所联合博士后。他的研究方向为集成电路自动化设计，在国内外权威期刊及国际会议上发表论文15篇，申请国家发明专利7项，入选中国航天电子技术研究院“聚才计划”，获得吉林省科学技术进步奖一等奖1项。

陈雷（通讯作者），1978年11月出生，中共党员，研究员，博士生导师。中央企业青联委员、副秘书长，中国航天电子技术研究院副院长，北京微电子技术研究所所长，享受国务院政府津贴，入选2020年中组部中青年创新领军人才、2014年中组部青年拔尖人才计划，获2019年度中国科协求是杰出青年成果转化奖、2018年度国防科技创新团队带头人等荣誉。

他于2006年在西北工业大学获博士学位，我国航天微电子领域的第一位博士后。作为我国宇航用FPGA技术的带头人，率先在国际上提出了宇航用单粒子加固SRAM型FPGA技术路线，突破了超深亚微米、65纳米、28纳米工艺下宇航用FPGA关键核心技术，攻克了SRAM型FPGA空间应用时单粒子翻转的世界性难题，构建了国产万门级到亿门级宇航用FPGA研制平台，形成了5个系列近百个规格的产品谱系，实现了航天核心关键元器件的自主可控。