CUHK electronic theses & dissertations collection

To reduce chip-scale topography variation, dummy fill is commonly used to improve the layout density uniformity. Previous works either sought the most uniform density distribution or sought to minimize the inserted dummy fills while satisfying certain density uniformity constraint. However, due to more stringent manufacturing challenges, more criteria, like line deviation and outlier, emerge at newer technology nodes.This work presents a joint optimization scheme to consider variation, total fill, line deviation, outlier, overlap and running time simultaneously. More specifically, we first partition the rectilinear fillable regions into rectangles for later processing. Inspired by the work–PTR (Polygon-To-Rectangle) in [3], we implement I-PTR (Improved PTR) and another new decomposition algorithm called L-PTR (Lowest overlapping edge PTR) to divide the fillable regions into rectangles according to the window boundaries on one hand and to get more large resulting rectangles on the other hand. After decomposition, we insert dummy fills into the fillable rectangular regions optimizing the fill metrics simultaneously. We propose three approaches–Fast Median approach, LP approach and Iterative approach. Among the three fill insertion algorithms, Fast Median is proven to be the best. Therefore we compare Fast Median with the top three contestants in the ICCAD Contest 2014 on the industrial benchmarks released by the contest organizer. Experiments show that Fast Median is 25× faster than the fastest one among the top three teams, and its quality score (0.70) outperforms the top three teams of which the scores are 0.63, 0.61 and 0.61 respectively.為了降低芯片的密度差異，冗餘的金屬填充物通常會被用來提高布線板的密度均勻性。過去的研究工作要麼一味以最大化均勻性为目标，要麼在滿足一定的密度差異的基礎上以加入佈線板的金屬填充物的總量最少为目标。然而，由於更加嚴格的工業製造挑戰，很多新的目標越來越舉足輕重，比如列密度差和異常值。本文提出了同時考慮總差異、填充物總量、列密度差、異常值、重疊和運行時間的優化方法。具體來說，首先我們將表示可填充區域的直角多邊形分解成矩形，方便後續的處理。受到相關工作——PTR[3]的啟發，我們實現了I-PTR和另外一種新的分解算法L-PTR來分解可填充區域，一方面，我們根據窗口邊界來分解，另一方面我們盡量分解得到更多大面積矩形。分解之後，我們將金屬填充物加入到可填充區域，同時優化各個目標函數。我們提出了三種優化方法——快速中值法，LP法和迭代法。在這三種方法當中，快速中值法被證明是最好的。所以我们将快速中值法與ICCAD 2014年競賽的前三名算法分別運用在比賽發佈的測試集上，進行對比。實驗數據表明，我們的快速中值法比前三名最快的還要快25倍。並且，我們的總得分（0.70）要優於前三名的得分（分别是0.63、0.61和0.61）。Liu, Chuangwen.Thesis M.Phil. Chinese University of Hong Kong 2015.Includes bibliographical references (leaves 59-62).Abstracts also in Chinese.Title from PDF title page (viewed on 12, October, 2016).Detailed summary in vernacular field only.Detailed summary in vernacular field only