多重掩模场景详细布线算法
Detailed Routing Algorithm for Multi-Mask Scenes
-
摘要: 为了在多重掩模自动布线场景中取得缝线数目较少、总线长较小的布线效果,提出一种基于虚拟格点(virtual-vertex,V-V)模型的满足多重掩模约束的详细布线算法.首先在均匀网格下构建可以支持同色及异色间距的V-V模型,V-V的规模由工艺文件中定义的布线层的掩模数决定;然后为每个多端线网生成考虑多重掩模约束的最短路径拓扑结构,并将多端线网分解为多个双端线网;最后基于提出的V-V模型结合搜索算法,以最短路径拓扑结构作为指导,对每个双端线网完成自动布线,并通过代价函数严格控制缝线的引入,保证了以最小缝线数完成线网的连接.在详细布线比赛的基准测试集及其衍生测例进行实验的结果表明,与布线完成后再进行掩模分配的技术方案相比,所提算法可以减少约26%的缝线数.Abstract: A detailed routing algorithm is proposed to optimize the routing process in technology files with multiple masks. The algorithm is based on the virtual-vertex (V-V) model, which is designed to reduce the number of stitches and shorten the total length of the routing. The V-V model is constructed under a uniform grid and supports both uniform and non-uniform spacing. Its size is determined by the number of masks in the layer being routed. The algorithm generates a shortest path topology structure for each network with multiple terminals and splits the network into multiple two-terminal networks. The V-V model and search algorithm are then utilized to automatically route each two-terminal network with the shortest path topology as a guide. The introduction of stitches is strictly controlled through the cost function to ensure the minimum number of stitches required to connect the network. Experimental results show that the proposed algorithm can reduce the number of stitches by approximately 26% compared to the method of mask allocation after routing is completed. The algorithm satisfies the constraints of various masks and is proven to be effective in benchmark test sets and its derivative test cases of the detailed routing competition.