技术征文第1期：FPGA芯片的布局合法化（安路篇）--西南交通大学--“一个问号有三个小朋友”队

1657      2022-07-16 11:11:21

一、活动背景

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

二、团队介绍

队伍名称：一个问号有三个小朋友

所属学校：西南交通大学

队伍成员：陈锦炜 西南交通大学、张凤娇 西南交通大学、刘佳欣 西南交通大学

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

指导老师：邸志雄，博士，硕士研究生导师，西南交通大学信息学院电子工程系副系主任。CCF会员、中国图象图形学学会军民融合专委会成员、新工科联盟“可定制计算”专委会成员。师从中国科学院院士、西安电子科技大学郝跃教授，研究方向为高性能图像编解码芯片技术研究、布局布线算法研究。近年来主持国家自然科学基金青年项目、四川省科技厅项高新重点项目等纵向与横向项目，参与完成了我国自主研制的首颗宇航级高速图像压缩芯片“雅芯-天图”。主讲集成电路设计MOOC课程两门，指导学生多次获得中国研究生创芯大赛、集成电路设计EDA精英挑战赛、全国大学生集成电路创新创业大赛、全国大学生FPGA创新设计竞赛、Xilinx OpenHW等国家级学科竞赛奖项。

三、作品分享

1、赛题背景及目标

FPGA合法化优化问题数学形式

本团队算法策略： 

将条件4)从不等式约束等效为等式约束后：

1）将离散解具体化为器件对格点的使用；

2）合法化要求从相邻器件间距大于宽度变为每个格点的使用量最多为1；

3）将混合高度器件视作多个格点；

4）这样求解思路变为，对格点资源使用进行合理分配来减少器件移动。

3、算法流程

⚪ 坐标轴转换与初始排序

通过转换坐标轴将问题演化为统一高度问题。

排序规则：按照器件的左下角纵坐标、横坐标升序排序。

⚪  器件预处理

行对齐：利用器件的纵坐标与8的倍数关系移动至最近的行。

处理出界器件：将右/上边界出界的器件左/下移至最近的入界位置。

⚪ 后优化

>>器件启发式移动：

含义：在合法化的前提下,向可行位置插入。

目的：寻找剩余合法化空间中最小移动代价位置。

>>小区域器件交换：

a)在小区域内，对当前器件的位置进行交换；器件初始位置与当前位置构成二分图。

b)用Kuhn-Munkre方法求解完美匹配问题。

c)采用区域间并行策略加速匹配算法。

四、团队采访

1、团队工作介绍

⚪ 混合高度器件合法化是一个充满挑战的问题。我们将放置位置视作网格，每个网格限定容量为1，合法化的目标则是在满足网格使用量不超过容量的前提下，减少器件位移；

⚪ 实验结果显示，对于前4个case，平均运行时间在2s左右，第5个case运行时间在16s左右，器件移动得到了有效控制；

⚪ 我们复现DAC’2017相关方法，应用到该赛题中，并进行了对比，结果表明，我们的方法具有一定优越性，除此之外我们的方法能灵活扩展处理围栏区域约束。

2、如何选择赛题

在第二届EDA设计精英挑战赛中，一共有八个赛题，涉及到布局、布线、验证、仿真、测试等内容，覆盖面广，给同学们更多的选择来参与赛事。我们从以下几点出发，最终选择了赛题八-布局合法化：

1）个人（导师）研究大方向；

2）对该问题研究的基础、积累；

3）该赛题的难易程度是否超出预期；

4）对该赛题相关的数据结构、算法的认识和掌握程度。

总之，赛题不一定正好做过，极少有能直接拿“成品”参赛情况，需要我们克服困难，不断调试，尽全力完成赛题需求。

3、如何组织

1）计划安排

在完成选题、确定团队成员后，我们需要规划一个计划安排，来提升执行效率。首先我们根据初赛提交作品截止时间，做一个大致的完成目标，我们的安排如下：

（1）截止时间前一周为报告文档编写时间，即最后一周一定要达到赛题基本需求。同时在这一周前，要注意文件、脚本目录、命名规范，对算法或测试的调试、改变进行记录，以易编写文档。

（2）开始第1-2周为赛题熟悉、论文调研阶段：由一人整理赛题基本资料，弄清赛题需求，再一起讨论难点；由团队成员搜寻问题相关优秀论文，进行粗读，筛选论文，整理出论文题目清单，之后让所有成员阅读论文清单上的论文，记录并学习论文上的方法。

（3）中间的时间为赛题实现阶段，需要做好团队分工、沟通协调。

2）团队分工

（1）在1-2周的调研后，团队要先讨论、确定一种可行思路，各个模块由谁负责，函数名、参数等接口统一，同时要积极沟通，将问题及时反馈。

（2）在赛题设计初步完成后，需要不断进行调试，不同方式、思路的调试可以由团队成员分工完成。

（3）在时间允许的情况下，团队一起实现新的思路或引入现有论文对比。

3、资源推荐

为实现更好的功耗，面积，可布线性和性能的折衷，混合高度单元电路在先进技术中变得越来越流行，且随着现代电路设计的工艺和围栏区域约束，混合高度单元合法化问题变得更具挑战性。

⚪ 现已有大量论文研究该问题，如abacus及其变种方法，模拟退火、解析法、图方法等。

[1] G.Wu and C.Chu. Detailed placement algorithm for VLSI design with double-row height standard cells. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 35(9):1569–1573, September 2016.

[2] W.-K. Chow, C.-W. Pui, and E.F.Y. Young. Legalization algorithm for multiplerow height standard cell design. In Proceedings of ACM/IEEE Design Automation Conference, 2016.

[3] C.-H. Wang, Y.-Y. Wu, J. Chen, Y.-W. Chang, S.-Y. Kuo, W. Zhu, and G. Fan. An e_ective legalization algorithm for mixed-cell-height standard cells. In Proceedings of IEEE/ACM Asia and South Paci_c Design Automation Conference, 2017.

[4] Y. Lin, B. Yu, X. Xu, J.-R. Gao, N. Viswanathan, W.-H. Liu, Z. Li, C. J. Alpert, and D. Z. Pan. MrDP: multiple-row detailed placement of heterogeneous-sized cells for advanced nodes. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 7:1–7:8, 2016.

[5] J. Chen, Z. Zhu, W. Zhu, and Y.-W. Chang. Toward optimal legalization for mixed-cell-height circuit designs. In Proceedings of ACM/IEEE Design Automation Conference, 2017.

[6] H.Li,W.-K.Chow, G.Chen, E. F. Y. Young, and B. Yu. Routability-driven and fence-aware legalization for mixed-cell-height circuits. In Proceedings of ACM/IEEE Design Automation Conference, 2018.

⚪ 可以学习的课程包括《最优化方法理论》、《图论》等。

⚪ 开源合法化器：

https://github.com/jojojojojojojojojojo/Cad_Contest_C