Network flow based cut redistribution and insertion for advanced 1D layout design

Ye Zhang, Wai Shing Luk*, Fan Yang, Changhao Yan, Hai Zhou, Dian Zhou, Xuan Zeng

*Corresponding author for this work

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

2 Scopus citations

Abstract

End Cutting 1D layout design is a promising candidate for sub-10nm process nodes. Given a 1D layout with horizontal wires, cut redistribution technique is used for sliding the line-end cuts in order to align them vertically or resolve spacing conflicts. The aligned cuts can then be merged into a single shot of cuts. In this paper, we proposed a network flow based method for efficient cut redistribution and insertion. Normally, a pair of movable cuts could have three possible relations, left-of, right-of and merge-into. We observe that if the left-right-merge orderings of cuts are fixed, the cut redistribution can be formulated as a network flow problem, which can be solved efficiently. We also find that inserting cuts can resolve the spacing conflicts in some circumstances. This cut insertion strategy is introduced in our proposed method to reduce the spacing conflicts. Moreover, the complementary e-beam lithography for printing the cuts is also considered in this paper. Experimental results show that compared with a previous ILP-based method, our method can achieve a 200X speedup and competitive solution quality.

Original languageEnglish (US)
Title of host publication2017 22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages360-365
Number of pages6
ISBN (Electronic)9781509015580
DOIs
StatePublished - Feb 16 2017
Event22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017 - Chiba, Japan
Duration: Jan 16 2017Jan 19 2017

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Other

Other22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017
Country/TerritoryJapan
CityChiba
Period1/16/171/19/17

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Fingerprint

Dive into the research topics of 'Network flow based cut redistribution and insertion for advanced 1D layout design'. Together they form a unique fingerprint.

Cite this