命题单位：北京华大九天软件有限公司

　　北京华大九天软件有限公司（简称“华大九天”）成立于2009年，致力于面向泛半导体行业提供一站式 EDA及相关服务，是目前国内规模最大、技术实力最强的EDA龙头企业。

　　在EDA方面，华大九天可提供模拟/数模混合IC设计全流程解决方案、数字SoC IC设计与优化解决方案、晶圆制造专用EDA工具和平板显示设计（FPD）全流程解决方案，拥有多项全球独创的领先技术。围绕EDA提供的相关服务包括设计服务及晶圆制造工程服务，其中晶圆制造工程服务包括PDK开发、模型提取以及良率提升大数据分析等。华大九天总部位于北京，在南京、成都和深圳设有全资子公司，并在上海、日本、韩国、东南亚等地设有分支机构。

　　一、需要具备哪些专业背景和基础知识？

　　该赛题经过抽象，基本没有门槛

　　·只要学过编程，不限C/C++/Python；

　　·只要学过初中几何，有一定抽象思维能力；

　　·不限任何专业背景，玩过俄罗斯方块的同学可能更具优势。

　　二、赛题背景

　　在芯片设计、制造等过程中，常常遇到模块拼接的情形， 即对于给定数目的多个不同形状和尺寸的芯片版图（模块），根 据给定规则，对其进行合理摆放，使得组合而成的矩形区域面积最小b体育官网入口。这个背景来源于多芯片的 MPW 拼接成一个曝光面积矩形（称为一次 shot，即光刻机进行一次曝光的面积大小），需要求出最小的曝光面积，对于晶圆的利用率则最高。 在带有连接关系的版图自动布局布线中，其结果好坏的指标计算时间很长，对问题的求解形成障碍。求解方案需要考虑时间 代价b体育官网。而人工版图拼接的工作量负担沉重、且无论对于以上那种情形，利用率均难达最优。急需自动生成版图拼接技术。该需求可以扩展到其他有关 AI Placement 的应用，前景十分广泛。

　　三、赛题描述

　　（大白话版）

　　给定N个不同形状的多边形和一些拼接规则，要求放进一个长方形区域中，求能容纳所有多边形的最小长方形面积。

　　拼接规则请参考官方正式版赛题描述。

　　（正式版）

　　请参考官方链接：http://eda.icisc.cn/download/index?type=2

　　四、赛题解析

　　相信大家从小都玩过俄罗斯方块（Tetris），这道赛题的本质与俄罗斯方块游戏类似。通过旋转、交换顺序等方式，减少拼接面积。因此，该赛题可以理解为开发一个俄罗斯方块游戏的AI玩家。

　　此外，两个问题最大的不同是，俄罗斯方块游戏中的多边形是一个一个到达的（online形式），该赛题中所有多边形的形状、尺寸在一开始都已经给定（offline形式）。

　　解题思路：

　　赛题没有标准答案，这里的解题思路并非限制同学们的思路，请大家在实战中尽情发挥。

　　思路一：动态规划

　　参考早期Floorplan中的Stockmeyer算法，假设Slicing结构，简化拼接规则，

　　“Optimal Orientation of Cells in Slicing floorplan Designs” L. Stockmeyer, Information and Control 57(1983), 91-101b体育

　　请同学们自行拓展到该赛题的实际问题中。

　　Figure 1 动态规划中只保留非冗余解（摘自UT Austin David Pan教授EE382V物理设计课程）

　　思路二：强化学习

　　参考谷歌基于强化学习的Macro布局思路（https://arxiv.org/abs/2004.10746），假设长方形区域是一个棋盘，一个一个摆放多边形，把最终最小覆盖所有多边形的长方形面积当作奖励，训练智能体。

　　（Figure 2 强化学习智能体预测摆放位置）

　　赛题解析老师简介：

　　林亦波，北京大学高能效计算与应用中心助理教授。2013年毕业于上海交通大学微电子系，获得理学学士学位。此后分别于2017年和2018年在美国德克萨斯大学奥斯汀分校电子与计算机工程系获得硕士和博士学位。2019年6月加入北京大学信息科学技术学院。他曾获2020年国际物理设计专题研讨会（ISPD）、2019年设计自动化大会（DAC）、2018年Integration期刊、2016年SPIEAdvanced Lithography会议的最佳论文奖bsport。他目前的研究兴趣包括基于机器学习的设计自动化算法以及GPU/FPGA加速。