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, 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, to more recently proposed new techniques for LELE, and proof of the inherent computational limitation imposed by hierarchy. CAD support for SADP, on the other hand, is almost non-existent.
Note: By clicking on the above link, this paper will be emailed to your EE Times log-in address by Mentor Graphics.
Please disable any pop-up blockers for proper viewing of this Whitepaper.