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

田春生，陈 雷，王 源，王 硕，周 婧，张瑶伟，庞永江，周 冲，马筱婧，杜 忠，薛 钰

（1.北京大学信息科学技术学院微纳电子学系，北京 100871；2.北京微电子技术研究所，北京 100076）

1 引言

1984 年，Xilinx 公司首次提出现场可编程门阵列（Field Programmable Gate Array，FPGA）的概念，作为一种半定制电路，FPGA 凭借其设计成本低、速度快、异构逻辑资源丰富等优势，一经面世便广泛应用于现代数字系统的设计中［1，2］.随着各种新兴技术的不断涌现，FPGA 的应用范围也在逐步从普通的消费电子向物联网（Internet of Things，IoTs）［3］、高性能运算［4］、云计算［5］、人工智能［6，7］等领域不断拓展.FPGA 的集成度也在不断增大，从最初只含有64 个逻辑单元发展到迄今为止的超过900万个逻辑单元以及350亿个晶体管.集成度的不断提升使得FPGA 能够被用于设计更加复杂的电路系统，但同时也对FPGA 电子设计自动化（Electronic Design Automation，EDA）软件工具造成了负担［8］.FPGA 的研发离不开EDA 工具的支持，以硬件描述语言（Hardware Description Language，HDL）设计的电路，通过FPGA EDA 工具会被编译为二进制的码流文件，通过该码流文件能够完成对FPGA 芯片的配置最终实现所需的电路功能［9］.但随着FPGA芯片集成度以及电路规模的不断提高，FPGA EDA 工具将电路描述文件编译为二进制格式的文件所需花费的时间也越来越长，这将直接降低FPGA 在设计阶段的开发效率、增加时间成本，制约FPGA芯片的健康发展［10，11］.

FPGA EDA 工具的设计流程主要包括设计输入、行为综合、逻辑映射、打包、布局、布线以及二进制码流生成.其中，布局与布线作为FPGA EDA 工具设计流程中至关重要的环节，其最终结果直接决定了所设计的电路在FPGA 芯片上实现后的性能.因此，布局和布线技术的研究对于FPGA 的健康可持续发展具有重大的意义.本文全面综述了FPGA 布局、布线问题的研究现状与进展，完成了相关理论成果和技术方法的梳理，对FPGA 布局和布线的关键技术进行了详细阐述，最后对FPGA布局、布线技术未来的发展趋势进行了展望.

2 FPGA布局关键技术

使用HDL 语言设计的电路在经过行为综合、逻辑映射和打包等操作后，会被转化为一个电路网表，FPGA 布局就是指根据线长、时延、功耗以及面积等约束条件，将电路网表中的异构逻辑单元与实际FPGA 芯片中的物理位置建立一一映射的过程［12］.现有的FPGA布局技术主要包括基于划分的布局技术、基于启发式的布局技术以及基于解析式的布局技术.

2.1 基于划分的布局技术

基于划分的布局技术是指根据已知的布局约束关系，在最原始的布局实例的基础上，通过递归迭代对布局实例进行划分，直至所有布局实例均小于事先设定的阈值为止［13］.SimPL布局方法便是基于划分的布局技术中的一种典型的代表［14］，该方法以线长为约束条件，首先分别计算线长的下界和上界，接下来通过采用一种基于自顶向下的几何分割和非线性缩放的前向合法化方法不断迭代，最终能够使逻辑单元收敛到合法的位置.随着图论以及超图划分理论方法的不断演进［15～19］，最小割布局方法也得到了研究学者们的广泛关注.基于划分的布局技术的优点在于通过对较大规模的电路执行递归划分操作，将原始布局问题转化为相互正交的不同的子问题，收敛到最终布局结果的速度较快，但通过使用基于划分的布局技术得到的布局结果，不能保证布局解的最优性，容易陷入到局部最优解当中.

2.2 基于启发式的布局技术

基于启发式的布局技术以现有科学领域中的一些自然现象为设计原理，对FPGA 逻辑单元的布局过程进行建模.典型的包括遗传算法［20，21］、蚁群算法［22～24］和模拟退火算法［25］等，其中又以模拟退火算法的研究最为广泛.1953 年，Metropolis 等最早提出了模拟退火算法理论［26］，模拟退火算法是一种基于Monte-Carlo 求解方式的随机搜索算法，其原理是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性.1988年，Carl 等［27］首次将模拟退火算法的思想引入到超大规模集成电路（Very Large Scale Integration，VLSI）布局领域.随后，越来越多的研究学者开始关注模拟退火算法在VLSI、FPGA 等布局领域的应用.学术界较为流行的FPGA 通用布局布线（Versatile Placement and Routing，VPR）工具，其布局器的基础框架正是基于模拟退火算法.

使用传统的模拟退火算法对FPGA 执行布局操作时，首先会得到一个初始的布局状态，初始布局状态是布局器随机生成的，随后布局器会通过执行逻辑单元的交换或是移动等操作对当前的布局解进行扰动，进一步得到新的布局解并计算得到初始温度.布局器的主体包含内外两层循环，内层循环控制交换的逻辑单元，外层循环执行温度的更新以及逻辑单元交换半径的计算等操作.内层循环每次选择一个逻辑单元，随后依据交换半径在FPGA 芯上选择一个位置，若该位置为空则直接将所选择的逻辑单元移动到该位置上，若该位置上已放置有逻辑单元则执行两个逻辑单元的位置交换操作［28］.以ΔC表示逻辑单元交换前后成本函数的差值，如果ΔC＜0，表示新的布局解要优于原始的布局解，则接受本次的移动或是交换过程；如果ΔC＞0，则以的概率接受新的布局解，其中T表示当前温度.这样做的好处在于能够使布局器具备一定的爬坡能力.当内层循环的迭代次数达到上限后，退出内层循环进入外层循环，外层循环会依据当前的布局状态对逻辑单元的交换半径以及温度进行更新.当温度小于特定阈值时跳出外层循环，结束布局过程.模拟退火算法的本质还是一种基于概率的算法，能够在一个很大的空间内寻找近似最优解，在时间允许的情形下，能够得到全局最优解，并且能够有效避免陷入到局部最优陷阱.其缺陷在于当电路规模较大时，算法收敛的时间较长，因此对模拟退火算法的收敛时间进行优化研究显得至关重要［29］.

利用多个中央处理器进行加速是减少FPGA布局运行时间的有效手段，2010 年，Brik 等［30］利用事务性内存（Transactional Memory，TM）对模拟退火算法进行并行加速，在布局质量几乎没有任何下降的前提下，能够获得可观的加速比.2011年，Altera 公司（现Intel公司）研究人员［31］提出了一种确定性的FPGA 并行布局算法，能够对关键路径进行优化，在整个退火的过程中最高能够实现高达3.7倍的加速比.2014年，An等［32］以VPR工具为基础，探索了基于模拟退火机制的FPGA 并行布局方法如何能够在保证布局质量的同时，确保布局结果的确定性.实验结果表明，在保证布局质量以及确定性的情况下，能够获得5.9倍的加速比.2018年，Hu等［33］使用多线程同时处理逻辑单元的移动过程，避免了数据流的冲突，实现了FPGA布局过程的加速.

通过对模拟退火方法中逻辑单元的移动过程进行优化，从而加速FPGA 布局过程的收敛同样是一个非常有意义的研究方向［34～37］.2009 年，Vorwerk 等［34］提出了多种策略来创建逻辑单元的移动过程，通过计算每一种移动过程的有效性，以此有效性为指标决定布局器选取每一种移动过程的概率，以便更有效的在FPGA 布局空间中搜索最优的解决方案，能够获得更好的线长以及时序上的实现效果.Intel 公司的Quartus II 布局器中便采用了多达10 余种的直接移动（Directed Moves，DM）过程，但在布局时DM 过程的选择机制却从未对外披露［31］.2017年，Yuan等［38］以线长为指标，提出了基于区域范围的移动过程，将逻辑单元的移动操作限制在某一特定的区域内，同时通过设置优先级的方法，优先对那些性能较差的线网执行布局操作.2019 年，Yuan 等［39］对此项工作做了进一步拓展，在布局的过程中加入了时序优化.此外，随着机器学习、人工智能等技术的发展，越来越多的研究学者利用机器学习类方法来优化基于模拟退火算法的FPGA 布局过程［40］.2019 年，Murray等［41］使用单状态强化学习策略提出了一种自适应的FPGA 布局方法，在每一次布局的过程中能够自动地选取需要交换的逻辑单元，节省了布局所需要的时间，与VPR 工具相比较，在获得同等性能参数的前提下，能够获得2倍以上的加速比.在此项工作基础上，2020年，Elgammal等［42］做了进一步探索，使用多状态强化学习策略以优化DM过程的选取过程，基于模拟退火方法的FPGA布局器的性能得到了进一步优化.

2.3 基于解析式的布局技术

基于解析式的布局技术将FPGA 布局问题建模为一个连续优化问题，通过梯度下降的方法得到布局问题的最优解.根据目标函数的不同，可以分为二次方布局技术［43～46］以及非线性布局技术［47，48］.二次方布局技术是指通过二次函数来逼近最终的布局解，而非线性布局技术是指利用更加具有表现力的高阶方法来完成对布局结果的近似.

二次方布局技术通常以线长为优化目标完成对目标函数的建模，随后通过Krylov子空间方法将上述优化问题转化为对称与正定（Symmetric and Positive-Definite，SPD）线性系统的求解问题，最终得到优化问题的解［49］.但纯粹以线长为优化目标，最终的布局结果将导致越来越多的逻辑单元重叠在一起，因此需要采用合适的方法对二次方布局技术进行优化，以减少各逻辑单元间的重叠.其中，力导向法得到了广泛的关注.在每一次布局迭代的过程中，力导向法能够使逻辑单元均匀的分散开，这些逻辑单元的位置将被作为锚节点，随后，将指向这些逻辑单元的额外的拓展力应用于下一次迭代中，以辅助逻辑单元的布局，不断重复上述过程，最终能够得到一个所有逻辑单元的位置均互不重叠的布局解决方案［50，51］.与二次方布局技术不同，非线性布局技术使用不可微分的非线性函数来表示非重叠的约束条件，并将其与线长一起在统一的目标函数中进行求解.由于高阶非线性函数比二次函数更具有表现力，因此，通过非线性布局技术得到的布局解的质量要优于二次方布局技术，但这种布局质量的改进需要牺牲更多的系统运行时间［52］.

基于解析式的布局技术其布局结果的可接受度以及系统运行时间要优于基于划分的布局技术与基于启发式的布局技术.然而，为了更加高效地利用FPGA 芯片资源，基于解析式的布局技术在一些具体的布局细节方面仍需进一步优化，这些具体的布局细节通常以低温模拟退火方法或是一些基于贪婪思想的启发式方法来实现［53，54］.

本文总结了基于划分的布局技术、基于启发式的布局技术与基于解析式的布局技术的优势与不足，具体如表1所示.

表1 FPGA布局技术总结

3 FPGA布线关键技术

FPGA 布线问题是指通过对芯片中的可编程互连开关进行配置，从而完成对电路逻辑单元间的连接，同时需要保证所有的互连资源都不能被重复使用.在布线时，FPGA 芯片内的硬件资源会被抽象为有向的布线资源图（Routing Resource Graph，RRG）G=（V，E），其中，V表示RRG 中顶点的集合，每一个顶点v，∀v∈V表示FPGA 芯片内的互连线资源或是逻辑单元的引脚.E表示RRG 中边的集合，每一条边ei，j，∀ei，j∈E表示逻辑资源引脚与互连线资源或是互连线资源间的可编程互连开关［55］.RRG 作为布线算法与FPGA 硬件间的纽带，能够将FPGA 布线问题转化为图论中最短路径的求解问题，布线算法直接在RRG 上对电路线网执行布线操作即可.每个电路线网Ni由一个源端si，∀si∈V与一个或多个漏端ti，j，∀ti，j∈V组成.有了RRG的概念，线网Ni的布线问题被转化为能否在RRG 中找到合法的路径连接si与ti，j，这些路径共同组成线网Ni的布线树（Routing Tree，RT）RT(Ni) ⊂G.

1995 年，McMurchie 等［56］首次提出了基于拥塞协商思想的FPGA 布线方法PathFinder，它允许FPGA 中互连资源被重复使用的情况下执行线网的布线操作，迭代地对电路中的线网进行“拆线-重布”，每次迭代时PathFinder 会以协商的方式确定各线网间互连资源的分配.随着迭代次数的增加，PathFinder 会逐渐增加对重复使用的互连资源的惩罚力度，以此来逐步消除互连资源的重复使用.

PathFinder 方法的实现是一个内外三层循环的嵌套结构，最外层的循环被称为全局布线器，在每一次迭代时会调用第二层循环中的线网布线器，对电路中的线网逐一执行布线操作.全局布线器在所有线网完成布线迭代后，会将布线资源的历史拥挤度进行更新，并根据布线迭代的结果对线网执行时序分析的操作.检查是否有布线资源被重复使用，若所有布线资源均没有被重复占用，则结束布线流程；否则，此次布线迭代过程非法，继续执行下一次布线迭代操作.当线网布线器对电路中的第i个线网Ni执行布线操作时，线网布线器会释放线网Ni所对应的RT（Ni）上的资源，并对节点的当前拥挤度进行更新，随后根据连接的关键度信息对线网Ni中所有的漏端ti，j执行降序排列操作，最后线网布线器会调用最内层的迷宫布线器依次对线网Ni内的每一个漏端ti，j进行布线.PathFinder 拥塞协商方法起到了引路者以及奠基人的角色，它是目前大部分FPGA 布线算法的基础，学术上通用的VPR 工具以及nextpnr 工具在布线阶段使用的都是在PathFinder 基础上改进的布线方法.同时，现阶段几乎所有的FPGA 厂商都在使用基于拥塞协商的PathFinder 布线方法，或是在这个方法基础上引申出来的其他布线方法，但随着电路规模的增大，PathFinder 布线方法耗时越来越长，这一问题随着FPGA 的发展将愈发突出.因此，亟需探索新的解决方案或是对现有解决方案进行优化以适应FPGA 不断发展的需求［57］.现有的解决方案可以分为FPGA串行布线与FPGA并行布线两种类型.

3.1 FPGA串行布线技术

现有的FPGA串行布线技术都是基于PathFinder方法的改进.将FPGA 电路中常用的逻辑单元打包成宏并提前进行编译，是减少布线时间的有效手段［58，59］.2011 年，Lavin 等［59］通过设置硬宏的方法将FPGA 电路中常用的一些逻辑单元提前进行编译并在数据库中加以保存，在对用户设计电路进行编译时便可以从数据库中选择与之相匹配的硬宏.这种方法可以明显减少电路编译的时间，同Xilinx 公司的ISE 工具相比较，此方法能够获得10 到50 倍的加速比，改进效果是非常可观的.2012 年，Coole 等［60］构建了一种新的FPGA 布局布线工具，通过设置宏单元能够使布线方法在更高的层次上运行，能够获得指数级的加速比.但由于宏单元是提前设置并封装好的，在实际布线时其中的连接关系是无法更改的，增加了FPGA 布线时的局限性.简化FPGA 的布线结构是另一种降低FPGA 布线时间的方法［61］.PathFinder 方法在每次对线网执行布线迭代时需要确定具体使用的是布线通道中的哪条布线资源，2015 年，Ferreira 等［62］提出在使用PathFinder 方法确定布线通道后，将布线通道中互连资源的分配问题建模为布尔满足问题［63，64］，随后使用求解器MiniSat 对上述问题进行了求解［65］.通过简化FPGA 结构的方法，能够明显降低FPGA 布线方法复杂度，但此类方法过分依赖FPGA 硬件架构，并不适用于商用FPGA 芯片的设计流程，实用性有待进一步加强.

PathFinder 方法以线网为单位每次执行“拆线-重布”的操作，在检测到存在布线资源重复使用的情况时，对所有线网进行拆分，依次执行重新布线.上述过程是非常耗时的.为此，2016 年，比利时根特大学研究人员［66，67］提出了基于连接的FPGA 布线方案，连接由线网Ni中的单个源端si与单个漏端ti，j组成，在每次迭代的过程中以连接为单位执行“拆线-重布”的操作，只有当不同的连接属于同一个线网时才可以共享相同的布线资源节点.与VPR 7.0相比基于连接的FPGA 布线方案在布线阶段能够提供3.4倍的加速比［67］.与基于连接的FPGA 布线方案不同，2020 年，Murray 等［68］设计了一种自适应的增量布线器，能够保持一种自然的基于线网的结构，在每次“拆线-重布”时只拆除非法的布线资源节点，从而保证在下次迭代时，合法的路径能够被重复使用，减少了在RRG 中重复搜索所需要的时间.同时，针对一些具有高扇出属性的线网制定了特殊的前向搜索机制，即每次只对与漏端ti，j空间上相近的布线节点进行搜索，以降低布线所需时间.相比于基于连接的FPGA布线方案，能够进一步减少17%的布线时间.

3.2 FPGA并行布线技术

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

表2 FPGA并行布线技术

3.2.1 粗粒度FPGA并行布线技术

（1）基于字典序的FPGA并行布线

1997 年，Chan 等［73］首次尝试将PathFinder 方法执行并行化操作，研究人员首先将所有线网按字典序进行排序，从而使那些可能共享资源的线网相邻并尽可能分配给同一个中央处理器（Central Processing Unit，CPU）.随后，将线网列表划分成互不相交的集合，每个集合静态地分配给CPU 执行并行布线.并行布线的过程中，每个CPU 会单独保存线网布线的拥塞状态等信息，一旦某个CPU 的拥塞状态信息发生变化，该CPU 将首先更新本地保存的数据信息，并通过UNIX 套接字通知其他处理器对拥塞信息进行更新.与原始PathFinder 算法相比较，上述方法最高能够获得3.2 倍的加速比.但此方法的布线结果具有不确定性，布线结果依赖于线网的布线顺序，并且由于是静态的线网划分，每个CPU 间存在负载不均衡的问题.2000年，上述团队的研究人员［74］对CPU 负载不均衡的问题进行了优化，但布线结果仍然具有不确定性.

（2）基于负载均衡的FPGA并行布线

2012 年，Gort 等［75］提出了多进程并发执行的方式以加速布线过程，这些并发执行的进程运行在不同的CPU 内核中（如图1 所示）.每个进程运行一个单独的VPR 实例，负责对分配给它的线网执行布线操作并维护自身的数据结构.不同VPR 实例间的信息同步通过消息传递接口（Message Passing Interface，MPI）来实现.

图1 基于负载均衡的FPGA并行布线

VPR 实例在完成某一信号的布线后，会向其他VPR 实例发送无阻塞更新信息，随后继续执行布线操作而无需等待从其他VPR 实例接收更新消息.VPR 实例发送的更新信息中包含了最新的布线信息，这些信息被保存在MPI的信息队列中.为了接收更新的消息，VPR 实例会在布线过程中的特定位置发出阻塞接收的调用请求，并且为了保证布线结果的确定性，这些位置在每次运行过程中都是相同的.如果某一时刻VPR 实例想要接收信息但更新消息却不可用，由于先前已经调用了阻塞接收的请求，VPR 实例会暂停其布线流程直至消息更新可用为止.为了最大程度地减少VPR 实例驻留时间，作者会在任务划分的过程中保证每个VPR 实例的负载都尽可能相等，并且仅在MPI 消息队列中存在VPR 实例想要更新的消息时，才会允许VPR实例发出阻塞接收的调用请求.与此同时，为了能够精准地确定阻塞接收调用请求的发出时间，每个VPR 实例都会维护一个工作计数器以评估每个VPR 实例所执行的工作量.

（3）基于迭代划分的FPGA并行布线

北京大学团队研究人员［76］与中山大学团队研究人员［77］在前人研究工作的基础上探索了基于迭代划分的FPGA 并行布线方案，通过递归划分的方法能够将线网划分为多个集合，每个集合内的线网互不相交，进而可以执行并行布线的操作.

首先，使用二分法能够将FPGA 划分为两个子区域，根据划分的结果能够得到三个不同的线网集合：横跨两个子区域的线网集合以及完全在两个子区域内的线网集合.由于在两个子区域内的线网互不相交，因此可以执行并行布线的操作.可以通过迭代的方式重复上述步骤以增加布线方法的并行度.

图2 展示了基于迭代划分的FPGA 并行布线方法的原理.首先，图中的蓝色实线将FPGA 分成了上下两个区域：S1与S2.随后，图中绿色的虚线进行了进一步的划分：将区域S1划分为S3与S4两个子区域，将区域S2划分为S5与S6两个子区域.最后，图中红色的虚线又进一步执行了划分的操作：将区域S3划分为S7与S8两个子区域，将区域S4划分为S9与S10两个子区域，将区域S5划分为S11与S12两个子区域，将区域S6划分为S13与S14两个子区域.上述划分过程可以使用一个L级二叉树表示（如图2（a）所示）.划分完成后，布线问题被建模为分布式内存系统的任务调度问题：任务T0负责对所有的线网执行布线操作，任务T1负责对子区域S1内的线网执行布线操作，任务T2负责对子区域S2内的线网执行布线操作，依此类推，任务Ti负责对子区域Si内的线网执行布线操作.上述任务被静态地映射到不同进程，不同进程使用MPI 进行数据间的同步（如图2（b）所示）.布线过程从主进程p=0开始执行，即在一个L级的完美二叉树上执行任务T0.T0首先将线网划分为S1与S2两个子区域，接下来T0会对横跨两个子区域的线网集合执行串行布线的操作，布线结束后，它会将右侧的L-1 级子树分配给进程p+2L-1=p+4.最后，T0通过递归调用函数ParMaze（）会将左侧的L-1级子树分配给任务T1.随后，进程p+4 与任务T2会返回子区域S2内线网的布线树，任务T1会返回子区域S1内线网的布线树.不断重复上述过程，直至所有的线网都完成了布线操作.

图2 递归划分原理

但随着递归迭代次数的增加，跨区域线网的数量也在同时增多，导致FPGA 并行布线方法的并行度越来越低.针对上述问题，2020年，Wang等［78］提出了一种混合线网划分机制，在线网递归划分的过程中将线网划分为互斥线网集合与重叠线网集合，随后针对两组不同的集合采取不同的并行布线策略，并且在布线的过程中可以很好地解决资源冲突以及负载不均衡的问题.

3.2.2 细粒度FPGA并行布线技术

不同于粗粒度FPGA 并行布线技术，细粒度FPGA并行布线技术在布线时不会改变线网的布线顺序.据统计，约70%的布线时间花费在了搜索邻居节点以及优先级队列的处理上［79］.因此，如何对PathFinder 算法的迷宫布线器进行细粒度加速是当前亟需解决的问题［80～82］.

（1）基于Galois模型的FPGA并行布线

2014 年，Moctar 等［83］率先探索了使用Galois 模型对PathFinder 算法中的迷宫布线器进行并行加速的操作，并在VPR 5.0 的基础上对该项工作进行了实现.多线程的并行策略基于Galois 迭代合并机制，即允许单个线程同时处理多个迭代.每个线程都会维护一个本地优先级队列，优先级队列中存储了需要进行拓展的节点，若本地优先级为空，线程将访问存储在共享内存空间中的全局优先级队列.上述工作使用互斥锁实现不同线程间的同步，但当某些情况下无法获取互斥锁时，Galois 会根据先前保存的数据副本将冲突进行回滚，以尽可能降低不同线程间的数据冲突.同VPR 5.0 相比，基于Galois 模型的FPGA 并行布线方法最高能够获得5.46 倍的加速比.但根据此方法得到的布线结果具有不确定性，布线结果依赖于线程完成工作的先后顺序.此外，Galois 在回滚的过程中将会产生大量的开销，严重影响了该方法的可扩展性.2018年，上述团队研究人员［84］对此项工作进行了扩展，消除了因数据回滚操作而带来的影响，通过Galois 模型多线程能够同时对单个线网执行并行布线的操作，在布线结果具有确定性的情况下，能够实现3.67 倍的加速比.

（2）基于Posix线程的FPGA并行布线

2010 年，Gort 等［79］提出使用Posix 线程来加速迷宫布线器中成本函数的计算过程.当存在N个可用的线程时，将其拆分为一个主线程与N-1 个辅助线程（如图3 所示）.主线程执行迷宫布线器的串行部分以及1/N的并行部分.每个线程都会维护自己的优先级队列，主线程首先会查看所有优先级队列的顶部节点，随后借助同步路障选取出成本函数最低的节点，在此基础上，主线程会拓展这个成本函数最低的节点并通知所有的辅助线程做好准备工作.接下来，所有的线程会计算待拓展节点的成本函数并将其添加到各自的优先级队列中.一旦主线程完成了添加节点的操作，它会在第二道同步路障处等待其他线程，不断重复上述步骤，直至迷宫布线器完成布线.

图3 基于Posix线程的FPGA并行布线

Zhu 等［85］同时考虑粗粒度与细粒度的FPGA 并行布线，提出利用线程来代替进程以减少通信开销，根据线网的扇出将线网划分为高扇出线网与低扇出线网两种类型.高扇出线网会被进一步划分为互不重叠的低扇出线网的集合，从而能够执行并行布线的操作.对于低扇出线网，该团队研究人员使用互不重叠的边界框对线网进行标记，并同时执行布线操作.上述布线方法最终在VPR 5.0架构的基础上通过Posix多线程技术进行了实现.与文献［81］的方法相类似，在实现的过程中由主线程负责所有的辅助线程，并通过设置同步路障的方式完成线程间的同步.此并行布线方法同样包含两道同步路障，第一道同步路障负责唤醒所有的辅助线程对线网执行并行布线操作.当所有辅助线程完成布线任务后，第二道同步路障负责通知主线程将布线结果合并、更新阻塞信息等，进入下一次布线迭代.通过该方法得到的布线结果具有较好的确定性.

4 未来发展趋势

迄今为止，国内外科研人员对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工具在布局和布线阶段所需花费的时间.

5 结论

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