技术征文第8期：图分割算法（国微思尔芯篇）--西安电子科技大学-“308A”队

一、背景

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

二、团队介绍

队伍名称：308A

队伍成员：李本正、汤正光、何析逸

所在学校：西安电子科技大学

所获奖项：

2020第二届集成电路EDA设计精英挑战赛全国总决赛麒麟杯

三、指导老师

游海龙，博士，美国佐治亚理工学院博士后，西安电子科技大学微电子教授，兼聘西电管理科学与工程学科研究生导师，西电-国微EDA研究院副院长，西安市系统芯片与微系统重点实验室副主任。游海龙教授主要研究方向为集成电路可靠性与设计自动化，长期从事半导体制造过程控制、集成电路设计自动化与可靠性设计等关键技术研究。2005年至今，主持包括国家自然科学基金、科技部专项等省部级课题二十余项，科研经费超过1500万。在权威学术期刊与国际会议上发表论文30余篇，其中被SCI、EI、ISTP检索二十余篇；出版三部专著和教材。

祁仲冬，博士，西安电子科技大学微电子学院准聘副教授。分别于2009年和2015年在清华大学计算机科学与技术系获得学士和博士学位，2015年至2017年在加州大学河滨分校从事博士后研究。祁仲冬老师研究方向为超大规模集成电路物理设计中的算法和建模问题，以及人工智能应用。已发表国际期刊和会议论文10篇，并获得ICCAD 2014最佳论文提名，对于电子设计自动化邻域中的布线拥塞问题，首次提出基于机器学习的拥塞建模方法，显著提升了模型的准确性和建模的自动化程度，并使芯片布线的质量和收敛性得到较大提升。

四、赛题介绍

本作品的题目是由国微思尔芯在2020年集成电路EDA设计精英挑战赛中进行命制，题目为：图分割算法（数字集成电路设计方向）

国微思尔芯（S2C）自2004年成立以来始终专注于集成电路EDA领域。作为业内知名的EDA解决方案专家，公司业务聚焦于数字芯片的前端验证，已与超过500家国内外企业建立了良好的合作关系，服务于人工智能、超级计算、图像处理、数据存储、信号处理等数字电路设计功能的实现，广泛应用于物联网、云计算、5G通信、智慧医疗、汽车电子等终端领域。

国微思尔芯在EDA领域的技术实力受到了业界的广泛认可，通过多年耕耘，已在原型验证领域构筑了技术与市场的双领先优势。并参与了我国EDA团体标准的制定，承担了多项国家及地方重大科研项目。

五、作品分享

1、作品背景

随着计算技术的发展，大数据时代的到来，超大规模图的分割问题越来越引起人们的关注，并被广泛应用于大数据处理的各个领域，如分布式计算问题划分、推荐策略、布局等。典型应用有超大规模数字集成电路仿真验证中的多FPGA系统分割，通过不同的分组权重将电路分割成若干分组，进而实现快速高效的系统验证。

2、题目要求

对给定的数字集成电路门级电路的网表文件（已进行图论建模）进行不同模式的划分，将节点分割到若干个分组。在保证整个图拓扑结构不变和满足约束条件的情况下，要求每个分组之间互联线数目尽可能少。

3、作品

我们算法的流程框图如下：

算法首先解析输入数据，简单判断是否存在可行解，之后对相同的线网进行权重相加并去重。接着我们的多级划分算法会将节点进行多级聚类、划分、改善操作。针对于不同的分割模式，这些操作的具体实现会有所不同。最终将每个节点分配到具体的FPGA上，并生成分配方案报告。

在聚类阶段，一些相关性强的节点会聚集成团，从而减少节点团的数目，方便后续的划分操作。聚类算法采用了一种多级模式，每一级聚类会将节点团数目减小一半。当团的总数不再发生变化或者总数足够小时，聚类算法将会终止。

初始划分时我们将粗略地把所有聚类生成的团节点分配到FPGA上。首先我们会计算出每个团与每个FPGA上已经固定的节点的线网权重总和。之后将每个与FPGA相连的团分配到其权重和最大的FPGA上。上述操作会进行多次，直至所有的节点都被分配到特定的FPGA中为止。

在多级改善阶段，总体方法是根据多级聚类形成的结果，每一级的划分结果会投射到下一级进行改善，即每个节点的子节点会继承根节点的划分进行改善，直到改善完原图。

4、作品创新点

在一些跟划分算法相关的文献中，时序驱动的因素包括触发器驱动约束、时钟约束、资源平衡约束在内的约束则极少被考虑。我们针对每种约束要求提出了各自的解决方法。能够在不提高时间和空间复杂度的前提下尽力去寻找满足约束的可行解。并且在保持不破坏约束条件的基础下，比默认模式增加尽量少的cutsize。实验结果表明我们的算法有效的避免了约束规则违反，并且结果仅比无约束情况变差了1%左右。

5、问题及解决方法

我们遇到的最大的问题是对题目里面一些时序驱动的约束规则的理解。

解决方法是积极和命题单位的答疑人员沟通，搞清楚这些规则及其相应的背景。

六、团队采访

1、赛前准备

赛前需要提前准备以及了解EDA领域算法，并且可以多参加同类型竞赛积累经验，本团队成员先后在第一届EDA精英挑战赛、ISPD以及ICCAD竞赛中获奖，在这些竞赛经历中可以不断培养我们的团队合作能力以及编码能力。当然，如果是之前没怎么接触过这个领域的团队，也可以在比赛完成作品的过程中边学习边实践，选择EDA精英挑战赛每年给出的赛题连续参赛，到现场与获奖大佬、企业交流，相信这样一定可以使大家更快地提高。

2、如何选择赛题

建议大家选择赛题尽量选与自己原本研究方向相关的和有一定的初步思路的，这样比较有动力来高质量的完成赛题。对于刚接触EDA的同学可以选择一些规则比较简单的题目和赛方提供部分代码或者有开源项目的题目，相对比较容易上手。

另外比较重要的一点是结合官方邀请专家对赛题做出的赛题分析，以及建议提前对相关工作论文进行调研，对赛题要求做什么，怎么做有个大致的认知，避免盲目。

3、工作计划安排

在开始实现的1-2周内，首先最重要的是对赛题的理解，然后确定整体框架以及代码统一标准，并且可以先实现一个最基础的功能，如果赛题有多个要求，可以先实现其中最基础的部分；

第二步工作主要就是要往框架中补充和完善内容，如果赛题各个任务是较为分离的可以团队拆分任务不同人进行实现，如果赛题要求是整体的，可以先准备多组方案，团队成员同步进行实现，实现完成之后对比性能进行选择；

最后进行性能提高以及创新点实现，在完成赛题所有要求基础上，进一步对算法时间空间复杂度进行优化，结合赛题特点提出自己的创新点并加以实现。

4、参赛记忆

比赛结束前一天晚上，我们被告知第二天早上要去参加路演，然后我们就赶回酒店去做准备。路演时间比封闭答辩短很多，最初的PPT被老师批评说完全不行。于是我们就跟着老师一起推倒重来，做了一份全新的ppt，每个细节都修改打磨了好久，再加上演练，一直工作到凌晨4点才睡觉。在短时间的展示中得到专家的认可和我平时接触的学术报告真的很不一样，这对我们而言是一次很好的锻炼。

为了完成赛题，我们查阅了很多相关的资料，也有深刻的思考和讨论，所以通过大赛我们获得了赛题相关的一个新的科研课题，相信把比赛中的成果进一步加工后能产生一篇不错的论文。同时这个解决问题的过程对我们的科研能力也是一次很好的锻炼，相信我们获得的奖项对将来求职也能带来一定的帮助。