Share Email Print

Proceedings Paper

Comparison of triple-patterning decomposition algorithms using aperiodic tiling patterns
Author(s): Christopher Cork; Jean-Christophe Madre; Levi Barnes
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper 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.

Paper Details

Date Published: 19 May 2008
PDF: 7 pages
Proc. SPIE 7028, Photomask and Next-Generation Lithography Mask Technology XV, 702839 (19 May 2008); doi: 10.1117/12.793116
Show Author Affiliations
Christopher Cork, Synopsys SARL (France)
Jean-Christophe Madre, Synopsys SARL (France)
Levi Barnes, Synopsys, Inc. (United States)

Published in SPIE Proceedings Vol. 7028:
Photomask and Next-Generation Lithography Mask Technology XV
Toshiyuki Horiuchi, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?