An effective triple patterning aware grid-based detailed routing approach

Triple patterning lithography (TPL) is attracting more and more attention due to further scaling of the critical feature size. How fully the benefits of TPL can be utilized depends very much on both the decomposition and layout steps. However, it is non-trivial to perform detailed routing and layout decomposition simultaneously on a large-scale complicated circuit to achieve decomposability on one hand, and short wirelength, small number of stitches and small number of vias on the other hand. In our approach, routing and coloring are done iteratively but integrated closely to reduce the problem complexity. The routing step is able to detect and avoid native conflicts as much as possible. If any conflicts occur in the coloring step, the router will rip-up and re-route to get rid of them. This technique proves to be effective and efficient in improving the quality of the coloring assignment. Compared with previous works [1] on TPL using simultaneous routing and coloring, the number of stitches and the number of vias are reduced by 76.8% and 2.1% respectively while our running time is 36.6% less and the wirelength is very comparable.