jmsjjyl@com 许多世界顶级“建筑师”是你可能从未听说过的人。他们设计并创造了许多前所未见的神奇结构，包括芯片内的复杂系统。木片的基本原料是沙子，木片本身已经成为现代人生活中必不可少的一部分。每当您使用手机或电脑，或通过互联网发送和接收信息时，您总是可以从这些建筑师的伟大作品中受益。
自20 世纪80 年代诞生以来，FPGA 已经从简单的可编程门阵列发展到具有大量可编程逻辑的复杂片上系统。不仅是硬件结构，FPGA开发工具和应用场景也显着进步和扩展，增加了FPGA在整个半导体行业中的重要性。 FPGA芯片的演进离不开这些“架构师”的不断发明创造。
几年前，这些顶级FPGA 架构师评选出了从20 世纪90 年代开始的过去20 年来FPGA 领域最具影响力的25 个研究成果。通过这些重要结果，您可以了解FPGA 如何随时间演变，并了解FPGA 技术未来将向何处发展。
这25项研究成果根据其研究领域分为架构、EDA工具、电路和应用等主要类别，每项工作均由该领域的领先专家推荐。接下来，我们将分几个部分介绍这些改变FPGA开发流程的重要研究成果。本文介绍布局布线算法。有关FPGA 架构的重要创新，请参阅两篇文章：《系统架构篇》 和《微架构篇》。
01
Pathfinder：用于FPGA 性能优化的基于协商的路由算法
一句话总结：有史以来最强大的FPGA 路由算法。
英文名称：Pathfinder: 用于FPGA的基于协商的性能驱动路由器
作者：拉里·麦克默奇、卡尔·埃贝林
推荐人：Sinan Kaptanoglu（美高森美公司）
Karl Ebeling（现任华盛顿大学教授）
这项工作可以被认为是过去二十年来影响FPGA技术发展的最重要成就之一。这一结果对工业界和学术界都产生了重大影响。最重要的是，这项工作将FPGA 互连的研究从结果高度可变的问题转变为可以很好控制的优化问题。目前，几乎所有的FPGA制造商都使用本研究提出的协商拥塞路由算法或由该算法衍生的其他路由技术。此外，学术界使用最广泛的FPGA架构设计和分析工具VPR就是基于这项工作开发的。
一般来说，一些研究成果对学术界有直接影响，而另一些研究成果在被充分理解之前一段时间内仍然没有得到充分重视。这个结果属于后一类。使用FPGA 设计工具的大部分工作涉及提出新想法、使用基准测试对其进行实验，并与当时的其他工作相比实现5% 到10% 的改进。我并不是说这些工作不够好，但大多数工作的结果和影响都是暂时的，因为效果更好的新CAD 工作将不断出现。
1995年，大多数FPGA研究人员认为这项工作只是额外增加了10%的性能提升，与其他工作没有什么不同。很少有人意识到这一结果是一项根本性的突破性创新，它将经受住其他工作的挑战，并且在未来几十年内不会被其他路由算法超越。幸运的是，在接下来的几年里，学术界和工业界都逐渐意识到这项工作提出的想法正在达到前所未有的高度。
本书首先解释了协商的基本概念以及如何处理一阶拥塞。接下来我们分析二次拥堵，引入“历史成本”的必要性，如下图所示。后来，这个想法被推广到包括布线延迟。最后，我们给出了该算法的伪代码和一些实验结果。与当时的其他商业工具相比，该方法实现了11% 的性能提升。
客观来说，这是一部优秀的作品，但表达的清晰度并不完美。每次看到这个作品，都会有细微的差别。
协商拥塞算法现已广泛用于成功解决FPGA 路由问题。尽管如此，对于这种方法为何如此有效，学者们在理论层面仍存在分歧。例如，虽然我们可以充分理解和分析退火算法如何工作和收敛，但我们对协商拥塞算法的理解还远远没有达到这个水平。也就是说，人们还没有为这个想法建立起足够严谨的理论体系。因此，本研究将继续鼓励研究人员进一步研究这一课题。
02
FPGA 路由架构：分段和缓冲及其速度和逻辑密度的优化
总之，VPR工具的突破性优化直接影响高端商用FPGA的形成和发展。
英文名称：FPGA Routing Architecture: 分段和缓冲以优化速度和密度
作者：沃恩·贝茨、乔纳森·罗斯
推荐人：Carl Ebeling（华盛顿大学）
Vaughn Betts（现任多伦多大学教授）
这项工作为VPR 增加了对时序优先路由算法的支持，从而可以准确估计延迟。这使得VPR 能够对FPGA 互连结构进行更详细的研究。通常，FPGA上90%的面积用于可编程布线，80%的关键路径延迟是布线延迟。因此，如何构建合适的FPGA互连网络对于性能和资源消耗都很重要。随着FPGA 面积的不断增加，这一点变得更加明显，因为根据四旬斋定律，电路中的导线数量必须比逻辑单元的数量增长得更快。
然而，架构师通常习惯于根据直觉和过去的经验而不是基准测试或理论分析来做出决策。 CAD 工具通常针对单一架构进行优化，因此架构的更改不可避免地会降低工具的性能和有效性。此外，如果您想量化互连的性能影响，则需要时序驱动的综合、布局布线算法。
本研究将Elmore 模型引入VPR 中以进行准确的延迟估计，并展示了如何使用VPR 来分析和评估FPGA 路由架构。这使得FPGA架构师可以通过架构描述语言对FPGA架构进行建模和分析，并且工具可以自动适应该架构。
在本研究中，我们首先假设传统的孤岛FPGA 架构，然后尝试使用最佳方法对电线进行分段并连接这些分段。 VPR 自动探索大部分参数空间，并为指定参数提供最佳路由结果。
这项研究最大的贡献在于所使用的方法和工具。仅仅几年后，Altera 在构建Stratix 架构时使用了类似的设计方法和基于VPR 的工具包。这进一步表明，创新既需要跳出框框思考，又需要使用先进的工具来评估新想法。
03
根据高级描述自动生成FPGA 布线架构
一句话总结：将FPGA 路由架构研究中繁琐的部分自动化将极大地推进整个研究领域的发展。
英文名称：从高层描述自动生成FPGA布线架构
作者：沃恩·贝茨、乔纳森·罗斯
推荐人：Scott Hauck（华盛顿大学）
研究FPGA 架构非常复杂，即使回答最简单的问题也需要付出相当大的努力。 FPGA 架构师通常认为更大的逻辑块、新的进位链等新想法应该会显着提高系统功耗、性能、面积、稳定性和其他指标。然而，证明这些想法的可行性需要工具和现实世界的应用来验证这些想法。同时，许多与这些思想无关的FPGA架构细节必须组合起来才能形成一个完整的系统。在工具层面，流行的Pathfinder和VPR的出现为大多数逻辑映射任务提供了稳定高效的后端平台。
然而，关于FPGA 互连架构仍有许多细节需要注意。例如，布线长度、布线方法、逻辑块结构等。这些问题往往与你要研究的主要问题无关，但都是需要整体考虑的问题。单向导线可能是一个好主意，但由于面积和电容的增加，在每个互连节点使用单向导线很快就会掩盖该想法的优点和好处。那么，如果我们仅将其用于50% 的互连节点，并将所有逻辑块的输出连接到奇数编号的电线，并将所有逻辑块的输入连接到偶数编号的电线，会发生什么？如果我们考虑互连架构和方法会怎样？在这部作品出版之前，这些问题仍然没有得到解决。
因此，解决此类问题的重点是本研究中演示的架构描述语言和VPR架构生成器。简而言之，这项工作的重点是处理没人关心但非常重要的布线架构细节：逻辑块如何连接。我们如何确保连接之间的相互作用不会对系统产生不可靠的影响？ 交换结构是如何配置的？ 如果设计中有长电线，如何确保穿过该区域的电线被分段？适当的方式？这项工作将用于解决FPGA架构研究中的这些敏感问题。
因此，虽然这项研究并不关注建筑研究的重要或一般部分，但它将极大地帮助这个领域向前迈出一大步。这项工作将通过提供更高效的工具来帮助提高研究人员的生产力，从而从不同的角度为FPGA 架构研究带来更多创新。
04
时序驱动的FPGA 布局算法
一句话概括：现代FPGA CAD 工具中的核心布局和时序优化算法。
英文名称：FPGA时序驱动布局
作者：亚历山大（桑迪）马夸特、沃恩·贝茨、乔纳森·罗斯
推荐人：Jason Cong（加州大学洛杉矶分校）
乔纳森·罗斯（Jonathan Rose，现任多伦多大学教授）
众所周知，VPR是FPGA学术界最流行的开源CAD软件，几乎所有新的FPGA架构研究都使用VPR。这项工作详细介绍了VPR 中使用的时序驱动布局算法。除了流行和广泛使用之外，本工作中引入的T-VPlace 算法对FPGA 布局算法做出了三个重要贡献。
首先，T-VPlace算法通过最小化延迟和线长的加权和来实现时序优化过程。这个计算过程是由基于模拟退火的优化引擎完成的。其中，每个节点的权重是节点时序关键性的多项式函数。研究结果表明该加权函数能够实现良好的时序收敛。此外，线长和时序都可以根据之前的迭代自动归一化，使得算法非常稳定。
其次，这项工作表明，随着逻辑单元的移动，不需要不断更新每个节点的时序裕量。每次温度迭代完成后，只需执行准确的基于路径的时序分析即可。使用未更新的时序裕量一般不会影响时序优化，但会显着提高T-VPlace算法的性能和效率。然而，后续研究还发现，在高度流水线设计中，使用未更新的时序裕量会对性能产生负面影响。
第三，在某些分段可编程互连架构中，源/宿节点之间的延迟不能仅通过曼哈顿距离来估计。然而，在布局期间使用路由器来计算每个源/宿节点之间的延迟是不切实际的。因此，通过利用FPGA 架构的对称性，T-VPlace 算法可以使用按水平和垂直距离索引的预先计算的延迟查找表来快速查找延迟。
T-VPlace利用上述三种技术可以高效地生成高质量的时序优化结果。事实上，前两种技术也可以应用于集成电路设计中的标准单元布局。 T-VPlace 算法是现代FPGA 布局布线算法的基础。 2000年笔者所在的公司RightTrack被Altera收购后，T-VPlace及其优化技术被集成到Altera的Quartus设计软件中，至今仍被全球数千名FPGA设计人员所使用。
05
通用计算机上的高质量、确定性FPGA 并行放置算法
一句话概括：一项突破，大大缩短了使用多核处理器的FPGA 项目的编译时间
英文名称：High-Quality,Deterministic Parallel Placement for FPGAs on Commodity Hardware
作者：阿德里安·路德温、沃恩·贝茨、凯坦·帕达利亚
推荐人：乔纳森·罗斯
目前FPGA行业面临的最显着的问题之一是设计工具的编译时间过长。这是因为，一方面，计算机处理器的性能并没有质的提升。这是因为随着半导体制造工艺的发展，FPGA 的尺寸不断增大。使用多处理器核的并行编译是解决这个问题的有效方法。
这项工作旨在解决布局并行化问题，这是FPGA CAD 流程中最慢的部分之一。这项工作使用了几种非常独特且重要的方法。例如，这是第一个也是唯一一个并行化工业级布局软件并最终将结果转化为成功的商业软件的尝试。在此之前，已经有很多工作尝试并行化布局算法，但它们实际上是基于算法的学术版本。这意味着这些研究不必处理大型设备数据库、复杂的时序分析或商业应用。版本软件遇到的各种详细问题。
此外，这项研究还提供了有关算法确定性的重要细节。算法的确定性是指无论使用多少个处理器来执行该算法，其结果都将完全相同。尽管在学术界存在争议，但确定性在商业软件中对于再现和调试结果至关重要。这一结果表明必须采取一系列仔细的预防措施来确保算法的确定性。此外，这项研究表明这些努力几乎不会导致性能下降。
这项研究还详细分析了内存架构对并行算法性能的影响。特别是，我们表明内存结构的差异对算法性能有显着影响。
总体而言，这一结果显着提高了算法的性能。在布局阶段，使用四个处理器核心可实现2.2 倍的性能提升。对于大型设计，这种性能改进可以节省数小时的运行时间。完整的FPGA编译过程仍然存在许多耗时的阶段，这也意味着需要做更多的工作来进一步缩短最终的FPGA项目编译时间。不过，这一结果对于实现这一目标有很大贡献，也是后续其他研究值得参考的典范。
结论
这五篇在FPGA布局和布线算法领域的重要工作，有的为几乎所有现代商用FPGA布线算法奠定了基础，有的则改变了FPGA布局、布线、时序优化等方面，显着提高了算法性能。有些改进了FPGA CAD。该软件已得到显着改进。更重要的是，这些研究所采取的方法论、思维方式、视野与实践的统一以及严谨的学术态度，为后续学术和产业研究树立了最好的典范。
