3.1、Preprocessing

3.1.1. Symmetry constraint allocation

• 考虑给定的Symmetry constraint
• 识别layout中对称的Pin
• 对称约束的考虑： 几何约束与电气约束。

1. mirror-symmetry
2. cross-symmetry
3. self-symmetry
4. partial-symmetry
   

• 算法：
  

• 符号表
  

• 自对称度计算

1. $ne{t}_i$关于坐标$x$的对称度：$f_i(x)=\frac{\sum _k{a}_{i,k}(x)}{|P_i|}$
2. $ne{t}_i$自对称度最大的对称轴: ${\lambda }_i=\underset{1<=k,k^{{}^{\prime }}<=|P_i|}{\mathrm{argmax}}{f}_i(\frac{x_{i,k}+x_{i,k^{{}^{\prime }}}}{2})$
3. $ne{t}_i$关于${\lambda }_i$的自对称度： ${\psi }_i=f_i({\lambda }_i)$

• 相互对称度计算

1. $ne{t}_i$ 和 $ne{t}_j$关于对称轴${\lambda }_{i,j}$的对称度： ${\psi }_{i,j}=f_{i,j}({\lambda }_{i,j})$
2. $ne{t}_i$ 和 $ne{t}_j$间对称度最大的对称轴：${\lambda }_{i,j}=\underset{1<=k<=|P_i|,1<=k^{{}^{\prime }}<=|P_j|}{\mathrm{argmax}}{f}_{i,j}(\frac{x_{i,k}+x_{j,k^{{}^{\prime }}}}{2})$
3. 计算当前坐标x的对称度：$f_{i,j}(x)=\frac{max(\sum _k{b}_{i,k}^j(x),\sum _{k^{{}^{\prime }}}{b}_{j,k^{{}^{\prime }}}^i(x))}{max(|P_i|,|P_j|)}$

• 案例：
  

图a为实际版图，图b为net构建的匹配网络图，每个net作为一个顶点

1. $n_i$自对称度的计算：
   $n_1$内部在对称轴${\lambda }_i$出相互对称的pin为$[(p_{1,1},p_{1,4}),(p_{1,2},p_{1,3})]$,所以$\sum _k{a}_{1,k}(x)$=4， 而pin的总数$|P_1|$=5，计算得${\psi }_1=\frac{4}{5}$。构建匹配图边($e:v_1-v_1^{{}^{\prime }},w=\frac{4}{5})$

2. $n_i,n_j$间对称的计算
   如$n_2,n_3$, 能关于对称轴${\lambda }_{i,j}$最多大相互对称得pin为$[(p_{2,2},p_{3,2}),(p_{2,3},p_{3,3})]$,所以$max(\sum _k{b}_{2,k}^3(x),\sum _{k^{{}^{\prime }}}{b}_{3,k^{{}^{\prime }}}^2(x))=4$ , $max(|P_2|,|P_3|)=3$， 所以${\psi }_{2,3}=\frac{4}{3}$。构建匹配图的边：($e:v_2-v_3,w=\frac{4}{3}$)

3. 寻找symmetry的网络：Edmond’s blossom 算法，在构建的带权无向图中寻找最大权重匹配。然后将匹配结果转换为指定网络的对称约束。

• 时间复杂度分析：

1. 边权计算： $O(|P{|}^2)$
2. 最大权重匹配：$O(|V{|}^2|E|,|V|=2|N|,|E|<=(|N{|}^2+|N|)/2$,
   实际应用中，图$G$是稀疏的，因为$N$中的许多子集是互斥的，并且大量的$net$是自解关联的。电路层次结构将整个网络列表进一步划分为多个分区。因此，该算法的执行效率很高

• 相关定义：

1. net互斥： $n_i$ 和$n_j$间的对称度为0
2. net自解关联：$n_i$自对称度为0

2. Pin Access assignment

分析Pin的形状， 根据首选Access方向的确定Pin Access point。方便后续布线过程中的Pin的连接。

3.2、Core procedures

1. Routing

• 算法：obstacle-aware path-finding algorithm。
• 在对称轴两侧同时执行Obstacel-aware path-finding, 实现对称布线。
• 查找过程中考虑设计规则（parallel run spacing，end-of-line spacing，Min-area，Min-step）
• 无法找到路径时，进入rip-up & reroute优化迭代，直到找到可行方案。
  

2. Rip-up

• Viaolated net removal
  

3.3、Post-refinement

在布线结果中寻找违反Design rule。通过向metal shapes中增加补丁，解决Min-step违例。

参考文献：Toward Silicon-Proven Detailed Routing for Analog and Mixed-Signal Circuits