Layout decomposition with pairwise coloring for multiple patterning lithography

Ye Zhang, Wai Shing Luk, Hai Zhou, Changhao Yan, Xuan Zeng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

42 Scopus citations

Abstract

While double patterning lithography (DPL) is still in active development, triple or even quadruple patterning has recently been proposed for the next technology node. In this paper, we propose a pairwise coloring (PWC) method to tackle the layout decomposition problem for general multiple patterning lithography (MPL). The main idea is to reduce the problem to sets of concurrent bi-coloring problems. The overall solution is refined iteratively by applying a bi-coloring method for pairs of color sets per pass. One obvious advantage of this approach is that the existing DPL techniques can be reused seamlessly. Any improvement of them can directly benefit to the MPL counterpart. Moreover, we observe that with the help of the SPQR-tree graph division method, each pass can be fulfilled in nearly linear time. In addition, to prevent the solution getting stuck in the local minima, a randomized initialization strategy is incorporated. The PWC method is executed certain number of times with different randomized initial solutions, out of which the best solution is selected as output. We have implemented our method for particular triple patterning lithography (TPL). The experimental results show that compared with two recently published methods for TPL, our method can reduce the number of conflicts up to 33.2% and 44.9% respectively.

Original languageEnglish (US)
Title of host publication2013 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - Digest of Technical Papers
Pages170-177
Number of pages8
DOIs
StatePublished - Dec 1 2013
Event2013 32nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013 - San Jose, CA, United States
Duration: Nov 18 2013Nov 21 2013

Other

Other2013 32nd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2013
CountryUnited States
CitySan Jose, CA
Period11/18/1311/21/13

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Layout decomposition with pairwise coloring for multiple patterning lithography'. Together they form a unique fingerprint.

Cite this