A Gridless Approach to the Satisfiability of Self-Aligned Triple Patterning

自對準三圖案技術是次世代半導體製程進展至16nm以下之技術節點的解決方案。 自對準技術擁有能夠減少光罩之間重疊誤差的優勢因而非常具有吸引力。 然而，自對準三圖案的光罩分割是複雜且非直觀的，因此具有挑戰性。 自對準三圖案技術的光罩分割問題仍未被完整的研究，並欠缺實際的解決方法。 本論文提出了一個不須將佈局網格化之有效的演算法來解決自對準三圖案技術之光罩分割問題。 布林可滿足性以及線性規劃被應用來有效率的尋找解。 除了尋找最小化疊對誤差的光罩分割之外，我們亦提供了當光罩分割無解時，能偵測圖案設計中造成光罩無法製作的區域，使我們能更便利的修正圖案。 實驗結果證明了我們所提出的演算法優於過去所提出的解決自對準三圖案技術之光罩分割問題之演算法，並展示出利用布林可滿足性以及線性規劃來求解的優勢。Self-aligned triple patterning (SATP) lithography is one of the most promising technologies for next-generation semiconductor manufacturing process. Self-aligned patterning attracts much interest because of its significant advantage over the litho-etch-litho-etch patterning in reducing the overlay problem in lithography. However, pattern decomposition in SATP is challenging due to its counterintuitive mask synthesis. It remains relatively unstudied and its practical solutions remain to be proposed. This thesis proposes an effective algorithm for SATP layout decomposition without grid-based quantization and thus substantially reduces the number of variables and constraints in solution search. Boolean satisfiability (SAT) and integer linear programming (ILP) are exploited for efficient computation. In addition to deriving high-quality layout decomposition solutions with overlay minimization, our method also allows non-decomposable spot identification to facilitate layout rectification. Experimental results demonstrate the superiority of our method compared to prior work and show the relative advantages of SAT and ILP formulations