Detailed Routing Algorithm with Triple Patterning Lithography Constraints

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%.