学位论文笔记--Study of Routing Algorithms for PCB Design（第二章）

第二章–PCB布线原理

本章回顾了PCB布线的一些基础知识。 首先，解释了四种类型的信号网布线问题。 然后，分别讨论了两种基本的布线方法及其代表算法。 基于这些布线架构和方法，我们对PCB布线设计进行了研究。

2.1 信号网布线

在现代PCB布线设计中，由于复杂度越来越高，电子设计自动化（EDA）已被广泛用于自动化优化。 EDA是设计电子系统的一类软件工具。 它在复杂的PCB布线设计过程中高度依赖[13]。 放置过程结束后，所有网络都应在布线区域进行布线。 网络是一组应该连接的具有相同电位的引脚。 对于信号网，布线通常包括三个阶段：全局布线，详细布线和定时驱动布线。 此外，在布线过程中还会考虑一些特殊的布线问题。

2.1.1全局布线

通常，组件上的引脚应在详细布线之前进行全局布线。全局布线不布线，而仅规划连接[14]。全局布线的输入是组件和引脚的位置。 在全局布线过程中，在布线区域中临时分配网络的线段。 通常，粗网格用于表示布线区域。 网格图中的边表示可用的布线资源，用来分配网络。

全局布线旨在提供详细布线以及布线网络的位置。 通常，全局布线的目的是减少总导线长度，减少布线延迟或提高进一步详细布线的可能性。全局布线流程包括三个步骤。 首先，布线区域形成为某些区域类型，例如通道，开关盒等。 然后将网络映射到布线区域。最后分配一些交叉点。 如图2.1 [13]所示，要路由四个组件和三个网络，并且布线区域用粗网格表示。 net1，net2和net3的图解表示法在划分的布线区域中进行全局布线。

2.1.2 详细布线

全局布线后，已确定网络的布线区域。 详细布线使用此信息来确定每个网络的确切电线连接和层[14]。 在详细布线期间，将网的线段分配给特定的布线路径。 另外，在详细布线中必须考虑设计规则。详细布线旨在完成组件之间的电线连接。 通常，其目标是减少总线长，层数或布线延迟。

详细布线取决于全局布线结果，通常网络的配置不会更改。 因此，如果全局布线结果良好，则详细布线结果也将同样良好。

2.1.3 时序驱动布线

有时，由于在布线阶段要考虑互连延迟，因此需要时序驱动布线。 时序驱动路由的目的是减少最大的源漏延迟或总的依赖于负载的延迟.通常，源漏延迟由源漏线长反映，与负载有关的延迟表示为总线长[13]，我们分别在它们的名称中使用深度和成本。 因此，理想的路由树可以同时减小最大源漏线长度和总线长。 但是，在大多数情况下很难同时最小化这两个项目。

图2.3 [13]说明了最大源漏线长度和总线长的折衷。 在图中，s0是源极引脚，黑点表示接收器。 图2.3（a）中的路由树获得最小深度=8。它的最短路径树是由迪杰斯特拉算法得出的，但是，在这棵树中，成本= 20非常大。 在图2.3（b）中，路由树获得的最低成本= 13，它是由以下项构建的最小生成树（MST）的Prim算法，但是深度为13在生成树中变得更大。

图2.3（c）显示了路由树在深度和成本上的折衷，因为在实践中不希望路由树中的大成本或大深度。

2.1.4专用路由

除了全局布线，详细布线和时序驱动布线外，现代PCB布线设计中还考虑了一些特殊的布线问题。 本小节讨论了两个典型的特殊路由问题，即区域路由中的网络Net Order in Area Routing顺序和非曼哈顿路由。

Net Order in Area Routing
在某些类型的设计中，全局布线和详细布线不是分开执行的，而是区域布线直接连接信号引脚，旨在实现交叉最小化。 区域路由通常受技术，电力和几何因素[13]的约束，例如层数，信号完整性等。

布线多个网络时，区域布线中的网络顺序将影响最终布线结果和总运行时间。 通过同时最小化每个网的线长来贪心地布线多个网，可能会导致许多无法布线的网或较大的总线长。 而且，相对于两个引脚的网络，多针网络的布线复杂性增加了，这更多地取决于网络顺序。 例如，在图2.4中，有两个网络要布线。 如果我们一次布线一个网络以优化其线长，则无论是首先路由net1（图2.4（a））还是net2（图2.4（b）），由于布线区域的限制，它都可能无法布线另一个网络。 但是，如果我们不最小化每个网的线长，则可以同时布线这两个网。

因此，区域路由中的网络顺序通常是由一些路由算法预先确定的。不同的路由算法会导致不同的网络顺序。提出了将多针网分解为两针网的基于斯坦纳树的[20]-[21]算法，并利用几何准则优化网序。例如，可以根据针的x坐标对网进行排序，然后从左到右进行布线。

Non-Manhattan Routing
在传统的曼哈顿路由中，它只允许垂直和水平的线段。然而，使用对角线段可能会产生更短的线长。由于斜线段不能是任意的，一般45度或60度的线段加到水平和垂直线段上。这种布线模型通常由一个参数r来表示走线方向的数量和线段的角度。r= 2时，有四个走线方向，电线成90度，这是传统的曼哈顿走线。 当r= 3时，有六个布线方向，导线为60度，称为Y布线。 当r= 4时，有八个布线方向，导线为45度，称为X布线。 后两种路由类型是非曼哈顿路由[13]。

非曼哈顿布线模型的优势体现在总线长和通孔数量的减少上。 但是，长期的物理验证和光刻技术的局限性使得非曼哈顿布线难以实现。 因此，非曼哈顿布线模型主要用于PCB布线问题。

例如，图2.5说明了非曼哈顿迷宫路由方法。 该方法基于传统的迷宫路由算法[22]，但是在八个方向而不是四个方向上扩展节点。 它从源pin开始，并用数字1标记所有未搜索的相邻网格（图2.5（a））。 然后，它从以数字1标记的每个节点重新启动，并以数字2标记所有未搜索的相邻网格。此扩展将继续，直到达到目标引脚T为止。 最后，从目标引脚到源引脚，追溯到一条包含45度线段的路径，如图2.5（b）所示。

2.2基本布线方法

在PCB布线设计中，通常考虑基于图遍历的布线方法。图遍历以某种顺序访问图的顶点[23]。 深度优先搜索（DFS）方法和广度优先搜索（BFS）方法是解决图形相关问题的两种基本技术。 这两种方法都以某些方式构造生成树[24]。 基于它们，提出了许多布线算法。

2.2.1深度优先布线方法
DFS是一种遍历有限图的方法。 对于路由问题，它从源顶点开始，然后迭代地从当前顶点探索到未访问的邻居顶点，直到到达目标顶点或没有剩余的未探索顶点为止。或在图2.6（a）中的示例中，有限图中有六个顶点，其中包括源顶点S以及目标顶点T。 DFS从S开始，并探索其相邻顶点1和3。然后分别从1和3开始搜索到它们的下一个未访问的相邻顶点。 进行此探索，直到T到达或没有剩余未访问的顶点。 此DFS的生成树如图2.6（b）所示。 从这棵生成树中，我们可以从S到达T获得所有可能的路径。

应用DFS时，可以列出所有可能的路径。此外，该算法还有效地解决了k路径的随站问题，即[25]问题。典型的基于深度优先搜索的布线算法是彩色编码布线算法。

彩色编码布线算法
颜色编码是一种随机方法，用于在长度固定的图形中查找路径[26]-[27]。 首先用随机的颜色绘制图的顶点。 颜色的数量等于固定的长度，并且一种颜色应至少使用一次。 然后进行了改进的深度优先搜索。 找到目标长度的路径后，该过程结束。

以一个例子为例。 图2.7（a）显示了具有必需条件的网格布线问题，首先，我们用不同的数字标记所有网格（图2.7（b）），这个问题可以表示为图2.7（c）所示的图形。 该图的顶点代表网格，并且边缘显示这些网格之间的连接关系。 然后我们用五种颜色随机绘制顶点。 DFS从S开始，并反复探索未访问的邻居顶点。 如果一个顶点与先前访问的顶点具有相同的颜色，例如顶点5和1且具有相同的黄色，则将停止对该路径的探索。 如图2.7（d）所示，此过程一直持续到第一个Tis到达或没有未探索的顶点为止，然后从T到S进行追溯，并可以生成目标长度为5的布线路径（图2.7（e））。

2.2.2广度优先布线方法
BFS是遍历有限图的另一种方法。 对于路由问题，它始于源顶点vertex，然后先探索同一级别中未访问的邻居顶点，然后再探索下一级邻居。 此级别取决于当前顶点之间的距离，如果到达目标顶点或没有剩余未探索的顶点，则探索结束。 然后，它将沿访问的顶点回溯到原始源顶点。 BFS通常用于查找最短路径。 对于图2.6（a）中的同一示例，BFS以S开头，并且由于第一级中只有一个顶点（Distance = 0），因此它将探索下一级的顶点1和3。 进行此探索，直到Tis到达或没有剩余未访问的顶点。 图2.8显示了此BFS的生成树。 从此生成树中，我们可以从S到T获得最短路径。

Maze Routing Algorithm
迷宫路由算法的目的是解决网格路由问题中的最短路径[22]。它从源顶点开始，用从小到大的数字在四个方向上标记当前顶点的相邻网格。一旦到达目标顶点，过程就结束了。

例如，在图2.9中，有一个网格布线问题，需要找到从源顶点sto 目标顶点T的最短路径。在这个例子中，以黑色方块表示的障碍物也被考虑在内。该算法从沙标记所有未访问的邻居网格开始，在四个方向上标记数字1(图2.9 (a))。然后，它从每个标有1的网格重新启动，并将所有未访问的相邻网格标记为2。这种扩张一直持续到极限。最后，对从T到S进行最短路径回溯，如图2.9 (b)所示

DFS和BFS各有优缺点。尽管DFS可以找到所有的可能的路径或生成具有固定长度的路径，其时间复杂度非常大。 另一方面，BFS的运行时间很短，但是通常会消耗更多的计算机内存。 近年来，关于将BFS与DFS结合的一些研究已经开始[28]-[29]。 对于本文的研究，主要采用基于广度优先搜索的路由算法。

2.3结论

在本章中，将回顾PCB布线的一些基础知识。 首先解释了四种类型的信号网络布线问题。 然后分别讨论了两种基本的布线方法及其代表算法。在此基础上，我们提出了PCB设计的布线方法。