- 學位論文
基於衝突圖預先著色之無縫合三圖樣微影感知繞線
Non-stitch Triple Patterning-Aware Routing Based on Conflict Graph Pre-coloring
摘要
多圖樣微影技術(Multiple patterning lithography)已成為一種改善製程節點的有效技術。為了進一步地將製程節點減少至14奈米以下，使用了三個不同的光罩於三次獨立曝光的三圖樣微影技術(Triple patterning lithography)被提出。要應用三圖樣微影技術必須解決三圖樣佈局分割(Triple patterning decomposition)問題，也就是如何分散佈局圖樣(Layout patterns)至三個光罩上。由於分割問題的高度複雜性，如何在繞線階段考慮三圖樣微影成為一個主要的挑戰。另一方面，縫合(Stitch)，也就是被分解的圖樣接合的地方，會由於重疊誤差而導致產率的損失。因此在分解過程中應盡量減少縫合數。為了徹底消除縫合的重疊錯誤，我們著重於無縫合三圖樣微影感知繞線(Non-stitch triple-patterning-aware routing)，也就是繞線中不允許縫合的產生。在這篇論文中，我們觀察到相關最先進的三圖樣微影感知繞線研究在延伸至無縫合繞線時可能產生自我交錯線路(Self-crossing net)。而且他們的演算法可能會由於連續的顏色決定而降低性能。要解決這些問題，我們提出一個不會在繞線中產生自我交錯線路的圖模型，並使用修改後的加權衝突圖來考慮整體的著色。在所提出的圖模型與加權衝突圖的基礎上，我們提出第一個無縫合三圖樣微影的繞線演算法，其中包括兩個主要階段：（1）衝突圖預先著色(Conflict graph pre-coloring)和（2）基於預先著色結果的無縫合繞線(Pre-coloring-based non-stitch routing)。衝突圖預先著色是於繞線之前基於加權衝突圖來決定顏色的程序。基於預先著色結果的無縫合繞線即是在無縫合繞線時加上預先著色的結果。實驗結果表明，與延伸的最先進研究相比，我們的繞線演算法可以有效率地達到無顏色衝突且無縫合的繞線結果。
並列摘要
Multiple patterning lithography has become a promising technology to enhance the feature density of advanced process nodes. For sub-14 nanometer technologies and below, triple patterning lithography that uses three different photomasks for three separate exposures is required. To apply the triple patterning technology, the triple patterning layout decomposition problem has to be solved, which decomposes the layout patterns into three photomasks such that the distance between any pair of patterns on a mask is larger than a threshold value, the minimum coloring spacing. Because of the high complexity of the decomposition problem and the low decomposability of an arbitrary layout, considering the decomposition constraints during the routing stage becomes a critical step for realizing triple patterning lithography. In addition, stitches, where the split mask patterns combine, may cause yield loss because of the overlay errors among different masks. Thus, the number of stitches should be minimized during decomposition. In order to completely avoid stitch-induced yield loss, we focus on the non-stitch triple patterning-aware routing problem, where stitch insertion is not allowed. In this thesis, we first observe that directly extending the algorithms of a state-of-the-art triple patterning-aware routing work to non-stitch routing may generate self-crossing nets. Furthermore, their algorithms may degrade performance due to sequential color decision. To resolve these problems, we propose a graph model not producing self-crossing nets during routing and use a weighted conflict graph to globally consider the net coloring. Base on the model and the weighted conflict graph, we propose the first non-stitch triple patterning-aware routing scheme, which consists of two main stages: (1) conflict graph pre-coloring followed by (2) pre-coloring-based non-stitch routing. Conflict graph pre-coloring is a process that decides the colors of nets by considering the weighted conflict graph before routing. Pre-coloring-based non-stitch routing is a process that routes the nets without inserting stitches based on the pre-coloring result from the first stage. Compared with the extended algorithms of the state-of-the-art work, the experimental results show that our routing scheme can efficiently generate routing results without any stitch and coloring conflict for the generated benchmarks.
參考文獻
延伸閱讀
- 賴弼廷（2011）。雙圖案微影技術下考慮原生衝突之電路軌道繞線〔碩士論文，國立中央大學〕。華藝線上圖書館。https://www.airitilibrary.com/Article/Detail?DocID=U0031-1903201314425273
- Chen, Y. S. (2020). 透過強化視覺問答模型進行微影製程熱點偵測之佈局圖案擷取 [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU202000507
- Chen, S. Y. (2009). 雙圖案微影技術下考慮原生衝突之導線攪動 [master's thesis, National Taiwan University]. Airiti Library. https://doi.org/10.6342/NTU.2009.02575
- 林軒平（2009）。利用決策樹、粒子族群最佳化與支持向量迴歸設計具脈衝雜訊偵測之中值型影像濾波器〔碩士論文，國立虎尾科技大學〕。華藝線上圖書館。https://doi.org/10.6827/NFU.2009.00032
- Kuo, C. Y. (2011). On the IC-colorings of complete tripartite graphs [master's thesis, Chung Yuan Christian University]. Airiti Library. https://doi.org/10.6840/cycu201100444