超大規(guī)模集成電路的優(yōu)化布局算法.pdf

1、如今，隨著信息技術(shù)日新月異的進(jìn)步，集成電路技術(shù)得了長(zhǎng)足的發(fā)展，大規(guī)模集成電路的自動(dòng)布圖技術(shù)己經(jīng)被應(yīng)用于包括計(jì)算機(jī)，半導(dǎo)體、通訊、航天、航空、消費(fèi)電子和軍用電子等子在內(nèi)的諸多應(yīng)用領(lǐng)域。然而，世界著名的廠家均將此技術(shù)視為核心機(jī)密加以保護(hù)。在國(guó)內(nèi)，掌握集成電路核心技術(shù)的公司更是屈指可數(shù)，因此市場(chǎng)前景相當(dāng)廣闊。 同時(shí)，隨著超大規(guī)模集成電路制造工藝進(jìn)入了亞微米/深亞微米的時(shí)代，半導(dǎo)體工藝的特征尺寸越來越小、高集成度、高速度和高性能成了集成

2、電路設(shè)計(jì)的趨勢(shì)。這些新的發(fā)展趨勢(shì)都對(duì)集成電路版圖的計(jì)算機(jī)輔助設(shè)計(jì)提出了新的要求。作為版圖設(shè)計(jì)中至關(guān)重要的環(huán)節(jié)，布局也面臨著更加嚴(yán)峻的挑戰(zhàn)。這就要求研究人員根據(jù)目前的工藝技術(shù)不斷改進(jìn)布局算法，開發(fā)出更加適合VLSI產(chǎn)業(yè)發(fā)展的物理設(shè)計(jì)方法及可靠的集成電路設(shè)計(jì)軟件產(chǎn)品。本文即是在這個(gè)思想的引導(dǎo)下展開研究工作的。 本文首先介紹了計(jì)算機(jī)輔助設(shè)計(jì)在集成電路產(chǎn)業(yè)中的必要性，然后大體介紹了集成電路的設(shè)計(jì)流程和布圖設(shè)計(jì)以及布圖設(shè)計(jì)自動(dòng)化的概念，尤

3、其是和本文關(guān)系密切的物理設(shè)計(jì)中的布圖規(guī)劃和布局的概念；然后概述了國(guó)內(nèi)外的產(chǎn)業(yè)現(xiàn)狀，提出了集成電路技術(shù)在物理設(shè)計(jì)方面的發(fā)展和挑戰(zhàn)；最后提出了本文所做的研究的方向和內(nèi)容。 接著,重點(diǎn)討論線長(zhǎng)優(yōu)化目標(biāo)的布局算法。首先介紹分級(jí)設(shè)計(jì)的主要思想，然后介紹標(biāo)準(zhǔn)單元設(shè)計(jì)的基本方法，它是目前自動(dòng)化布圖設(shè)計(jì)的一種基本方式，這種設(shè)計(jì)方式是以預(yù)先設(shè)計(jì)好的標(biāo)準(zhǔn)單元庫(kù)為基礎(chǔ)的（本文的算法都是建立在標(biāo)準(zhǔn)單元庫(kù)基礎(chǔ)上的）；文中對(duì)幾種常用的線長(zhǎng)估算模型作了介紹，

4、這些模型在具體的算法實(shí)現(xiàn)上有精確度之分，經(jīng)過綜合考良，我們選擇半周長(zhǎng)估算模型，該方法計(jì)算簡(jiǎn)單，適用于超大規(guī)模電路布局中線網(wǎng)長(zhǎng)度的計(jì)算，另外，在大多數(shù)情況下，其估算誤差是可以接受的；然后以模擬退火算法為重點(diǎn)介紹幾種常見的線長(zhǎng)優(yōu)化布局算法；本文提出的線長(zhǎng)優(yōu)化驅(qū)動(dòng)布局算法思是：分為單元選擇和單元安置兩步進(jìn)行單元布局調(diào)整，在單元選擇中選擇內(nèi)外連接度作為選擇策略，單元優(yōu)化調(diào)整過程中采用改進(jìn)的等分節(jié)點(diǎn)法作為安置策略，最后給出實(shí)驗(yàn)結(jié)果和相應(yīng)的比較分析

5、。 亞微米/深亞微米工藝下互連線的時(shí)延已經(jīng)超過單元門時(shí)延成為決定集成電路芯片性能的關(guān)鍵因素，為了減少設(shè)計(jì)流程中“設(shè)計(jì)—驗(yàn)證—修改—再驗(yàn)證”循環(huán)的次數(shù)，縮短設(shè)計(jì)周期，提高整體性能，就必須在設(shè)計(jì)過程中考慮互連線時(shí)延因素，因而在設(shè)計(jì)模型和設(shè)計(jì)方法上都面臨巨大挑戰(zhàn)。對(duì)此，本文著重討論了以路徑為優(yōu)化目標(biāo)的布局算法。首先介紹了時(shí)序問題的基本概念，分析了互連線時(shí)延估算模型，并對(duì)當(dāng)前的時(shí)延布局算法進(jìn)行了分類分析。在此基礎(chǔ)上，提出了一種時(shí)延驅(qū)動(dòng)的

6、布局算法，該算法將優(yōu)化路徑時(shí)延問題轉(zhuǎn)化為優(yōu)化路徑上單元的位置問題，通過對(duì)各路徑單元實(shí)際延遲時(shí)間的估算，建立被優(yōu)化單元選擇隊(duì)列，然后通過改進(jìn)的等分節(jié)點(diǎn)法調(diào)整單元目標(biāo)位置，最終達(dá)到優(yōu)化關(guān)鍵路徑時(shí)延的目的。 隨著對(duì)芯片運(yùn)算速度及散熱性能要求的不斷提高，功耗驅(qū)動(dòng)布局算法重要性日益凸現(xiàn)。工業(yè)界通常采用減小芯片及封裝電容，降低供電電壓，采用電源管理策略以及使用較好的電路規(guī)劃技術(shù)等方法來降低功耗。而對(duì)于電路的布局優(yōu)化過程，在基于CMOS管的零

7、時(shí)延模型中，門的轉(zhuǎn)換率（switching rate）是保持不變的，降低功耗的唯一有效途徑就是減小高轉(zhuǎn)換率門單元的負(fù)載，采取在優(yōu)化目標(biāo)函數(shù)中引入轉(zhuǎn)換電容的方法來進(jìn)行功耗優(yōu)化。本文在先前采用基于等分節(jié)點(diǎn)法的單元安置策略的時(shí)延優(yōu)化布局算法優(yōu)化電路的整體時(shí)延特性的基礎(chǔ)上，進(jìn)一步建立功耗驅(qū)動(dòng)的目標(biāo)函數(shù)，再次優(yōu)化電路的功耗特性。同時(shí)在算法設(shè)計(jì)上較好解決二者之間優(yōu)化方向的一致性的問題，實(shí)驗(yàn)結(jié)果表明該算法是行之有效的。 最后，對(duì)本文所做的主要