請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78218
標題: | QB 樹: 一個趨向最佳之拓樸表示法及其於類比佈局設計之應用 QB-Trees: Towards an Optimal Topological Representation and Its Applications to Analog Layout Designs |
作者: | I-Peng Wu 吳一鵬 |
指導教授: | 張耀文(Yao-Wen Chang) |
關鍵字: | 實體設計,電路擺置,類比積體電路, Physical Design,Placement,Analog ICs, |
出版年 : | 2016 |
學位: | 碩士 |
摘要: | 現今的類比積體電路擺置需要考慮多樣化的幾何限制來產生符合要求的布局設計。為了要能夠同時解決一般性的幾何限制,文獻上最先進的研究通常基於拓樸表示法並使用simulated annealing 來產生結果,由於拓樸表示法的解空間較小並且效率較好。然而,沒有文獻能夠對一般幾何性的限制達到最佳的時間複雜度,此外,每份文獻僅能處理部分的限制。為了要彌補這些不足,在這篇論文裡我們提出了一個混合式的表示法,結合四分樹以及B*樹 (簡稱QB 樹) 在線性且最低時間複雜度內處理所有的限制。實驗結果顯示,跟目前文獻相比,本論文所提出的拓樸表示法及演算法不僅能同時最小化晶片的連線半周長以及面積,並且能在不同的工業界晶片上都有穩定且有效率的結果。 A modern analog placer often needs to consider various geometrical constraints to generate desired layouts. To handle general constraints simultaneously, current state-of-the-art works adopt simulated annealing based on topological representations, due to their smaller solution spaces and higher efficiency. However, no published work achieves the optimal time complexity for general geometrical constraint handling and module packing. Besides, only limited constraints are considered and handled in each work. To remedy these insufficiencies, we present a new hybrid representation of a quadtree and B*-trees (QB-tree, for short) to handle general geometrical constraints while achieving linear, lower-bound time complexity of module packing and constraint handling. Experimental results based on real industrial designs with various constraints show that our placer outperforms the leading published works in both runtime and solution quality. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78218 |
DOI: | 10.6342/NTU201600580 |
全文授權: | 有償授權 |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-R03943092-1.pdf 目前未授權公開取用 | 2.52 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。