英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
Dijkstra最短路径算法的推广及其在VLSI路由中的应用
我们推广了Dijkstra算法，用于在具有非负整数边长度的有向图中找到最短路径。我们不是标记单个顶点，而是标记分割给定图形的子图。如果涉及的子图的数量与原始图的顺序相比较小，那么我们可以实现更好的运行时间，并且限制在这些子图中的最短路径问题在计算上是容易的。作为一个应用程序，我们考虑VLSI路由问题，我们需要在具有数十亿个顶点的部分网格图中找到数百万个最短路径。在这里，我们的算法可以应用两次，一次在粗抽象中（其中标记的子图是矩形），一次在详细模型中（其中标记的子图是间隔）。使用第一种算法的结果通过面向目标的技术加速第二种算法可以大大缩短运行时间。我们使用最先进的工业芯片上的最先进的布线工具来说明这一点。
关键词：Dijkstra的算法 物理设计 VLSI路由
1.介绍
最短路径问题是最基本，最重要和研究最充分的算法问题之一。它出现在无数的实际应用中。在具有非负边长的有向图G（V（G），E（G））中求解它的基本策略是Dijkstra算法.在使用Fibonacci=堆的最快强多项式实现中它的运行时间为O（V（G）log V（G）E（G））。
已经提出了各种技术来加速Dijkstra的原始标记过程。对于无向图，可以实现整数长度的线性运行时间或者在随机设置中平均。对于在实践中出现的许多实例，图形具有一些基础几何结构，其也可以被利用以加速最短路径计算。类似地，实例可能允许自然分层分解或预处理可能揭示最短路径计算可以使用的本地信息。目标导向使用估计或下界的技术，例如Alowast;算法，首先被描述为启发式算法人工智能设置后来作为一般背景下的精确算法并结合其他技术进行了讨论。已经进行了大量的实验努力来评估这些技术的组合。看到全面概述过去几年发布的加速技术。
这里介绍的研究动机源于VLSI设计中的路由问题，其中完成整个设计过程所需的时间是要解决的最关键问题之一。在今天的实例中在这个应用程序中，必须在具有数十亿个顶点的图形中找到数百万条最短路径。因此，没有大量利用特定实例结构的算法可以导致可接受的运行时间。
VLSI路由问题的简化视图如下。在三维网格的子图中，我们寻找连接给定终端集（网）的顶点不相交的Steiner树。由于不均匀的导线宽度和距离规则，作为（离网）形状组的引脚（端子）而不是单个网格节点，以及特殊网络的额外规则，存在额外的复杂性。由于这些对本文主题的算法核心影响不大，因此我们不在此详细讨论它们（尽管我们在BonnRoute中实现，这是一个用于路由许多最复杂的工业芯片的程序，考虑所有这些约束）。
标准方法是计算全局路由首先，即在具有边缘容量的凝聚网格中包装Steiner树。在第二步中，详细路由确定实际布局，主要是通过在全局路由走廊内顺序计算最短路径，每条路径连接两个组件。像ripup-and-reroute这样的启发式方法允许修改先前的决定，如果卡住了。一些路由器有一个中间步骤（轨道分配，拥堵驱动的电线规划）在全局和详细路由之间或两个以上的粗化级别之间，但我们没有。
基本上所有详细路由器的核心问题是在必须电连接的两个金属部件之间找到最短的接线连接。这可以被建模为部分网格图中的最短路径问题（参见章节3 详情）。与实践中的许多其他应用（例如，在道路网络中找到最短路径）相比，固定静态图的昂贵预处理是减少实际查询时间的合理且有效的方法，VLSI环境中的实例图每个单路径搜索的路由不同。
传统路由器使用非常简单的Dijkstra算法（称为迷宫运行或Lee的算法）），今天常规使用几种加速技术。有些人放弃寻找最短路径（线搜索，线路扩展，瓷砖扩展但是，由于较长的路径浪费空间并且在时间和功耗方面更糟糕，我们不考虑这种放松。注意，在全局路由期间确定由于拥塞和容量约束而且由于足够的时序裕度而允许的路由路径的绕行并且在全局路由走廊中进行编码。在全局路由期间，实际上假设最终路径将接近其走廊内的最短路径。
在精确的加速方法中，目标导向的技术被广泛使用并且已被证明非常有效。的Hetzel提出通过一组相邻顶点的间隔来表示部分网格图，并在他的面向目标的Dijkstra算法版本中标记这些间隔而不是单个顶点。我们的部分工作是Hetzel算法的概括。Cong等人和李等人构建连接图，它是由所有障碍物引起的Hanan网格的一部分。邢和高考虑一个类似的图，但在该图的边缘传播分段线性函数。我们的算法也是这种方法的概括。
我们的主要想法之一是引入三个层次的层次结构。图的顶点是最低和最详细级别的元素。中间级别是顶点集的分区。因此，中间级别的元素对应于顶点集。我们不是像Dijkstra算法的原始版本那样标记单个顶点，而是标记这个中间层的元素。最后，顶层是中间层的分区，即中间层的几个顶点集是相关联的。层次结构顶层的作用是允许延迟某些标记操作。我们在中间层的元素之间执行标记操作，这些元素立即包含在顶层的相同元素中，而所有其他标注操作将被延迟。根据底层图的结构，适应性选择的层次结构和标签操作的实施，我们可以在理论上和实践中实现运行时间缩短。
我们称之为GeneralizedDijkstra的新算法以两种方式为Dijkstra算法提供了一种加速技术。首先，它可以直接应用于通过图形传播距离标签。与其他技术的主要区别在于我们的方法标记了顶点集而不是单个顶点。如果顶点可以被分组使得它们的距离可以由相对简单的距离函数表示并且更新相邻集合快速工作，则是有益的。在我们的VLSI应用中，顶点集是三维网格的一维间隔。GeneralizedDijkstra的第二个应用是面向目标的搜索。在过去的几年中，文献中讨论了确定良好下界的三种主要技术：度量相关距离，地标获得的距离和图形凝结的距离[41].本文提出的方法是另一种计算下界的方法：
在输入图的反向图的超图G,中输入从目标到所有顶点的最短距离。在这里，G,必须选择它以使其近似反映原始距离并允许顶点集的分区以便执行距离标签的快速传播。在我们的VLSI应用中，G,是表示全局路由的子图走廊，这是只有少数矩形的联合。
在节中2 我们提出了算法的通用版本。部分3 致力于我们策略的两个应用，这些应用导致所描述的VLSI应用的显着加速。在节中3.1 我们展示了如何在中间层的元素在底层三维网格图中引入二维矩形的情况下应用该算法。在节中3.2 我们解释了如何将通用框架应用于详细路由，概括了Hetzel提出的过程[17].这次中间层的元素对应于一维间隔。实验结果见4 表明我们可以显着减少VLSI路由的总体运行时间。
2.推广Dijkstra的算法
在整个部分中，G =（V（G），E（G））是具有非负整数边长c：E（G）→Z0的有向图。对于顶点u，visin;V（G），我们用dist（G，c）（u，v）表示G中从u到v的路径相对于c的最小总长度，或者
infin;如果v无法从u到达。对于给定的非空源集SSV（G），我们定义函数d：V（G）→cup;{infin;}
D（V）：＝DIST（G，C）（S，V）：＝min DIS1T（G，1C）（S，V）S s
对于visin;V（G）。如果我们给出目标集Tsube;V（G），我们想要计算距离
D（t）：＝DIST（G，C）（S，T）：1＝min 1D（t）T t
我们不是用距离相关的值标记单个顶点，而是用距离相关函数标记由顶点子集引起的G的子图。因此，我们假设给出V的V（G）的不相交子集和V的子集S和T的集合V，使得
V (G) = Uisin;V U, S =Uisin;S U and T = Uisin;T U.
我们要求图G与V（G）：= V和
E(G) := (U,)exist;uisin;U, uisin;U ,(u, u )isin; E(G)c-(u, u )= 0
是非循环的。（注意，我们不需要为G假设这个。此外，人们总是可以通过收缩V（G）的强连通分量得到这个属性，{eisin;E（G）：c（e）= 0}。）因此，存在拓扑顺序V 1，V 2，...，lt;i，如果（Vi，V j）isin;E（G）。对于Uisin;V，我们将U的索引定义为I（U）= i iff U = Vi 。
我们希望利用图G的特定结构并区分两种不同的标记操作。为此，我们还需要将V分区为N1设置V1，...，Vn ，称为块，函数B：V→{V1，... ，Vn}
这样得到
我们的算法GeneralizedDijkstra的核心思想如下：我们区分顶点集U的两个操作 选择它来标记其邻居：U直接更新同一块内的相邻集合isin;，并将标记操作注册到不同块中的顶点集合以供以后使用。这种方法有两个优点：首先，如果在处理注册的操作之前达到目标顶点，则可能永远不必执行许多注册的标记操作。其次，如果集合通常在同一块内具有很少的相邻集合，则在一次执行而不是一个接一个地执行时，块之间的更新操作可以更加有效。
图 1 顶点集Vi和块i的示意图
顶点集的从左V到右的顺序是拓扑顺序。弧显示更新操作。如果在广义Dijkstra的步骤7中选择Vk 和（GVk），则对于，...，，键（Vi）gt;lambda;和（VBi，lambda;） ，并保持此属性。然后首先执行对块（Vk）的所有已注册更新（ProjectR_Register=ed，thin=arcs），然后按顺序扫描具有键lambda;的（Vk）元素（我们仅显示Vk ），块内的更新直接执行（更B新，粗体弧），并注册其他块的更新（寄存器，虚线弧）。每个Vk 在相位lambda;中B最多选择一次。
Project FromBlockR队列中的所有顶点集U，其根据其拓扑顺序等于当前标签lambda;。如果isin;目U标顶点集是队列中的最小元素，则整个算法将停止。否则，同一块中的所有相邻顶点集由Update直接标记，而对不同块中的邻居的标记操作由Register注册。
最后，我们可以制定整体算法。只要没有设置已经收到最终标签并且仍然需要执行标签操作，它就会执行T标签操作。它在所谓的阶段中运行，其中在关键lambda;的相位中，具有距离lambda;的所有顶点将接收它们的最终标签。在与键lambda;相位的情况下，选择包括包含具有键lambda;的顶点的最小索引的顶点集的块。如果不存在这样的顶点，则采用具有值lambda;的推迟标签U的块。对于，按顺序调用Project Registered和Project FromBlock。必须在从顶点集中的顶点标记步骤之前调用Project RegiUstered，以便通过不同块的邻居更新标签lambda;处的顶点U。否则，Project_FromBlock可能无法有效运行，因为顶点可能在稍后的算法中获得标签lambda;，这再次需要对其中的邻居进行更新操作。只要它们仍然是要扫描的顶点或具U有延迟标签的块，就可以完U成关键lambda;的循环。一旦顶点进入，
算法就会停止，收到它的最终标签并将其返回，或者它返回无穷大以表示无法访问。
因此，如果T可从S到达，则元素Tisin;T将在最小距离lambda;=d（T）处从队列中移除。否则，只要Q为空并且R中没有标签注册，GeneralizedDijkstra就会停止并返回infin;。对于visin;Uisin;V，从S到可从S到达的任何顶点visin;V（G）的距离由du（v）给出。
除了从S到T或从S到所有顶点的计算距离之外，通常还对最短路径感兴趣。这些可以从GeneralizedDijkstra的输出中轻松导出。或者，可以在封装在Update中的最短路径计算期间存储前驱信息。
GeneralizedDijkstra的理论运行时间及其在实践中的表现取决于底层图G的结构及其在顶点集和块中的划分。GeneralizedDijkstra与Dijkstra算法，本质区别在于，对于一般顶点集，如果队列中的元素包含多个顶点，则它可以再次进入队列。因此，对于队列的最小元素，最多有多个查询。两个时间范围都假定由Fibonacci堆实现。GeneralizedDijkstra主要适用Q于具有规则结构的图形，对于该图形，地面集合V可以被划分为一组顶点集合，其具有对于所有U的易于计算的函数，例如线性函数。GeneralizedDijkstra在VLSI路由中的两个应用，其中算法特别有效。
2.VLSI路由中的应用
通常用于对VLSI路由的搜索空间建模的图是三维网格图。路由在少数不同层中实现，即，与x-y层（目前为105105）的扩展相比，不同z坐标的数量非常小（目前为10）。每个x-y层都分配了一个偏好方向（x或 sim;y）和连续层具有不同的偏好方向。 设G0（:V=（G0），E（G0））是顶点集V（G0）Z3的无限三维网格图，其中两个顶点（ x，y，z）V（G0:）= 和（x,，y,，z,）V（G0）由一对相等isin;长度的相等边缘连接起来并isin; 且仅当xx,yy,zz,1时。在一层内与偏好方向正交运行的导线可能阻挡许多导线。
因此，应优先避免电线。而且，由于若干原因，通孔（连接相邻层的边缘）是不希望的，包括它们的高电阻和对制造产量的影响。这通常由边长c：E（G0）→Z 0建模，偏好优先方向上一层内的边：对于每一层zisin;Z有常数cz，1，cz，2，cz isin;Zgt; 0。
图 2
图2右下角的源顶点（绿色）和图片左下角的目标顶点（红色）通过长度为153的最短路径（蓝色）连接。走廊由全局路由确定（在这个例子中，黄色）在四个不同的层上运行。在优先方向上运行并且与偏好方向正交的边的成本是1和4，相应地，通孔的成本是13.（对于在该图图例中对颜色的引用的解释，读者被称为网络版本的本文。）
为了使用面向目标的方法加速G0的子图中的最短路径的计算，可以使用距离上的良好下界。为了确定这个下限，我们只考虑通过全局路由计算的走廊，忽略障碍物和先前确定的与其相交的路径。由于这些走廊是由全局路由产生的，因为相对较少的矩形的并集，GeneralizedDijkstra有效地计算距离。
图 3
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[426858]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
