Layout Decomposition Co-Optimization for Hybrid E-Beam and Multiple Patterning Lithography

Yunfeng Yang, Wai Shing Luk, David Z. Pan, Hai Zhou, Changhao Yan, Dian Zhou, Xuan Zeng*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


As the feature size keeps scaling down and the circuit complexity increases rapidly, a more advanced hybrid lithography, which combines multiple patterning and electron-beam lithography (EBL), is promising to further enhance the pattern resolution. In this paper, we formulate the layout decomposition problem for this hybrid lithography as a minimum vertex deletion K-partition problem, where K is the number of masks in multiple patterning. Stitch minimization and EBL throughput are considered uniformly by adding a virtual vertex between two feature vertices for each stitch candidate during the conflict graph construction phase. For K=2 , we propose a primal-dual (PD) method for solving the underlying minimum odd-cycle cover problem efficiently. In addition, a chain decomposition algorithm is employed for removing all 'noncyclable' edges. Furthermore, we investigate two versions of the PD method, one with planarization and one without. For K>2 , we propose a random-initialized local search method that iteratively applies the PD solver. Experimental results show that compared with a two-stage method, our proposed methods reduce the EBL usage by 65.5% with double patterning and 38.7% with triple patterning on average for the benchmarks.

Original languageEnglish (US)
Article number7368163
Pages (from-to)1532-1545
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number9
StatePublished - Sep 2016


  • Electron-beam (E-beam)
  • graph bipartization
  • hybrid lithography
  • layout decomposition
  • multiple patterning
  • primal-dual (PD)

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Layout Decomposition Co-Optimization for Hybrid E-Beam and Multiple Patterning Lithography'. Together they form a unique fingerprint.

Cite this