A polynomial time triple patterning algorithm for cell based row-structure layout

Haitong Tian, Hongbo Zhang, Qiang Ma, Zigang Xiao, Martin D.F. Wong

Research output: Contribution to journalConference article

Abstract

As minimum feature size keeps shrinking, and the next generation lithography (e.g, EUV) further delays, double patterning lithography (DPL) has been widely recognized as a feasible lithography solution in 20nm technology node. However, as technology continues to scale to 14/10nm, DPL begins to show its limitations and usually generates too many undesirable stitches. Triple patterning lithography (TPL) is a natural extension of DPL to conquer the difficulties and achieve a stitch-free layout decomposition. In this paper, we study the standard cell based row-structure layout decomposition problem in TPL. Although the general TPL layout decomposition problem is NP-hard, in this paper we will show that for standard cell based TPL layout decomposition problem, it is polynomial time solvable. We propose a polynomial time algorithm to solve the problem optimally and our approach has the capability to find all stitch-free decompositions. Color balancing is also considered to ensure a balanced triple patterning decomposition. To speed up the algorithm, we further propose a hierarchical algorithm for standard cell based layout, which can reduce the run time by 34.5% on average without sacrificing the optimality. We also extend our algorithm to allow stitches for complex circuit designs, and our algorithm guarantees to find optimal solutions with minimum number of stitches.

Original languageEnglish (US)
Article number6386589
Pages (from-to)57-64
Number of pages8
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
StatePublished - Dec 1 2012
Event2012 30th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2012 - San Jose, CA, United States
Duration: Nov 5 2012Nov 8 2012

Fingerprint

Lithography
Polynomials
Decomposition
Extreme ultraviolet lithography
Computational complexity
Color
Networks (circuits)

ASJC Scopus subject areas

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

Cite this

A polynomial time triple patterning algorithm for cell based row-structure layout. / Tian, Haitong; Zhang, Hongbo; Ma, Qiang; Xiao, Zigang; Wong, Martin D.F.

In: IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD, 01.12.2012, p. 57-64.

Research output: Contribution to journalConference article

@article{ef4d1bf129b440d6b6f955bdfdc14cf5,
title = "A polynomial time triple patterning algorithm for cell based row-structure layout",
abstract = "As minimum feature size keeps shrinking, and the next generation lithography (e.g, EUV) further delays, double patterning lithography (DPL) has been widely recognized as a feasible lithography solution in 20nm technology node. However, as technology continues to scale to 14/10nm, DPL begins to show its limitations and usually generates too many undesirable stitches. Triple patterning lithography (TPL) is a natural extension of DPL to conquer the difficulties and achieve a stitch-free layout decomposition. In this paper, we study the standard cell based row-structure layout decomposition problem in TPL. Although the general TPL layout decomposition problem is NP-hard, in this paper we will show that for standard cell based TPL layout decomposition problem, it is polynomial time solvable. We propose a polynomial time algorithm to solve the problem optimally and our approach has the capability to find all stitch-free decompositions. Color balancing is also considered to ensure a balanced triple patterning decomposition. To speed up the algorithm, we further propose a hierarchical algorithm for standard cell based layout, which can reduce the run time by 34.5{\%} on average without sacrificing the optimality. We also extend our algorithm to allow stitches for complex circuit designs, and our algorithm guarantees to find optimal solutions with minimum number of stitches.",
author = "Haitong Tian and Hongbo Zhang and Qiang Ma and Zigang Xiao and Wong, {Martin D.F.}",
year = "2012",
month = "12",
day = "1",
language = "English (US)",
pages = "57--64",
journal = "IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers",
issn = "1092-3152",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - A polynomial time triple patterning algorithm for cell based row-structure layout

AU - Tian, Haitong

AU - Zhang, Hongbo

AU - Ma, Qiang

AU - Xiao, Zigang

AU - Wong, Martin D.F.

PY - 2012/12/1

Y1 - 2012/12/1

N2 - As minimum feature size keeps shrinking, and the next generation lithography (e.g, EUV) further delays, double patterning lithography (DPL) has been widely recognized as a feasible lithography solution in 20nm technology node. However, as technology continues to scale to 14/10nm, DPL begins to show its limitations and usually generates too many undesirable stitches. Triple patterning lithography (TPL) is a natural extension of DPL to conquer the difficulties and achieve a stitch-free layout decomposition. In this paper, we study the standard cell based row-structure layout decomposition problem in TPL. Although the general TPL layout decomposition problem is NP-hard, in this paper we will show that for standard cell based TPL layout decomposition problem, it is polynomial time solvable. We propose a polynomial time algorithm to solve the problem optimally and our approach has the capability to find all stitch-free decompositions. Color balancing is also considered to ensure a balanced triple patterning decomposition. To speed up the algorithm, we further propose a hierarchical algorithm for standard cell based layout, which can reduce the run time by 34.5% on average without sacrificing the optimality. We also extend our algorithm to allow stitches for complex circuit designs, and our algorithm guarantees to find optimal solutions with minimum number of stitches.

AB - As minimum feature size keeps shrinking, and the next generation lithography (e.g, EUV) further delays, double patterning lithography (DPL) has been widely recognized as a feasible lithography solution in 20nm technology node. However, as technology continues to scale to 14/10nm, DPL begins to show its limitations and usually generates too many undesirable stitches. Triple patterning lithography (TPL) is a natural extension of DPL to conquer the difficulties and achieve a stitch-free layout decomposition. In this paper, we study the standard cell based row-structure layout decomposition problem in TPL. Although the general TPL layout decomposition problem is NP-hard, in this paper we will show that for standard cell based TPL layout decomposition problem, it is polynomial time solvable. We propose a polynomial time algorithm to solve the problem optimally and our approach has the capability to find all stitch-free decompositions. Color balancing is also considered to ensure a balanced triple patterning decomposition. To speed up the algorithm, we further propose a hierarchical algorithm for standard cell based layout, which can reduce the run time by 34.5% on average without sacrificing the optimality. We also extend our algorithm to allow stitches for complex circuit designs, and our algorithm guarantees to find optimal solutions with minimum number of stitches.

UR - http://www.scopus.com/inward/record.url?scp=84872340080&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84872340080&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:84872340080

SP - 57

EP - 64

JO - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers

JF - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers

SN - 1092-3152

M1 - 6386589

ER -