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

Qiao Li

doi:10.1117/12.864302

24 September 2010 NP-completeness result for positive line-by-fill SADP process

Qiao Li

Proceedings Volume 7823, Photomask Technology 2010; 78233P (2010) https://doi.org/10.1117/12.864302
Event: SPIE Photomask Technology, 2010, Monterey, California, United States

Abstract

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.

Citation Download Citation

Qiao Li "NP-completeness result for positive line-by-fill SADP process", Proc. SPIE 7823, Photomask Technology 2010, 78233P (24 September 2010); https://doi.org/10.1117/12.864302

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available