国际计算机与通信工程创新研究杂志
菜单在线刊号(2320-9801)印刷刊号(2320-9798)
在线刊号(2320-9801)印刷刊号(2320-9798)
| Arpana Bhagwat1 印度班加罗尔BMS工程学院CSE系研究生 |
| 有关文章载于Pubmed，谷歌学者 |
更多相关文章请访问国际计算机与通信工程创新研究杂志
线性斯坦纳最小树(RSMT)是VLSI设计中的全局路由技术之一，该树通过垂直或水平到达每个引脚来跨越给定的引脚集。在构建这样的rsmt时，可能会遇到许多障碍。为了构建无障碍的rsmt，人们做了许多研究工作。本文对近年来的一些研究工作进行了回顾，以了解这一问题，并了解可行的解决方案。它涵盖并比较了用于寻找OARSMT的不同方法和方法。这里讨论的一些不同的方法是Geo-Steiner方法，Maze路由方法，自顶向下分区方法和贪婪启发式方法。比较这些算法的速度，效率，所使用的资源和其他优缺点也被列为这项工作的一部分。为实现不同算法的实际性能，制作了实验结果表。
关键字 |
| 直线斯坦纳最小树，障碍，回转约束。 |
介绍 |
| 斯坦纳树问题可以定义为“给定一个包含n个输入点的集合”PâÂ′Â′，需要找到一个新的点集合S，称为斯坦纳点集合，使得跨越点“P U SâÂ′Â′”的路径长度最小。在直线斯坦纳最小树(RSMT)的情况下，连接任何两点的边必须是水平或垂直的。障碍物是矩形块，大多数时候不允许连接边缘/电线。障碍物之间不重叠，但可以有共同的边或共同的顶点。在最初的RSMT中，假设没有障碍，但在现实世界的应用中，我们遇到了一些常见的障碍，如路由阻塞、预路由网络、IP块、超大规模集成电路设计中的宏单元。 |
| 现在真正的挑战是有一个有效和快速执行的算法来获得“避障直线斯坦纳最小树- OARSMTâ '  '。在增量方法查找OARSMT的情况下，最初生成OARSMT时考虑到空的障碍列表，然后在障碍列表中引入障碍，从而细化先前生成的doarsmt。进行迭代，直到在此过程中发现障碍重叠。有时在问题陈述中会发现一个轻微的变化，它说不是所有的边都必须避免越过障碍物，而是有一个约束，使得边的最大长度/秒不应该越过一些称为回转约束的阈值。这是因为导线可以通过障碍物，但不允许通过缓冲器或中继器，这反过来限制了导线通过障碍物的长度。 |
| 在VLSI设计的全局路由阶段，使用了arsmt，这是一个理想的用例，因为在VLSI设计的这个阶段，存在一些宏单元，这些宏单元是为在芯片中执行特定功能而构建的，并以其矩形形状为特征。RSMT在超大规模集成电路设计本身也有一些应用。计算机系统网络是其应用的另一个领域，计算机与多条电缆和电线互连;RSMT用于寻找最小线长。在通信网络中，RSMT用于组播路由。RSMT用于跨组播的所有节点，并确定通信的最短路径。 |
| 接下来的部分将包括调查，比较他们的实验结果和最后的结论。 |
综述:oa-rsmt的方法 |
| 本节包括关于OARSMT概念的不同论文的调查。这一调查包括了在实现论文中解释的方法和算法的简要说明。 |
ï ·GeoSteiner Approach [1] |
| 全斯坦纳树(FSTs)是GeoSteiner方法的构建模块。在FST中，所有考虑的引脚都是叶节点。GeoSteiner框架主要包括两个阶段。第一个是FST代，它包括根据一些预处理信息修剪掉不必要的节点。观察到该阶段的运行时间是二次的。第二阶段是在第一阶段产生的fst的串联。它可以被看作是一个整数线性规划(ILP)，可以用分支和切搜索方法求解。首先要考虑一组实际的引脚。每个障碍物的每个角落都被认为是一个虚拟的大头针。对于FST生成，这些虚拟引脚也包括在内，而不需要考虑是否在最终的最优树生成中考虑这些。 In the incremental method of FST generation FST is first generated for two points which can be done in any of the two ways,first is both the points are real points and second isat least one of the points is virtual. Techniques are adopted to make sure the redundant edges which are created due to multiple FSTs are removed. The same method is extended to recursively generate three and more point FSTs. Once all the useful FSTs are generated, ILP is set up in order to select appropriate subset of FSTs and concatenate them to get an OARSMT. |
ïÂ‑·一个最优方法[2] |
| 这是对[1]做的功。提出该方法的论文指出，生成并使用oafst而不是使用fst。提出了一种两阶段算法;其中一期为OAFST发电，二期为OAFST的OARSMT施工。该方法对每个障碍物只使用两个虚拟点，并采用增量处理障碍物的方法来减少运行时间。利用瓶颈斯坦纳距离、空菱形、空角矩形和空内矩形属性递归生成每个终端的oafst。在第二阶段，利用这些OAFSTs生成OARSMTs，并将其制定为ILP，并使用分支和截断搜索进行求解。该方法采用增量法，避免了OAFST爆炸。 |
ï ·在障碍物上转换约束[3] |
| 这一概念包含了一个最优解的分析，以寻找OARSMT与转换约束，然后提出了一个算法，以寻找最优解嵌入扩展哈南网格。给定一个源点和一组汇聚点，生成RSMT并称为t。一种新的点类型被认为是一组边界终端。这些是位于障碍物边界上的节点，它们都至少有一条入射线穿过障碍物。树T被分解成更小的树，直到我们有一个清晰的划分，即完全位于障碍物内部的树(Ti)和完全位于障碍物外部的树(To)。假设缓冲区只能插入到" Toâ '  '，而不能插入到" Tiâ '  ' '，但可以插入到边界终端的缓冲区除外。因此，为了保持“TiÃ①Â′”中的信号质量，引入了约束条件。在本文中，转换速率被认为是波形通过10%点和90%形式所花费的时间。该算法分为两个阶段。第一阶段生成“TiÃ①Â′Â′和ToÃ①Â′Â′”的候选树，第二阶段确定这三个的子集，并将这些树组合起来以给出最优解。实验结果表明，该算法的速度提高了800倍，路由资源减少了5%左右。 |
ï ·高性能解决方案[4] |
| 本文提出了一种新的避障路由图(OARG)，并给出了一种求解避障路由图问题次优解的三步优化算法。该三步算法可以概括为:第一步是构造时间复杂度为O(n log n)、空间复杂度为O(n)的OARG，第二步是在O(n log n)时间内构造MST-OARG，第三步是使用MST-OARG约简方案将MST-OARG转换为OARST。在局部细化过程中，对OARST进行了总线长缩减。该优化方案采用一般情况，并采用排序方法使方案更加贪婪。用三步算法估计的线长可以在O(n log n)时间内显著缩短。如前所述，本工作中的OARG保持了O(n)空间，因此有助于在O(nlog n)时间内获得更好的初始解。此外，它的线性空间和避障特性对性能也有显著的贡献。 |
ïÂ‑·基于斯坦纳点选择[5] |
| 本文提出了一种基于斯坦纳点的算法，以达到性能提速和线长缩短的目的。它声称在Θ(n log n)经验时间内实现该解决方案，否则在空间图中使用迷宫路由需要Ω (n2)时间。基于Steiner点的框架甚至可以扩展到多层OARSMT和OA优先方向RSMT。该算法分为四个步骤。图的构造，斯坦纳点的选择，最小终端生成树(MTST)的构造，最后的细化。MTST是一种树，其中树只跨越给定的终端集，而不跨越任何其他中间顶点。利用哈南网格和转义图来确定斯坦纳点的位置。这两种方法都会在终端或障碍角的延伸线的交叉点生成一个顶点。然而，这会产生大量这样的顶点，这使得顶点选择需要更长的时间。因此，该算法采用了不同的方法。在图构造步骤中，避障Voronoi图(OAVG)是在O(n log n)时间内用给定的终端集、障碍物顶点和理想的斯坦纳点候点构造的。 Good Steiner points are then selected from the constructed OAVG using PrimâÂÂs algorithm and Shortest Path Region (SPR) bounded by the two terminals. In the third step OARST is constructed in O(n log n) time using MTST algorithm proposed by Long and Liu. MTST on OAVG is constructed spanning the given vertices and the selected Steiner points. LongâÂÂs MTST algorithm includes the terminal path generation and also MST generation using these paths and LiuâÂÂs algorithm has directly critical path generation. Refinement is done in O(n log n) time to reduce redundant segments created in the above steps. |
ï ·基于关键中继的延迟和松弛优化方法[6] |
| 将单源单目标迷宫路由扩展到所有源上，甚至称为多源单目标迷宫路由，然后在每个汇聚的延迟约束下将不相连的点连接起来，构建关键卡车。本文简要介绍了不同研究人员之前提出的算法，并表明有时效率可以与性能相权衡。基于关键树干的树木生长算法主要解决了两个问题。第一个是Performance Driven OARST (PDOARST)，第二个是Slack Driven OARST (SDOARST)。PDOARST的目标是在每个接收器上有最小的延迟。有时，减少最大延迟可能会在时间限制方面产生问题。SDOARST用于满足时间约束和解决最坏负松弛(WNS)违反。提出了两种算法，分别针对上述问题，它们都有四个步骤，并且在步骤级别上是相似的。它从PD/SD关键树干生长后的OASG开始，然后是PD/SD子树的生长。PDOARST在使树成为直线并对其应用细化后结束。 Final two steps of SDOARST contain rectilinearization and redirection to maximize the WNS of the OARST. |
一个¯·这儿碰面[7] |
| FOARS(基于笛子的避障直线斯坦纳树构造)遵循自顶向下的分治方法。利用基于障碍感知快速查找表的线长估计(OA_FLUTE)将初始解划分为多个子问题，生成线长估计(OARSTs)并重新组合。FOARS使用OASG来创建初始连接图。FLUTE是一个非常健壮和快速的RSMT工具，广泛用于学术全局路由器，但FLUTE不是为处理障碍而构建的。为了创建OARSMT，将使用FLUTE生成的SRT与障碍物一起应用，进行局部优化，然后将所有局部优化的树组合起来得到最终的解决方案。但由于没有考虑全局视野，该方案无法支持大量点或复杂设置的障碍。针对这一问题，提出了分区算法，该算法从全局的角度对问题进行了较高层次的划分，并将问题划分为较小层次的问题。该算法分为五个阶段。采用八分区OASG生成算法，生成OASG生成连通性图。障碍惩罚MST (Obstacle penalty MST, OPMST)生成——MTST由OASG生成，OPMST由MTST生成。OAST生成——基于OPMST进行分区，分区后的结果在OA_FLUTE下进行处理。OARST generation – Rectilinearization is done and later V-shape refinement is done to reduce the wire length.Run time complexity of FOARS algorithm is O(n log n). |
ï ·感知缓冲的直线斯坦纳最小树构造[8] |
| 在此基础上，提出了一种基于缓存的块上RSMT (BOB-RSMT)算法。与OARSMT相比，它有助于在转换约束的限制下减少路由资源。这是一种增量算法，最初使用FLUTE构造RSMT。对于落在障碍物内的RSMT部分，检查回转约束并相应地修改边缘。关于这个算法，有一些重要的地方需要注意。它最初包括在障碍物边界上生成斯坦纳点，以使回转保持在最小值。接下来是细化这个点集，以平衡导线长度和转换值之间的权衡，然后将其制定为ILP。一旦点被固定，迷宫路由应用，以获得一个超阻塞树。最后将转换模式缓冲区插入到树中任意未阻塞的位置。 |
ï ·障碍物长度限制[9] |
| 本文提出了求解最坏情况时间复杂度为O(n log n)2的OARSMT问题的2-逼近算法。该算法分为两个阶段，首先构建一个跨越所有给定终端和障碍物角点的可见性图;使用Dijkstra-Kruskal方法构造这些点的斯坦纳树。使用简单的局部搜索启发式作为后优化步骤。 |
ï ·时间驱动，预缓冲和转换约束[10] |
| 这项工作的贡献是，它试图减少到关键sink的延迟，并通过使用过块路由减少到其他sink的线路长度，它满足转换约束，并将缓冲区放在非阻塞的地方，预缓冲用于提供一个时间戳，导致在寻找关于时间的良好拓扑时有用，并在构造的树上进行优化，以提高到关键sink的延迟。本文提出的方法是一种时间驱动的、有回转约束的跨块RST算法。它主要由五个步骤组成。首先是构造带有预缓冲的时间驱动初始RST“Tâ '  '。然后根据转换约束将T的拓扑结构更改为。然后对T进行缓冲，根据缓冲信息对T进行拓扑优化。再次对T执行缓冲。 |
巩固实验结果 |
| 本节包含由参考编号表示的算法的系统配置。针对不同的算法，本节还列出了不同基准测试的执行时间和线路长度。对于一些算法，没有添加相同的参数，因为它们的结果依赖于一些更多的参数，如转换约束。 |
 |
 |
结论 |
| 本文简要介绍了OARSMT技术以及目前解决这一问题的一些方法。这项工作甚至试图根据他们的实验结果和各自参考论文中声称的其他参数进行比较。未来的工作将包括通过在一个共同平台上实现这些算法来验证所列出的算法。 |
确认 |
| 作者要感谢技术教育质量改进计划[TEQIPII]， BMS工程学院和SPFU[国家项目促进单位]，卡纳塔克邦对本文报道的工作的支持。 |
参考文献 |
|
