引言
尽管业界对芯片布局的研究已有数十年历史，但业内专家仍需花费数周的时间进行迭代，以完成一个满足多方面设计标准的解决方案。随着现代超大规模集成电路（VLSI）规模的不断扩大，基于优化的传统方法面临越来越多的挑战。因此，研究人员开始探索基于深度学习的一系列方法，以提高布局质量，其中强化学习方法尤为引人注目。例如，MaskPlace[1]、ChiPFormer[2] 和 EfficientPlace[3]等方法在一定程度上提升了布局质量，并显著减少了所需时间。接下来，我们一起学习这些方法吧！
研究背景
论文1：MaskPlace: Fast Chip Placement via Reinforced Visual Representation Learning
论文链接：https://arxiv.org/pdf/2211.13382
由于超图不可扩展以全面编码网表信息，引脚对的相对位置（偏移）在之前一些强化学习模型（例如，Graph Placement和DeepPR）中被丢弃。如果没有引脚的相对位置信息，线长的估计是不准确的；但如果对这些丰富的信息进行编码，又会使得超图过于复杂，因为每个模块上可以有数百个引脚，放置过程也会需要大量的计算。为了解决这个问题，该论文提出了一种新颖的强化学习方法，名为MaskPlace, 它可以在几个小时内自动生成高质量且有效的布局，而不像以前可能要用商业电子设计自动化（EDA）工具耗时近72小时评估布局，再进行手动细化修改不合法的布局。MaskPlace 将芯片布局问题视为使用卷积神经网络进行电路模块像素级视觉表示学习的问题。MaskPlace可以使用三种类型的像素级特征图来完全表示大量网络和引脚配置，从而能够在大画布尺寸上的完整动作空间中快速放置。而由于问题的大小，MaskPlace主要用于宏布局。
MaskPlace的整体架构
位置掩码：例如, 是一个尺寸为224*224的画布网格的二进制矩阵。其中值“1”表示放置模块的可行位置。位置掩码的目的是保证模块之间没有重叠（即满足重叠约束）并了解布局和线长之间的关系。
布线掩码：例如 是一个连续矩阵，用于表示如果在特定位置放置模块，总布线长度（HPWL）将如何增加。
视图掩码：表示为 ，是对当前芯片布局的全局观测，其中值为“1”表示该网格单元已经被一个模块占据。MaskPlace考虑了模块的实际尺寸。例如，如果一个模块的尺寸为 ，它在画布上覆盖 个网格单元，其中 和 表示画布的尺寸。
实验结果
实验表明MaskPlace模型在24个公共芯片基准测试中优于最新的先进方法。能够极大减小线长，并且做到0%重叠的布局。论文还通过消融实验，证明了MaskPlace中各个组件的重要性，如掩码、稠密奖励等。与之前的方法相比，MaskPlace在各项性能指标上都有显著提升（如表1所示）：
• 在HPWL（半周长线长）指标上，MaskPlace可以减少60%~90%。
• 在拥塞和密度指标上，MaskPlace可以保证所有模块完全不重叠。
论文2：ChiPFormer: Transferable Chip Placement via Offline Decision Transformer
论文链接：https://proceedings.mlr.press/v202/lai23c/lai23c.pdf
尽管基于强化学习的方法可以实现比经典优化方法更强的布局性能，但其较长的运行时间使其不如在几分钟内生成布局设计的经典方法实用。这是因为在较大的布局搜索空间中，之前的强化学习算法在线学习策略很慢，当芯片电路规模增加时尤其如此。ChiPFormer[2]将芯片放置问题建模为离线强化学习问题，从而能够从固定的离线数据中高效地学习可迁移的放置策略。ChipFormer使用一个专家级别的多任务芯片放置数据集，表示为 ，其中 表示芯片电路任务的索引， 表示与 对应的已收集的专家级别放置行为。与传统的离线强化学习不同，ChipFormer通过考虑专家级别的行为，省略了奖励项。在Chipformer完成宏布局后，宏布局结果将作为初始布局结果，使用基于优化的方法完成标准单元布局。
ChiPFormer的整体架构
电路token生成模块：首先通过预训练的条件变分自编码器(Conditional VAE)模型，从电路的拓扑结构(邻接矩阵和节点特征)中提取出一个表示该电路的token，作为ChiPFormer的输入之一。
状态嵌入模块：用类似于MaskPlace的位置掩码、布线掩码和视图掩码作为一个三通道输入来表示state token，并以此作为ChiPFormer的另一个输入。
动作嵌入模块：对于动作token，用宏元件的二维坐标来表示，作为ChiPFormer的第三个输入。
决策变换器模块：ChiPFormer的核心是一个基于GPT架构的决策变换器模型,它使用因果自注意力机制自回归地预测下一个动作。该模块将上述三种输入token(电路token、状态token和动作token)拼接在一起,并通过多层transformer编码器进行处理,最终输出下一个动作。
在线强化学习模型不断与环境（即布局模拟器或EDA设计工具，用于从布局设计中获取指标，其时间消耗通常与电路规模成正比）交互，从头开始学习策略。因此，在ISPD05基准测试中，在线策略学习在一张芯片上要花3个多小时。在（b）中，离线方法使ChiPFormer能够使用固定的离线放置数据来学习策略，从而消除耗时的在线交互。当出现没有看见过的芯片时，只需几次部署即可通过多任务离线数据中重用和转移学到的经验来对ChiPFormer进行微调。我们发现，与之前的在线方法相比，这种离线方法可以将ISPD05基准测试中的运行时间减少十倍。
实验结果
方法后面的式子指的是在线的布局尝试次数。ChiPFormer(1)表示零样本布局表现。粉红色和青色的百分比分别表示与最先进的基线结果相比HPWL的降低和增加率。与最佳基线MaskPlace（3k）相比，通过将尝试次数减少10倍，ChiPFormer（300）仍然可以在12个电路中的10个达到最小HPWL值。此外，当将尝试次数增加到2k（仍然小于之前基线所需要的时间）时，ChiPFormer可以在所有电路中实现最先进的结果。受益于离线预训练，在混合尺寸上，ChiPFormer可以产生当时最先进的布局质量。
论文3：Reinforcement Learning within Tree Search for Fast Macro Placement
论文链接：https://openreview.net/pdf/553a91760b8f7315d16d55796fdc93ceb4d2b16f.pdf
模型架构
全局树搜索：构建一个搜索树，其中每个节点代表一个布局状态。动态管理一组“前沿节点”，即表示当前关注状态的节点。在每一轮迭代中，以前沿节点为初始状态执行多次回溯，用于扩展树结构并通过反向传播来指导树的演化。在每轮迭代中更新前沿节点，并对不需要再次访问的节点进行剪枝。
局部策略学习： 使用强化学习代理执行回溯操作。该代理专注于利用前沿节点，推动树的扩展。强化学习代理在搜索过程中不断训练，提升其在更广泛的树结构中进行有效局部搜索的能力。
实验结果
如表4的相关实验结果表明，EfficientPlace在ISPD2005基准测试集上的宏观布局质量优于最新的状态技术，包括基于强化学习(GraphPlace、DeepPR、MaskPlace、ChiPFormer)和基于黑箱优化(SA、WireMask-EA)的方法。
总结与展望
参考文献
[1] Lai, Y., Mu, Y., & Luo, P. (2022). Maskplace: Fast chip placement via reinforced visual representation learning. Advances in Neural Information Processing Systems, 35, 24019-24030.
[2] Lai, Y., Liu, J., Tang, Z., Wang, B., Hao, J., & Luo, P. (2023, July). Chipformer: Transferable chip placement via offline decision transformer. In International Conference on Machine Learning (pp. 18346-18364). PMLR.
[3] Geng, Z., Wang, J., Liu, Z., Xu, S., Tang, Z., Yuan, M., ... & Wu, F. (2024). Reinforcement Learning within Tree Search for Fast Macro Placement. In Forty-first International Conference on Machine Learning.
初稿 ：诸俊涵 颜学明
复审 ：颜学明
终审 ：金耀初
