Double patterning lithography aware gridless detailed routing with innovative conflict graph

Yen Hung Lin*, Yih-Lang Li

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

23 Scopus citations


Double patterning lithography (DPL) is the most feasible solution for sub-32nm nodes owing to the recurrent delay in next generation lithography. DPL attempts to decompose a single layer of one layout into two masks in order to increase pitch size and improve depth of focus (DOF). Considering DPL at detailed routing stage can improve the flexibility of layout decomposition as compared to the post-routing layout decomposition. The conflict graph proposed in [8] provides a global view of all nets in a layout to obtain a highly decomposable layout with less yield loss. However, adopting conflict graph in routing process using grid-based model or gridless model both brings huge overhead. This work presents an innovative conflict graph (ICG) to realize adopting conflict graph in a routing process. Three routing-friendly characteristics of ICG are constanttime conflict cycle detection, lazy ICG update, and light-weight routing overhead. To efficiently utilize routing resources for a crowded region, gridless models provide a better solution space than grid-based models do. This work also develops, to our knowledge, the first DPL-aware gridless detailed routing with ICG to generate a highly decomposable routing result. Moreover, greedily assigning colors for routed nets may cause unnecessary stitches or even a coloring conflict. This work presents a deferred coloring assignmentbased routing flow to escape local optimum of a greedy coloring approach. Experimental results indicate that DPL-aware routing results contain no coloring conflicts, and the stitches produced by the proposed router are less than those produced by a greedy coloring approach by 41% on average with only 0.22% and 30% increment in wirelength and runtime, respectively.

Original languageEnglish
Title of host publicationProceedings of the 47th Design Automation Conference, DAC '10
Number of pages6
StatePublished - 2010
Event47th Design Automation Conference, DAC '10 - Anaheim, CA, United States
Duration: 13 Jun 201018 Jun 2010

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X


Conference47th Design Automation Conference, DAC '10
Country/TerritoryUnited States
CityAnaheim, CA


  • Detailed routing
  • Double patterning
  • Gridless model


Dive into the research topics of 'Double patterning lithography aware gridless detailed routing with innovative conflict graph'. Together they form a unique fingerprint.

Cite this