Comparison of triple-patterning decomposition algorithms using aperiodic tiling patterns

Christopher Cork; Jean-Christophe Madre; Levi Barnes

doi:10.1117/12.793116

19 May 2008 Comparison of triple-patterning decomposition algorithms using aperiodic tiling patterns

Christopher Cork, Jean-Christophe Madre, Levi Barnes

Proceedings Volume 7028, Photomask and Next-Generation Lithography Mask Technology XV; 702839 (2008) https://doi.org/10.1117/12.793116
Event: Photomask and NGL Mask Technology XV, 2008, Yokohama, Japan

Abstract

Double patterning has gained prominence as the most likely methodology to help keep Moore's law going towards 22nm 1/2 pitch lithography. However, most designs cannot be blindly shrunk to run using only two patterning layers and a variety of constraints must be imposed on designs to allow for correct decomposition. These constraints are more onerous for the contact layer than for line/space patterns because they more easily form odd cycles on the 2D plane, which cannot be broken using polygon cutting. As this can adversely limit packing density, especially in bit cells, a triple patterning decomposition capability could be attractive for the contact layer. Pattern decomposition for contacts can be likened to coloring a map where minimum spaces between contacts are replaced with borders. It is well known that 4 colors can color any map, but it is an NP-complete problem to compute the minimum number of colors needed to color any given map. This should place an upper limit on the scalability of any algorithm able to color large networks. A variety of test patterns that are known 3-colorable are needed to compare suitable algorithms. It has been proved that a set of aperiodic tiling known as "Penrose Tiles" is 3-colorable. This paper compares the scalability of different coloring algorithms using a variety of contact patterns based on Penrose Tiles.

Citation Download Citation

Christopher Cork, Jean-Christophe Madre, and Levi Barnes "Comparison of triple-patterning decomposition algorithms using aperiodic tiling patterns", Proc. SPIE 7028, Photomask and Next-Generation Lithography Mask Technology XV, 702839 (19 May 2008); https://doi.org/10.1117/12.793116

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