以下五个FPGA布局布线算法领域的重要工作几乎奠定了现代算法的基础.docx

《以下五个FPGA布局布线算法领域的重要工作几乎奠定了现代算法的基础.docx》由会员分享，可在线阅读，更多相关《以下五个FPGA布局布线算法领域的重要工作几乎奠定了现代算法的基础.docx（8页珍藏版）》请在第一文库网上搜索。

1、以下五个FPGA布局布线算法领域的重要工作几乎奠定了现代算法的基础很多世界顶尖的“建筑师”可能是你从未听说过的人，他们设计并创造出了很多你可能从未见过的神奇结构，比如在皿内部的复杂体系。制造芯片的基本材料源于沙子，但芯片本身已经成为人们当代生活不可或缺的东西。如果你使用手机、电脑,或者通过互联网收发信息，那么你就无时无刻不在受益于这些建筑师们的伟大工作。FPGA是芯片的其中一种，从上世纪八十年代诞生起，FPGA己经从简单的可编程门阵列,发展成为了有着大量可编程逻辑的复杂片上系统。除了硬件结构之外，FPGA的开发工具和应用场景也都取得了长足的进步和扩展，FPGA在整个生身隹行业的重要性也在不断增

2、强。FPGA芯片的演进，离不开这些“建筑师”的不断发明创造。几年前，这些FPGA的顶级建筑师们选出了自上世纪九十年代起的20年以来FPGA领域最有影响力的25个研究成果。通过这些重要的成果，我们会理解FPGA是如何发展至今，并且知道FPGA技术未来将会发展向何处。这25个研究成果按研究领域分为架构、EDA工具、电路、应用等大类，每项成果都由一名该领域的顶级学者做推介。接下来，我将在几篇文章里，分别介绍这这些改变了FPGA发展进程的重要研究成果。本文是布局布线算法篇。关于FPGA架构领域的重要创新，请参见这两篇：系统架构篇和微架构篇。01寻路者：基于协商的FPGA性能优化布线算法一句话总结：历史

3、最强FPGA布线算法，没有之一。英文名：Pathfinder：ANegotiation-BasedPerformance-DrivenRouterforFPGAs1arryMcMurchie,Car1Ebe1ing发表时间：1995年推介人：SinanKaptanog1u(Microsemi公司)这项工作可以算是过去二十年中影响FPGA技术发展的最重要的成果之一。这项成果对工界和学术界都产生了极其深远的影响。最重要的是，这个工作将FPGA的布线研究，从一个结果波动极大的问题，转化为一个能够很好控制的优化问题。时至今日，几乎所有的FPGA匚商都在使用这项工作提出的协商拥塞(NegOtiatedC

4、ongestion)的布线算法，或者是由这个算法引申出来的其他布线方法。此外，学术界最为广泛使用的FPGA架构设计和分析工具VPR,就是基于这项成果而开发的。通常来说，有些研究成果会立刻对学术界带来启发，而有些则会首先被低估一段时间，然后才会被人们完全理解。这项成果就属于后者。很多研究FPGA设计工具的工作都是提出一些新的想法，使用基准测试对这些想法进行实验，然后比当时的其他工作取得5%到10%的提升，诸如此类。并不是说这些工作不够优秀，但大多数的工作所取得的成就和影响都是暂时的，因为会不断出现新的CAD工作取得更好的结果。在1995年，大多数FPGA研究者都认为这项工作也只不过是又一个取得了

5、10%性能提升的成果，和其他研究并无二致。只有很少的人认识到，这项成果带来的是改变整个游戏规则的根本性创新，它将在今后的几十年里经受住其他工作的挑战，而且不会被其他布线算法所超越。幸运的是，在随后的几年里，学术界和工业界都渐渐认识到，这项成果所提出的理念已经达到了前所未有的高度。这项工作首先阐述了协商的基本思想，以及处理一阶拥塞的方法。然后分析了二阶拥塞，见下图，并引入了对“历史成本(historycost)”的需求。之后将这个概念进行了推广，并将布线延时引入考量。最后给出了这个算法的伪代码，以及一些实验结果。相比于当时的其他商用工具，这个方法能取得IK的效果提升。Figure2.Second

6、Order-esvior；客观的说，尽管这是一项出色的工作，但它在表述时的清晰程度并非完美。当你每次审视这项工作时，都能体会出一些细微的差别。时至今日，我们已经能够广泛而成功的使用协商拥堵算法来处理FPGA的布线问题了。尽管如此，这个方法为何如此有效，学术界在理论层面上仍然莫衷一是。例如，我们能完全理解和分析退火算法是如何工作和收敛的，但对于协商拥堵算法的理解还远远达不到这个层次。也就是说，人们还没有对这个思想构建起足够严谨的理论体系。因此，这项工作仍将继续激发研究者们对这一课题的进一步研究。02FPGA布线架构：分段与缓冲及其对速度和逻辑密度的优化一句话总结：对VPR工具的跨越式优化，从而直

7、接影响高端商业FPGA的成形和发展。英文名：FPGARoutingArchitecture：SegmentationandBufferingtoOptimizeSpeedandDensityVaughnBetz,JonathanRose发表时间：1999年推介人：Car1Ebe1ing(华盛顿大学)这项工作在VPR中加入了对时序优先布线算法的支持，并对延时进行了精确估计。这使得VPR可以对FPGA互联网络结构进行更加深入的研究。通常来说，FPGA上90%的面积都是用来进行可编程布线的，而关键路径延时里有80%都是布线延时。因此，如何构建正确的FPGA互联网络，对于性能和资源消耗来说都是至关重要

8、的。随着FPGA面积的不断增加，这一点更为明显，因为根据Rent法则，电路中导线数量的增长必须快于逻辑单元数量的增长。然而，架构师经常习惯于根据直觉和以往的经验做出决策，而不是根据基准测试和理论分析。CAD工具通常针对单一架构进行优化，因此如果架构进行了变更，工具的性能和有效性就会不可避免的下降。此外，如果要量化互联对性能的影响，就需要有基于时序驱动的综合、布局和布线算法。这项工作在VPR中引入了一种用来精确估计延时的E1more模型，并阐述了一种使用VPR对FPGA布线架构进行分析和评估的方法。这使得FPGA架构师可以通过一种架构描述语言(architecturedescription1an

9、guage),对FPGA架构进行建模和分析，然后工具就可以自动对这种架构进行适配。Circuit这项成果首先假设了一个传统的岛型FPGA架构，然后尝试使用最优的方法对连线进行分段，并将这些分段连接起来。通过使用VPR,可以自动对大部分的参数空间进行探索，从而得到对于给定的参数的最优布线结果。这项成果最大的贡献在于它所使用的方法论和工具。仅仅在几年之后，A11era在构建Stratix架构时就采用了相似的设计方法，以及基于VPR的工具包。这进一步表明，创新既需要跳出固有的思维模式，也要使用先进的工具来评估这些新的想法，两者缺一不可。03从高层描述自动生成FPGA布线架构一句话总结：通过自动处理F

10、PGA布线架构研究中繁琐的部分，推进了整个研究领域的跨越式发展。英文名：AutomaticGenerationofFPGARoutingArchitecturesfromHigh-1eve1DescriptionsVaughnBetz,JonathanRose发表时间：2000年推介人：ScottHauck(华盛顿大学)FPGA的架构研究是非常复杂的，有的时候即使是为了回答最简单的问题，都需要付出相当程度的努力。在很多情况下，FPGA架构师会认为他们的一些新想法，诸如更大的逻辑块、新型的进位链等等，理应会极大的提升系统的功耗、性能、面积、稳定性等指标。然而，为了证明这些想法的可行性，就需要设计

11、工具和实际应用来对这些想法进行验证。同时，也需要结合很多和这些想法无关的FPGA架构细节，以组成一个完整的系统。在工具层面，大名鼎鼎的Pathfinder和VPR的出现，已经为大多数逻辑映射工作提供了一个稳定而高效的后端平台。Connectionb1ockProgrammab1econnection/switchProgrammaMeroutingswitchwiresegment.wiresegmentSwitch抚Nk然而，对于FPGA互联架构来说，仍然有着很多细节问题需要注意。例如，连线长度、互联方法、逻辑块结构，等等。这些问题往往与希望研究的主要问题无关，但都是必须统筹考虑的问题。尽管

12、单向导线(UnidireCtiona1wires)也许是个好的想法，但如果我们将其用于所有的互联节点，那么面积和容抗的增加将迅速掩盖这个想法带来的优点和好处。那么，如果我们只将其用于50%的互联节点，然后将所有的逻辑块输出连接到奇数号导线、将所有逻辑块输入连接到偶数号导线呢？如果我们又想到了其他的互联架构和方式呢？在这项成果面世之前，这些问题都是无法求解的。因此，解决这类问题的重点，是这项成果所展示的架构描述语言，以及VPR中的架构生成器。简单来说，这项成果专注于处理那些布线架构中没人关心、但却非常重要的细节问题，比如：逻辑块是如何连接的？如何保证连线之间的交互不会对系统产生不确定影响？交换架

13、构是如何组织排列的？当设计中存在长导线时，如何保证这条穿过芯片多个区域的连线以合理的方式进行分段？等等等等。而这项成果就是用来解决这些在FPGA架构研究中的细微问题。正是如此，尽管这项工作并没有专注于架构研究的重点和流行的部分，但它极大的帮助了这个领域向前推进了一大步。通过提供更加高效的工具，这项工作使研究人员更有生产力，从而在另外一个角度帮助FPGA架构研究带来了大量创新。04时序驱动的FPGA布局算法一句话总结：现代FPGACAD工具中的核心布局与时序优化算法。英文名：Timing-drivenp1acementforFPGAsA1exander(Sandy)Marquardt,Vaugh

14、nBetz,JonathanRose发表时间：2000年推介人：JaSonCong(加州大学洛杉矶分校)众所周知，VPR是FPGA学术界最流行的开源CAD软件，几乎每个新的FPGA架构研究都使用了VPR0而这项成果就详细阐述了在VPR中使用的时序驱动的布局算法。在这项成果中介绍的T-VP1ace算法，除了广受好评和广泛使用之外，它还对FPGA的布局算法有着三个重要的贡献。第一，在T-VP1ace算法中，时序优化的过程是通过最小化延时与导线长度的加权和实现的。这个计算过程通过一个基于模拟退火(辿UIatedannea1ing)的优化引擎完成。其中，每个节点的权值是该节点时序临界性的多项式函数。这

15、项工作的结果表明，这种权值函数能够得到很好的时序收敛。此外，导线长度和时序都可以根据前一次的迭代进行自主归一化，这使得算法有着很好的稳定性。第二，这项工作表明，每个节点的时序裕量(timings1ack)不需要随着逻辑单元的移动而不断更新。只需要在对每个温度进行的迭代完成之后，再进行精确的基于路径的时序分析即可。使用未更新的时序裕量通常并不会对时序优化造成影响，反而会大幅提升TTP1aCe算法的性能和效率。不过，后来的工作也表明，在高度流水线化的设计中，如果使用未更新的时序裕量会对性能造成负面影响。第三，在一个给定的分段可编程互联架构中，在源-汇节点间的延时不能简单的通过其曼哈顿距离来估计。然

16、而，如果在布局期间使用一个布线器来计算每个源-汇节点之间的延时也是非常不现实的。因此，通过利用FPGA架构中的对称性，TTP1ace算法使用了一个预先计算的延时查找表，根据水平和垂直方向的距离作为索引，从而实现对延时的快速查找。通过以上三种技术，使得T-VP1ace可以高效的产生高质量的时序优化结果。事实上，前两种技术同样可以被应用于集成虫壁设计中的标准单元布局。可以说，T-VP1ace算法是现代FPGA布局布线算法的基石。作者所在的RightTrack公司在2000年被A1tera收购后，T-VP1ace及其优化技术就被整合进A1tera的QUartUS设计软件中，并被世界上成千上万的FPGA设计者所使用至今。05在商用计算机上的高质量、确定性的FPGA并行布局算法一句话总结：利用多核处蹴