许多国际顶尖的“建筑师”或许是你从未听说过的人，他们规划并发明出了许多你或许从未见过的奇特结构，比方在芯片内部的杂乱体系。制作芯片的根本资料源于沙子，但芯片自身现已成为人们今世日子不可或缺的东西。假如你运用手机、电脑，或许经过互联网收发信息，那么你就无时无刻不在获益于这些建筑师们的巨大作业。
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 软件进行了跨越式提高。更重要的是，这些作业所选用的办法论、思想办法、前瞻性与实用性的一致、以及谨慎的治学情绪，都为之后的学术和工业研讨树立了最高的模范。
