Layout decomposition for triple patterning lithography
Layout decomposition for triple patterning lithography
复制标题
DOI：
10.1109/iccad.2011.6105297
复制
发表时间：
2008-11
期刊：
影响因子：
--
通讯作者：
Bei Yu;Kun Yuan;Boyang Zhang;Duo Ding;D. Pan
中科院分区：
文献类型：
--
作者：
Bei Yu;Kun Yuan;Boyang Zhang;Duo Ding;D. Pan
随着最小特征尺寸和间距的进一步减小，三重图案化光刻(TPL)可能是沿着双图案化光刻(DPL)范例的193 nm延伸。然而，关于第三方物流布局分解的研究却很少。本文证明了第三方物流布局分解是一个比动态布局分解更困难的问题。在此基础上，提出了一种能同时最小化冲突和针数的第三方物流布局分解的一般整数线性规划公式。由于ILP的可扩展性很差，在不牺牲解质量的情况下，我们提出了三种加速技术：独立元件计算、布局图简化和桥计算。对于非常密集的布局，即使使用这些加速技术，ILP公式可能仍然太慢。因此，我们提出了一种新的第三方物流分解的向量规划公式，并通过有效的半定规划(SDP)逼近进行求解。实验结果表明，与基准ILP相比，采用加速技术的ILP可以减少82%的运行时间。使用基于SDP的算法，运行时间可以进一步减少42%，同时在针数(减少7%)和冲突(增加9%)之间进行一些折衷。然而，对于非常密集的布局，基于SDP的算法即使与加速的ILP相比也可以获得140倍的加速。
As minimum feature size and pitch spacing further decrease, triple patterning lithography (TPL) is a possible 193nm extension along the paradigm of double patterning lithography (DPL). However, there is very little study on TPL layout decomposition. In this paper, we show that TPL layout decomposition is a more difficult problem than that for DPL. We then propose a general integer linear programming formulation for TPL layout decomposition which can simultaneously minimize conflict and stitch numbers. Since ILP has very poor scalability, we propose three acceleration techniques without sacrificing solution quality: independent component computation, layout graph simplification, and bridge computation. For very dense layouts, even with these speedup techniques, ILP formulation may still be too slow. Therefore, we propose a novel vector programming formulation for TPL decomposition, and solve it through effective semidefinite programming (SDP) approximation. Experimental results show that the ILP with acceleration techniques can reduce 82% runtime compared to the baseline ILP. Using SDP based algorithm, the runtime can be further reduced by 42% with some tradeoff in the stitch number (reduced by 7%) and the conflict (9% more). However, for very dense layouts, SDP based algorithm can achieve 140× speed-up even compared with accelerated ILP.