Abstract
In this article we present a pairwise coloring (PWC) approach to tackle the layout decomposition problem for triple patterning lithography (TPL). The main idea is to reduce the problem to a set of bi-coloring problems. The overall solution is refined by applying a bi-coloring method for pairs of color sets per pass. One obvious advantage of this method is that the existing double patterning lithography (DPL) techniques can be reused effortlessly. Moreover, we observe that each pass can be fulfilled efficiently by integrating an SPQR-tree-graph-division-based bi-coloring method. In addition, to prevent the solution getting stuck in the local minima, an adaptive multi-start (AMS) approach is incorporated. Adaptive starting points are generated according to the vote of previous solutions. The experimental results show that our method is competitive with other works on both solution quality and runtime performance.
| Original language | English (US) |
|---|---|
| Article number | 2 |
| Journal | ACM Transactions on Design Automation of Electronic Systems |
| Volume | 21 |
| Issue number | 1 |
| DOIs | |
| State | Published - Nov 2015 |
Funding
This work was supported in part by the National Natural Science Foundation of China under Project 61125401, Project 61376040, Project 61274032, in part by the National Basic Research Program of China under Grant 2011CB309701, in part by the Shanghai Science and Technology Committee under Project 13XD1401100, in part by NSF under CCF-1115550, CCF-1218906 and CNS-1441695, and in part by SRC under 2014-TS-2559.
Keywords
- Adaptive multi-start
- Design for manufacturability
- Layout decomposition
- Pairwise coloring
- Triple patterning lithography
ASJC Scopus subject areas
- Computer Science Applications
- Computer Graphics and Computer-Aided Design
- Electrical and Electronic Engineering