以可繞度為導向考慮障礙物之巨集電路擺置

Abstract

為了加速產品上市速度，矽智財 (Intellectual Property) 巨集電路已 被廣泛地使用在先進系統單晶片 (System-on-a-Chip) 中。其中，部分 的巨集電路因為製程及其他設計的需求而被限制擺放在特定位置。對 於巨集電路擺置而言，這些須預置擺放的巨集電路將被視為障礙物， 且不得與其他巨集電路或標準單元重疊。在本篇論文中，我們提出一 個新的環形堆積樹 (CP-tree) 表示法來處理預置擺放巨集電路的問題。 CP-tree 藉由預置擺放巨集電路來快速且有效地擺置巨集電路於晶片四 周，並且保留完整空間來擺置標準單元。此外，巨集電路的位置與方 向會顯著影響標準單元放置及繞線擁塞程度。因此，不像其他的巨集 電路擺置器只考慮巨集電路之間的連線而忽略標準單元之可繞度，我 們提出一個全新的以可繞度為導向的繞線模型 (Routability-Driven Wirelength Model) 來降低繞線時的壅塞程度。此繞線模型不僅可以快速估計巨集電路與標準單元之間的連線長度，並且可將巨集電路直通 矽晶穿孔 (Macro Porosity) 反映在此模型上來增加晶片可繞度。實驗結 果顯示出，我們所提出的巨集電路擺置演算法方法相較於先前的巨集 電路擺置器，可以有效地得到最好的電路擺置結果。並且，藉由業界 的實際電路實驗結果亦顯示出，我們的方法可以得到最好的可繞度且 最能接近工程師手動擺置的結果。

To speed up the time to market for system-on-a-chip (SoC), a chip usually contains tens or even hundreds of intellectual property (IP) macros (e.g., analog blocks, embedded memories). Some of those macros, namely pre-placed macros, need to be placed at speci ed locations for di erent issues, such as power, ther- mal, and the connections with IO pads. In macro placement, the pre-placed macros are treated as blockages and not allowed to overlap with other macros. Hence, for complex designs with many pre-placed macros, it would incur the di culties of nding a non-overlapping placement result. To handle the blockages and prevent overlaps among macros, we propose a new circular-packing tree (CP-tree) oorplan representation for our macro placement algorithm. A CP-tree could exibly pack movable macros toward corners or toward pre-placed macros along chip boundaries circularly to optimize the macro positions and preserve a complete placement re- gion for standard-cell placement. Moreover, the macro positions and orientations would signi cantly a ect the wirelength and routing congestion in the standard-cell placement and routing stages, but most of existing macro placers only consider the interconnections among macros. Therefore, a routability-driven wirelength model is presented to fast estimate the wirelength among macros and standard cells and to consider the macro porosity e ect for better routability. Experimental results show the e ectiveness and e ciency of our macro placement algorithm. Compared with state-of-the-art academic macro placers, our algorithm obtains the best wire- length results in ISPD 2006 placement benchmarks. Furthermore, for real industry benchmarks, our algorithm can achieve the shortest routed wirelength results as competitive as manual designs, compared with leading academic mixed-size placers.