FORSTer：一种高效的障碍物避让直角Steiner树构造算法

"FORSTer: An Efficient Heuristic for Obstacle-Avoiding Rectilinear Steiner Tree Construction，这是一篇由胡昱、冯哲等人撰写的关于VLSI布局布线中的障碍物避让策略的研究论文。文章主要关注的是物理设计领域中的一个问题，即如何构建有效的直角Steiner最小树（Rectilinear Steiner Minimum Tree, RSMT），同时避开宏单元、IP块和预布线网等障碍物。" 在VLSI（Very Large Scale Integration）设计中，物理设计是关键步骤之一，它涉及到电路布局和布线。直角Steiner最小树（RSMT）是一种优化技术，用于连接电路中的各个终端节点，同时最小化路径长度。然而，在实际应用中，由于存在如宏单元、IP模块和预布线网络等障碍物，传统的RSMT算法往往无法满足高效且避免冲突的布线需求。 FORSTer（FORstacle-Avoiding Rectilinear Steiner Tree construction）是一个提出的新颖启发式算法，旨在解决多端口网络的OARSMT问题，即障碍物避让的直角Steiner最小树构建。该算法分为三个步骤：首先，在障碍物存在的情况下将所有终端分割成多个子集；然后，对于每个连通图，使用一个或多个树来连接其中的终端；最后，通过优化步骤来改进这些树结构，以进一步减少路径交叉和提高整体布局效率。 在Step1中，终端分区策略有助于减少障碍物的影响，通过将终端分组，可以避免在处理大型复杂网络时的计算复杂性。Step2的多树连接方法允许更灵活地处理不同区域的终端连接，而Step3的优化过程则可能包括剪枝、合并或重新路由等操作，以生成最终的无冲突布线方案。 FORSTer算法的提出，对于提高VLSI设计的自动化程度和性能至关重要，它能有效地降低布线的复杂度，减少信号延迟，同时降低功耗和提高布线成功率。这篇论文的研究成果对实际的集成电路设计工具和流程有着深远的影响，为解决VLSI布线阶段的障碍物避让问题提供了新的思路和解决方案。