EDA布线(routers)算法简介

简介

布线总体目标

1）最小化 总线长、通孔数量、和违例的数量；

2）最小化 运行时间，最大化布线成功率。

其一般分为单层/多层布线（由通孔via连接交叉），全局（global)和详细(detailed)布线。

这里列出总体分类基本算法介绍

1、传统布线算法

传统方法分为有网格布线和无网格布线。

一般有网格布线较为容易，有均匀划分网格，和不均匀的汉娜网格（hanna grid)。

方法大致分为以下几类

1.1、基于图的方法

迷宫算法，最早是lee算法，从源点(source)开始向四周扩散，直到访问到汇点（sink)。

该方法效率低，soukup提出结合DFS和BFS进行搜索，DFS可以尽可能向终点靠拢，BFS在遇到障碍或者DFS失效时启动，增加广度探索。Dijkstra最短路径算法，更新所有节点到源点的最短路径，并找到最短的一条path.

A*算法则考虑了最短路径遍历节点的优先级，不仅有限选择当前节点到源点最近的距离，也计算当前节点到终点的距离，如此算法总是倾向于选择到终点更近的点进行访问。

这类方法都是每次从线网（nets)中选择一条拆成两端线网来进行布线，效果取决于布线顺序。

另外，算法未考虑约束（可布性、拥塞、间距），而这些约束都有滞后性，需要线网全部布线完成后，才能体现。

因此基于以上方法的工作更多在顺序布线（sequential routing)前期就考虑各种约束[1-5]。

1.2、整体布线：整数线性规划（IPL,Integer Linear Programming)

这类方法可以直接对所有线网布线（Concurrent Approach），并考虑交叉、拥塞等约束。算法提前生成端点之间可能的走线方案，并用一0-1变量表示是否选择本方案。问题随后转化为带约束的线性整数规划问题：

其中表示节点,  表示连接两节点的代价，C表示容量。

显然这类整数规划求解器规模较大，复杂度高，一般求解器Gurobi，cplex都是商用。为此，我们可以采用层次化方法（hierachical）的方法[6]，先将网格划分为粗网格，找到粗网格间的布线，然后将网格细化，对每个子模块递归求解，每次求解规模均极小。

1.3 生成树方法（spanning tree）

对于某些多端net,除拆为2端线网采用1.1方法外，一般都采用最小斯坦纳（steiner)生成树方法。比如遵守水平垂直走线的Rectilinear Steiner Minimal Tree.一般生成树算法算法非常多，比如Kruskal，prime, spanning-graph[7],edge-substitution. 另外考虑实际布线中允许45，60度走线，也有对应八向斯坦纳最小生成树（octilinear steiner)方法[8].

1.4 扩展&讨论

1. 顺序布线的顺序非常关键，一般纵横比高的、在其他net最大矩形框内Pin数量多的、关键路径的选择顺序靠前
2. 拆线重布（rip-up and re-touter):布线失败时，需要拆掉部分线重来。
3. 详细布线阶段或者特殊布线阶段，需要针对特殊场景比如channel,swithbox,采用一些特别的启发算法完成布线。另外在数字设计中，时钟树网络（clock-tree-network)也有很多特殊要求和方法，需要注意时钟延迟考虑寄生RC下其并不正比于线长。这里略去

2、并行加速布线

协商布线[9]: 暂时忽略布线之间的重叠拥塞，各组布线分别并行进行。一旦出现拥塞重叠等，则在该区域增加惩罚，使得下次迭代布线尽可能绕过此处。

区域分组：将布线区域划分为多个区域，将不相邻的net分配到不同任务组别，从而并行优化时不同任务的布线之间基本不会发生交叉拥塞。典型的布线器有TritonRoute[10]和 MCFRoute[11]

3、当前研究方法

今年机器学习大热，这类方法文献较多，这里不详列。

结合AI：比如使用AI模型预测拥塞率，在顺序布线早期阶段减少拥塞，降低时间。比如利用强化学习，自行学习走线过程。

布线-拆线：有点类似对抗生成网络思想。Alpha-PD-Router有两个玩家，布线器（router）和拆线器（cleaner）。布线器以总线长为目标布线，而拆线器则拆线重布，以使布线器布线更容易为目标，如此往复下去。

4、布线竞赛

ISPD是非常有名的布局布线竞赛，里面有很多测试集，可以参考。

本文有参考书籍《超大规模集成电路物理设计：从图分割到时许收敛》和 [13]。

参考文献

[1] MANA: A Shortest Path Maze Algorithm Under Separation and Minimum Length NAnometer Rules. IEEE TCAD, 2013

[2] Dr. CU 2.0: A Scalable Detailed Routing Framework with Correct-by-Construction Design Rule Satisfaction. ICCAD 2019

[3] Spacer-Is-Dielectric-Compliant Detailed Routing for Self-Aligned Double Patterning Lithography. DAC’2019

[4] Detailed Routing for Spacer-Is-Metal Type Self-Aligned Double/Quadruple Patterning Lithography. DAC’2015

[5] DSAR: DSA Aware Routing with Simultaneous DSA Guiding Pattern and Double Patterning Assignment. ISPD’2017

[6] Hierarchical Approach to Speed Up Integer Programming Formulation For Global Routing ，TCAD’1982

[7] Efficient steiner tree construction based on spanning graph,TCAD’04

[8] efficient octilinear steiner tree construction based on spanning graphs, ASPDAC’2004

[9] A Multithreaded Initial Detailed Routing Algorithm Considering Global Routing Guides.ICCAD’2018

[10] TritonRoute: An Initial Detailed Router for Advanced VLSI Technologies.ICCAD’2018

[11] A Multicommodity Flow-Based Detailed Router With Efficient Acceleration Techniques. TCAD’2018

[12] A Reinforcement Learning-Based Framework for Solving Physical Design Routing Problem in the Absence of Large Test Sets. MLCAD’2019

[13] VLSI 详细布线算法研究进展综述文章. 微电子学与计算机 2021

转自： https://zhuanlan.zhihu.com/p/664207835