QB 樹: 一個趨向最佳之拓樸表示法及其於類比佈局設計之應用

Abstract

現今的類比積體電路擺置需要考慮多樣化的幾何限制來產生符合要求的布局設計。為了要能夠同時解決一般性的幾何限制，文獻上最先進的研究通常基於拓樸表示法並使用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.