RL Macro Placement的自由心证

本文尝试总结2021年至今围绕Google Research发表的文章《A graph placement methodology for fast chip design》和其提出的强化学习(RL)求解宏模块布局(Macro Placement)方法的争议，旨在梳理出时间线，总结双方的主要质疑、回应、对回应的回应，写一点自己对这些质疑的看法，希望不仅对机器学习求解组合优化这一领域加深理解，也锻炼一下个人的批判性思维。是非对错，还请各位读者自由心证。

【正1】A graph placement methodology for fast chip design

(google on Nature 2021) https://www.cl.cam.ac.uk/~ey204/teaching/ACS/R244_2021_2022/papers/Mirhoseini_NATURE_2021.pdf
google发表nature正式提出RL求解macro placement问题的方法，这就是一切的开端。
作者提出把macro placement转成一个游戏场景，按照从大到小顺序一个一个放macro，每次选一个合法的位置。policy和value模型共用一个GCN在前，policy模型进一步施加一系列反卷积得到“把macro放在哪里比较好“的二维表格，布局流程就是在二维表格里合法的位置直选最大值，不走回头路。中间的reward都是0，全部放完以后用force directed方法放standard cell，估算WL/congestion/density给出加权的reward。
初步的印象就是方法很简单，但是肯定很难训练。
文章展示了跟知名开源布局工具replace和人手工布局的结果比较，显示RL方法大幅占优。还对比了模拟退火这一经典的通用搜索算法，也显示大幅占优。以上大幅占优意味着关键指标提升20%以上。
macro placement是一个很有代表性的困难的组合优化问题，假如能够证明RL能够起到好的效果，显著优于传统的基于搜索/启发式/连续优化等技术的算法的话，那可以肯定影响力绝不仅限于芯片设计本身，因为NP难的组合优化问题太多了，而且这些问题大都具有很高的实用价值。

【反2】Stronger Baselines for Evaluating Deep Reinforcement Learning in Chip Placement

(anonymous)  https://statmodeling.stat.columbia.edu/wp-content/uploads/2022/05/MLcontra.pdf
这是一篇匿名质疑的文章，或许是首个。质疑文章的成文甚至可能早于nature最终发表时间。
作者在开源的ibm benchmark上复现nature的RL算法和baseline。比较了RL和直接基于电场的传统mixed size placement算法（replace），以及模拟退火。RL算法区分pretrain与否，用在相同benchmark上预先运行一段时间来实现。
发现传统算法比RL在wirelength上好26%，congestion好43%，而且效率非常高（因为不需搜索）。
模拟退火和RL使用相同的资源情况下能够比RL好，说明RL即使花了很多精力做预训练也没打过一个完全没用机器学习的经典搜索heuristic。这里本文既实现了nature的模拟退火baseline，也在上面提出了更强的模拟退火方法（增加了一个任意移动操作和一个shuffle操作），前者比RL好1%，后者比RL好4%.
这一系列结果和nature文中的结果大相径庭。
值得注意的是，文章在深入分析模拟退火和RL的实验部分，采用了Google的未开源TPU block做为预训练和测试的样例，而且说是和nature文章中使用的完全相同的20个。这说明本质疑文章的合作作者有google内部人士，也解释了为什么文章要匿名——google内部出现了“吹哨人”。在后续我们会介绍的【6】中，这篇文章的作者列表掉码了，在reference里都展现了出来，不知是不是意外。事实上，作者列表里一位名为Chatterjee的engineer，后来遭到google解雇，据信（ https://www.engadget.com/google-fires-ai-researcher-over-paper-challenge-132640478.html ）与此事相关。

【正3】Scalability and Generalization of Circuit Training for Chip Floorplanning

(google, ISPD 2022) https://dl.acm.org/doi/10.1145/3505170.3511478
由于nature没有开源，上述质疑其实都没有办法得到消解。这篇ispd中，google开源了一个自己复现自己的circuit training代码库（和nature并不是相同的代码，但是是相同的思路，原班人马）。 https://github.com/google-research/circuit_training （后续升级成了alphachip）
这其中有一半的篇幅是和效率相关的，一些distributed training的scalability，我们跳过。实际上传统的模拟退火也可以distributed，所以我认为仍然可以在相同的计算资源下比较两个方法。
与论战最相关的就是generalization了。为此，文中的figure 7&8展示了两个有趣的结果：前者是在非常相似的旧版netlist上预训练，要好于在丰富的tpu block上预训练；后者是在丰富的tpu block上预训练，要好于在一个block group里的不同slice上预训练（这些slice由于i/o的区别，虽然内部逻辑类似，但最佳placement有很大差别）。
按这样来说，其实在完全相同的netlist上预训练效果应该是最好的，在长得类似但最优解有很大不同的netlist上训练效果则是最差的。这个挺符合直觉的，但其实是一个挺严重的坏消息，这暗示模型其实仍然没有本质上解决组合优化问题和机器学习模型可能是最大的gap：有关连续性的inductive bias——长得像的两幅图片（只差几个像素）可以说一定是一个分类，但长得像的两个芯片布局问题（只差几个连线）却可能导致完全不同的结果。

【反4】Assessment of Reinforcement Learning for Macro Placement

ISPD 2023 https://arxiv.org/abs/2302.11014
开源的实现deserves开源的验证 https://github.com/TILOS-AI-Institute/MacroPlacement 。几位eda领域大佬一起尝试在google上述开源的circuit training (CT)框架上做一个完整的evaluation。
彼时，这个CT框架虽然开源，但是缺少大量关键模块，尤其是用于预训练的模块。代码如此，那数据就更糟糕了。因此本文作者做了大量的辛苦工作：仔细对比了nature和CT的方法区别；在sky130和asap7上造了大量带macro且有代表性的芯片benchmark；与EDA vendor沟通开源Tcl流程脚本；在开源nangate 45nm和闭源globalfoundries 12nm上测试了CT，对比了CT和之前的stronger baseline的模拟退火、开源的place工具replace、开源的改进了macro placement和参数搜索的GPU加速place工具autodmp（基于dreamplace和abcdplace）、cadence的闭源商业工具CMP；甚至请来了human expert。
这篇文章提出了一系列质疑。
(1) CT的代码显示，CT运行之前就需要已知一个所有元件的布局，也就是依赖一个初始解，nature在文章和审稿回复中都没提这件事。进一步实验显示，CT的性能和初始解非常相关。
(2) CT和nature的参数设置区别很大，对距离的定义也有微妙的区别（能够发现这些细节区别，可以想见这个分析工作多认真细致..）进一步实验显示，无论如何设置参数CT都不太行。事实上，CT仍然保留了闭源的二进制代码，其中包括proxy cost的计算这种重要的模块。
(3) 实验结果显示CMP和AutoDMP显著优于CT，差距可达40%；human expert在macro较多的设计上超越CT；模拟退火和CT打得有来有回，而且模拟退火的结果从统计上看明显更稳定。文章还发现，有一个电路样例叫做Ariane，它的macro placement明显要简单很多，即使打乱macro，也不会太多影响关键指标，而Ariane正是google使用的唯一开源样例，这可能导致false positive的结果。
综合这些结果，可以看到google开源的CT完全没有展示出对任何传统方法的明显优势。
这篇文章的实验结果据称被另外两位研究者复现，as expected，因为文章和开源仓库写得非常详细，就是为了复现做准备的（ https://github.com/TILOS-AI-Institute/MacroPlacement?tab=readme-ov-file#new-faqs-after-the-release-of-our-ispd-2023-paper-here-and-on-arxiv ）值得注意的是只有流程开源了，本文并没有开源benchmark，可能是因为PDK的问题。不过这几位独立复现者单独找作者要到了一些case。
另外，本文作者之一ABK老师公布了一些其他的细节（ https://docs.google.com/document/d/1vkPRgJEiLIyT22AkQNAxO8JtIKiL95diVdJ_O4AFtJ8/edit?tab=t.0 ），表示他正是nature文章的审稿人之一，并公布了全部审稿意见和作者回复；他也表明了自己温和的态度，表示自己最终的目的是澄清误会，让RL方法这一新的方法论的研究走向正轨。
本文有两个主要质疑：初始布局是否造成信息泄露和不公平；实验结果明显不匹配。本文自己的漏洞也有一个：没有做预训练(pretraining)。作者在开源仓库的README/FAQ中解释了原因(1)pretrain代码根本没开源；(2)拿不到TPU block；(3)之前的【2】已经做过预训练的实验了，结果是对reward数值有点改进，但对关键指标如wirelength/congestion并无改进；(4)nature文章也没有claim这些关键指标能通过预训练改进。
(5) 事实上，google发布的CT早期版本的readme中，明确说了不用pretrain也能有类似的效果（ https://web.archive.org/web/20240927125230/https://github.com/google-research/circuit_training/tree/r0.0.4 ，“With this code we are able to get comparable or better results training from scratch as fine-tuning a pre-trained model”）

【正5】How AlphaChip transformed computer chip design

https://deepmind.google/discover/blog/how-alphachip-transformed-computer-chip-design/   and nature addendum(https://www.nature.com/articles/s41586-024-08032-5)
在以上质疑文章发表后，nature编辑给出了editorial notice，表示将调查google的nature文章并采取适当行动。大约一年以后，google为文章提交了补充说明(addendum)，结束了nature的调查。同时，google在CT代码库中开放了一个预训练的检查点。
这次addendum主要澄清了以下几点：
(1) 强调需要充分的pretrain，给出了自己使用20个TPU block做pretrain的检查点，并给出了使用CT做pretrain的教程。同时，宣称之前的质疑工作由于缺少合理的pretrain而无效。学术界很难复现google的pretrain，倒不是因为算力不够，主要是tpu block不是开源的。唯一的机会就是在匿名发表的【2】中了，这里面有几近相同的case和设置，也没发现有啥改进，不过google总可以再提别的理由（后面也这么做了），比如【2】的训练并不充分，算力不够，没收敛之类的。好在，google这次发布的预训练权重至少可以用做测试。
(2) 澄清了布局初始解只用于clustering，并补充了布局初始解的消融实验，实验结果显示不使用任何初始解也不影响结果。这是一个对关键质疑的正面回应。当然，还遗留一些问题，比如这和【4】的开源复现结果明显不符，【4】在后续还补充了一个实验，显示如果对google开源的CT的初始解加一点微小扰动，就可以让最终结果普遍变差很多，这反而说明CT对初始解很敏感。
(3) 表示google的实验使用了商业的sub-10nm制程，而质疑工作如【4】测试的是45nm和12nm，因此他们的工作不一定适用，需要调整reward函数才行。能解决困难的先进制程布局，反而不能解决落后成熟制程的布局，这个回应完全说不通。另外，nature文章里的reward函数并没有什么针对先进制程的复杂项，都是很简单直接的wirelength, congestion, density。再者，【4】里明确测试了各种reward的加权方式，结果是普遍的不好。
在google的宣传中，这次addendum被冠以“AlphaChip“的新名称，与其说是一次澄清，这看起来更像是一次新品发布会。朋友圈里一位eda界知名老师揶揄说这是“公关的教科书”。确实，怎么看怎么有点丧事喜办的意思.. 国内AI领域三大顶会量子位（ https://mp.weixin.qq.com/s/IXFTgA0ug9tdPBRPrxs2hw ）、机器之心（ https://mp.weixin.qq.com/s/9ZfY10fKlU85RMmiinmh-A ）、新智元（ https://mp.weixin.qq.com/s/XO0YqfEcRhaYkzLwGCidjA ）均有报导，其中尤以新智元“AI几小时设计芯片超越人类！”“直接碾压人类专家！这种超人芯片布局，……人类设计芯片的方式，已被AI彻底改变。”最为震惊体。不知这几位顶会得知此次addendum的实际背景后会怎么想。

【反6】The False Dawn: Reevaluating Google’s Reinforcement Learning for Chip Macro Placement

(Igor) https://arxiv.org/abs/2306.09633
相比质疑文章【4】的温和，Igor Markov老师的质疑文章【6】则剑拔弩张得多。这篇文章发表于CACM，而arxiv版本标题前面有一个“The False Dawn“，攻击性很浓。打开文章则发现更是丝毫不留情面，最终也是明确希望nature撤稿。
本文提出了一些具体的质疑，其中一些是要求解释，如
(1) 标题fast chip design的claim模糊，不得而知baseline到底哪些步骤被算成了用时，只有感性描述没有针对具体样例分别展示运行时间。RL使用了大量的CPU/GPU资源，因此也具有不公平的起跑优势。
(2) 测试用例完全是黑盒，缺少一些关键指标（如macro数量、面积使用比率等）用以估计测试用例的设计难度；而且只有5个，一般的EDA领域工作远不止。
(3) 文章对比了human expert，但是“expert“过于主观，没有定量展示人类所花时间。
(4) 文章在RL后还接了一个商业EDA工具（指force directed？）来优化standard cell，或许还包括了更复杂、拥有独立设计空间的电源网络设计、时钟树综合、时序signoff等步骤，这些步骤并不标准化，而且对最终结果的时序（WNS, TNS）有至关重要的影响。文章只展示了一轮结果，并没有统计显著性测试，因此无法得出可靠结论。
(5) 文章对比模拟退火的例子和对比replace的例子不相同。而replace是直接在标准单元cluster之后应用的，这不是replace的正确用法，正确用法应该是不做cluster，直接全部丢进去。
其他的质疑基本在【4】中已有过了。另外还有一些动机揣测和情绪，省略之。
有意思的是本文提到了近期举办的MLCAD 2023 macro placement contest for FPGA，分析了比赛的设定，发现比赛其实和google nature的设定很相似，很有利于RL方法的使用，然而google没有派人参加，而最终比赛的前六名都是不使用机器学习的传统方法取得（笔者所在的课题组也参加了此比赛获得第二名 https://magic3007.github.io/2023/11/13/MLCAD2023/ ），无人用google开源代码CT或者自行实现类似方法取得好的名次。没能复现曾经imagenet刷榜或者alphago打赢世界冠军的优良战绩。
本文还一一回应了很多google团队的回应，摘取几点
(1) pretraining，道理和我们在【5】中评论的一样。另外补充了一点是，jeff dean的报告中曾经claim说即使不pretrain结果也strong，现在又用pretrain缺失做理由回应不太站得住脚。（我去看了那次报告的slides，本质上就是nature paper的图Fig.4蓝线在30h之后的解释）
(2) train until convergence才有效？一是google在nature paper里没提（存疑），二是复现工作【4】尝试了不考虑任何过拟合问题在测试集上训练足够久，发现效果并不会普遍变好。

【正7】That Chip Has Sailed: A Critique of Unfounded Skepticism Around AI for Chip Design

(google on linkedin) https://arxiv.org/abs/2411.10053
这篇可以理解成google针对以上质疑，尤其是Igor Markov的【6】的愤怒的回应。其中的technical部分其实仍然是一样的，比如强调pretraining，强调convergence，觉得design不够有代表性，但是这些回应其实已经被多次重新质疑过了。
剩下的文章部分大都是情绪输出，我们略过。值得注意的是google在这篇文章，以及在linkedin上jeff dean的公开回应中，扣了好多帽子。比如【4】是deeply flawed, non-peer-reviewed，比如【6】的Markov来自Synopsys，是代表旧算法利益的相关方等等。
这篇文章也列出一个时间表，强调了AlphaChip已经多次使用于google内部的芯片设计实践中，并取得良好效果。
针对【4】，他们说【4】大范围自行实现了算法，与nature的算法不符，但这实际上是因为截至【4】发表时google还没有把核心算法真正开源，只在github上放了binary，跑不起全流程。另外他们指称【4】如果发表前多问问他们就能解决大部分问题。【4】实际上跟google team一直有紧密交流，不过可能并没有把最终文章给他们看过。
过滤掉主观判断后，可以看到正反双方的质疑和回应都“converge”了。学术界不可能像google所言完全复现google的方案，首先数据就不可能拿得到；学术界对间接复现的各种努力也不为google所承认。看来，这桩事件随着最后的【5】【6】大概率会变成一桩悬案。

本文涉及7篇相关文献，是挑选了可能争论最激烈的几篇，并不完整，但可以勾画出故事的概况。另外还有很多优秀细致的相关工作篇幅原因未全部列出，如https://arxiv.org/abs/2407.15026。另外，Samuel K. Moore发布的 https://spectrum.ieee.org/chip-design-controversy “Ending an Ugly Chapter in Chip Design: Study tries to settle a bitter disagreement over Google’s chip design AI“，也是一个相关讨论的英文评论文章，写得很好。推荐感兴趣的读者进一步阅读。

nature文章发表后，eda学术界有多篇文章跟进，对RL方法提出改进，也有很多不错的思路，发表在了eda领域和ai领域的会议上。不过这些文章都没有完全复现nature文章的结果（主要是针对传统方法的大幅改进这一claim），而是主要把nature文章当作baseline。换句话说，nature文章的有效性验证反而变得更加重要，因为这决定了eda学界整个研究方向的焦点是否准确。