NeurIPS 2022 | PRNet：基于策略梯度的布局与生成式布线网络求解芯片布局布线

本文我们将介绍一项被 Thirty-sixth Conference on Neural Information Processing Systems ( NeurIPS’22 ) 会议接收的新工作 ，我们于该工作中提出了名为 PRNet 的模型以解决上述问题，其中布局端通过基于策略梯度的强化学习方法来实现，同时考虑元件的实际大小；布线端则由生成对抗模型 (cGAN) 完成网级 (net) 布线。

论文地址： https://openreview.net/forum?id=uNYqDfPEDD8 代码地址： https://github.com/Thinklab-SJTU/EDA-AI

目前芯片设计的一个趋势是元器件尺寸不断减小，元件之间的连接关系也越来越复杂，这使得电路密度越来越大，给布局以及布线求解器带来了许多新的问题。近年来机器学习方法开始被广泛应用于EDA领域，特别是求解布局[1,2]和布线[3]任务。其中有两个值得我们特别关注的问题：

1. 宏元件往往是大小不一的[4]，这给基于网格的布局方法带来了一定挑战；

2. 布线数据集 (例如ISPD-07[5]) 的网格规模过于精细，而目前基于强化学习的布线器在每一步只决定相邻的网格的布线方向[6]，因此过大的网格规模使得强化学习无法处理。

这促使我们提出一种新的思路来解决布线问题。另一方面，端到端的神经网络通过对整个系统的联合优化往往可以实现比较好的性能；而目前为止还没有单纯使用神经网络联合求解布局布线问题的方法。因此，我们的思路是提出一个不涉及传统算法，只包含神经网络的布局布线训练框架。

本文我们将介绍一项被 Thirty-sixth Conference on Neural Information Processing Systems (NeurIPS’22) 会议接收的新工作，我们于该工作中提出了名为 PRNet 的模型以解决上述问题，其中布局端通过基于策略梯度的强化学习方法来实现，同时考虑元件的实际大小；布线端则由生成对抗模型 (cGAN) 完成网级 (net) 布线。

该工作的亮点总结如下：

• 不同于现有基于学习的布局方法 [1, 2, 7]，我们提出了一个针对混合尺度布局问题的强化学习模型，使得布局结果更贴近现实，需要更少的后处理优化元件碰撞。

• 我们提出了一个生成对抗网络，可以一次性完成网级布线 (one shot)。此外，我们通过学习适应性地优化布线顺序，而不是和传统布线器一样事先固定好顺序。

• 结合以上两种方法，我们提出了完全依赖神经网络的布局布线框架 PRNet。据我们所知，这是第一个仅使用神经网络解决布局和布线问题的方法。

• 通过在多个公开数据集上的实验，我们验证了所提出 PRNet 具有成本效益高 (与强化学习布线器[6]相比) 且性能优异的特点。

一、方法

给定一张网表作为输入，布局的目标是将其中的宏元件 (macro) 和标准元件 (standard cell) 放置在芯片版上，最小化线长的同时尽可能减小元件之间的重叠面积。基于布局结果，布线需要在满足所有约束的前提下连通同一个net中的所有元件。我们期望能通过强化学习更灵活高效的解决混合尺寸布局问题，并提出了生成式布线模型一次性 (one shot) 完成网级布线。注意到我们的布局布线流程完全依赖于神经网络，而之前提出的方法[2]仍需要传统布线器的参与。

1.1 强化学习求解混合尺寸布局问题

为了解决混合尺寸布局问题，之前的工作 (如DeepPlace) 假定每个元件都占据整个网格的一个单元，但映射到实际的芯片版后，最终布局结果就会存在比较严重的元件重叠问题，同时这些方法也没有考虑预先放置好的元件。因此我们基于混合尺寸布局重新定义了这个马尔科夫决策过程：状态表示仍然由全局图像和网表图两部分组成，但我们额外考虑了提前放置的元件，在初始状态时就把它们对应的坐标 设成1。动作方面，作为一个有效的放置位置当且仅当整个邻域都是没有被占用的。这里

也就是整个元件的真实形状。在奖励函数方面，为了进一步控制最终布局结果的重叠面积，我们在之前的线长和拥塞的基础上引入了重叠损失，将三者的线性组合作为最终的奖励函数。

1.2 生成式布线模型

首先定义一下待求解的布线问题：我们希望能一次性布好整个net，这个net中可能存在多个pin (即包含多个元件)，而不是按照之前布线器的思路先把一个net分解成很多个pin-to-pin问题再依次解决。生成式布线模型的输入包含三个通道：pin的位置，以及水平方向和垂直方向的布线资源。输出的每个像素对应这个网格属于布线结果的概率。为了保证最后的布线结果是连通的，我们采用maze routing作为后处理来修正。

以下是我们的模型示意图：

左图的生成器包含基础生成器处理输入小于等于 的情况；当输入大于时额外引入了生成器 ，两个网络一起训练并共同输出结果。右图的判别器同样由两部分组成，分别判断真实性和连通性 (布线问题的特别需求)。

损失函数方面我们同样做了一些改进，包括引入focal loss解决标签不均衡问题，考虑到大部分网格都不参与布线；同时我们引入regularization term计算生成的线长与HPWL (线长的下界) 的差值，期望达到尽可能缩短线长的效果等等，具体细节请参考我们的论文。最终采用的目标函数如以下公式所示：

1.3 整体布局布线网络工作流程

我们结合了上述的混合尺寸布局智能体得到布局结果，并通过生成式布线器对每个net布线，从而实现整个流程的pure neural pipeline。

布局布线网络的工作流程如下图所示：

在更新时我们受到EM算法的启发，得到布局结果之后我们首先训练生成式布线器 (类似于 E step)，然后布局和布线顺序智能体通过训练后的布线器提供线长反馈来联合训练整个强化学习框架，最终使线长最小 (类似于 M step)。

在整个pipeline中，我们提出了两点改进：首先，注意到训练刚开始时布局质量很差，同一个net中的元件也分布的比较分散，因此生成式布线器难以得到比较准确的布线结果。据此我们提出了一个自适应的线长计算方法：

初始时 ，线长主要由半周长线长来粗略估计；随着迭代轮数增加，逐渐趋向于1，这时候线长则完全由生成式布线器来决定了。此外，我们发现布线顺序对布线结果具有很大的影响，传统布线器往往采用heuristics决定顺序，例如优先布更小的net。但很难找到一种策略在不同情况都能达到最优，所以我们提出了布线顺序智能体动态决定下一个要布线的net并调用布线器。布线顺序智能体与宏元件布局智能体两个强化学习模块在整个流程中是一起训练的。

二、实验结果

布局方面，我们仍然和DeepPlace一样采用ISPD-05[8]数据集；布线方面，我们采用了ISPD-07[5]数据集，并根据性能最好的传统布线器得到的布线结果作为训练标签。下表展示了我们混合尺寸布局结果。可以看到与DeepPlace相比，我们的方法仅仅牺牲了1.3%的线长，但重叠面积平均缩小了四倍。从长远角度来看，由于元件之间的重叠需要额外的后处理来解决，所以我们的方法最终得到线长与DeepPlace相比也是更优的。

布线方面，我们首先在ISPD-07上比较了不同backbone以及改进的判别器和损失函数的影响。可以看到改进后的bi-discriminator对结果有比较明显的提升，并且改进后的损失函数有助于减小最终的线长。

进一步地，我们将训好的布线模型在ISPD-98数据集上进行了测试，并提出了并行版本以解决时间开销问题。实际上"并行"是布线效果与运行时间之间的一个 trade-off，因为同时对多个有关联的net布线可能会产生布线资源的冲突，从而引入一定的overflow。从表中可以看出并行版本在时间上的提升是比较明显的。

我们比较了所提出的 PRNet 与DeepPlace，以及 PRNet 除去布线顺序模块在整体布局布线任务上的效果。可以看到我们提出的训练流程在线长与拥塞两个指标上都有一定提升。此外，引入布线顺序模块后拥塞得到了明显降低，这说明布线顺序智能体可以找到高效布线的序列。

最后，我们展示了模型在电路上的mixed-size布局结果。我们提出的布局方法倾向于将大的宏元件放置在芯片版中心，从而减小了元件间的重叠面积。

三、总结

在该文章中，我们提出了一个完全依赖于神经网络的布局布线框架PRNet。具体来说，我们提出了一个针对混合尺度布局问题的强化学习模型来解决元件间的重叠问题，使得布局结果更贴近现实。我们还设计了一个一个生成式布线模型，可以一次性 (one shot) 完成网级布线。在多个公开数据集的实验结果表明，我们的模型在布局与布线两个任务上均带来了显著的提升。

四、写在最后

We’re always open for possible collaborations and feel free to contact us. 欢迎一起交流与进步！如果有对机器学习在EDA领域的应用感兴趣的同学，欢迎阅读我们的另一篇survey：https://arxiv.org/abs/2202.13564

参考

[1] A. Mirhoseini, A. Goldie, M. Yazgan, J. W. Jiang, E. Songhori, S. Wang, Y.-J. Lee, E. Johnson, O. Pathak, A. Nazi et al., “A graph placement methodology for fast chip design,” Nature, 2021.

[2] R. Cheng and J. Yan, “On joint learning for solving placement and routing in chip design,” NeurIPS, 2021.

[3] J. Liu, G. Chen, and E. F. Young, “Rest: Constructing rectilinear steiner minimum tree via reinforcement learning,” in DAC, 2021.

[4] Y.-L. Chuang, G.-J. Nam, C. J. Alpert, Y.-W. Chang, J. Roy, and N. Viswanathan, “Designhierarchy aware mixed-size placement for routability optimization,” in ICCAD, 2010.

[5] G.-J. Nam, M. Yildiz, D. Pan, and P. Madden, “Ispd 2007 global routing contest,” 2007.

[6] H. Liao,W. Zhang, X. Dong, B. Poczos, K. Shimada, and L. Burak Kara, “A deep reinforcement learning approach for global routing,” Journal of Mechanical Design, 2020.

[7] D. Vashisht,‍‍ H. Rampal, H. Liao, Y. Lu, D. Shanbhag, E. Fallon, and L. B. Kara, “Placement in integrated circuits using cyclic reinforcement learning and simulated annealing,” arXiv preprint arXiv:2011.07577, 2020.

[8] G.-J. Nam, C. J. Alpert, P. Villarrubia, B. Winter, and M. Yildiz, “The ispd2005 placement contest and benchmark suite,” in Proceedings of the 2005 international symposium on Physical design, 2005, pp. 216–220.

作者：程若愚 文章来源：公众号【sjtuThinklab】

Illustration by Sushama Patel from IconScout

-TheEnd-

多家技术企业招聘来啦！

多家技术企业招聘来啦！有求必应的小将收集到来自TechBeat技术社群内技术企业的招人需求，包含来自微软亚研、腾讯、小红书等企业算法工程师等正式及实习岗位，欢迎有需求的大家向这些公司投递简历哦！

扫描了解详情~

关于我“门”

将门是一家以专注于发掘、加速及投资技术驱动型创业公司的新型创投机构，旗下涵盖将门创新服务、将门技术社群以及将门创投基金。

将门成立于2015年底，创始团队由微软创投在中国的创始团队原班人马构建而成，曾为微软优选和深度孵化了126家创新的技术型创业公司。

如果您是技术领域的初创企业，不仅想获得投资，还希望获得一系列持续性、有价值的投后服务，欢迎发送或者推荐项目给我“门”:

bp@thejiangmen.com

点击右上角，把文章分享到朋友圈

⤵一键送你进入TechBeat快乐星球