An efficient linear time triple patterning solver

Haitong Tian; Hongbo Zhang; Zigang Xiao; Martin D.F. Wong

doi:10.1109/ASPDAC.2015.7059006

An efficient linear time triple patterning solver

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

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

7 Citations (Scopus)

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 language	English
Title of host publication	The 20th Asia and South Pacific Design Automation Conference
Publisher	IEEE
Pages	208-213
Number of pages	6
ISBN (Electronic)	9781479977925, 9781479977901 (CD)
DOIs	https://doi.org/10.1109/ASPDAC.2015.7059006
Publication status	Published - Jan 2015
Event	The 20th Asia and South Pacific Design Automation Conference - Chiba, Japan Duration: 19 Jan 2015 → 22 Jan 2015 https://ieeexplore.ieee.org/xpl/conhome/7050531/proceeding (Link to conference proceedings)

Publication series

Name	Proceedings of Asia and South Pacific Design Automation Conference

Conference

Conference	The 20th Asia and South Pacific Design Automation Conference
Country/Territory	Japan
City	Chiba
Period	19/01/15 → 22/01/15
Internet address	https://ieeexplore.ieee.org/xpl/conhome/7050531/proceeding (Link to conference proceedings)

Access to Document

10.1109/ASPDAC.2015.7059006

Cite this

@inproceedings{ce3aee16a4044add82854e628c24bcdb,

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.}",

note = "Funding Information: This work was partially supported by the National Science Foundation under Grants CCF-1320585 and CCF-1421563. Publisher Copyright: {\textcopyright} 2015, IEEE; The 20th Asia and South Pacific Design Automation Conference ; Conference date: 19-01-2015 Through 22-01-2015",

year = "2015",

month = jan,

doi = "10.1109/ASPDAC.2015.7059006",

language = "English",

series = "Proceedings of Asia and South Pacific Design Automation Conference",

publisher = "IEEE",

pages = "208--213",

booktitle = "The 20th Asia and South Pacific Design Automation Conference",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/7050531/proceeding",

}

Tian, H, Zhang, H, Xiao, Z & Wong, MDF 2015, An efficient linear time triple patterning solver. in The 20th Asia and South Pacific Design Automation Conference., 7059006, Proceedings of Asia and South Pacific Design Automation Conference, IEEE, pp. 208-213, The 20th Asia and South Pacific Design Automation Conference, Chiba, Japan, 19/01/15. https://doi.org/10.1109/ASPDAC.2015.7059006

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/1

Y1 - 2015/1

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 - https://www.scopus.com/record/display.uri?eid=2-s2.0-84926429871&origin=inward

U2 - 10.1109/ASPDAC.2015.7059006

DO - 10.1109/ASPDAC.2015.7059006

M3 - Conference proceeding

T3 - Proceedings of Asia and South Pacific Design Automation Conference

SP - 208

EP - 213

BT - The 20th Asia and South Pacific Design Automation Conference

PB - IEEE

T2 - The 20th Asia and South Pacific Design Automation Conference

Y2 - 19 January 2015 through 22 January 2015

ER -

An efficient linear time triple patterning solver

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this