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