We develop new algorithmic techniques for VLSI detailed routing. First, we improve the goal-oriented version of Dijkstra's algorithm to find shortest paths in huge incomplete grid graphs with edge costs depending on the direction and the layer, and possibly on rectangular regions. We devise estimates of the distance to the targets that offer better trade-offs between running time and quality than previously known methods, leading to an overall speed-up. Second, we combine the advantages of the two classical detailed routing approaches - global shortest path search and track assignment with local corrections - by treating input wires (such as the output of track assignment) as reservations that can be used at a discount by the respective net. We show how to implement this new approach efficiently.
翻译:我们开发了新的电子设计自动化中的算法技术,用于解决VLSI详细布线问题。首先,我们改进了面向目标的Dijkstra算法,以在具有边缘方向、层的成本,并可能涉及矩形区域的巨大不完整网格图中查找最短路径。我们设计了到目标距离的估计,这些估计在运行时间和质量方面提供比以前已知的方法更好的平衡,从而导致总体速度提升。其次,我们将两种传统的详细布线方法的优点结合起来,全局最短路径搜索和轨道分配与局部修正,通过将输入线路(例如轨道分配的输出)视为“预定”,相应的网络可以以折扣价使用输入线路。我们展示了如何高效地实现这种新方法。