技术征文第2期：MPW版图拼接--复旦大学--“306摸鱼对”队

一、活动背景

集成电路EDA设计精英挑战赛 是国内首个EDA领域专业赛事，赛题覆盖EDA应用及算法，从本科到博士都可参赛，需具备计算机、电子、物理、数学等知识储备，对参赛队伍的要求极具综合性。通过两届大赛的举办，受到了来自产业及高校的高度关注，产业界和学术界专家反馈，参赛作品具有很好的参考和学习价值，继第一届后现选出第二届优秀作品并参与技术征文投稿的队伍作品和大家分享。

二、团队介绍

队伍名称：306摸鱼对

学校名称：复旦大学

队伍成员：陈兆庭、李铭涛 复旦大学、杨   洋

获奖情况：2020第二届集成电路EDA设计精英挑战赛全国总决赛一等奖

指导老师：严昌浩（复旦大学 教授）、杨   帆（复旦大学 教授）

三、赛题介绍

本次分享的作品题目由华大九天命制的赛题：MPW拼接-芯片设计中的俄罗斯方块问题

扫码查看第二届该赛题指南

命题企业：北京华大九天科技股份有限公司（简称“华大九天”）成立于2009年，一直聚焦于EDA工具的开发、销售及相关服务业务。主要产品包括模拟电路设计全流程EDA工具系统、数字电路设计EDA工具、平板显示电路设计全流程EDA工具系统和晶圆制造EDA工具等EDA软件产品，并围绕相关领域提供包含晶圆制造工程服务在内的各类技术开发服务。

四、作品分享

1、参赛作品背景

在IC的设计、制造等过程中，常会遇到需要拼接版图的情况：对给定数目的多个不同形状和尺寸的版图，根据给定规则，进行合理摆放，使得组合而成的矩形区域面积最小。由于人工进行版图拼接工作繁重，且无论对于以上哪种情形wafer利用率都难达最优，因此版图自动化拼接的问题亟待解决。此外，该问题还能扩展到其他有关AI Placement方面的应用，前景十分广泛。

2、作品成果

我们实现了一个智能MPW版图拼接程序，该程序读取输入文件中由顶点坐标描述的多个曼哈顿形状的数据，经算法处理，输出摆放后的图形位置文件。输出文件中的图形与输入文件中一一对应，即经过旋转或对称能互相重合，且输出文件中所有图形占据的总曝光面积会尽可能最小，同时该曝光区域（矩形）的长宽比会尽量接近1:1。

3、作品创新点

1）给出了评估拼接效果的目标函数；

2）提出了一种可行的多阶段优化拼接方案；

3）提出了样本生成算法；

4）能在多核处理器上并行加速。

4、问题及解决思路

Q：如何检测和消除图形间的重叠？

由于输入文件中描述的多边形不都是矩形，而是边均为正交方向的多边形，因此不能用简单的方法判断图形间是否存在重叠，从而给消除图形间的重叠带来了困难。

A：针对多边形之间可能出现的各种重叠情况依次检测和判断。包括检查每个顶点三角形的重心是否在另一图形内，检查每条边的中点是否在另一图形内，以及检查每条边是否与另一图形的边有垂直交叉。

Q：如何在给定的空间范围内减小曝光面积，同时尽量减小长宽比？

因为曝光的窗口一定是个矩形，所以单纯使所有图形间的平均间距减小不一定能使曝光面积最小，还要考虑到它们聚在一起后的规整程度。此外，赛题还限制了曝光面积的长宽范围，以及要求使曝光面积尽量接近正方形，这进一步增加了处理难度。

A：采用多阶段局部拼接策略，每个阶段的拼接目标不同，最终目的是使最后的版图接近正方形。四个阶段分别为简化拼接、矩形化与无效拼接解除、最大化拼接以及空隙填充。

Q：怎样折中拼接效果与拼接时间？

如果运行时间足够长，便可以对拼接效果不断优化。但要在有限时间内达到一个较好的效果具有一定的挑战。因此，在保证拼接效果的前提下，需要对程序的运行时间进行优化。

A：使用多线程技术，充分挖掘算法的并行性。

1、服务器有64个逻辑核,现在的CPU往往具有8个甚至更多逻辑核；

2、评估两个多边形的拼接价值时，多种变换相互独立，可并行执行；

3.对于输入图形较多的情形，将其分成多组并行初始化其拼接价值；

4.对其他for循环的并行加速。

Q：提供的测试样例较少，怎么办？

提供的测试样本较少，为了进一步的测试、训练和优化，需要生成更多类似的测试样本，然而待拼接多边形的数量和图形不规则性，为样本生成程序带来了较大的挑战。

A：在图形样本生成程序中，我们创新性地提出了基于点位移的多边形生成算法。该算法生成的样本初始位置分布更随机，支持生成更复杂的多边形结构，且能通过参数控制样本复杂度。

五、团队采访

1、如何选择赛题

1）先把所有赛题简要看一遍

略过不了解背景且完全没有想法的题目，不要浪费无谓的时间；如果题目比较好理解、易于上手或者看到后立刻产生了一些思路，则是可以考虑选择的题目；若某道题和你们的研究方向相近，便是最佳选择。另外，备选题数量不宜过多。

2）仔细分析可选赛题

因为是比赛，所以最重要的是分析评分标准，找到其中的关键需求和难点，这样才能把功夫用在刀刃上，才能和其他队拉开差距。然后，还要对每道备选题进行相关资料的查阅，列举能想到的解决方案。

3）对比和确认

最后确定的赛题最好满足以下要求：有框架性思路，能较快速地完成初版；在难点上有好的想法，便于和别人拉开差距；有多种方案可以尝试改进。

2、怎么分工合作

1、减少耦合

将总体任务分成相对独立的几个部分，每部分由一个人完成，这样出现问题后容易定位，且只需一个人去解决即可。因为大家的时间不好统一，这样可以最大化团队效率。

2、扬长避短

每个人尽量发挥自己的优势，降低学习成本。遇到长期解决不了的问题一定要找时间交流或者向指导老师请教。

3、队长多担当，队员齐发力

3、应该以怎样的心态参加比赛

一定要摆正心态。参赛的一般是本科生或者低年级的研究生，那么大家参加EDA竞赛的目的和初衷，应该是锻炼自己的文献阅读、查找代码然后实现小项目的准研究能力。千万不可抱有一定要获奖的心态，因为竞赛的不确定性非常大，也许稍有闪失连决赛都难以入围，而且有的队伍所在的团队可能对问题有长期研究，所以大家的起跑线可能并不一致。因此，大家最好是出于兴趣而来，能坚持把题目做完得到一个不错的结果，这个锻炼的过程才是最重要的，也是我们指导老师希望你们能收获的东西。

4、如果选题和自己（未来）的研究方向不一致怎么办

如果选题就是你未来的研究方向，那固然很好。但若选题和以后的方向无关怎么处理？我的建议是首先一定要找指导老师讨论。EDA的方向里面，从高层次综合一直到后端寄生参数提取是一个很长的链条，每一个物理问题是完全不一样的。所以，拿到问题后与指导老师讨论，可以先大致了解该问题所属的方向以及可能的解决方法。第二，要适量阅读相关的文献资料，这可以帮助你快速了解该问题传统的解决方法，但一股脑陷进文献里会浪费大量时间而收获甚微。最后，这类竞赛题通常为NP或者NPC问题的简单抽象，需要平衡好时间与性能间的关系，所以大家要找到一个合适的切入点，采用一些经验性的、新颖的方法可能会有较好的效果。

5、晋级决赛后，最后一周应该做些什么？

初赛成绩公布后距离决赛大致只有一周时间，在这样短的时间内大改算法是不明智的，也是很难出更好结果的。所以，不妨仔细研究一下评分标准，看看有什么细节可以调整。在这道题里，我们经过讨论抓住了时间和内存这两个指标，作为和非专业队伍竞争的核心目标。内存是很难优化的，因此最后一周我让他们把主要精力放在并行加速上，大概只用了一两天时间，就获得了不小的时间性能提升。