A novel layout decomposition algorithm for triple patterning lithography

ABSTRACT

While double patterning lithography (DPL) has been widely recognized as one of the most promising solutions for the sub-22nm technology node to enhance pattern printability, triple patterning lithography (TPL) will be required for gate, contact, and metal-1 layers which are too complex and dense to be split into only two masks, for the 15nm technology node and beyond. Nevertheless, there is very little research focusing on the layout decomposition for TPL. The recent work [16] proposed the first systematic study on the layout decomposition for TPL. However, the proposed algorithm extending a stitch-finding method used in DPL may miss legal stitch locations and generate conflicts that can be resolved by inserting stitches for TPL. In this paper, we point out two main differences between DPL and TPL layout decompositions. Based on the two differences, we propose a novel TPL layout decomposition algorithm. We first present two new graph reduction techniques to reduce the problem size without degrading overall solution quality. We then propose a stitch-aware mask assignment algorithm, based on a heuristic that finds a mask assignment such that the conflicts among the features in the same mask are more likely to be resolved by inserting stitches. Finally, stitches are inserted to resolve as many conflicts as possible. Experimental results show that the proposed layout decomposition algorithm can achieve around 56% reduction of conflicts and more than 40X speed-up compared to the previous work.

References

1. G. E. Bailey, A. Tritchkov, J.-W. Park, L. Hong, V. Wiaux, E. Hendrickx, S. Verhaegen, P. Xie, and J. Versluijs, "Double pattern EDA solutions for 32nm HP and beyond," Proc. SPIE, vol. 6521, pp. 65211K, 2007.
2. Y. Borodovsky, "Lithography 2009 overview of opportunities," in Semicon West, 2009.
3. C. Cork, J.-C. Madre, and L. Barnes, "Comparison of triple-patterning decom- position algorithms using aperiodic tiling patterns," Proc. SPIE, vol. 7028, pp. 702839, 2008.
4. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein "Introduction to Algorithms." The MIT Press, 2009.
5. M. R. Garey, D. S. Johnson, and L. Stockmeyer, "Some simplifed NP-complete problems," Proc. STOC, pp. 47--63, 1974.
6. D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, "Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning," Operations Research, 39:378--406, 1991.
7. A. B. Kahng, C.-H. Park, X. Xu, and H. Yao, "Layout decomposition approaches for double patterning lithography," IEEE TCAD, vol. 29, no. 6, pp. 939--952, 2010.
8. S. Khanna, N. Linial, and S. Safra, "On the hardness of approximating the chromatic number," Proc. ISTCS, pp. 250--260, 1993.
9. M. LaPedus, "SPIE: Intel to extend immersion to 11-nm," EE Times, Feb. 22, 2010.
10. F. T. Leighton, "A graph coloring algorithm for large scheduling problems," Journal of Research of the National Bureau of Standards, 84(6):489--506, 1979.
11. L. Liebmann and A. Torres, "A designer's guide to sub-resolution lithography: enabling the impossible to get to the 15nm node," Proc. DAC, 2011.
12. R. Merritt, "Otellini: Intel to ship more SoCs than PC CPUs--someday," EE Times, Sep. 22, 2009.
13. R. Tarjan, "Depth-first search and linear graph algorithms," Proc. SWAT, pp. 114--121, 1971.
14. Y. H. Tsin, "A simple 3-edge-connected component algorithm," Theory of Computing Systems, 40:125--142, 2007.
15. D. B. West, "Introduction to Graph Theory," Prentice Hall, 2001.
16. B. Yu, K. Yuan, B. Zhang, D. Ding, and D. Z. Pan, "Layout decomposition for triple patterning lithography," Proc. ICCAD, 2011.

Index Terms

• Hardware

  • Electronic design automation

    • Physical design (EDA)