An efficient linear time triple patterning solver

Haitong Tian, Hongbo Zhang, Zigang Xiao, Martin D F Wong

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

Abstract

Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. In this paper, we applied triple patterning lithography on standard cell based designs, and proposed a novel algorithm to solve the problem. The algorithm guarantees to find a legal TPL decomposition with optimal number of stitches if one exists. A graph model is proposed to reduce the number of vertices in the solution graph, and a fast approach is developed to achieve simultaneous runtime and memory improvement. An efficient approach to limit the number of stitches is also proposed, which greatly reduces the total number of stitch candidates and enables an incremental implementation of the algorithm. Experimental results shows that the proposed algorithm is very efficient, which achieves 39.1% runtime improvement and 18.4% memory reduction compared with the state-of-the-art TPL algorithm on the same problem.

Original languageEnglish (US)
Title of host publication20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages208-213
Number of pages6
ISBN (Electronic)9781479977925
DOIs
StatePublished - Mar 11 2015
Event2015 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015 - Chiba, Japan
Duration: Jan 19 2015Jan 22 2015

Publication series

Name20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015

Other

Other2015 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015
CountryJapan
CityChiba
Period1/19/151/22/15

Fingerprint

Patterning
Linear Time
Lithography
Data storage equipment
Graph Model
Decomposition
Decompose
Cell
Experimental Results
Graph in graph theory
Vertex of a graph

ASJC Scopus subject areas

  • Computer Science Applications
  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Modeling and Simulation

Cite this

Tian, H., Zhang, H., Xiao, Z., & Wong, M. D. F. (2015). An efficient linear time triple patterning solver. In 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015 (pp. 208-213). [7059006] (20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ASPDAC.2015.7059006

An efficient linear time triple patterning solver. / Tian, Haitong; Zhang, Hongbo; Xiao, Zigang; Wong, Martin D F.

20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 208-213 7059006 (20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015).

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

Tian, H, Zhang, H, Xiao, Z & Wong, MDF 2015, An efficient linear time triple patterning solver. in 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015., 7059006, 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015, Institute of Electrical and Electronics Engineers Inc., pp. 208-213, 2015 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015, Chiba, Japan, 1/19/15. https://doi.org/10.1109/ASPDAC.2015.7059006
Tian H, Zhang H, Xiao Z, Wong MDF. An efficient linear time triple patterning solver. In 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015. Institute of Electrical and Electronics Engineers Inc. 2015. p. 208-213. 7059006. (20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015). https://doi.org/10.1109/ASPDAC.2015.7059006
Tian, Haitong ; Zhang, Hongbo ; Xiao, Zigang ; Wong, Martin D F. / An efficient linear time triple patterning solver. 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015. Institute of Electrical and Electronics Engineers Inc., 2015. pp. 208-213 (20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015).
@inproceedings{ceb607c89dac42379c8ceb2a58dbff24,
title = "An efficient linear time triple patterning solver",
abstract = "Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. In this paper, we applied triple patterning lithography on standard cell based designs, and proposed a novel algorithm to solve the problem. The algorithm guarantees to find a legal TPL decomposition with optimal number of stitches if one exists. A graph model is proposed to reduce the number of vertices in the solution graph, and a fast approach is developed to achieve simultaneous runtime and memory improvement. An efficient approach to limit the number of stitches is also proposed, which greatly reduces the total number of stitch candidates and enables an incremental implementation of the algorithm. Experimental results shows that the proposed algorithm is very efficient, which achieves 39.1{\%} runtime improvement and 18.4{\%} memory reduction compared with the state-of-the-art TPL algorithm on the same problem.",
author = "Haitong Tian and Hongbo Zhang and Zigang Xiao and Wong, {Martin D F}",
year = "2015",
month = "3",
day = "11",
doi = "10.1109/ASPDAC.2015.7059006",
language = "English (US)",
series = "20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "208--213",
booktitle = "20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015",
address = "United States",

}

TY - GEN

T1 - An efficient linear time triple patterning solver

AU - Tian, Haitong

AU - Zhang, Hongbo

AU - Xiao, Zigang

AU - Wong, Martin D F

PY - 2015/3/11

Y1 - 2015/3/11

N2 - Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. In this paper, we applied triple patterning lithography on standard cell based designs, and proposed a novel algorithm to solve the problem. The algorithm guarantees to find a legal TPL decomposition with optimal number of stitches if one exists. A graph model is proposed to reduce the number of vertices in the solution graph, and a fast approach is developed to achieve simultaneous runtime and memory improvement. An efficient approach to limit the number of stitches is also proposed, which greatly reduces the total number of stitch candidates and enables an incremental implementation of the algorithm. Experimental results shows that the proposed algorithm is very efficient, which achieves 39.1% runtime improvement and 18.4% memory reduction compared with the state-of-the-art TPL algorithm on the same problem.

AB - Triple patterning lithography (TPL) has been recognized as one of the most promising techniques for 14/10nm technology node. In this paper, we applied triple patterning lithography on standard cell based designs, and proposed a novel algorithm to solve the problem. The algorithm guarantees to find a legal TPL decomposition with optimal number of stitches if one exists. A graph model is proposed to reduce the number of vertices in the solution graph, and a fast approach is developed to achieve simultaneous runtime and memory improvement. An efficient approach to limit the number of stitches is also proposed, which greatly reduces the total number of stitch candidates and enables an incremental implementation of the algorithm. Experimental results shows that the proposed algorithm is very efficient, which achieves 39.1% runtime improvement and 18.4% memory reduction compared with the state-of-the-art TPL algorithm on the same problem.

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

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

U2 - 10.1109/ASPDAC.2015.7059006

DO - 10.1109/ASPDAC.2015.7059006

M3 - Conference contribution

AN - SCOPUS:84926429871

T3 - 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015

SP - 208

EP - 213

BT - 20th Asia and South Pacific Design Automation Conference, ASP-DAC 2015

PB - Institute of Electrical and Electronics Engineers Inc.

ER -