A3-增量式时序优化算法

1. 问题背景

芯片在手机、电脑、汽车等电子设备中扮演着关键角色，芯片的时序性能控制着数据的传输速度、指令的执行时间，确保设备的高效运作和用户的流畅体验。本问题针对芯片设计的性能需求，聚焦于增量式降低芯片的时延。

时序优化问题一直是芯片设计中的一个重要问题，随着芯片集成度的不断提高，时序问题也变得越来越复杂和关键。时序优化问题的核心在于如何降低芯片的时延，以保证芯片的正常工作。在不改变网表的情况下，时序优化的常用技术包括门控大小（gate sizing）和单元移动。权衡单元的上下游负载电容，从而实现延迟的降低。

门控大小技术可以通过调整逻辑门的尺寸来减少电路路径上的延迟。具体而言，增大门尺寸可以驱动更大的负载，从而减小下游延迟。然而，增大的门尺寸，会导致其驱动单元的负载增加，从而增大上游延迟；单元移动技术可以通过重新排列电路中的逻辑单元来改善电路性能。通过将相关单元放在靠近彼此的位置，可以减少电路路径长度并降低延迟。

本问题针对布局后单元分布与走线情况，在不改变网表的情况下使用调整门控大小和单元移动等技术进行增量式时序优化，要求参赛队伍能够选取合适的算法，并尽可能采用并行等性能优化方法，提供高性能的时序优化算法。

2. 问题描述

2.1 描述

本问题中，为了简化问题，将芯片区域划分成网格，忽略网格中单元的坐标与重叠，只需满足网格内单元的总面积不超过指定的最大可容纳面积。同样的，以网格作为GCell，只需考虑二维布线，保证线网连通且每个GCell内的走线不超过指定的布线容量。如图1所示。

需要参赛队伍结合对时序优化手段的理解，设计一个C++程序，该程序应能根据问题共建方提供的解析后数据，构建合适的数据结构，并通过时序优化算法，完成对版图的优化。程序输出为优化后的布局和布线结果。图2给出了简单示例。

借助开源项目，问题共建方提供参考流程与文件解析，如图3所示（其中黄色部分需要参赛队伍进行填充设计），参赛队伍需要完成以下几点：

（1）根据问题共建方提供的解析后数据，构建合适的数据结构，兼顾高效存储与算法应用。

（2）对于单元布局，要求在不改变网表的情况下进行优化，其中门控大小调整会提供标准单元库，单元库中为每种功能的逻辑单元提供了n个size，即有n个不同的库单元实现了相同的组合逻辑功能。为了保证优化后的网表保持原有的逻辑功能，每个单元只能替换为具有相同组合逻辑功能的库单元。

（3）对于单元移动后需要更新走线情况，需要满足布线需求小于布线容量，布线需求的计算方式为通过GCell完整的track条数，布线容量的计算方式为当一根线完整地经过GCell时，将使用一根完整的track，对于未完全穿过，则简单计算为0.5根track。问题共建方会提供样例进行比对。

（4）在满足增加面积的约束基础上，进行时序优化，输出时序优化后的合法布局布线结果。

（5）使用问题共建方的时序评估工具获得评价结果，根据参赛队伍输出的走线情况，根据线长和单位RC，时序评估工具使用非线性延时模型（NLDM）和互连线Elmore计算最差/总负裕量。

本问题允许参赛队伍结合算法的具体需求，使用最多8线程进行并行加速。

2.2 问题Case

问题共建方为参赛队伍提供问题Case用于验证和优化设计的程序。下面是对所提供的文件的简单示例。

（1）网表：netlist(.v文件)

（2）初始布局：GCell单元位置信息(.def文件)

具体单元描述如下：

• Cell

对应工艺下的单元，包含形状（如宽、高）、类别标记（Gate Sizing所需）等信息。

数据（信息）获取接口：

int get_width() const; // 获取单元宽度
int get_height() const; // 获取单元高度
equivCellType get_equiv_cell_type() const; // 获取单元所属类别

• Instance

设计文件使用的单元实例，对应具体的Cell；标注连接关系（Net）所需的引脚（Pin）点，提供位置的获取和更新接口。

数据（信息）获取接口

Cell get_cell() const; // 获取工艺下对应的
Cellint get_coordi_x() const; // 获取Instance左下角横坐标
int get_coordi_y() const; // 获取Instance左下角纵坐标
void update_location(Point);

全局接口

vector `<Instance>` get_inst_list() const; // 获取设计所有单元集合
vector `<Net>` get_net_list() const; // 获取设计所有线网集合
vector `<Cell>` obtain_equiv_cells(Cell* cur_cell); // 输入当前Cell，获取同类型的Cell集合（供Gate Sizing）

（3）初始绕线

• GCell

GCell是一个矩形方格，通过GCell将版图划分为多个方格，每一层的GCell规格一样，其定义如下：

GCELLGRID [axis] [start] DO [scale_num] STEP [interval]

其中"GCELLGRID"为GCell定义的起始字段；"[axis]"为所要描述的轴方向，X和Y；"[start]"为轴开始的坐标；"[scale_num]"为轴上的坐标数量；"[interval]"为坐标之间的间隔。

在def中的示例如下：

GCELLGRID X 1200 DO 2 STEP 500
GCELLGRID X 0 DO 5 STEP 300
GCELLGRID Y 1050 DO 2 STEP 50
GCELLGRID Y 150 DO 4 STEP 300
GCELLGRID Y 0 DO 2 STEP 150

以上GCellGrid定义在版图(Die)上如下所示：

• Guide文件

Guide作为布线的结果，其单位是一个完整的GCell，Guide只需要描述routing层即可。

以net0举例，其布线结果在guide文件如下：

net0(
300 150 1200 450 M1
900 150 1200 1050 M2
900 750 1200 1050 M1)

GCell在每一层的大小分布都是一致的，通过分析guide，net0的布线结果如下：

• 开源工艺库（.tlef文件、.lef文件、.lib文件）
• sdc文件(.sdc文件)，定义需要进行时序优化的时钟。

2.3 输出文件

本问题要求参赛队伍的程序在完成时序优化之后输出优化后的单元布局和布线结果。输出文件的格式应与问题共建方提供的问题Case中输入的格式保持一致。

2.4 环境

建议参赛队伍的开发环境和运行环境，C++使用兼容C++20版本，并在Linux系统环境下进行开发。下述给出参考方式：

（1）代码下载地址：https://gitee.com/oscc-project/iEDA/tree/OS-Contest/

（2）从Dockerhub上下载，使用镜像提供的编译工具和依赖库进行项目构建。

（3）手动安装依赖并编译。

3. 评分标准

问题的所有测试案例根据网表规模分为大、中、小三类测试案例。问题从这三类测试案例中筛选并提供一部分案例给参赛队伍评估算法的质量；其余案例只作评分用途，不开放给参赛队伍。

每个测试案例有独立的评分，遵循同样的评分标准：

（1）在限制增加面积的基础上，比较最差/总负裕量的提升幅度，数值越大排名越靠前。取队伍的前10名，第一名10分，第二名9分，依此类推。

（2）输出的布局结果需要满足合法性要求（GCell内的单元面积，GCell间走线无溢出），在给定的运行时间和内存限制下运行，否则不得分。

（3）对评分案例集中的每个案例进行评分后，总得分为单个案例得分的加权求和，其中单个案例的权重系数与该案例的规模成正相关。总计分越高的队伍，排名越高。