超大規(guī)模集成電路布局算法研究.pdf

1、當今信息時代，作為電子信息技術發(fā)展的核心和基礎，集成電路得到了迅猛的發(fā)展，這除了由于半導體工藝技術、設備、原材料等方面的不斷改進之外，計算機輔助設計技術的采用也是一個重要原因。然而，隨著半導體制造工藝的特征尺寸越來越小，芯片的集成度越來越大，電路的工作頻率越來越高，布圖工藝越來越復雜，這些發(fā)展都對集成電路計算機輔助設計技術提出了新的要求。布局作為集成電路版圖設計中一個基本而且非常重要的環(huán)節(jié)，也面臨著嚴峻的挑戰(zhàn)，在大規(guī)模(上百萬門的單元需

2、要布局)和復雜的設計約束(時延、噪聲、功耗、擁擠度等)條件下，如何獲得高質量的布局結果同時花費較少的布局時間非常關鍵。本文正是圍繞這些問題展開計算機輔助設計領域內的超大規(guī)模集成電路布局算法研究工作的，通過改進現有的方法以及提出新的布局算法，嘗試更好地解決當前和未來集成電路設計中的一些問題。 首先介紹了本文的研究對象——標準單元設計模式和基本的布局理論，然后對傳統(tǒng)的以線網總長為優(yōu)化目標的基本布局算法進行了分類分析。在此基礎上，提出

3、了一個基于改進等分節(jié)點法的啟發(fā)式迭代優(yōu)化布局算法，該算法對原有的等分節(jié)點法進行了改進，使得單元的目標位置在更廣的范圍內得到搜尋，從而提高了迭代法的優(yōu)化質量，而且通過使用啟發(fā)式策略使迭代優(yōu)化跳出局部最優(yōu)，設定合理的局部尋優(yōu)次數來有效地終止布局優(yōu)化，并采用記憶裝置記錄最優(yōu)布局結果，使整個優(yōu)化布局過程在沒有花費過多時間的情況下，得到了較充分的迭代優(yōu)化。實驗表明，與接近全局最優(yōu)的()Wolf7.0布局算法相比，該算法能夠獲得更好的布局質量。

4、 針對超大規(guī)模集成電路線長優(yōu)化布局中布局質量和花費時間的嚴峻挑戰(zhàn)，討論了面向高復雜度、大規(guī)模問題的有效解決策略——分級設計方法，分析了基于分級設計的各種超大規(guī)模集成電路線長優(yōu)化布局算法。在此基礎上，提出了一個基于劃分的迭代優(yōu)化布局算法，該算法采用分級設計將大規(guī)模的布局問題分拆，借鑒好的遞歸劃分方法將電路分解，采用和改進結群、終端傳遞等技術提高了劃分質量，并且結合本文提出的啟發(fā)式迭代優(yōu)化方法在劃分所得的各個子電路內進行并行布局優(yōu)化，在

5、保證布局質量的同時提高了布局速度。實驗表明，與當前流行的FengShui布局工具相比，該算法在花費稍長一點的時間內獲得了更好的布局質量。 時序約束作為保證電路正常工作性能的一個重要因素，本文討論了以路徑時延為優(yōu)化目標的布局算法。首先介紹了有關時序問題的基本知識，分析了互連線時延的估算模型，并對當前的各種時延驅動布局算法進行了分類分析。在此基礎上，提出了一個時延驅動布局算法，該算法基于對電路時延圖的拓撲結構分析，將優(yōu)化路徑時延的問

6、題轉換成優(yōu)化路徑上單元位置的問題，通過建立優(yōu)化單元位置的隊列鏈表，采用一種新的等分節(jié)點法尋找路徑上單元的目標位置，使得關鍵路徑的時延得到了有效地減小，路徑時延的分布更加合理。在優(yōu)化路徑時延的同時還結合了優(yōu)化線長的布局算法，在獲得好的路徑時延優(yōu)化效果的同時，能夠盡量保留原有已取得的好的線長優(yōu)化效果，使兩種布局優(yōu)化目標能夠有機地結合。 在深亞微米及更先進的工藝條件下，芯片的設計密度問題變得嚴峻起來，它會導致對布線資源需求的大幅度增加

7、，當芯片某些區(qū)域內的布線資源無法滿足實際的走線需要時，就會迫使線網繞道而行從而惡化設計性能，甚至無法實現100﹪布通率，造成布線擁擠，因此本文對以布線密度為優(yōu)化目標的擁擠度驅動布局算法進行了研究。首先介紹了布局階段使用的布線密度分析方法和常見的布線密度估計模型，在對現有的各種擁擠度驅動布局算法分析的基礎上，提出了一個用于布局后處理的擁擠度驅動布局算法，該算法對原有的線網邊框布線估計模型進行了改進，在保留估算速度快，易于編程實現等優(yōu)點的同

8、時，提高了分析布線密度的精度；在優(yōu)化布線擁擠度時，提出以線網為中心，通過逐步擴大或者縮小布線擁擠區(qū)域內線網邊框尺寸的方法，最終達到降低布線擁擠度的目的。實驗結果顯示，電路的布線溢出總量和布線溢出峰值都明顯減小，電路的布線擁擠情況得到了明顯的緩解。 最后，將本文布局算法的研究成果進行了軟件實現，開發(fā)了具有自主知識產權的布局自動設計工具。論文首先介紹了布局程序系統(tǒng)的結構框架，然后針對系統(tǒng)中各個軟件模塊分別進行了解釋和說明，并給出了用