請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78212
標題: | 為達擺置線長最佳化考慮障礙區塊之端點傳遞 Blockage-Aware Terminal Propagation for Placement Wirelength Minimization |
作者: | Sheng-Wei Yang 楊勝為 |
指導教授: | 張耀文(Yao-Wen Chang) |
關鍵字: | 實體設計,電路擺置,端點傳遞,線長最佳化, Physical Design,Placement,Terminal Propagation,Wirelength Minimization, |
出版年 : | 2016 |
學位: | 碩士 |
摘要: | 在電路擺置演算法的發展中,線長最佳化一直是電路擺置問題最重要的其中一個目標。隨著製程的演進,縱使擺置問題出現了許多新目標與限制條件,繞線線長始終是現代電路擺置器中一個無法忽視的最佳化目標。電路擺置器多年來往往使用連線半周長作為衡量線長的比較標準。但連線半周長只有計算連線定界框周長的一半,因而過度簡化了連線線長。雖然連線半周長是一個快速又有效率的連線估計方法,卻無法反映一個連線是否可能產生迂迴繞線的情形。這是因為連線半周長計算連線長度時忽略了連線內部的連接狀態、連接數量以及是否繞過障礙區塊。在有障礙區塊的設計電路中,即使周遭仍有足夠區域的可擺置空間,以連線半周長為最佳化目標的電路擺置器很可能會為了達到連線半周長最佳化而將可移動之元件擺置在障礙區塊之上。這種現象很容易在障礙區塊附近形成迂迴繞線。另一方面,現今有很多精心設計的高效能電路擺置器是以連線半周長為最佳化核心引擎,因此,重新修正這些高效能電路擺置器的引擎會非常困難與昂貴。於
是,我們需要一個有效可以解決這個因為連線半周長而導致迂迴繞線的演算法,但又不能改變原本電路擺置器以連線半周長為最佳化核心目標的引擎。因此,這篇論文題出了一個端點傳遞電路擺置流程。端點傳遞電路擺置流程把我們提出的端點傳遞演算法和傳統電路擺置流程整合。端點傳遞的主要構想是依據每塊障礙區塊上的端點之連線情形創造端點空間,並將端點空間傳遞至估計繞線連線長最佳化之位。在迂迴繞線情況嚴重時,把擺置問題轉換成最小成本最大流問題並使用相對應的圖學演算法尋找最佳解。實驗數據顯示,相比於傳統電路擺置流程,本論文題出的端點傳遞電路擺置流程可以在不同的設計電路中皆達到更佳的全域繞線線長。 Throughout the development of placement algorithms, wirelength minimization has been one of the most important objectives for all placement problems. Although numerous objectives and constraints are added into placement problems, routed wirelength is still a non-negligible objective to almost all modern placement problems. Placers have been using half-perimeter wirelength (HPWL) as the metric for wirelength minimization for ages. However, HPWL oversimplifies wirelengths of nets by taking only the half-perimeter of the bounding boxes of nets. HPWL, although fast and efficient, cannot reflect possible routing detours due to its neglect of connectivities and blockages within bounding boxes of nets. For designs with preplaced blocks, placement algorithms with HPWL as their objective function can easily place cells onto preplaced blocks for the fullest minimization on half perimeter wirelength, in lieu of placeable regions. Such phenomenon may easily lead to serious routing detours around preplaced blocks. On the other hand, many well-developed modern placers are based on HPWL minimization, which makes HPWL too expensive to be replaced by any modified cost metrics. Therefore, an effective algorithm is needed to solve these HPWL-rooted routing detours without changing the original placement objective of HPWL minimization. This thesis describes an effective and efficient terminal propagated placement flow by integrating our fast and feasible preplacement algorithm into traditional placement flow. The main idea of our algorithm is to create an area for each preplaced terminal according to the connectivity of the terminal, and propagate preplaced terminals to feasible locations with minimized approximated routed wirelength from the original position to the propagated position. A mininum-cost maximum flow algorithm is applied if necessary to ensure that a propagation with optimal approximated routed wirelength is performed by our algorithm. Experimental results show that our flow outperforms traditional flow by 4% in average global routed wirelength. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78212 |
DOI: | 10.6342/NTU201600853 |
全文授權: | 有償授權 |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-R03943138-1.pdf 目前未授權公開取用 | 4.69 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。