Color balancing aware double patterning

Meng Yi Lin, Yih-Lang Li, Kuen Wey Lin

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

Abstract

In electronic design automation, the problem of double patterning lithography (DPL) can be formulated as follows. Two features of a layout should be assigned different colors if their spacing is less than the minimum coloring spacing. Because only two colors are used in DPL, a layout may contain a pattern which cannot be assigned a color. To resolve the conflict, a stitch is used to split a feature into two parts and then the two parts can be assigned different colors. However, stitches will cause yield loss. Moreover, a balanced coloring will lead to better patterning quality. In brief, the focus of DPL is the reduction of conflicts and stitches and the balance of colors. In this paper, we propose an integer linear programming (ILP)-based algorithm to address the DPL problem with graph theory. Because it is time-consuming to generate a solution for a whole layout with ILP, we extract faces from the conflict graph which is used to represent a layout. Thus, an ILP formulation for face is proposed. Finally, these faces are merged according to the negotiation on the quality of solution. Experimental results show that, compared to the method without considering the balance of color, our algorithm can generate solutions with 15% less area difference averagely with the same quality of conflicts and stitches. Moreover, compared to the previous algorithm of layout decomposition, our algorithm can reduce the number of conflicts by 29%, the number of stitches by 12% averagely.

Original languageEnglish
Title of host publicationProceedings of the 2017 IEEE International Conference on Applied System Innovation
Subtitle of host publicationApplied System Innovation for Modern Technology, ICASI 2017
EditorsTeen-Hang Meen, Artde Donald Kin-Tak Lam, Stephen D. Prior
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages284-287
Number of pages4
ISBN (Electronic)9781509048977
DOIs
StatePublished - 21 Jul 2017
Event2017 IEEE International Conference on Applied System Innovation, ICASI 2017 - Sapporo, Japan
Duration: 13 May 201717 May 2017

Publication series

NameProceedings of the 2017 IEEE International Conference on Applied System Innovation: Applied System Innovation for Modern Technology, ICASI 2017

Conference

Conference2017 IEEE International Conference on Applied System Innovation, ICASI 2017
CountryJapan
CitySapporo
Period13/05/1717/05/17

Keywords

  • Double patterning lithography
  • Integer linear programming and layout decomposition

Fingerprint Dive into the research topics of 'Color balancing aware double patterning'. Together they form a unique fingerprint.

Cite this