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

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