面向三重版图曝光约束的详细布线算法

Detailed Routing Algorithm with Triple Patterning Lithography Constraints

在进一步缩小特征尺寸的问题上,三重版图曝光技术(triplepatterninglithography,TPL)发挥着重要的作用.针对TPL中的版图分解问题,提出了一种基于TPL约束的详细布线算法.将版图分解问题转化为满足同色间距约束和最小间距约束的详细布线问题,使用网格编码的方法来满足2种间距约束;利用与2种间距约束相结合的Hannan网格来提升布线资源的利用率以及布线的速度;结合多源迪杰斯特拉算法进行多端线网的最短路径搜索;最后将布线结果进行版图分解,实现最小化冲突数量和缝合点数量的目标.算法在2.20 GHzCPU和32 GB内存的Ubuntu20.04环境下运行,使用2018年ISPD详细布线比赛的测试集.实验结果表明,与普通详细布线相比,可降低约60%的冲突数量以及70%的缝合点数量.

The triple patterning lithography(TPL)technique is a key factor in achieving a reduction in feature size,and is widely recognized as an important advancement in the field.However,the layout decomposition problem in TPL presents a unique challenge.To address this challenge,a novel detailed routing algorithm based on TPL constraints has been proposed.By transforming the layout decomposition problem into a detailed routing problem that satisfies the same color spacing and minimum spacing constraint,the algorithm ensures the use of a grid encoding method that meets the spacing constraints.The Hannan grid,in conjunction with the spacing constraints,is utilized to optimize the routing resources utilization and speed,which has a significant impact on the overall effectiveness of the algorithm.To facilitate multi-terminal routing,the algorithm employs the multi-source Dijkstra algorithm to search for the shortest path.The results are then decomposed and colored to minimize the number of conflicts and stitches.The findings demonstrate that when contrasted with conventional detailed routing,the proposed approach can significantly mitigate conflicts by approximately 60%and minimize stitches by 70%.