A Comprehensive Survey on Electronic Design Automation and Graph Neural Networks: Theory and Applications

原文：doi:10.1145/3543853 · Sánchez et al., TODAES 2023

1. Background

Modern EDA work flow:

传统的基于启发式搜索或者其他求解器的方法求解的都是 NP 完全问题，实际表现差，用 ML 方法更好。在逻辑综合、器件放置、布线、测试、验证等环节都已经引入了机器学习方法，这些环节用传统方法都非常耗时。电路本质也是一种图，传统机器学习方法处理图都先要对图做 Graph embedding，实现输入的降维和规模限制。典型基于 random walk 的 embedding 方法在一般任务上表现良好，但是当输入规模很大的时候同样非常耗性能，并且这种 embedding 忽略了原始图的结构，也不能学习到新的结点类型。提出图神经网络，将图的邻接矩阵直接作为系统的输入，旨在最大程度地保留图的整体结构信息，对处理图结构的数据应当会有更优秀的效果。

2. Classification

任务上：

技术上：

2.1. Recurrent Graph Neural Networks

图上的循环神经网络。按照图的连接交换信息更新节点状态， $t$ 时刻节点 $u$ 的隐藏向量 $h^t_u$ 可以表示为_：_

h^t_u=\sum_{v \in N(u)} \phi(x_u, x^e{u,v},x_v,h_v^{(t-1)})

即节点 $t$ 时刻隐藏向量的状态分别和节点的特征向量 $x_u$ 、相邻节点的特征向量 $x_v$ 、相邻边的特征向量 $x^e{(u,v)}$ 以及上一时刻的隐藏向量 $h_v^{(t-1)}$ 有关。按上述方法迭代到收敛状态，但是有的时候达不到收敛的状态，所以会设置一个迭代总次数上限 $T$ 。

2.2. Convolutional Graph Neural Networks

卷积图神经网络，可以从频域角度理解或者从空域角度理解。频域上来说，图不具有平移不变性，所以可以把卷积认为是做傅里叶变换的过程，在时域上的卷积可以看做在频域上的相乘。频域方法都是基于拉普拉斯特征的。空域的方法和在图像上做卷积类似，只是要注意图中的卷积核的 “大小” 和图像中不一样，并不是固定的。

2.2.1. GCN

h_v=f(\frac{1}{|N(v)|}\sum_u\in N(v) Wx_u+b), \forall u \in V.

聚合相邻节点特征，做线性变换。若堆叠多层就变成：

h_v^{k+1}=f(\frac{1}{|N(v)|}\sum_u\in N(v) W^kh_u^k+b^k), \forall u \in V.

缺点：

一次要读入整个图，耗显存，处理不了大图
transductive，只能处理训练中见过的节点类型

2.2.2. GraphSAGE

训练时只保留样本之间的边，包含 Sample 和 Aggregate 两个步骤。Sample 指如何对相邻节点的个数进行采样，Aggregate 指获得相邻节点的 embedding 之后如何更新自己的 embedding。 Sample: 对于一个节点，从它相邻的节点中选择 $S_1$ 个，假设采样深度为 $K$ ，还要对选择的节点再进行 $K$ 次相同的采样。这种选择时有放回的，要保证每个节点采样后的邻居数量一致，拼接成了定长的 Tensor。 Aggregate: 分为 Mean Aggregator、LSTM Aggregator 和 Pooling Aggregator。其中 Mean Aggregator 可以写作：

H^{l+1}u=\phi([W^l\sum{v\in N(u)} \frac{h_v^l}{|N(u)|}||B^lh_u^l])

和 GCN 的做法基本一致，所以也可以分类到卷积图神经网络中。LSTM Aggregator 就是对邻居按照一个随机排列组成的 tensor 做 LSTM。Pooling Aggregator 可以写作：

AGGREGATE^{pool}k=max({\sigma(W{pool}h^k_{u_i}+b)},\forall u_i\in N(v))

通过学习节点的 embedding，模型变成了 inductive 的，并且通过假设相邻节点的 embedding 应当相似还可以转化成无监督的学习。

2.2.3. GAT

为了给相邻节点之间的权重不同，借鉴类似 Transformer 的方法加入 self-attention 机制，写作：

h_u^{l+1}=\phi(\sum_{v\in N(u)}\alpha_{(u,v)}^lz_v^l)

同样可以引入多头的 self-attention。

2.3. Graph Autoencoders

无监督，主要在图表示学习和图生成工作应用的比较多。Encoder-Decoder 结构，Encoder 一般是之前的 ConvGNN 或者 RecGNN，将图转换低维的包含结点结构信息的向量，输入到 Decoder 中。Decoder 通过向量重建图的邻接矩阵表示，学习中要损失函数计算的重建图和原图之间的距离。

2.4. Spatial-Temporal Graph Neural Networks

输入的图是随时间变化的序列，一般方法是建模描述动态节点输入，并且要假设相邻节点之间的相互依赖性。

3. GNN for EDA

3.1. Logic Synthesis

D-SAGE 预测的是 HLS 部署到 FGPA 上之后的 delay，然后预测 node 是部署到 DSP 上还是 Lookup Table 里面，edge 连接的两个点是否部署在相同的设备上。逻辑综合主要包括哪些步骤？需要后续的学习

3.2. Verification and Signoff

GRANNITE 预测的是 toggle rate，电平变化的速率，关注的还是结果质量方向的问题。

3.3. Floorplanning

在设计规则的约束下把网表转换为元器件 2D grid，马尔可夫过程，适合用 RL。

3.4. Placement

RL 为主，引入 GraphSAGE 和 GCN 帮助提取图特征的也有。

3.5. Routing

从非欧的图连接转换为符合要求、分数最高的 2D 布线方案。方法比较丰富，有直接产生布线的，也有在布线优化中产生转角关节的。

3.6. Testing

测试的时候不仅要观察最终结果，还需要观察中间过程，但是没有办法直接观察整个电路的工作情况，所以测试的时候需要添加测试点。测试点的选取完全是经验性的，并且添加过多的测试点也会很耗时费力。一种基于 GCN 的方法将结点分类为是否容易观察到错误两种，保证生成测试点的数量尽可能少的情况下能覆盖大部分错误。

3.7. Reverse Engineering

主要以组件识别和 IO boundaries 分类为主。

4. Challenges

鲁棒性，可解释性，更复杂的图类型，安全性，训练耗时和数据集问题。在 EDA 领域，输入规模过大，需要额外的图种类的处理和新结构的设计。目前的数据基本是由 EDA 工具在设计过程中生成的，有时候由于生成的数据都具有相同的生成参数，可能会产生 bias 的数据。

5. Future Works

Transfer learning, Feature information, bigger datasets,…