多重掩模场景详细布线算法

为了在多重掩模自动布线场景中取得缝线数目较少、总线长较小的布线效果,提出一种基于虚拟格点(virtual-vertex,V-V)模型的满足多重掩模约束的详细布线算法.首先在均匀网格下构建可以支持同色及异色间距的V-V模型,V-V的规模由工艺文件中定义的布线层的掩模数决定;然后为每个多端线网生成考虑多重掩模约束的最短路径拓扑结构,并将多端线网分解为多个双端线网;最后基于提出的V-V模型结合搜索算法,以最短路径拓扑结构作为指导,对每个双端线网完成自动布线,并通过代价函数严格控制缝线的引入,保证了以最小缝线数完成线网的连接.在详细布线比赛的基准测试集及其衍生测例进行实验的结果表明,与布线完成后再进行掩模分配的技术方案相比,所提算法可以减少约26%的缝线数.