NP-completeness result for positive line-by-fill SADP process

摘要

Double patterning (DP) is a necessity for at and below 32nm half pitch production. The two top contending DP technologies are litho-etch-litho-etch (LELE) and self-aligned double patterning (SADP). While both LELE and SADP are actively researched and optimized on the process side [1] [2] [3] [4], CAD support for them has been very different.When cut candidates can be explicitly specified, the problem of LELE mask assignment transforms into the familiar 2-colorability problem and benefits from the extensive research ranging from what originally was conducted for alt-PSM lithography [5], to more recently proposed new techniques for LELE [6], and proof of the inherent computational limitation imposed by hierarchy [7].CAD support for SADP, on the other hand, is almost non-existent. Such lack of CAD support for SADP is not coincidental. For a layout, LELE solutions tend to look similar while SADP solutions can be vastly different in style. Due to the flexibility offered by trim mask, SADP inherently has a much larger solution space than LELE.In this paper, we take the first step in investigating the CAD implications of the positive line-by-fill SADP process by proving that the problem of SADP manufacturability is NP-complete.