FPGA是芯片的个中一种，从上世纪八十年代出身起，FPGA已经从大略的可编程门阵列，发展成为了有着大量可编程逻辑的繁芜片上系统。除了硬件构造之外，FPGA的开拓工具和运用处景也都取得了长足的进步和扩展，FPGA在全体半导体行业的主要性也在不断增强。FPGA芯片的演进，离不开这些“建筑师”的不断发明创造。
几年前，这些FPGA的顶级建筑师们选出了自上世纪九十年代起的20年以来FPGA领域最有影响力的25个研究成果。通过这些主要的成果，我们会理解FPGA是如何发展至今，并且知道FPGA技能未来将会发展向何处。
这25个研究成果按研究领域分为架构、EDA工具、电路、运用等大类，每项成果都由一名该领域的顶级学者做推介。接下来，我将在几篇文章里，分别先容这这些改变了FPGA发展进程的主要研究成果。本文是布局布线算法篇。关于FPGA架构领域的主要创新，请拜会这两篇：《系统架构篇》和《微架构篇》。
01 寻路者：基于协商的FPGA性能优化布线算法
一句话总结：历史最强FPGA布线算法，没有之一。
英文名：Pathfinder: A Negotiation-Based Performance-Driven Router for FPGAs
作者：Larry McMurchie, Carl Ebeling
揭橥韶光：1995年
推介人：Sinan Kaptanoglu（Microsemi公司）
Carl Ebeling（现任华盛顿大学教授）
这项事情可以算是过去二十年中影响FPGA技能发展的最主要的成果之一。这项成果对工业界和学术界都产生了极其深远的影响。最主要的是，这个事情将FPGA的布线研究，从一个结果颠簸极大的问题，转化为一个能够很好掌握的优化问题。时至今日，险些所有的FPGA厂商都在利用这项事情提出的协商拥塞（Negotiated Congestion）的布线算法，或者是由这个算法引申出来的其他布线方法。此外，学术界最为广泛利用的FPGA架构设计和剖析工具VPR，便是基于这项成果而开拓的。
常日来说，有些研究成果会急速对学术界带来启示，而有些则会首先被低估一段韶光，然后才会被人们完备理解。这项成果就属于后者。很多研究FPGA设计工具的事情都是提出一些新的想法，利用基准测试对这些想法进行实验，然后比当时的其他事情取得5%到10%的提升，诸如此类。并不是说这些事情不足精良，但大多数的事情所取得的造诣和影响都是暂时的，由于会不断涌现新的CAD事情取得更好的结果。
在1995年，大多数FPGA研究者都认为这项事情也只不过是又一个取得了10%性能提升的成果，和其他研究并无二致。只有很少的人认识到，这项成果带来的是改变全体游戏规则的根本性创新，它将在今后的几十年里经受住其他事情的寻衅，而且不会被其他布线算法所超越。幸运的是，在随后的几年里，学术界和工业界都逐渐认识到，这项成果所提出的理念已经达到了前所未有的高度。
这项事情首先阐述了协商的基本思想，以及处理一阶拥塞的方法。然后剖析了二阶拥塞，见下图，并引入了对“历史本钱（history cost）”的需求。之后将这个观点进行了推广，并将布线延时引入考量。末了给出了这个算法的伪代码，以及一些实验结果。比较于当时的其他商用工具，这个方法能取得11%的效果提升。
客不雅观的说，只管这是一项出色的事情，但它在表述时的清晰程度并非完美。当你每次核阅这项事情时，都能体会出一些细微的差别。
时至今日，我们已经能够广泛而成功的利用协商拥堵算法来处理FPGA的布线问题了。只管如此，这个方法为何如此有效，学术界在理论层面上仍旧莫衷一是。例如，我们能完备理解和剖析退火算法是如何事情和收敛的，但对付协商拥堵算法的理解还远远达不到这个层次。也便是说，人们还没有对这个思想构建起足够严谨的理论体系。因此，这项事情仍将连续引发研究者们对这一课题的进一步研究。
02
FPGA布线架构：分段与缓冲及其对速率和逻辑密度的优化
一句话总结：对VPR工具的超过式优化，从而直接影响高端商业FPGA的成形和发展。
英文名：FPGA Routing Architecture: Segmentation and Buffering to Optimize Speed and Density
作者：Vaughn Betz, Jonathan Rose
揭橥韶光：1999年
推介人：Carl Ebeling（华盛顿大学）
Vaughn Betz（现任多伦多大学教授）
这项事情在VPR中加入了对时序优先布线算法的支持，并对延时进行了精确估计。这使得VPR可以对FPGA互联网络构造进行更加深入的研究。常日来说，FPGA上90%的面积都是用来进行可编程布线的，而关键路径延时里有80%都是布线延时。因此，如何构建精确的FPGA互联网络，对付性能和资源花费来说都是至关主要的。随着FPGA面积的不断增加，这一点更为明显，由于根据Rent法则，电路中导线数量的增长必须快于逻辑单元数量的增长。
然而，架构师常常习气于根据直觉和以往的履历做出决策，而不是根据基准测试和理论剖析。CAD工具常日针对单一架构进行优化，因此如果架构进行了变更，工具的性能和有效性就会不可避免的低落。此外，如果要量化互联对性能的影响，就须要有基于时序驱动的综合、布局和布线算法。
这项事情在VPR中引入了一种用来精确估计延时的Elmore模型，并阐述了一种利用VPR对FPGA布线架构进行剖析和评估的方法。这使得FPGA架构师可以通过一种架构描述措辞（architecture description language），对FPGA架构进行建模和剖析，然后工具就可以自动对这种架构进行适配。
这项成果首先假设了一个传统的岛型FPGA架构，然后考试测验利用最优的方法对连线进行分段，并将这些分段连接起来。通过利用VPR，可以自动对大部分的参数空间进行探索，从而得到对付给定的参数的最优布线结果。
这项成果最大的贡献在于它所利用的方法论和工具。仅仅在几年之后，Altera在构建Stratix架构时就采取了相似的设计方法，以及基于VPR的工具包。这进一步表明，创新既须要跳出固有的思维模式，也要利用前辈的工具来评估这些新的想法，两者缺一不可。
03 从高层描述自动天生FPGA布线架构
一句话总结：通过自动处理FPGA布线架构研究中繁琐的部分，推进了全体研究领域的超过式发展。
英文名：Automatic Generation of FPGA Routing Architectures from High-Level Descriptions
作者：Vaughn Betz, Jonathan Rose
揭橥韶光：2000年
推介人：Scott Hauck（华盛顿大学）
FPGA的架构研究是非常繁芜的，有的时候纵然是为了回答最大略的问题，都须要付出相称程度的努力。在很多情形下，FPGA架构师会认为他们的一些新想法，诸如更大的逻辑块、新型的进位链等等，理应会极大的提升系统的功耗、性能、面积、稳定性等指标。然而，为了证明这些想法的可行性，就须要设计工具和实际运用来对这些想法进行验证。同时，也须要结合很多和这些想法无关的FPGA架构细节，以组成一个完全的系统。在工具层面，大名鼎鼎的Pathfinder和VPR的涌现，已经为大多数逻辑映射事情供应了一个稳定而高效的后端平台。
然而，对付FPGA互联架构来说，仍旧有着很多细节问题须要把稳。例如，连线长度、互联方法、逻辑块构造，等等。这些问题每每与希望研究的紧张问题无关，但都是必须统筹考虑的问题。只管单引导线（unidirectional wires）大概是个好的想法，但如果我们将其用于所有的互联节点，那么面积和容抗的增加将迅速粉饰这个想法带来的优点和好处。那么，如果我们只将其用于50%的互联节点，然后将所有的逻辑块输出连接到奇数号导线、将所有逻辑块输入连接到偶数号导线呢？如果我们又想到了其他的互联架构和办法呢？在这项成果面世之前，这些问题都是无法求解的。
因此，办理这类问题的重点，是这项成果所展示的架构描述措辞，以及VPR中的架构天生器。大略来说，这项成果专注于处理那些布线架构中没人关心、但却非常主要的细节问题，比如：逻辑块是如何连接的？如何担保连线之间的交互不会对系统产生不愿定影响？交流架构是如何组织排列的？当设计中存在长导线时，如何担保这条穿过芯片多个区域的连线以合理的办法进行分段？……等等等等。而这项成果便是用来办理这些在FPGA架构研究中的细微问题。
正是如此，只管这项事情并没有专注于架构研究的重点和盛行的部分，但它极大的帮助了这个领域向前推进了一大步。通过供应更加高效的工具，这项事情使研究职员更有生产力，从而在其余一个角度帮助FPGA架构研究带来了大量创新。
04 时序驱动的FPGA布局算法
一句话总结：当代FPGA CAD工具中的核心布局与时序优化算法。
英文名：Timing-driven placement for FPGAs
作者：Alexander (Sandy) Marquardt, Vaughn Betz, Jonathan Rose
揭橥韶光：2000年
推介人：Jason Cong（加州大学洛杉矶分校）
Jonathan Rose（现任多伦多大学教授）
众所周知，VPR是FPGA学术界最盛行的开源CAD软件，险些每个新的FPGA架构研究都利用了VPR。而这项成果就详细阐述了在VPR中利用的时序驱动的布局算法。在这项成果中先容的T-VPlace算法，除了广受好评和广泛利用之外，它还对FPGA的布局算法有着三个主要的贡献。
第一，在T-VPlace算法中，时序优化的过程是通过最小化延时与导线长度的加权和实现的。这个打算过程通过一个基于仿照退火（simulated annealing）的优化引擎完成。个中，每个节点的权值是该节点时序临界性的多项式函数。这项事情的结果表明，这种权值函数能够得到很好的时序收敛。此外，导线长度和时序都可以根据前一次的迭代进行自主归一化，这使得算法有着很好的稳定性。
第二，这项事情表明，每个节点的时序裕量（timing slack）不须要随着逻辑单元的移动而不断更新。只须要在对每个温度进行的迭代完成之后，再进行精确的基于路径的时序剖析即可。利用未更新的时序裕量常日并不会对时序优化造成影响，反而会大幅提升T-VPlace算法的性能和效率。不过，后来的事情也表明，在高度流水线化的设计中，如果利用未更新的时序裕量会对性能造成负面影响。
第三，在一个给定的分段可编程互联架构中，在源-汇节点间的延时不能大略的通过其曼哈顿间隔来估计。然而，如果在布局期间利用一个布线器来打算每个源-汇节点之间的延时也是非常不现实的。因此，通过利用FPGA架构中的对称性，T-VPlace算法利用了一个预先打算的延时查找表，根据水平和垂直方向的间隔作为索引，从而实现对延时的快速查找。
通过以上三种技能，使得T-VPlace可以高效的产生高质量的时序优化结果。事实上，前两种技能同样可以被运用于集成电路设计中的标准单元布局。可以说，T-VPlace算法是当代FPGA布局布线算法的基石。作者所在的RightTrack公司在2000年被Altera收购后，T-VPlace及其优化技能就被整合进Altera的Quartus设计软件中，并被天下上成千上万的FPGA设计者所利用至今。
05
在商用打算机上的高质量、确定性的FPGA并行布局算法
一句话总结：利用多核处理器显著降落FPGA项目编译韶光的标志性事情
英文名：High-Quality, Deterministic Parallel Placement for FPGAs on Commodity Hardware
作者：Adrian Ludwin, Vaughn Betz, Ketan Padalia
揭橥韶光：2008年
推介人：Jonathan Rose
FPGA业界当前面临的最关键的问题之一是设计工具编译的韶光过长，这一方面是由于打算机处理器的性能并没有质的飞跃，其余一方面是由于FPGA的大小随着半导系统编制造工艺的发展而不断增加。为了应对这个问题，一个有效的方法是利用多个处理器核心进行并行编译。
这项成果旨在应对FPGA CAD流程中最慢的部分之一，即布局的并行化问题。在这个事情中，采取了几项非常独特而主要的方法。例如，这是目前首个，也是唯一一个考试测验对工业级布局软件进行并行化的事情，并终极将成果转化为成功的商用软件。在此之前，只管有很多事情试图对布局算法做并行化处理，它们实在都是基于学术版本的算法，也便是说，这些事情并不须要应对海量的器件数据库、繁芜的时序剖析、以及在商业版软件中会碰着的各种细节问题。
此外，这项工为难刁难算法的确定性（determinism）做了主要阐述。算法的确定性指，不管利用多少个处理器运行算法，它的结果都会是完备相同的。只管在学术界中存在争议，但在商业软件中确定性对付复现结果以及调试都是不可或缺的。这项成果表明，须要做一系列细致的事情以担保算法的确定性。此外，这项成果也证明了这些工为难刁难性能的丢失很小。
这个事情还就内存架构对并行算法性能的影响进行了深入剖析。值得把稳的是，它表明不同的内存构造对算法性能的影响很大。
总体来说，这项成果对算法性能取得了很大的提升：在布局阶段，利用4个处理器内核可以得到2.2倍的性能提升。对付大型设计，这样的性能提升会节省好几个小时的运行韶光。在一个完全的FPGA编译流程中，还存在着很多耗时的阶段，这也意味着须要做更多的事情，才能终极将FPGA项目的编译韶光进一步缩短。但是，这个成果为实现这一目标做出了巨大的贡献，也是其他后续事情值得参考的典范。
结语
这五个FPGA布局布线算法领域的主要事情，有的奠定了险些所有当代商用FPGA的布线算法根本，有的大幅改进了FPGA布局、布线、时序优化等环节的算法性能，有的则对FPGA CAD软件进行了超过式提升。更主要的是，这些事情所采取的方法论、思维办法、前瞻性与实用性的统一、以及严谨的治学态度，都为之后的学术和工业研究树立了最高的典范。
（注：本文仅代表作者个人不雅观点，与任职单位无关。）
往期精选
FPGA 20年最有影响力的25个研究成果 – 系统架构篇
FPGA 20年最有影响力的25个研究成果 – 微架构篇
