面向EDA的GNN训练加速的超图划分与代表性子图选取方法

本技术涉及电子设计自动化（electronic design automation，eda）领域，特别涉及一种面向eda的gnn训练加速的超图划分与代表性子图选取方法。

背景技术：

1、随着集成电路规模呈指数级增长，物理设计阶段的布局布线迭代成本愈发高昂。在布局阶段提前准确预测线长与拥塞等关键物理指标，对于指导布局优化、减少设计违例以及加速整体流程收敛具有重要意义。近年来，图神经网络（graph neural networks，gnn）已成为eda任务中的核心工具 。但在处理超大规模电路时，gnn面临“邻域爆炸”和计算冗余挑战 。

2、传统图切割方法往往破坏多引脚高阶连接结构，而以hmetis、kahypar为代表的传统超图工具仅以最小化割边为目标，不感知节点在嵌入空间的语义相似性，无法保证子图在特征分布上的均衡与覆盖性，无法与下游预测任务的语义诉求对齐，导致大量算力浪费在高度相似的冗余样本训练中。因此，亟需一种面向gnn训练加速、以子图结构多样性与语义连贯性为优化导向的高效超图划分与子图选取方法。

技术实现思路

1、本发明提供一种面向eda的gnn训练加速的超图划分与代表性子图选取方法，旨在解决现有技术中超图划分运算复杂度高、子图语义连贯性差、训练样本冗余度大等问题，在不显著损失下游gnn预测精度的前提下，大幅降低训练时间。

2、实现本发明目的的技术解决方案为：

3、一种面向eda的gnn训练加速的超图划分与代表性子图选取方法，包括：

4、步骤1：将用于gnn训练的训练图对应的电路超图展开为节点-超边二部图，并以csr格式存储两组邻接索引，基于超图随机游走策略在csr结构上执行节点-超边-节点的两阶段随机游走，构建正样本对集合，从电路超图的节点集合中随机采样节点构建负样本集合；

5、步骤2：构建节点编码器，基于正样本对集合和负样本集合进行节点编码器的自监督训练，训练收敛后，输出超图全部节点的的嵌入矩阵；

6、步骤3：基于binpack容量约束贪心算法，对超图全部节点的的嵌入矩阵进行聚类划分，输出电路超图的节点分区标签，代表超图的划分结果；

7、步骤4：根据节点分区标签，按训练图的连接关系为每个分区重建出包含其全部相关节点、边及特征的训练子图，得到k个训练子图数据；

8、步骤5：通过编码与全局均值池化将每个训练子图映射为图级嵌入向量，通过k-center greedy算法对图级嵌入向量进行处理，输出包含s个代表性子图的训练样本集，面向eda领域的gnn训练。

9、进一步地，所述步骤1中电路超图，其中表示超图节点，表示超边。

10、进一步地，对于net级线长预测任务，超图节点为线网节点，超边为逻辑门节点；对于gate级拥塞预测任务，超图节点为引脚节点与i/o引脚节点，超边为线网超边与逻辑门超边，两组邻接索引包括索引节点到所属超边的邻接索引，以及索引超边到所含节点的邻接索。

11、进一步地，基于超图随机游走策略在csr结构上执行节点-超边-节点的两阶段随机游走，构建正样本对集合，具体包括：对每个节点执行多次独立的两阶段随机游走，每一次先从当前节点所属的超边集合中均匀采样一条超边，再从该超边所包含的节点集合中均匀采样下一个节点，获得长度为预设值的游走序列，游走窗口遍历游走序列，游走窗口内共现的节点对构成正样本对集合。

12、进一步地，所述步骤2中节点编码器由双路mlp和可学习位置嵌入三个并行分支构成，其中：

13、第一分支设置两层线性变换，以prelu为激活函数；

14、第二分支的结构与路径a结构相同，参数独立，另外设定两层mlp；

15、第三分支嵌入设定一个可学习的位置嵌入矩阵，为每个节点分配独立的可训练向量，直接从位置嵌入矩阵中按节点全局索引查表获取。

16、进一步地，所述步骤2中节点编码器采用infonce对比损失为优化目标进行自监督训练；所述infonce对比损失为：

17、

18、其中，为训练批次，为正样本集，为负样本集，、分别为第i个正样本、第p个负样本经过三个并行分支的输出逐元素相加后经 l2 归一化得到的嵌入特征，为温度系数。

19、进一步地，所述步骤2中节点编码器按照批次训练，并引入全局嵌入缓存矩阵机制：所述全局嵌入缓存矩阵的行索引与超图节点索引一一对应，的第i行存储节点在当前模型参数下的嵌入向量，每轮训练开始时，将各节点的嵌入向量按全局索引写入全局嵌入缓存矩阵对应行，对所述全局嵌入缓存矩阵进行一次全量初始化，每个批次梯度更新后立即对全图节点执行一次完整的前向推断，以当前模型参数刷新所述；训练过程中以负样本集合中节点索引为键，从全局嵌入缓存矩阵中按行查表，获取对应的负样本嵌入，参与infonce对比损失计算并反向传播，采用adam优化器更新所有参数后更新。

20、进一步地，所述步骤3中binpack容量约束贪心算法是基于容量约束的均匀划分，以节点嵌入矩阵为输入，首先调用k-means聚类算法将全部节点聚类为k组，获得语义上连贯的聚类中心；随后为每个节点查询其最近的个候选分区，构造候选距离矩阵，将全部个候选分配对按距离在全局升序排列，依序将节点分配到满足容量约束的最近分区，最终输出长度为n的节点分区标签向量。

21、进一步地，各分区容量上限：

22、

23、其中为平衡系数，为向上取整，为各分区容量上限，各分区容量约束为：要求任意分区的节点数不超过理想均匀大小的倍数，=1.05。

24、进一步地，在所述步骤4中，以步骤3得到的节点分区标签向量和原始训练图数据为输入，对分区标签为的超图节点作为核心节点集先进行分配，再依据原始训练图的连接关系收集与所述核心节点集相关联的其他类型节点、边及对应特征，构造出可直接用于下游gnn训练的完整子图，最终输出k个独立的训练子图的集合。

25、进一步地，所述步骤5具体包括：首先对每个训练子图的节点进行特征编码，然后经全局均值池化得到每个子图的图级嵌入向量，进而得到子图嵌入矩阵，其第行即为；随后随机选取初始中心，通过k-center greedy算法，以minimax覆盖准则迭代选取距当前已选中心集合最远的子图作为新中心，直至选满目标数量s，输出包含s个代表性子图的训练样本集。

26、本技术采用 k-center greedy算法求解上述问题，其算法流程为：每次迭代均选取距当前已选中心集合最远的子图作为新中心，直至选满s个为止。具体步骤5的流程为：输入子图嵌入矩阵 ；目标选取数量s，初始化初始中心和，再初始化最小距离向量。遍历所有子图，计算所有子图到最新中心 的欧氏距离，选取距当前中心集合最远的子图作为新中心，多次循环后最后输出核心集索引集合 ，作为训练集。算法的关键在于增量式距离更新：第步无需重新计算所有子图到全部已选中心的距离，只需将各子图到最新中心的距离与上一步维护的取最小值，即比较到前个中心的最小距离，即可在的时间内完成本步更新，从而将整体复杂度控制在。

27、本技术的有益效果在于：第一，采用基于超图随机游走的对比表示学习驱动划分，使节点嵌入捕获超图局部结构语义，保证后续划分子图内部的语义连贯性，克服了hmetis、kahypar等传统超图划分工具仅以最小化割边为目标、不感知节点语义相似性的局限；第二，基于binpack容量约束的贪心划分算法整体时间复杂度对节点规模保持线性，放弃了传统fm细化步骤的反复迭代，在保证划分严格均衡的同时显著提升运算效率；第三，引入全局嵌入缓存机制，有效解决对比学习中批次外负样本嵌入的时效性问题，使训练更加稳定；第四，k-center greedy核心集策略剔除结构冗余样本，以最小训练成本获得最大结构多样性。实验表明，本方法在线长预测与拥塞预测两类eda任务上，均可显著降低训练时间，且预测精度与全量训练基准基本持平。