[發(fā)明專利]基于多水平劃分法和賦權(quán)超圖的大規(guī)模集成電路劃分方法

無效

• 申請(qǐng)?zhí)枺?/td>: 201210155738.6
• 申請(qǐng)日: 2012-05-19
• 公開（公告）號(hào): CN102693340A
• 公開（公告）日: 2012-09-26
• 發(fā)明（設(shè)計(jì)）人: 冷明;孫凌宇;冷子陽
• 申請(qǐng)（專利權(quán)）人: 孫凌宇;冷明;冷子陽
• 主分類號(hào): G06F17/50
• 分類號(hào): G06F17/50;G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及一種設(shè)計(jì)大規(guī)模集成電路用的基于多水平劃分法和賦權(quán)超圖的大規(guī)模集成電路劃分方法。

背景技術(shù)

電路劃分在使用硬件描述語言設(shè)計(jì)大規(guī)模集成電路中占有重要的地位。隨著集成電路技術(shù)的快速發(fā)展，在一個(gè)芯片上集成幾百萬門甚至幾千萬門電路已成為現(xiàn)實(shí)，因此在大規(guī)模集成電路設(shè)計(jì)中使用電路劃分，可有效地降低對(duì)集成電路進(jìn)行模擬或綜合的復(fù)雜性等要求。電路劃分也是層次化設(shè)計(jì)思想的重要一環(huán)，電路可以在不同級(jí)別上進(jìn)行劃分：進(jìn)行系統(tǒng)級(jí)劃分把一個(gè)系統(tǒng)劃分到一組印刷電路板上，進(jìn)行板級(jí)劃分把印刷電路板上的電路劃分成一組芯片，進(jìn)行芯片級(jí)劃分把芯片中的電路劃分成更小的電路。電路劃分還有一個(gè)重要的原因就是滿足封裝性要求，電路中門的數(shù)目與輸入輸出引腳數(shù)目之間的關(guān)系受Rent規(guī)則約束，每個(gè)芯片上輸出引腳的數(shù)目以及門電路的數(shù)目都不能無限制增加，加之對(duì)大規(guī)模集成電路封裝性要求，所以必須對(duì)大規(guī)模集成電路進(jìn)行劃分。研究出一個(gè)好的電路劃分方法是提高大規(guī)模集成電路設(shè)計(jì)性能的必要條件。

請(qǐng)參見圖1所示，現(xiàn)有技術(shù)的電路劃分方法，第一步，用硬件描述語言描述被劃分的電路101，得到電路源代碼102；第二步，詞法分析電路的源代碼，得到對(duì)應(yīng)的單詞符號(hào)103；第三步，在詞法分析基礎(chǔ)上進(jìn)行語法分析，得到對(duì)應(yīng)的語法短語104；第四步，在語法分析基礎(chǔ)上進(jìn)行語義分析，得到對(duì)應(yīng)的類型信息105；第五步，在語義分析基礎(chǔ)上生成中間代碼，構(gòu)造對(duì)應(yīng)的電路線網(wǎng)106；第六步，根據(jù)中間代碼生成的線網(wǎng)，調(diào)用劃分程序109對(duì)電路進(jìn)行劃分；第七步，根據(jù)劃分結(jié)果修改對(duì)應(yīng)的線網(wǎng)，得到修改后線網(wǎng)107；第八步，對(duì)修改后線網(wǎng)進(jìn)行電路輸出，得到劃分后電路描述源代碼108。

從現(xiàn)有技術(shù)的電路劃分系統(tǒng)中有若干種邏輯電路的劃分法，這些劃分法從互連線數(shù)目最小，劃分后電路子集的邏輯單元數(shù)目均勻分布等不同的方面來實(shí)現(xiàn)，其中：基于遷移的劃分法。首先，產(chǎn)生電路的隨機(jī)初始劃分，同一個(gè)電路邏輯單元不能同時(shí)屬于兩個(gè)電路子集。在遷移優(yōu)化階段，該劃分法在兩個(gè)電路子集中各選取一個(gè)電路邏輯單元進(jìn)行成對(duì)交換，這兩個(gè)電路邏輯單元分別屬于兩個(gè)不同的電路子集且收益最大，從而每次都利用交換過程最大限度地改進(jìn)電路劃分質(zhì)量。在這個(gè)過程中，劃分法記錄割切達(dá)到最小值時(shí)刻的電路劃分結(jié)果，且一旦交換了選擇的兩個(gè)電路邏輯單元，在整個(gè)遷移過程余下的優(yōu)化改進(jìn)中，將這兩個(gè)電路邏輯單元鎖定使得它們不再被選中，重復(fù)上述過程直到所有可能的電路邏輯單元都經(jīng)遷移之后，然后回滾到累計(jì)收益最大值即割切最小值的時(shí)刻。該劃分法得到的電路劃分結(jié)果不穩(wěn)定，離散性很大，因此限制了該劃分法所能解決問題的規(guī)模。

水平嵌套劃分法。首先，選擇一個(gè)電路邏輯單元，把這個(gè)電路邏輯單元標(biāo)上0，然后把那些和這個(gè)電路邏輯單元相連的電路邏輯單元標(biāo)上1，之后對(duì)于那些還未標(biāo)上號(hào)碼，但是和已經(jīng)標(biāo)上號(hào)碼的電路邏輯單元相鄰的電路邏輯單元，將其標(biāo)號(hào)為相連的電路邏輯單元號(hào)碼上加1；直到一半的電路邏輯單元標(biāo)上號(hào)碼，標(biāo)號(hào)過程才結(jié)束。那些已經(jīng)標(biāo)上號(hào)碼的電路邏輯單元集合設(shè)為一個(gè)電路子集，其他電路邏輯單元為另一個(gè)電路子集。該劃分法只有在選取的初始電路邏輯單元接近外圍時(shí)，得到的電路劃分結(jié)果相對(duì)較好，因此得到的電路劃分結(jié)果也不穩(wěn)定。