在做完Placing后，就是Routing。Routing大致分为2步骤，Global Routing和Detail Routing。Global Routing主要是先大致做布线，让范围缩小些，接着再进行Detail Routing。现代的芯片都有很多层10-20层是基础，也就是连线可以穿越多层来进行连接，穿越的点叫做VIA。整体上是一个非常复杂的工程。

Detail Routing

Detail Routing从简单到复杂可以从单层2点-多点-多层-权重多层

单层2点

最简单的场景，只考虑一个平面，并且一个起点一个重点，不考虑fanout，算法也十分简单

1. 扩展：像石头丢进水里，从source开始，通过wavefront扩展法，直到遇到target
2. 反推：当遇到target为N，从N往前到N-1，直到回到1的source，获得path。
3. 迭代：将path置为obstacle，开始下一个source和target对
   
   
   

单层多点

接着考虑更复杂的情况，就是Gate是有fanout的，其实大致方法和单层2点是一样的
对于一组点要连接，设置一个为source，其他为targets，有N个

对于target_i有：

1. 单层2点：从source开始直到target_i -》接着反推
2. 整个路径上的点都设置为source作为下个i+1点连线的source
   当连线完N点后将全部设置为obstacle，由于最后的连线像树，我们称为steiner Tree
   
   

然而从上面算法我们会发现，target_i的顺序会影响steiner tree，我们不一定每次都会得到最优解。order的排序和我们之前讨论ROBDD一样，这是一个NP-hard的问题，因此有很多算法在解决这个问题，这里不展开。

多层多点

前面说过，芯片的连线层有非常多层，而他们是通过VIA连通上下层的，这里只讨论VIA位置已经固定的情况。

1. 单层多点算法，但是如果遇到VIA，则穿透到目标层加1后继续扩展
   
   
   然而其实我们并没有考虑到VIA设置在哪里，设置几个能够达到最优解。这课堂也没讲这部分，需要我们自己再去调研。

权重 nonuniform cost

这段说明真实的router算法如何实现，datastructor是什么

首先是算法部分，这里使用优先队列存储wavefront，让优先让cost低的地方开始扩展，其他基本就是Dijkstra算法

对于算法，我们需要记忆pathcost和pred（N）

对于数据结构，要保存cost，pred和reached：基本就是Dijkstra的变化

然而我们需要注意到一件事情，就是routing时我们会有很多的constrain，例如转弯需要加额外的cost（很容易理解，我们不太希望先弯折太多次），这样会产生第一个到达target的不一定是最优解。为此我们需要定义跑几个到target时要停止，因为我们也不可能跑完所有的可能，这样太复杂了。通常可以设置0.1*M，M为第一个到达target的路径长。这算法可以很灵活，带大家后续研究。



最后是加速我们的算法。我们发现其实扩展很多方向是不必要的（例如souce只需要往target大致的方向扩展即可，其他的扩展大概率是浪费，因此我们可以对权重进行调整。例如增加一个maze estimater的函数，对反方向的增加权重，让它在优先队列里面靠后

Global Routing

最后说的是global routing。这里给个大致的概念，因为实际业界使用的更加复杂。但原理上就是会在大尺度上先route一遍（例如格子画为200*200线宽为一格）。画出大致的路径后，缩小范围再使用Detail Router。

总结

这篇routing只讲解最基础的概念。我们跳过很多难题，例如order的排序，VIA的位置和数量设置，global routing的权重设计等