第六届研究生创芯大赛华为企业命题-ASIC芯片物理设计中的PathGroup规划算法

FrWalker2023-08-302023-08-30

研究生创芯大赛由教育部学位管理与研究生教育司指导，中国学位与研究生教育学会主办，是研究生创新实践系列赛事之一。所参加赛道的题目是华为企业命题赛题十一——ASIC芯片物理设计中的PathGroup规划算法，上机题选的是EDA方向,获得了大赛二等奖和华为专项二等奖,仅以此文进行记录。

题目

描述及要求

Netlist是ASIC芯片物理设计的输入件，其中定义了数以百万计的standard cell之间的连接情况。物理设计EDA工具会基于netlist完成standard cell的placement、routing以及PPA优化等任务。其中，定义path group是一种常见的PPA优化方法，它通过识别设计中的关键时序路径，定义关键时序路径在时序优化过程中的权重分级，引导工具的优化。具体来说，为了定义path group，需要给定一条或一组时序路径的起点寄存器和终点寄存器（多个寄存器可借助通配符*表达）以及该path group的优化权重。通常path group需要根据placement阶段后的时序情况来定义，将时序较差的若干路径设置为高权重的path group，具体操作中需要多次迭代与试错，效率较低。因此本课题希望能够寻找一种方法，基于原始的netlist文件，通过图论领域中的路径搜索、partition、连接复杂度分析等算法，在物理设计前发现设计中的潜在时序路径瓶颈，并形成path group约束传递到EDA工具中，以期引导工具达成更好的QoR结果。

要求1：在给定的测试集上，完成netlist网表到图数据（由节点和边以及相关属性组成）的转换。
要求2：在由上一步建模得到的图上，搜索寄存器到寄存器的时序路径、用适当的方式表征路径时序风险、按照时序风险对时序路径进行排序并完成时序关键路径的识别（以上可以只精确到路径的起点和终点）。可利用路径经过的节点数、每个节点的入度、出度或者其他合理方式表征路径的时序情况。
要求3：能够基于图上的时序情况预估结果，形成EDA工具可读的path group约束，并根据时序的瓶颈程度进行分级。即最终需要给出各path group的起点、终点和优化权重/优先级。
说明1：除精确算法，也鼓励使用启发式算法，做好预测精度与算法资源开销的平衡。
说明2：鼓励同学结合自身独特的背景和知识结构，跳出题目给出的提示，理解算法的最终目标，创造性地解决问题。
说明3：group path的权重分级有10个分档，权重分别为1到10.

评审得分点

1.算法效率。给出以大O符号表示的各阶段算法时间复杂度，以及各阶段算法在测试集上的实际运行时间。各阶段包括但不限于netlist到图的转化，以及在图上搜索寄存器到寄存器间路径长度的算法等。
2.硬件资源开销，内存资源开销越小越好。尽量给出以大O符号表示的各阶段算法空间复杂度，以及各阶段算法在测试集上的实际平均内存占用和峰值内存占用。如果算法对特殊内存空间有显著开销，例如递归算法与栈空间的开销，还应给出这部分的空间复杂度和执行过程中的实际开销。
3.路径瓶颈预测精度，预测到的瓶颈点与真实瓶颈点的相符性越高越好

输出要求

1.算法设计文档、代码与编译脚本，编程语言不限，可以调用开源组件。
2.在测试用例上的运行结果，要求至少以文本形式输出设计中按时序风险严重程度的起点寄存器与终点寄存器对，以及对应的group path约束文件。要求覆盖设计中的所有寄存器。

算法设计

作品基于经典的BFS路径搜索算法、数据结构两个方面进行，并提出了自己的数据划分和缓存方法，有效解决了广度优先搜索耗时长、效率低的问题。保留准确率优势的同时，加快了数据查找和访问的速度，并且可以在秒级的时间内完成寄存器到寄存器最长路径的搜索。

主体流程

算法主体流程

具体实现

1.结合邻接表和邻接矩阵两种数据结构，邻接表的头节点由数组改为哈希表进行存储，从而将netlist文件转换为图数据结构。
2.根据wire连接线的前三个字母组成一个community的名字。如右图所见，U10的输出端连接了n2132，U11的输入端连接了n2132，即U10和U11均加入名为n21的community中。在建图时，U10在搜索下一个节点时仅需搜索n21 community中的器件，并不需要遍历所有的数据，这极大提升了搜索速度，降低了建图所需要的时间。
3.基于BFS算法，加入了停止搜索的条件，当搜索到寄存器时停止继续搜索该支路的器件。