中国团队拿下 EDA 全球冠军，平均年龄 24 岁

　　原标题：中国团队拿下 EDA 全球冠军，平均年龄 24 岁

　　在 11 月 4 日结束的 EDA（电子设计自动化）领域的国际会议 ICCAD 2021（计算机辅助设计国际会议）上，华中科技大学计算机学院吕志鹏教授团队获得了 CAD Contest 布局布线（Routing with Cell Movement Advanced）算法竞赛的第一名。团队成员还包括苏宙行博士、研究生罗灿辉、梁镜湖和谢振轩。

　　ICCAD 会议始于 1980 年，是 EDA 领域历史最悠久的 学术会议之一，其中 CAD Contest 算法竞赛作为会议的标志性事件，长期以来受到国际学术界与工业界的广泛关注。每届竞赛的赛题均来自 Cadence、Synopsys、Mentor Graphics、Nvidia、IBM等全球 EDA 或半导体公司的真实业务场景，涵盖集成电路设计、制造与测试等环节中的核心算法难题，如逻辑综合、布局布线、等价验证、时序分析等。本届 CAD Contest 算法竞赛共有来自 12 个国家 / 地区的 137 支队伍参与，包括众多国内外知名高校与研究机构，如加州大学伯克利分校、东京大学、台湾大学、香港中文大学、复旦大学等。

　　EDA 是电子设计的基石产业，也被誉为「芯片之母」。本届竞赛的布局布线问题作为 EDA 芯片后端物理设计中最重要的环节，直接影响芯片的功耗、面积、时延等各项性能指标。其中，布局过程需将一系列电路单元放置于给定的长方体空间中；而布线过程则需将属于同一个网的单元引脚用导线连接起来。参赛算法需要在考虑空间容量、电压区、最小布线层、金属层布线方向等众多真实约束的情况下，确定每个单元在芯片内的位置，并同时为每个网规划无短路、无断路的信号传输路径，使得导线的加权总长度最短。吕志鹏教授团队所设计的启发式优化算法，在冗余导线检测、布线环路消除、并行化邻域评估加速、布局调整最优移动区域识别等多项关键技术上实现了突破。根据 ICCAD 2021 会议公布的竞赛结果，该团队所设计的算法在所有测试算例上均达到了竞赛中的最优结果。据悉，今年是该团队首次参加 ICCAD 竞赛。

　　EDA 作为我国「卡脖子」关键技术之一，难点主要在于算法，其核心问题在算法上通常具有极高的计算复杂度，即为 NP 难问题。本次竞赛的布局布线问题，涉及了图着色、集合划分、二次指派、广义指派、斯坦纳树、斯坦纳森林等众多经典的 NP 难问题，是计算复杂性理论研究与实际工业应用相结合的典型场景。

　　吕志鹏教授所在实验室自成立至今的 40 余年来，一直聚焦于 NP 难问题的求解算法与工业应用研究，曾多次获得国际算法竞赛全球前三名，如：2021 年 GECCO「最优相机布局与集合覆盖」国际算法竞赛第一名；2021 年 ISPD「晶圆级物理建模」切分布局布线国际算法竞赛第三名；2020 年 GECCO「最优相机布局与集合覆盖」国际算法竞赛第一名；2018 年 SAT 国际算法竞赛第三名；2017 年 SAT 国际算法竞赛第一名；2016 年 ROADEF/EURO「液化气库存路由」国际算法挑战赛第三名；2010 年国际护士排班算法竞赛第三名；2008 年国际大学排课表算法竞赛第二名等。