237
很多世界顶尖的“建筑师”可能是你从未听说过的人，他们设计并创造出了很多你可能从未见过的神奇结构，比如在芯片内部的复杂体系。制造芯片的基本材料源于沙子，但芯片本身已经成为人们当代生活不可或缺的东西。如果你使用手机、电脑，或者通过互联网收发信息，那么你就无时无刻不在受益于这些建筑师们的伟大工作。
FPGA 是芯片的其中一种，从上世纪八十年代诞生起，FPGA 已经从简单的可编程门阵列，发展成为了有着大量可编程逻辑的复杂片上系统。除了硬件结构之外，FPGA 的开发工具和应用场景也都取得了长足的进步和扩展，FPGA 在整个半导体行业的重要性也在不断增强。FPGA 芯片的演进，离不开这些“建筑师”的不断发明创造。
几年前，这些 FPGA 的顶级建筑师们选出了自上世纪九十年代起的 20 年以来 FPGA 领域最有影响力的 25 个研究成果。通过这些重要的成果，我们会理解 FPGA 是如何发展至今，并且知道 FPGA 技术未来将会发展向何处。
这 25 个研究成果按研究领域分为架构、EDA 工具、电路、应用等大类，每项成果都由一名该领域的顶级学者做推介。接下来，我将在几篇文章里，分别介绍这这些改变了 FPGA 发展进程的重要研究成果。本文是“其他 CAD 算法”篇，主要介绍了 FPGA 映射、包装、功耗优化等算法的突破性进展。
FPGA 领域的架构创新和布局布线算法创新，请参见这几篇文章：《系统架构篇》《微架构篇》《布局布线算法篇》。
01
在基于 LUT 的 FPGA 映射中最小化逻辑深度和面积
英文名：Simultaneous depth and area minimization in LUT- based FPGA mapping
一句话总结：FPGA 逻辑映射算法的基础性工作
作者：Jason Cong, Yean-Yow Hwang
发表时间：1995 年
推介人：Eugene Ding（赛灵思）
Jason Cong（现任 UCLA 教授）
这项成果为 FPGA 逻辑映射算法的发展起到了非常重要的推动作用。在 1994 年，Jason Cong 及团队发表了名为 FlowMap 的映射算法。它是首个有着多项式时间复杂度的映射算法，并且能在理论上对逻辑层数量达到最佳的优化。这个方法的核心思想是将 K 输入 LUT 的映射问题，建模成一个最小高度、K 可行度的割问题（minimum-height, K-feasible cut），而不是像传统方法那样基于局部的簇进行映射。
FlowMap 算法实际上就是在一个保证最小高度的图上计算最小割的问题。虽然这个方法简单而高效，但它有可能会产生并使用小的 LUT，并且会产生大量的逻辑冗余，而这都会造成更高的面积成本。虽然作者随后也提出了一些后处理的方法，以及考虑将非关键路径的高度约束进行适量放宽，但这些方法本质上都属于局部优化，因此并不属于这种基于全局割的理论框架。
在这个工作中，作者提出了 CutMap 算法。相比 FlowMap 算法，这个成果能在多项式时间内完成深度优化（depth-optimal）的映射结果，但使用的 LUT 数量会极大减少。
这项成果有着以下几个关键性的贡献。首先，它使用了成本函数以控制割数的产生。这样，除了最小割之外，算法不仅可以找到所有的可行割，还能在映射过程中考虑次要的优化目标，甚至考虑多个并行的优化目标。第二，CutMap 算法可以全局寻找共享逻辑的可能性、减少顺序依赖，以及将映射质量与逻辑网络的结构更加紧密的联系在一起。最后，它提出了一些剪枝规则，能帮助加速割计算的过程。虽然在今天看来，这里很多的想法和思路是显而易见的，但在当时，这些方法还并没有得到广泛应用。此外，CutMap 方法在实践中表现很好，并成为了后续很多工作用来对比的基础性工作。
基于割的多目标优化方法已经成为逻辑映射领域的标准性工作，而这并不局限在 FPGA 领域。正是这项工作推动了这一突破的不断发展。
02
割的排序和修剪：构建一个通用且高效的 FPGA 映射方法
一句话总结：FPGA 映射算法的再一次跨越式性能提升
英文名：Cut Ranking and Pruning: Enabling a General and Efficient FPGA Mapping Solution
作者：Jason Cong, Chang Wu, Yuzheng Ding
发表时间：1999 年
推介人：Steve Wilton（英属哥伦比亚大学）
这项成果通过割的生成、排序和修剪技术极大的减少了 LUT 映射的复杂度和运行时间，从而提升了 LUT 逻辑映射的可扩展性。
从最早的商用 FPGA 开始，查找表就是大多数器件中实现逻辑功能的主要结构。如何将逻辑功能映射到 LUT 上，一直是 FPGA CAD 工具所致力解决和优化的核心问题。正因为如此，在过去的很多年中，有大量的研究工作都在不断寻找高效的逻辑映射算法。
这项工作发表于 1999 年，在此之前，诸如 FlowMap、Chortle、DFmap 等方法都已经发表了，研究者们也已经知道对 LUT 进行有效的逻辑映射是可行的。对于这项工作来说，它不只是介绍了一种新的算法，更是阐述了一些足够通用的技术原理。这些技术可以用来提高几乎所有逻辑映射算法的核心操作效率。而这也是这项工作最为重要的贡献之一。
例如，这项工作讨论了割生成（cut generation）、割排序（cut ranking）和割修剪（cut pruning）。其中，割生成指的是如何构建一组割，割排序指的是如何对割进行评估和排序，割修剪指的是不重要的割会被丢弃和剪枝。对于大型电路来说，这些任务都有着很高的计算难度，因此亟需高效的算法以应对这些问题。此外，这项工作还展示了如何使用这些技术对以往发表过的映射算法进行改进和性能提升。
综上所述，这项成果已经成为任何 FPGA CAD 算法工程师必须掌握的理论技能，在实际的 FPGA 设计工具中这些技术也已经经过了多次迭代更新。时至今日，逻辑映射仍然是一个活跃的研究领域，这项发表于 1999 年的工作也将会继续影响新的逻辑映射算法的出现和进步。
03
使用基于簇的逻辑块和时序优先的包装算法来提升 FPGA 的速度和逻辑密度
一句话总结：FPGA 簇结构包装算法的奠基之作。
英文名：Using Cluster-Based Logic Blocks and Timing-Driven Packing to Improve FPGA Speed and Density
作者：Alexander (Sandy) Marquardt, Vaughn Betz, Jonathan Rose
发表时间：1999 年
推介人：Steve Wilton（英属哥伦比亚大学）
这项成果首次对基于簇的逻辑块（cluster-based logic blocks）的速度优势进行了量化分析。在 1999 年，在大部分的商用 FPGA 中都已经使用了基于簇的逻辑块，包括 Altera 的 Flex 系列和 Xilinx 的 Virtex 系列等。然而，对于这种体系结构的建模和分析仍然处于起步阶段。在之前的工作中，Vaughn Betz 已经证明基于簇的逻辑块结构可以提升逻辑密度。事实上，正如这项工作中所揭示的，基于簇的逻辑块的真正优势其实是在速度方面。正因此，这项工作开辟了一个全新的研究领域，即为众多包装算法（packing algorithms）搭建了基础框架，并成为了所有 FPGA CAD 流程中的基础性部分。
在这项工作中，作者首先描述了一个 CAD 流程（见下图），以及适用于对这类架构进行分析的方法。然后，作者根据 Vaughn Betz 之前的工作，给出了一个参数化的簇架构，它被用来探究不同的基于簇的逻辑块结构。接下来，他们提出了一个名为 T-VPACK 的算法，这个时序优先的算法负责将 LUT 和寄存器包装到逻辑簇中。通过实验验证，这项工作表明基于簇的逻辑块结构可以显著的提升 FPGA 的速度。此外，最优的簇大小是大约 7 到 10 个逻辑单元。由此之后的很多年，这种簇大小一直都是学术界和工业界的体系结构标准。
这项工作的真正价值在于，它为未来的研究人员开发新的簇包装算法、研究新的簇逻辑结构构建了理论基础。例如，后来的很多工作，包括 RPACK、iRAC、DVPack 和 P-T-VPACK 等都建立在这项成果之上。当前，FPGA 里的簇逻辑结构已经愈发重要。多伦多大学的这个课题组已经将簇逻辑结构的研究进行了极大的扩展，但这些扩展仍然保持着这项成果中提出的很多基本假设、评估方法以及体系结构框架。
04
FPGA 漏电流功耗的优化方法
一句话总结：充分利用 FPGA 特性的无损功耗优化方法。
英文名：Active Leakage Power Optimization for FPGAs
作者：Jason H. Anderson, Farid N. Najm, Tim Tuan
发表时间：2004 年
推介人：Russ Tessier（马萨诸塞大学）
Jason Aderson（现任多伦多大学副教授）
这项成果的主要贡献在于提出了一个简单的方法，可以显著的降低 FPGA 的漏电流功耗。
在 FPGA 的特征尺寸大于 100 纳米时，漏电流功耗通常是可以忽略不计的，FPGA 设计工具也通常不考虑这种功耗的优化。然而随着 FPGA 的特征尺寸降至 100 纳米以下，有越来越多的移动应用领域开始对 FPGA 产生了兴趣。要知道，在 100 纳米以内，总功耗超过 30%甚至更多的部分都是漏电流功耗。但是对于 FPGA 来说，它不能像 ASIC 那样完全关闭器件的某个区域，以实现功耗优化的目的。此外，随着 FPGA 被越来越广泛的使用于数据中心、移动通信等功耗敏感的领域，对 FPGA 功耗的要求也越来越严格。因此，漏电流功耗也随之成为了研究者关注和尝试优化的重要领域。
通常来说，在对特定约束进行优化时，往往需要进行多方面的权衡。例如在一个设计中，为了在一个维度取得良好的结果，一个或更多的其他维度有可能会变得更差。然而，这项成果所介绍的功耗优化技术很好兼顾了多个设计维度。这个方法只需要进行一些轻度的 FPGA 设计预处理，就可以节省高达 25%的静态功耗。除此之外，不需要牺牲额外的电路面积，抑或是损失系统性能。
这项工作基于一个简单但十分有效的概念：如果 CMOS 三极管的栅极为逻辑‘1’时，将漏极和源极也设置为逻辑‘1’，那么它的静态功耗就会降低。这样，如果布线架构将其驱动的信号默认设置为逻辑‘1’，那么互联架构的静态功耗也将大幅降低。由于 FPGA 有着可配置性，在大多数情况下可以对这些信号进行设置，由此就达成了功耗优化。
这项成果的最大贡献之一，在于它所阐述的观点有着极大的通用性和互补性。该技术可以和任何其他的 FPGA 功耗优化方法一起使用，而不会对其他方法产生负面影响。在软件层面，实现该技术所需要的软件也十分简单。毫无疑问，这项成果是充分利用了 FPGA 的灵活可配置性、将简单的思想应用于重要领域的一个典型代表。
结语
这四个 FPGA CAD 算法领域的重要工作，有的成为了现代 FPGA 通用的逻辑映射方法，有的从理论层面对逻辑簇结构及其包装算法进行了深入分析，有的则对 FPGA 的功耗提出了简单而强大的优化方法。更重要的是，这些工作所采用的方法论、思维方式、前瞻性与实用性的统一、以及严谨的治学态度，都为之后的学术和工业研究树立了最高的典范。
下载ECAD模型
