Layout decomposition for triple patterning lithography

Abstract

As minimum feature size and pitch spacing further decrease, triple patterning\nlithography (TPL) is a possible 193nm extension along the paradigm of double\npatterning lithography (DPL). However, there is very little study on TPL layout\ndecomposition. In this paper, we show that TPL layout decomposition is a more\ndifficult problem than that for DPL. We then propose a general integer linear\nprogramming formulation for TPL layout decomposition which can simultaneously\nminimize conflict and stitch numbers. Since ILP has very poor scalability, we\npropose three acceleration techniques without sacrificing solution quality:\nindependent component computation, layout graph simplification, and bridge\ncomputation. For very dense layouts, even with these speedup techniques, ILP\nformulation may still be too slow. Therefore, we propose a novel vector\nprogramming formulation for TPL decomposition, and solve it through effective\nsemidefinite programming (SDP) approximation. Experimental results show that\nthe ILP with acceleration techniques can reduce 82% runtime compared to the\nbaseline ILP. Using SDP based algorithm, the runtime can be further reduced by\n42% with some tradeoff in the stitch number (reduced by 7%) and the conflict\n(9% more). However, for very dense layouts, SDP based algorithm can achieve\n140x speed-up even compared with accelerated ILP.\n