2025/02/24 13:24

联手华为诺亚，南大LAMDA组获EDA顶会DATE 2025最佳论文

国内芯片设计研究团队，刚刚在国际学术顶会上获奖了。

近日，南京大学人工智能学院 LAMDA 组钱超教授团队在 DATE 2025 上发表论文《Timing-Driven Global Placement by Efficient Critical Path Extraction》获得了最佳论文奖。

论文：《Timing-Driven Global Placement by Efficient Critical Path Extraction》
论文链接：https://www.lamda.nju.edu.cn/qianc/DATE_25_TDP_final.pdf
开源：https://github.com/lamda-bbo/Efficient-TDP

本论文第一作者侍昀琦、四作林熙、五作薛轲分别是南京大学人工智能学院的硕士生、本科生和博士生，钱超教授为通讯作者，论文由南京大学与华为诺亚方舟实验室合作完成。

DATE 全称 Design Automation Test in Europe（欧洲设计自动化与测试会议），是 EDA 领域的顶级国际学术会议，由权威机构 IEEE 和 ACM 共同举办，吸引了全球电子设计自动化与测试领域的著名学者、企业界专家参与。

DATE 自 1994 年创办以来已举办 31 届，今年的大会将于 3 月 31 日至 4 月 2 日在法国里昂召开。今年的大会收到了超过 1200 篇投稿，录用率约 25%，共选出了四篇最佳论文奖。

南京大学等完成的针对大规模芯片标准单元的全局布局问题，通过高效的关键路径提取技术，覆盖所有时序（即传播时延约束，是实现芯片功能的关键）违例端点，从而精确建模时序目标，并且在优化时兼顾布线长度、布局密度、时序等多个目标。相较此前业界最先进算法，新方法在关键时序指标 TNS 和 WNS 上分别提升 40.5% 和 8.3%。

审稿人高度评价了该研究，称「结果令人印象非常深刻，超过了所有先进工作」（The results are very impressive, outperforming all state-of-the-art works），并取得了显著提升。

EDA 即电子设计自动化（Electronic Design Automation），是指利用计算机辅助设计（CAD）软件，来完成超大规模集成电路（VLSI）芯片的功能设计、综合、验证、物理设计（包括布局、布线、版图、设计规则检查等）等流程的设计方式。EDA 被誉为「芯片之母」，是电子设计的基石产业。

在超大规模集成设计领域，布局过程至关重要，它是逻辑设计和物理布局之间的桥梁。传统的布局方法虽然侧重于最小化线长和减少布线拥塞，但仅隐式地解决了时序指标，这可能无法满足现代大规模芯片设计的严格时序要求。直接优化时序是必不可少的，但通常需要大量的计算资源和周转时间，人们急需更有效的时序驱动布局方法来缩短设计周期并确保时序收敛。

现代布局算法通常由三个主要阶段组成：全局布局、合法化和详细布局。全局布局将单元分布在目标布局中，平衡线长和密度。然后通过合法化对粗略结果进行细化，并通过详细布局进行微调。在这三个阶段中，全局布局在确定单元的整体分布方面起着至关重要的作用，显著影响最终布局的质量，包括时序。

因此，针对全局布局的时序驱动布局 (TDP) 得到了广泛研究，重点优化关键时序指标，例如总负裕度 (TNS) 和最差负裕度 (WNS)。

这类时序驱动布局（TDP）技术基本上包含三个组成部分：基础布局算法、时序分析以及它们之间的接口。第一个组成部分利用传统的全局布局引擎，主要专注于优化线长和密度之间的权衡。第二个组成部分涉及内部或外部时序引擎，这些引擎评估当前布局以提供关键的时序数据，例如关键路径延迟或引脚裕量。第三个组成部分将时序指标转换为某些权重或约束，以驱动基础布局引擎。根据处理时序信息的方式，TDP 技术大致可以分为两类：基于网络的方法和基于路径的方法。

基于网络的方法使用时序分析动态或静态地调整网络权重或网络约束，间接引导布局关注关键网络。由于传统布局算法主要专注于最小化线长，这本身涉及网络的考虑，因此只需对这些算法进行最小修改即可适应时序驱动的方法。最近，有研究将先进的非线性布局工具 DREAMPlace 升级为其时序驱动版本 4.0。这个新版本动态调整网络权重，利用动量引导机制与时序分析引擎交互，增强了其对时序优化的关注。

基于路径的方法直接处理从时序图中提取的路径，通常将其表述为数学规划问题。这些方法在优化过程中保持对时序的准确视图，因此通常能够确保高质量的结果。然而，随着设计规模的增加，路径数量呈指数增长，这些方法常常面临可扩展性问题。最近又出现了一种全新可微分时序驱动布局框架，可将 GPU 加速的可微分时序引擎集成到 DREAMPlace 中，实现高效的基于路径的分析。这种方法不仅达到了最先进的性能，而且以具有竞争力的速度运行，有效解决了传统的可扩展性挑战。

综上所述，尽管取得了显著进展，时序驱动的布局问题在很大程度上仍未得到解决。基于网络的方法通常面临优化目标间接和时序信息利用不足的问题。对于基于路径的方法，尽管此前的研究在一定程度上解决了可扩展性问题，但他们的方法通过平滑时序指标可能会影响准确性。

南大研究引入了一个时序驱动的全局布局框架，该框架结合了细粒度的引脚到引脚（pin-to-pin）吸引力二次距离损失，直接针对时序指标进行优化。这一框架还配备了一个路径级时序分析模块，能够高效提取关键路径。其主要贡献包括：

开发了一个基于领先布局工具 DREAMPlace 4.0 的 GPU 加速时序驱动布局流程，优化了关键路径上的引脚到引脚吸引力；
引入了一种高效的关键路径提取方法，能够捕捉全面的时序信息，实现高速的时序优化 —— 相比默认的时序分析工具，速度提升了 6 倍；
设计了一种用于引脚到引脚吸引力的二次欧几里得距离损失，该损失与时序指标紧密对齐，显著提升了性能，与其他距离度量相比，TNS（总负时序裕量）和 WNS（最差负时序裕量）分别提升了 50% 和 30%；
在 ICCAD2015 竞赛基准测试套件上的实验结果表明，与 DREAMPlace 4.0 相比，新方法在 TNS（WNS）上实现了约 60%（30%）的提升；与 Guo 和 Lin 的工作相比，TNS（WNS）提升了约 50%（10%）。

算法创新点在哪里？

作者提出的「GPU 加速的时序驱动全局布局框架」在技术上有哪些创新之处呢？我们可以从下图 1 的架构流程洞见一二，一方面引入了细粒度引脚到引脚吸引力目标，并直接瞄准了时序指标；另一方面通过高效的路径提取方案和二次欧几里得距离损失来实现。

首先，为了得到细粒度的权重方案，作者认识到了传统网络加权方法的不足。这些方法通过为关键网络分配额外权重来提高时序性能，然而现代设计的复杂性往往要求具有大型扇出网络和共享数据路径，因而可能会对非关键引脚对施加不必要的权重，并忽略路径共享的影响，进而无法有效地优化时序性能。

为了解决这些问题，作者提出在集成时将引脚到引脚吸引力作为一个细粒度目标来看待，以取代传统的为时序优化应用额外网络权重的方法。从效果上来看，引脚到引脚吸引力可以使关键路径上的引脚靠得更近，从而减少线路延迟并提高时序性能。

具体来讲，改进后的目标函数如下所示：

下图 2 比较了传统网络加权方案与三引脚网络的引脚到引脚吸引力模型。作者使用了一个包含三个时序路径（分别用绿色、黄色和蓝色箭头表示）的示例展开了说明，其中引脚到引脚吸引力方法根据关键引脚（引脚 A、B 和 C）对各自的松弛量有选择地分配权重，从而提供更精细的控制，并有利于整体时序和线长。

在实现细粒度权重方案之后，接下来要考虑的是关键路径的提取。

为了能够高效地提取路径级时序信息，作者集成了 OpenTimer。这是一个高性能的时序分析工具，改编自 DREAMPlace 4.0，并被很多开源项目采用。OpenTimer 提供了一个高级功能 report_timing (n)，它在 n 值较小（比如 1）时可以有效地识别关键路径，从而快速地对特定路径进行详细分析。不过，由于分析路径呈二次增长，该功能的效率会随 n 的增加而降低。

意识到这一问题之后，作者提出了 report_timing_endpoint (n,k) 方法，实现了更好的关键路径提取效果。这里 n 表示最关键端点的数量，k 表示为每个端点提取的关键路径的数量。具体来讲，该方法返回了 n ×k 条路径，并确保每个提及的端点都得到适当地覆盖，从而全面反映整个芯片的时序问题并直接瞄准 TNS 指标。

下表 I 详细说明了使用不同方法时 superblue1 案例的时序分析结果。最初，作者共确定了 26300 个故障端点。从结果来看，本文 report_timing_endpoint (26300,1) 方法高效地覆盖了所有端点，并涵盖了更广泛的引脚对。此外，将每个端点的路径数增加到 10，时长会增加 3 倍，而引脚对的数量仅仅增加了 1.5 倍，这表明前一种设置足以进行有效的优化。

最后还需要解决二次欧几里得的距离损失问题。为了实现有效的优化，设计一个与最终时序指标保持一致的损失函数非常有必要且很重要。作者选择引脚到引脚的欧几里得距离的平方即二次损失作为目标函数：

下图 3 展示了二次损失设计的有效性，并使用 superblue16 案例对其与 HPWL 损失、欧几里得距离损失进行了比较。他们首先使用 report_timing (1) 从时序优化前的稀疏布局中识别出了最关键路径，如图 3 (a) 所示。图 3 (b) 和 (c) 分别展示了使用 HPWL 损失和线性欧几里得距离损失的情况下，优化至收敛的对应路径。

相比之下，图 3 (d) 采用了本文二次欧几里得距离损失，尽管总线长增加了一些，但路径松弛有所改善。这一结果要归功于二次损失促成了单元的更均匀分布，并保持了更一致的线段长度。

得益于以上三方面的创新，作者实现了 PP 损失的 CUDA 内核，并达成了 GPU 加速的目的。

实验结果

研究人员基于开源布局器 DREAMPlace 4.0 发布版本开发了时序驱动的全局布局器，并与此前业内最优方法进行了对比。

下表 II 全面比较了新时序驱动布局器与四种基线方法之间的 TNS、WNS 和 HPWL 指标。所有 DEF 结果均使用 ICCAD 2015 竞赛的官方评估套件进行评估，以确保公平比较。

结果显示，新方法明显优于最先进的时序驱动布局器，尤其是可微分 TDP 和分布 TDP。具体来说，它在 8 个测试案例中的 7 个中实现了最佳 TNS 结果，平均比可微分 TDP 提高了 50.0%，比分布 TDP 提高了 40.5%。

与这两个领先的布局器相比，该研究提出的布局器在 WNS 方面也显示出 8.3% 的持续改进。此外，与 DREAM Place （包括其 4.0 版）相比，新方法在 TNS 和 WNS 的所有 8 个案例中均表现更优。

作者表示，这种改进可以归因于有针对性的引脚到引脚吸引策略，该策略最大限度地减少了对非关键引脚的影响并有效地保持了线长质量，而不像 DREAMPlace 4.0 那样将权重应用于众多网络。此外，与早期收敛的 DREAMPlace 相比，额外的时间驱动优化迭代可以进一步优化 HPWL 的密度。

下表 III 总结了消融研究。前两列分别用 HPWL 和线性欧几里得损失代替了二次距离损失。

尽管如此，它们在 TNS 方面比 DREAMPlace 4.0 提高了 15%，证明了新方法的引脚对引脚吸引力建模和关键路径提取的有效性。此外，与 HPWL / 欧几里得损失相比，二次损失的卓越性能表明它比 Electrostatics-TDP 更具优势，后者依赖 HPWL / 欧几里得损失进行虚拟路径建模。

运行时分析和其他结果。下表 IV 比较了 DREAMPlace、DREAMPlace 4.0 和新方法在 8 种设计中的运行时间。因为专注于线长，没有耗时的计时引擎，DREAMPlace 在所有情况下都实现了最佳运行时间。

由于高效的时间分析和加权方案，新方法在大多数情况下都超越了 DREAMPlace 4.0，如下图 4 所示。

下图 5 展示了在布局运行过程中，新方法与 DREAMPlace 4.0 在半周长线长（HPWL）、溢出率（Overflow）、总负时序裕量（TNS）和最差负时序裕量（WNS）方面的对比。两条曲线在前 500 次迭代中保持一致，随后时序优化开始。在 HPWL 和溢出率的子图中，DREAMPlace 4.0 由于应用了较大的网络权重，导致 HPWL 性能较差且收敛速度较慢。

此外，新方法还迅速提升了 TNS 和 WNS 性能，并在优化完全收敛前保持稳定，从而证明了时序目标设计的有效性。

芯片设计是一个流程极其复杂的过程，包含大量优化问题。近年来，南京大学 LAMDA 组一直在持续攻关，希望建立 AI 赋能 EDA 技术的理论基础，并对算法设计提供指导。

此前，在 2019 年 LAMDA 组在 Springer 出版《Evolutionary Learning: Advances in Theories and Algorithms》，总结了他们在该方向上过去二十年的主要工作，并于 2021 年出版中文版《演化学习：理论与算法进展》。该团队基于在演化学习方向的长期理论研究，近期还针对芯片设计中的复杂优化问题设计出了多个原创领先算法，如针对芯片宏元件布局问题，较谷歌在 Nature 2021 年提出方法的布线长度缩短 80% 以上，较当前最先进的开源 EDA 工具 OpenROAD 的芯片最终时序指标提升超 65%，并在 ACM SIGEVO Human-Competitive Results 获奖。

据介绍，南大 LAMDA 组正在与华为合作攻关，希望通过先进芯片设计缓解当前先进制造工艺局限。

^{参考内容：}

^{https://www.date-conference.com/}

^{https://ai.nju.edu.cn/5d/02/c17806a744706/pagem.htm}

产业DATE 2025