A1-布局合法化算法实现
1 问题背景
布局流程中，可以分为三个阶段处理：总体布局(Global Placement)、合法化(Legalization)、详细布局(Detailed Placement)。在全局布局中把单元放到合适的位置，忽略单元重叠。合法化则是把单元放到行上，消除单元之间的重叠。
影响布局质量的主要因素包括：
● 线长：Placement阶段可以根据利用率对面积进行适当优化。
● 功耗：在重视功耗的设计中，标准单元可以按电压分为三种(HVT,LVT,SVT)。
● 性能：标准单元位置影响CTS过程(即时钟信号的延迟)，同时也会影响线长(即数据信号的延迟)。
● 可布线性：要对局部地congestion进行评估，以确保布线成功。
● 可制造性：随着工艺地不断演进，越来越多的约束也需要在DP阶段被考虑。
2 问题描述
给定版图规格之后，设计者需要将模块和标准单元在Die内放置好。满足单元无重叠，行对齐和site对齐，最优化线长，时序，功耗，可布通性。
1、实现要求：我们对全局布局的结果进行合法化，参考iEDA已有合法化的实现方法——Abacus[1]算法中的接口设计和逻辑交互（iEDA/src/operation/iPL/source/module/legalizer/method/abacus），需要实现Tetris[2]算法或采用其他合法化方法来进行合法化。
目前iEDA项目已封装好为工厂模式，同学们需要在iEDA/src/operation/iPL/source/module/legalizer/method目录下创建tetris目录，进行Tetris算法活其他算法的实现。
● 算法约束：单元在芯片区域内；单元间无重叠。
● 算法目标：全局布局结果改变最小。
● 主要挑战：需要保证全局视野；对算法复杂度要求高。
3 输入输出
算法输入
Def文件，存放了已完成全局布局的结果，包括已经经过粗略放置的电路设计中所有单元的位置坐标等。
具体数据结构设计如下（详细请见：iEDA/src/operation/iPL/source/module/legalizer/database）：
● LGCell：合法化单元，是布局过程中的最小单位。它通常表示一个正方形或矩形的区域。
| 数据名 | 数据类型 | 数据含义 |
|---|---|---|
| _index | int32_t | 单元索引号，由外部传入 |
| _name | string | 单元名称，是工艺库中的单元名字 |
| _type | LGCELL_TYPE | 单元类型，包括：宏单元，标准单元，时序单元（时钟缓冲器或触发器）等。枚举类型：kNone, kMacro, kSequence, kStdcell |
| _width | int32_t | 单元宽度 |
| _height | int32_t | 单元高度 |
● LGInstance：一个芯片通常由多个功能模块或电路单元组成，如处理器核、存储单元、输入输出接口等。每个功能模块可以被表示为一个实例。
| 数据名 | 数据类型 | 数据含义 |
|---|---|---|
| _index | int32_t | 实例索引，对实例vector进行遍历时给每个实例添加的索引号 |
| _name | string | 实例名称 |
| _master | LGCell* | 实例所对应的主要版本或原型，在实例化过程中提供参考布局和布线信息 |
| _shape | Rectangle<int32_t> | 实例形状 |
| _orient | Orient | 描述实例方向或朝向的属性 |
| _state | LGINSTANCE_STATE | 实例状态，包括：固定单元，已放置单元，未放置单元等。枚举类型：kNone, kUnPlaced, kPlaced, kFixed |
| _belong_region | LGRegion* | 实例所属的区域 |
| _weight | double | 表示实例的权重或重要性值。通过为不同实例分配权重，可以在布局过程中引导优化工具对实例进行优化，以满足设计要求和优化目标 |
● LGInterval：区间，因macro单元等不可移动单元的存在，布局区域可能划分为多个不连续的区间。
| 数据名 | 数据类型 | 数据含义 |
|---|---|---|
| _index | int32_t | 区间索引，对区间vector进行遍历时给每个区间添加的索引号 |
| _name | string | row_index + segment_index |
| _belong_row | LGRow* | 所属行 |
| _min_x | int32_t | 表示在X轴方向上该区间的最左位置 |
| _max_x | int32_t | 表示在X轴方向上该区间的最右位置 |
● LGLayout：布局数据结构，将电路设计中的各个组件、连线和其他结构以准确位置放置在芯片上的过程。
| 数据名 | 数据类型 | 数据含义 |
|---|---|---|
| _row_num | int32_t | 布局的行的数量 |
| _dbu | int32_t | dbu是芯片设计中的一个相对单位，database_unit，其具体数值取决于所采用的芯片制造工艺和设计工具的设定，用于表示布局中的距离、尺寸和位置，相当于物理空间中的一个单位。 |
| _max_x | int32_t | 布局中的最大 X 轴坐标值 |
| _max_y | int32_t | 布局中的最大 Y 轴坐标值 |
| _row_2d_list | vector<vector<LGRow*>> | 二维列表，用于表示布局中的各个行 |
| _interval_2d_list | vector<vector<LGInterval*>> | 二维列表，用于表示布局中的各个空间间距 |
| _region_list | vector<LGRegion*> | 区域列表 |
| _cell_list | vector<LGCell*> | 单元列表 |
| _region_map | map<string, LGRegion*> | 区域映射 |
| _cell_map | map<string, LGCell*> | 单元映射 |
● LGRegion：将芯片划分成不同的区域，并为每个区域指定布局约束，以更好地管理和优化布局过程中相关实例的布置和布线
| 数据名 | 数据类型 | 数据含义 |
|---|---|---|
| _index | int32_t | 区域索引，对区域vector进行遍历时给每个区域添加的索引号 |
| _name | string | 区域名称 |
| _type | LGREGION_TYPE | 区域类型，枚举类型，包括：kNone, kFence, kGuide。Fence（围栏）是一种用于限制组件或连线在布局中的位置和范围的边界线。Guide（指导线）是一条提供布局方向和位置参考的线。 |
| _shape_list | vector<Rectangle<int32_t>> | 区域的几何形状列表 |
| _inst_list | vector<LGInstance*> | 实例列表 |
● LGSite：芯片的物理结构划分为一个网格，该网格由一系列水平和垂直方向上的单元格组成。每个单元格称为一个 site，代表了可以放置一个组件、连线或其他功能元素的特定位置。
| 数据名 | 数据类型 | 数据含义 |
|---|---|---|
| _name | string | 单元格名称 |
| _width | int32_t | 单元格宽度 |
| _height | int32_t | 单元格高度 |
● LGRow：芯片的布局中的一种横向排列方式
| 数据名 | 数据类型 | 数据含义 |
|---|---|---|
| _index | int32_t | 行索引，对行vector进行遍历时给每个行添加的索引号 |
| _name | string | 行名称 |
| _site | LGSite* | 单元格对象 |
| _site_num | int32_t | 单元格数量 |
| _coordinate | Point<int32_t> | 坐标 |
| _orient | Orient | 方位 |
● AbacusCluster：合法化聚类，当不存在overlap的时候，每个单元的最优位置就是当前位置，而当存在overlap的时候，要为每个重叠的单元分配最优位置。我们把存在重叠的这些单元的集合称为Cluster，可以对每个"Cluster"进行独立的布局和布线，以满足该集合内实例之间的约束和优化目标。
| 数据名 | 数据类型 | 数据含义 |
|---|---|---|
| _name | string | 聚类名称 |
| _inst_list | vector<LGInstance*> | 实例列表 |
| _belong_segment | LGInterval* | 聚类所属的芯片布局区间 |
| _min_x | int32_t | 表示聚类的左边界或起始位置 |
| _weight_e | double | 边缘权重，用于衡量聚类与其周围环境之间的相互作用强度 |
| _weight_q | double | 质量权重，用于评估聚类的质量或优先级 |
| _total_width | int32_t | 聚类在芯片布局中所占据的总的水平宽度。 |
| _front_cluster | LGCluster* | 指向该聚类的前一个聚类 |
| _back_cluster | LGCluster* | 指向该聚类的后一个聚类 |
● LGDatabase：合法化数据库定义
| 数据名 | 数据类型 | 数据含义 |
|---|---|---|
| _placer_db | PlacerDB* | 布局相关自定义数据库，见PlacerDB.hh |
| _shift_x | int32_t | 横坐标偏移量 |
| _shift_y | int32_t | 纵坐标偏移量 |
| _lg_layout | LGLayout* | 合法化布局对象 |
| _lgInstance_list | vector<LGInstance*> | 实例列表 |
| _lgInstance_map | map<LGInstance*, Instance*> | 合法化实例与实例映射 |
| _instance_map | map<Instance*, LGInstance*> | 实例与合法化实例映射 |
| Legalizer | 类成员 | 合法化类对象，见Legalizer.hh |
算法输出
Def文件，verilog文件，合法化后的结果，包括合法的单元的坐标等。
4 评估指标
所有单元的竖直移动距离以及未来的水平移动距离之和最小。算法设计关键在于如何减小未来的水平移动距离。评估要求如下：
● 程序在合理运行时间和内存，正常运行结束，输出Def文件，所有标准单元布局合法。
● 运行时间上限：程序运行时间超出10分钟，认为程序死循环，实现失败。
● 运行内存上限：运行内存超过 10G，实现失败。
● 对于源代码，将对如下方面进行考察：
○ 代码风格是否优美，组织架构是否清晰，可读性是否良好
○ 有无良好的模块化设计
○ 命名风格和编程规范是否良好
● 输出实验报告行文要求条理清楚，详略得当，清楚易读，内容应该包括以下几个方面：
○ 算法原理，测试结果
○ 时间 / 空间复杂度分析
○ 代码设计上其他亮点（如果有），比如架构设计，模块复用，一些最佳实践等
5 参考实现
算法1：Abacus算法（iEDA已实现该算法）
目前iEDA项目的src/operation/iPL/source/module/legalizer/method/abacus目录中实现的布局合法化算法为Abacus算法。
1、Abacus算法主要步骤如下（动态规划算法，会移动已经合法化的单元）：
●**单元分散到行**：根据单元的横坐标对各个单元进行排序。每次处理一个单元，该单元首先移动到最近的行；
●**行内合法化**：计算该单元在本行的代价，以及移动到该行的上方和下方的代价，其中约束是对每一行中所有单元进行放置，使它们的总移动最小并且不重叠。代价计算是对一行中的所有单元簇以及簇的最佳位置，依靠簇的最优位置得到簇中的每一单元的最优坐标以及簇的代价；一行中所有簇的代价为该行的总代价；
●**单元放置**：将该单元放置到代价最小的行，同时更新簇，以及该行中的所有单元的坐标根据该单元移动过来后的最优簇的坐标进行更新。
2、优缺点分析：
● 优点：质量相比Tetris有较大提升。
● 缺点：质量不够稳定，依赖遍历的顺序，当存在较大的宽度差的时候，结果显著变差，速度变慢。
3、通过iEDA运行Abacus布局合法化的方法：
（1）以gcd设计为例，采用sky130工艺运行布图规划（iFP）、扇出优化（iNO_fix_fanout）和布局（iPL）的点工具
● sky130工艺库位置：iEDA/scripts/foundry/sky130
● 运行脚本主入口：iEDA/scripts/design/sky130_gcd/run_iEDA.py
● gcd设计的网表文件：iEDA/scripts/design/sky130_gcd/result/verilog/gcd.v
● sdc约束文件：iEDA/scripts/foundry/sky130/sdc/gcd.sdc
● 运行指令：
○ 进入到iEDA工程：cd [iEDA工程父目录]/iEDA
○ 更新代码为最新代码：git pull
○ 编译构建工程：bash[build.sh](https://build.sh)
○ 复制可执行文件到样例目录：cp bin/iEDA scripts/design/sky130_gcd/
○ 进入到样例目录：cd scripts/design/sky130_gcd
○ 修改文件并注释掉23行到文件末尾的内容：vim[run_iEDA.py](https://run_iEDA.py)
○ 运行脚本：python[run_iEDA.py](https://run_iEDA.py)
○ 运行结果解析：在进行详细布局之前，会对布局合法化的结果进行检查，如果合法化失败了，则会打印"Design Instances before detail placement are not legal"，且无法执行详细布局。
算法2：Tetris算法（iEDA未实现该算法）
Tetris 算法的思想源自经典的俄罗斯方块游戏，它的目标是对各个单元找到一个适合的位置，将待放置的逻辑单元放入芯片的物理空间中。
1、Tetris算法主要步骤如下（贪心算法，不会移动已经合法化的单元）：
●**候选空间选取**：首先对所有单元按照横坐标顺序进行排列，按顺序在每一行选取最左端的一个空白区域作为候选空间。
●**单元放置**：对于每个单元，在所有候选空间中挑出最近的一个，并将该单元放入。在放置逻辑单元后，更新已占用的格子信息，标记相应的格子为已占用状态。逐个放置剩余的单元，直到所有单元都被放置。
2、优缺点分析：
● 优点：是一种启发式算法，速度很快。
● 缺点：质量不稳定，局部获得良好的结果，不保证能够找到全局最优解，但是整体结果较差。
3、运行结果：
还是以设计gcd在工艺为skywater 130nm下的执行为例：
表1 方法关键参数指标对比结果样例
| 对比项 | Abacus方法 | Tetris方法 |
|---|---|---|
| 全局布局HPWL | 10127910 | 10127910 |
| 布局合法化HPWL | 10426323 | 11276288 |
| 详细布局HPWL | 9901517 | 10214554 |
| 合法化单元移动量 | 795829 | 2183285 |
| Total Time Elapsed （s） | 0.005505 | 0.000937 |
| Average Congestion of Edges（评估布局拥塞程度的一个指标，通过计算所有边缘（网格间隙中的垂直和水平线段）上的导线密度来评估布局的拥塞程度） | 0.821588 | 0.821588 |
| Total Overflow（模拟布线查看总溢出量情况） | 49 | 49 |
| Maximal Overflow （模拟布线查看局部溢出量情况） | 18 | 18 |
| Peak BinDensity（峰值密度，≤1则无重叠） | 1 | 1 |
| Total HPWL | 9901517 | 10214554 |
| Total STWL | 10637190 | 10950590 |
| Max STWL | 431085 | 435825 |
4、算法变体：
● 行密度拓展：大于某个密度的行不选取；
● 行选取的拓展：距离开始行比较近的地方；
● 局部拓展：将整个布局区域分为k份，在局部内做合法化
算法3：其他算法
请调研其他参考文献或者自己设计。
参考文献：
[1] P. Spindler, U. Schlichtmann, and F. M. Johannes. Abacus: fast legalization of standard cell Circuits with minimal movement. In Proceedings of ACM International Symposium on Physical Design, pp. 47–53, 2008. 【Abacus】
[2] Method and system for high speed detailed placement of cells within an integrated circuit design 发明人：Dwight Hill 申请号：US09273809, 公开日期：2002.04.09. 【Tetris】
[3] E. M. Gertz and S. J. Wright. Object-oriented software for quadratic programming. ACM Transactions on Mathematical Software, 29(1), pp. 58–81, 2003.
[4] 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.
[5] 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.
[6] 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.
[7] 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, June 2017.
[8] 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.
[9] 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.
[10] 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.
6 评测排名
| 排名 | 姓名 | 院校/单位 | 评估指标结果 | 是否开源 | 开源地址 |
|---|---|---|---|---|---|
| 1 | |||||
| 2 |