基於元胞自動機和賦權超圖的大規模集成電路劃分方法

2023-05-23 00:34:01

專利名稱：基於元胞自動機和賦權超圖的大規模集成電路劃分方法
技術領域：
本發明涉及一種設計大規模集成電路用的基於元胞自動機和賦權超圖的大規模集成電路劃分方法。
背景技術：
電路劃分在使用硬體描述語言設計大規模集成電路中佔有重要的地位。隨著集成電路技術的快速發展，在一個晶片上集成幾百萬門甚至幾千萬門電路已成為現實，因此在大規模集成電路設計中使用電路劃分，可有效地降低對集成電路進行模擬或綜合的複雜性等要求。電路劃分也是層次化設計思想的重要一環，電路可以在不同級別上進行劃分進行系統級劃分把一個系統劃分到一組印刷電路板上，進行板級劃分把印刷電路板上的電路劃分成一組晶片，進行晶片級劃分把晶片中的電路劃分成更小的電路。電路劃分還有一個 重要的原因就是滿足封裝性要求，電路中門的數目與輸入輸出引腳數目之間的關係受Rent規則約束，每個晶片上輸出引腳的數目以及門電路的數目都不能無限制增加，加之對大規模集成電路封裝性要求，所以必須對大規模集成電路進行劃分。研究出一個好的電路劃分方法是提高大規模集成電路設計性能的必要條件。請參見圖I所示，現有技術的電路劃分方法，第一步，用硬體描述語言描述被劃分的電路101，得到電路原始碼102 ;第二步，詞法分析電路的原始碼，得到對應的單詞符號103 ;第三步，在詞法分析基礎上進行語法分析，得到對應的語法短語104 ;第四步，在語法分析基礎上進行語義分析，得到對應的類型信息105 ;第五步，在語義分析基礎上生成中間代碼，構造對應的電路線網106 ;第六步，根據中間代碼生成的線網，調用劃分程序109對電路進行劃分；第七步，根據劃分結果修改對應的線網，得到修改後線網107 ;第八步，對修改後線網進行電路輸出，得到劃分後電路描述原始碼108。從現有技術的電路劃分系統中有若干種邏輯電路的劃分法，這些劃分法從互連線數目最小，劃分後電路子集的邏輯單元數目均勻分布等不同的方面來實現，其中基於遷移的劃分法。首先，產生電路的隨機初始劃分，同一個電路邏輯單元不能同時屬於兩個電路子集。在遷移優化階段，該劃分法在兩個電路子集中各選取一個電路邏輯單元進行成對交換，這兩個電路邏輯單元分別屬於兩個不同的電路子集且收益最大，從而每次都利用交換過程最大限度地改進電路劃分質量。在這個過程中，劃分法記錄割切達到最小值時刻的電路劃分結果，且一旦交換了選擇的兩個電路邏輯單元，在整個遷移過程餘下的優化改進中，將這兩個電路邏輯單元鎖定使得它們不再被選中，重複上述過程直到所有可能的電路邏輯單元都經遷移之後，然後回滾到累計收益最大值即割切最小值的時刻。該劃分法得到的電路劃分結果不穩定，離散性很大，因此限制了該劃分法所能解決問題的規模。水平嵌套劃分法。首先，選擇一個電路邏輯單元，把這個電路邏輯單元標上0，然後把那些和這個電路邏輯單元相連的電路邏輯單元標上1，之後對於那些還未標上號碼，但是和已經標上號碼的電路邏輯單元相鄰的電路邏輯單元，將其標號為相連的電路邏輯單元號碼上加I ;直到一半的電路邏輯單元標上號碼，標號過程才結束。那些已經標上號碼的電路邏輯單元集合設為一個電路子集，其他電路邏輯單元為另一個電路子集。該劃分法只有在選取的初始電路邏輯單元接近外圍時，得到的電路劃分結果相對較好，因此得到的電路劃分結果也不穩定。多水平劃分法。首先，採用隨機匹配將某些電路邏輯單元結合在一起，得到下一水平層的粗化電路圖，重複此過程直到粗化電路圖足夠小為止，即得到一個最小電路圖。然後，採用劃分法對最小電路圖進行對分，得到一個初始二劃分。之後，將最小電路圖投影回初始電路圖，在每一水平層的細化電路劃分中，按照貪心原則選擇收益值最大的電路邏輯單元進行遷移優化，得到最後的電路劃分結果。2008年中國專利局公告的由冷明，鬱松年和孫凌宇申報，中國專利號為200710043765. 3號《基於多水平劃分法的大規模集成電路劃分方法》的發明專利，針對現有技術方案中因採用隨機策略進行匹配和貪心原則進行遷移優化，導致無法逃離局部最優的劃分，提供了一種改進的基於多水平劃分法的大規模集成電路劃分方法，有效地提高了大規模集成電路劃分的效率和性能。該發明專利在多水平劃分法的粗化階段，通過對結點屬性進行賦權無向圖中所有結點的核值求解排序，按照基於結點核值的非嚴格降序訪問處於未匹配狀態的結點，依據一定規則對其進行匹配，從而將連接性好的結點合併在一起；在多水平劃分法的優化階段，採用免疫克隆優化程序改進貪 心原則的局部搜索方法，對在每一水平層投影的劃分進行優化，藉助克隆操作、克隆變異操作、接種免疫疫苗操作、克隆選擇操作，使得改進後的方法在利用啟發信息搜索局部最優解的同時，更大自由地對具有潛力的解空間進行搜索，增加全局搜索能力。然而，由於該發明專利採用賦權無向圖作為大規模集成電路劃分問題的數學模型，因此存在著賦權無向圖最優劃分和大規模集成電路最優劃分的不一致性。本發明採用賦權超圖對電路劃分問題進行數學建模，其中電路邏輯單元表示為賦權超圖中的結點，電路單元間的連線表示為賦權超圖中的超邊。相比賦權無向圖而言，賦權超圖為電路提供了更為精確的模型每條超邊可以連接兩個以上的結點，對應於電路單元間的信號可以連接兩個以上的電路邏輯單元。近而，本發明將大規模集成電路劃分問題轉換為賦權超圖劃分問題，其中大規模集成電路劃分問題要求每個電路子集所包含的電路邏輯單元數目相等，對應於賦權超圖劃分問題的平衡約束條件，劃分結果使得這些電路子集之間的內連線數據達到最小，對應於賦權超圖劃分問題的最小化總截權。2012年中國專利局公告的由孫凌宇，冷明和冷子陽申報，中國專利號為201210150329. 7號《基於結點屬性函數的大規模集成電路的核值計算方法》的發明專利，在採用多水平劃分法求解賦權超圖劃分問題的粗化階段中，提供了所需的基於結點屬性函數的大規模集成電路的核值計算方法。該發明專利有利於在賦權超圖的結點匹配過程中，發揮結點核值導向性作用，使得粗化後超圖中結點權值傾向於大小一致，並最大程度地減少超邊的數目以及超邊權值之和，為大規模集成電路多水平劃分的後續階段提供更優的粗化超圖。此外，本發明採用元胞自動機對賦權超圖劃分問題進行數學建模，其中元胞對應於賦權超圖中的結點，鄰接元胞對應於鄰接超邊所包含的結點，元胞的狀態對應於所在的劃分子集，進而採用快速的元胞收益值和劃分割切值的計算方法，有效地降低了大規模集成電路劃分方法的空間複雜度和時間複雜度，並提高了大規模集成電路劃分的性能
發明內容
本發明的目的在於針對已有技術存在的不足，提供一種基於元胞自動機和賦權超圖的大規模集成電路劃分方法，提高大規模集成電路劃分的效率和性能。為達到上述目的，本發明的構思如下實現電路線網到賦權超圖的轉換，並保存為賦權超圖文件；然後啟動基於元胞自動機的賦權超圖劃分程序，對生成的賦權超圖進行劃分；最後依據賦權超圖的劃分結果，修改電路對應的線網，並通過遍歷修改後的線網，將得到的電路劃分結果以硬體描述語言存儲在電路描述文件中。根據上述的發明構思，本發明的技術方案是這樣實現的一種基於元胞自動機和賦權超圖的大規模集成電路劃分方法，其特徵在於，具體步驟如下。步驟1，用硬體描述語言描述該電路，生成該電路的原始碼。步驟2，詞法分析，從左到右一個個讀入該電路的原始碼，對構成原始碼的字符流
進行掃描和分解，從而識別出一個個單詞。步驟3，語法分析，在詞法分析的基礎上將單詞序列分解成各類語法短語，依據硬體描述語言的語法規則，確定整個字符流是否構成一個語法上正確的硬體描述語言程序。步驟4，語義分析，在語法分析的基礎上審核原始碼有無語義錯誤，為中間代碼生成階段收集類型信息。步驟5，中間代碼生成，在語法分析和語義分析的基礎上，將原始碼生成中間代碼，用內部中間格式表示。步驟6，賦權超圖文件生成，基於中間代碼構造文本描述的電路對應的線網，經過電路線網到賦權超圖的轉換之後，保存為賦權超圖文件。步驟7，賦權超圖劃分，啟動基於元胞自動機的賦權超圖劃分程序，讀取賦權超圖文件，採用基於元胞自動機的壓縮存儲格式對賦權超圖進行存儲，對生成的賦權超圖進行劃分，將最終得到的劃分結果存儲在賦權超圖劃分文件中。步驟8，修改線網，在檢測到基於元胞自動機的賦權超圖劃分程序完成劃分之後，從賦權超圖劃分文件中讀取相應的劃分結果，根據劃分結果修改電路對應的線網。步驟9，電路輸出，遍歷修改後的線網，將得到的電路劃分結果以硬體描述語言存儲在電路描述文件中。上述的步驟6中，所述的賦權超圖文件生成的步驟如下。步驟6. 1，基於中間代碼構造電路原始碼描述電路對應的線網，生成完整電路線網。一個完整的電路線網看作是一個根模塊，它由層次化的子模塊實例和電路邏輯單元通過信號互連構成，且每個子模塊內部由埠、電路邏輯單元、嵌套子模塊的實例通過信號連接構成。步驟6. 2，從根模塊開始，遞歸遍歷層次化線網的模塊，為每個電路邏輯單元編號。步驟6. 3，從根模塊開始，遞歸遍歷層次化線網的模塊，為每個電路邏輯單元之間的信號編號，並確立每個信號X的連接方式，實現到賦權超圖的轉換。其中，電路線網中的電路邏輯單元用賦權超圖的結點表示，電路線網中的信號用賦權超圖的超邊表示。結點的權值代表電路邏輯單元的大小，超邊的權值代表電路邏輯單元之間信號連線的權值。i為賦權超圖中結點的編號，取值範圍為I到電路線網中電路邏輯單元的總個數n。j為賦權超圖中超邊的編號，取值範圍為I到電路線網中信號的總個數m。
步驟6. 4，將轉換得到的賦權超圖保存為賦權超圖文件。上述的步驟7中，所述的基於元胞自動機的賦權超圖劃分方法的步驟如下。步驟7. 1，讀取賦權超圖文件，採用基於元胞自動機的壓縮存儲格式對賦權超圖進行存儲，其中元胞對應於賦權超圖中的結點，鄰接元胞對應於賦權超圖中鄰接超邊所包含的結點。步驟7. 2,元胞初始化,遍歷每個元胞並隨機給定元胞所處的狀態0或I,分別代表元胞對應結點所處的劃分子集Vl或V2，從而得到初始劃分。步驟7. 3，初始化二維輔助數組EDG[2] [m]，依據初始劃分，初始化二維輔助數組EDG[2] [m]。 步驟7. 4，計算初始劃分的割切值，依據二維輔助數組EDG[2] [m]，快速計算當前劃分的割切值。步驟7. 5，循環初始化，初始化循環計數器COUNT為O。步驟7. 6，遍歷每個元胞是否結束，如果訪問未結束，即存在當前元胞未被訪問，則轉步驟7. 7 ;否則訪問結束，轉步驟7. 13。步驟7. 7，計算當前元胞的收益值，根據當前元胞的狀態和鄰接元胞的狀態，快速計算當前元胞的收益值。步驟7. 8，演化當前元胞狀態，如果當前元胞的收益值大於零，當前元胞狀態一定從當前狀態from翻轉到翻轉狀態to，否則當前元胞狀態以一定概率從當前狀態from翻轉到翻轉狀態to。步驟7. 9，如果當前元胞狀態從當前狀態from翻轉到翻轉狀態to，則轉步驟7. 10，否則轉步驟7. 6。步驟7. 10，更新二維輔助數組EDG[2] [m]，遍曆元胞的所有鄰接超邊e，執行EDG [from] [e]減 I 操作，EDG [to] [e]加 I 操作。步驟7. 11，更新當前劃分的割切值，依據二維輔助數組EDG[2] [m]，快速計算當前劃分的割切值。步驟7. 12，更新已找到的最優劃分，轉步驟7. 6。步驟7. 13，循環判斷，循環計數器COUNT加1，若滿足COUNT達到設定演化次數的條件I或者全部元胞都不再改變自身狀態的條件2時，執行步驟7. 14，否則返回步驟7. 6。步驟7. 14，運行基於FM-EE方法的賦權超圖劃分程序由於在基於元胞自動機的賦權超圖劃分過程中，可能違背賦權超圖劃分問題的平衡約束條件，因此在基於元胞自動機的賦權超圖劃分所求解的基礎上，運行基於FM-EE方法的賦權超圖劃分方法，使劃分解滿足平衡約束條件，從而得到賦權超圖劃分問題的劃分解。步驟7. 15，將最終得到的賦權超圖劃分結果存儲在賦權超圖劃分文件中。上述的步驟6. 3中，所述的確立信號X連接方式的步驟如下。步驟6. 3. 1，依次處理信號X的每個管腳連接，支持跨層次連接，尋找到連接端的電路邏輯單元y。步驟6. 3. 2，如果電路邏輯單元y已經存在信號x的連接中，則忽略該電路邏輯單元I。否則在信號X的連接中增加該電路邏輯單元y。上述的步驟7. I中，所述的賦權超圖的基於元胞自動機的壓縮存儲格式如下。
步驟7. I. 1，使用ID數組存儲元胞對應於賦權超圖中結點的編號信息，且ID數組的大小為賦權超圖中的結點個數。步驟7. I. 2，使用state數組存儲元胞的狀態信息，且state數組的大小為賦權超圖中的結點個數。步驟7. I. 3，使用vwgts數組存儲元胞對應於賦權超圖中結點的權值信息，且VWgt S數組的大小為賦權超圖中的結點個數。步驟7. I. 4，使用xadj數組存儲每個結點所有鄰接超邊列表的起始位置信息，即第i條結點的終止位置為第i+1條結點的起始位置減1，且xadj數組的大小為賦權超圖中的結點個數加1，xadj數組最後一個元素用於存放最後一條結點的終止位置。步驟7. I. 5，使用adjncy數組存儲每個結點所有鄰接超邊的列表信息，第i條結點的鄰接超邊列表存儲在adjncy數組中，從adjncy [xadj [i]]到adjncy [xadj [i+1] _1]。 步驟7. I. 6，使用eptr數組存儲每條超邊所包含的結點列表的起始位置信息，即第j條超邊的終止位置為第j+1條超邊的起始位置減1，且eptr數組的大小為賦權超圖中的超邊個數加1，eptr數組最後一個元素用於存放最後一條超邊的終止位置。步驟7. I. 7，使用eind數組存儲每條超邊所包含結點的列表信息，第j條超邊的鄰接結點列表存儲在eind數組中，從eind[eptr[j]]到eind[eptr [j+l]_l]。步驟7. 1.8,使用hewgts數組存儲超邊的權值信息,且hewgts數組的大小為賦權超圖中的超邊個數。上述的步驟7. 3中，所述的初始化二維輔助數組EDG[2] [m]的步驟如下。步驟7. 3. 1，二維輔助數組EDG [2] [m]清零。步驟7. 3. 2,讀取eptr數組和eind數組存儲的每條超邊所包含的結點信息,基於初始劃分計算每條超邊在劃分子集Vl和V2的結點個數，即二維輔助數組EDG[2] [m]的兩行分別存放每條超邊在劃分子集Vl和V2的結點個數。上述的步驟7. 4和步驟7. 11中，所述的快速計算當前劃分的割切值的步驟如下。步驟7. 4. 1，劃分割切值清零。步驟7. 4. 2，遍歷每條超邊是否結束，如果訪問未結束，即存在超邊e未被訪問，則轉步驟7. 4. 3 ;否則訪問結束，返回劃分割切值。步驟7. 4. 3，如果滿足EDG
[e]彡I的條件I和EDG[I] [e]彡I的條件2時，意味著超邊e在劃分子集Vl和V2的結點個數都大於等於1，即可判定超邊e是兩棲邊，並將劃分割切值累加上當前超邊的權值；否則判定超邊e不是兩棲邊，劃分割切值不變。步驟7. 4. 4，轉步驟 7. 4. 2。上述的步驟7. 7中，所述的快速計算當前元胞收益值的步驟如下。步驟7.7.1，元胞收益值清零。步驟7. 7. 2，讀取元胞的當前狀態from和翻轉狀態to。步驟7. 7. 3，遍曆元胞的所有鄰接超邊e，若二維數組EDG[from] [e]值為1，則將收益值加上超邊e的權值；若二維數組EDG[to] [e]值為0，則將收益值減去超邊e的權值。步驟7. 7. 4，返回元胞收益值。本發明與現有技術相比較，具有如下顯而易見的突出實質性特點和顯著優點。I、提高了電路劃分的效率。
本發明基於元胞自動機和賦權超圖的大規模集成電路劃分方法，由於通過電路線網到賦權超圖文件的轉換，然後啟動基於元胞自動機的賦權超圖劃分程序，對生成的賦權超圖進行劃分，從而避免了劃分方法直接在電路線網上進行劃分，並且可以通過設置劃分方法的參數來獲取較優的劃分結果後，再進行電路線網的修改，從而有效地提高了電路劃分的效率。2、提高了電路劃分的性能。本發明基於元胞自動機和賦權超圖的大規模集成電路劃分方法，藉助二維輔助數組EDG[2] [m]存儲每條超邊在劃分子集的結點個數，實現了快速的元胞收益值和劃分割切值的計算方法，有效地避免了遍歷超邊中的結點。基於ISTO98測試基準給出的18組電路，進行了賦權無向圖和賦權超圖劃分方法、遷移方法和元胞自動機、以及不同演化代數和接受劣解概率情況下的對比實驗。實驗數據表明，相比賦權無向圖劃分方法和遷移方法，該方法有效地找到比現有技術更優的電路劃分結果，降低了空間複雜度和時間複雜度，最終顯著地提高了電路劃分的性能。 通過以下對本發明基於元胞自動機和賦權超圖的大規模集成電路劃分方法的實例結合其附圖
的描述，可以進一步理解本發明的目的、具體結構特徵和優點。圖I是現有技術的電路劃分系統中電路劃分方法的流程圖。圖2是本發明基於元胞自動機和賦權超圖的大規模集成電路劃分方法的流程圖。圖3是本發明的賦權超圖的基於元胞自動機的壓縮存儲格式。圖4是本發明的基於元胞自動機的賦權超圖劃分方法的流程圖。圖5表中給出了基於元胞自動機的賦權無向圖劃分方法、基於FM的賦權超圖劃分方法和基於元胞自動機的賦權超圖劃分方法的割切最小值和平均值對比實驗數據表。圖6表中給出了本發明基於元胞自動機的賦權超圖劃分方法在不同演化代數和接受劣解概率情況下的割切最小值和平均值對比實驗數據。
具體實施方式
。為了能夠更清楚地理解本發明基於元胞自動機和賦權超圖的大規模集成電路劃分方法的技術內容，特舉以下實例詳細說明。現有技術的電路劃分方法的流程圖如圖I所示，第一步，用硬體描述語言描述被劃分的電路101，得到電路原始碼102 ;第二步，詞法分析電路的原始碼，得到對應的單詞符號103 ;第三步，在詞法分析基礎上進行語法分析，得到對應的語法短語104 ;第四步，在語法分析基礎上進行語義分析，得到對應的類型信息105 ;第五步，在語義分析基礎上生成中間代碼，構造對應的電路線網106 ;第六步，根據中間代碼生成的線網，調用劃分程序109對電路進行劃分；第七步，根據劃分結果修改對應的線網，得到修改後線網107 ;第八步，對修改後線網進行電路輸出，得到劃分後電路描述原始碼108。 本實施例的基於元胞自動機和賦權超圖的大規模集成電路劃分方法的流程圖如圖2所示，用硬體描述語言描述被劃分的電路201，得到電路原始碼202 ;詞法分析電路的原始碼，得到對應的單詞符號203 ;在詞法分析基礎上進行語法分析，得到對應的語法短語204 ;在語法分析基礎上進行語義分析，得到對應的類型信息205 ;在語義分析基礎上，構造對應的內部中間代碼206 ;基於內部中間代碼構造文本描述的電路對應的線網207，經過電路線網到賦權超圖的轉換之後，保存為賦權超圖文件210 ;啟動基於元胞自動機的賦權超圖劃分程序215，讀取賦權超圖文件210，得到基於元胞自動機的壓縮存儲格式的賦權超圖212 ;進入到劃分階段，進行基於元胞自動機的賦權超圖劃分程序213，對生成的賦權超圖進行劃分；進入到平衡階段，運行基於FM-EE方法的賦權超圖劃分程序214，使賦權超圖的劃分結果滿足平衡約束條件，並將最終得到的劃分結果存儲為賦權超圖劃分文件211 ;在檢測到基於元胞自動機的賦權超圖劃分程序215完成劃分之後，從賦權超圖劃分文件211中讀取相應的劃分結果，根據劃分結果修改電路對應的線網，得到劃分結果對應的修改後線網208 ;遍歷修改後的線網，將得到的電路劃分結果以硬體描述語言存儲為電路描述文件 209。本實施例的賦權超圖文件的文件存儲格式參見在先技術[I] 「G. Karypisand V. Kumar. HMetis 1.5.3: A Hypergraph Partitioning Package [R]. Technicalreport, Department of Computer Science, University of Minnesota, 1998.，，和在先技術[2] 「孫凌宇，冷明，郭愷強，朱平.一種VLSI設計到超圖的轉換系統[J].計算機 工程與應用，2012，Vol. 29，Issue. 2，Pages 7-16. 」。本實施例的基於FM-EE方法的賦權超圖劃分程序參見在先技術[3] "KarypisG, Aggarwal R, Kumar V, Shekhar S. Multilevel hypergraph partitioning:Applications in VLSI domain[J]. IEEE transactions on very large scaleintegration systems, 1999, Vol. 7, Issue.I, Pages 69-79. 」。本實施例的賦權超圖的基於元胞自動機的壓縮存儲格式如圖3所示。圖例302所示的元胞存儲結構，其中不僅存儲了自身的編號、狀態和權值，還存儲了鄰接超邊的起始位置。基於元胞自動機的壓縮存儲格式使用ID數組303存儲元胞對應於賦權超圖中結點的編號信息，且ID數組303的大小為賦權超圖中的結點個數。使用state數組304存儲元胞的狀態信息，且state數組304的大小為賦權超圖中的結點個數。使用vwgts數組305存儲結點的權值信息，且Wgts數組305的大小為賦權超圖中的結點個數。使用xadj數組306存儲每個結點所有鄰接超邊列表的起始位置信息，即第i條結點的終止位置為第i+1條結點的起始位置減1，且xadj數組306的大小為賦權超圖中的結點個數加1，xadj數組306最後一個元素用於存放最後一條結點的終止位置。使用adjncy數組307存儲每個結點所有鄰接超邊的列表信息。使用hewgts數組308存儲超邊的權值信息,且hewgts數組308的大小為賦權超圖中的超邊個數。使用eptr數組309存儲每條超邊所包含的結點列表的起始位置信息，即第j條超邊的終止位置為第j+1條超邊的起始位置減1，且eptr數組309的大小為賦權超圖中的超邊個數加1，eptr數組309最後一個元素用於存放最後一條超邊的終止位置。使用eind數組310存儲每條超邊所包含結點的列表信息。假設數組地址從零開始，結點編號從零開始，則第i條結點的鄰接超邊列表存儲在adjncy數組307中，從adjncy [xadj [i]]到adjncy [xadj [i+1]-I];第j條超邊的鄰接結點列表存儲在eind數組310中，從eind [eptr [j]]到eind [eptr [j+1]-I]。圖例301的賦權超圖包含總共7個結點和8條超邊，其中第6個結點的權值為7，有2條鄰接超邊f、h，對應的權值為4、I，且相應的鄰接結點分別為結點7、3、6和結點4、6。本實施例的基於元胞自動機的賦權超圖劃分方法的流程圖如圖4所示，步驟如下。AOl :讀取賦權超圖文件。
A02 :元胞初始化。A03 :初始化二維輔助數組EDG [2] [m]。A04 :計算初始劃分的割切值。A05 :初始化循環計數器COUNT為O。A06 :遍歷每個元胞是否結束，如果訪問未結束，即存在當前元胞未被訪問，則轉步驟A07 ;否則訪問結束，轉步驟A13。A07 :計算當前元胞的收益值。A08 :演化當前元胞狀態。A09 :如果當前元胞狀態從當前狀態from翻轉到翻轉狀態to，則轉步驟A10，否則 轉步驟A 06。AlO :更新二維輔助數組EDG [2] [m]。All :更新當前劃分的割切值。A12 :更新已找到的最優劃分，轉步驟A06。A13 :循環計數器COUNT加1，若滿足COUNT達到設定演化次數的條件I或者全部元胞都不再改變自身狀態的條件2時，執行步驟A 14，否則返回步驟A 06。A14:運行基於FM-EE方法的賦權超圖劃分程序。A15 :將最終得到的賦權超圖劃分結果存儲在賦權超圖劃分文件中。 本實施例中，基於元胞自動機和賦權超圖的大規模集成電路劃分方法採用ANSIC來實現，作業系統為WIN2003，運行在2. 4GHz的Intel公司的Xeon-CPU_E5620晶片上，內存為8G。實驗方案所用的測試基準電路為1998年IBM公司Austin研究實驗室的Alpert教授給出的18組電路測試基準ISTO98。ISTO98是基於IBM公司Austin、Burlington、Rochester設計部門給出的一系列內部電子產品經過轉換得到，包括總線仲裁器、總線電橋晶片、內存及周邊元件擴展總線接口、通訊適配器、內存控制器、處理器和圖形適配器等。本實施例分別按照在先技術[4] 「孫凌宇，冷明，彭宣戈.一種ISTO98電路網表到圖的轉換算法[J].井岡山學院學報(自然科學)，2008，Vol. 29, Issue. 4, Pages 19-21.」給出的ISTO98電路測試基準到賦權無向圖轉換方法，以及在先技術[5] 「冷明，孫凌宇，郭愷強.一種ISTO98電路網表到賦權超圖的轉換算法[J].微電子學與計算機，2011，Vol. 28, Issue. 9，Pages 111-114. 」給出的ISTO98電路測試基準到賦權超圖轉換方法的偽代碼，採用ANSI C編程實現，將ISTO98電路劃分問題轉換為賦權無向圖劃分問題和賦權超圖劃分問題。其中，在轉換後的賦權無向圖劃分問題中，電路單元表示為賦權無向圖的結點，電路單元間的連線表示為賦權無向圖的邊。在轉換後的賦權超圖劃分問題中，電路單元表示為賦權超圖的結點，電路單元間的連線表示為賦權超圖的超邊。電路劃分要求每個電路子集所包含的元件數目相等，對應於劃分問題的平衡約束條件，劃分結果使得這些電路子集之間的連線數據達到最小，對應於劃分問題的最小化總截權。ISTO98電路測試基準的18組電路轉換到賦權無向圖後，賦權無向圖中的結點數範圍從12752到210613，邊數範圍從109183到2235716 ；ISPD98電路測試基準的18組電路轉換到賦權超圖後，賦權超圖中的結點數範圍從12752到210613，賦權超邊數範圍從14111到201920。實驗方案針為了保證實驗結果的可重複性和公正性，針對每組電路測試基準轉換後的賦權無向圖和賦權超圖，本實施例進行了 20次二劃分的對比實驗。每次實驗設定平衡約束參數為0. 02，允許劃分得到的結點子集權值之和偏差為所有結點子集權值之和的2%。對於實驗結果採用的評估指標為20次劃分實驗中得到的劃分割切最小值(Min)和劃分割切平均值Ave);為了保證實驗結果的可重複性，在20次對比實驗中固定選用了 20個不同的隨機數種子。本實施例進行了基於元胞自動機的賦權無向圖劃分方法(CA-Graph)(參見在先技術[6] 「孫凌宇，冷明，彭宣戈.一種基於元胞自動機的無向圖剖分優化算法[J].計算機工程與應用，2008，Vol. 44, Issue. 24，Pages 46-49. 」)、基於FM的賦權超圖劃分方法(FM-HyperGraph)(參見在先技術[7]「Fiduccia C，Mattheyses R. A linear-timeheuristics for improving network partitions[C]. Proceedings of the 19th DesignAutomation Conference. Los Alamitos: IEEE Computer Society Press, 1982, Pages175-181.，，)和本發明基於元胞自動機的賦權超圖劃分方法(CA-HyperGraph)的割切最小值和平均值的對比實驗。在CA-Graph和CA-HyperGraph方法中，設定的演化代數是400,接受劣解的概率為0. 05,即元胞的當前收益值小於或等於零時進行元胞狀態翻轉的概率為 0. 05。圖5表中給出了基於元胞自動機的賦權無向圖劃分方法、基於FM的賦權超圖劃分方法和基於元胞自動機的賦權超圖劃分方法的割切最小值和平均值對比實驗數據表。實驗數據對比表明⑴CA-Graph的賦權無向圖劃分方法得到的割切值遠大於CA-HyperGraph和FM-HyperGraph賦權超圖劃分方法。表明賦權超圖相比賦權無向圖而言，為電路劃分提供了更為精確的模型每條超邊可以連接兩個以上的結點，對應於電路單元間的連線可以連接兩個以上的電路單元；(2) CA-HyperGraph和FM-HyperGraph方法分別得到8組電路的割切最小值，表明CA-HyperGraph方法,具備和FM-HyperGraph方法相同的逃離局部最優能力。然而，相比CA-HyperGraph方法的演化規則,FM-HyperGraph方法基於按結點收益值排序的散列結構，對收益值最大的結點進行遷移，增加了其時空複雜度和實現難度。本實施例還進行了基於元胞自動機的賦權超圖劃分方法在設定不同演化代數和接受劣解概率情況下的割切最小值和平均值的兩組對比實驗⑴第一組對比實驗設定演化代數是400，接受劣解的概率分別為0. 10,0. 05和0. 02 ;⑵第二組對比實驗設定演化代數是800，接受劣解的概率分別為0. 10,0. 05和0. 02。圖6表中給出了本發明基於元胞自動機的賦權超圖劃分方法在不同演化代數和接受劣解概率情況下的割切最小值和平均值對比實驗數據。實驗數據對比表明⑴在相同的演化代數情況下，割切最小值基本沒有變化；在相同的接受劣解概率情況下，割切最小值隨著演化代數的增加而變小。兩者表明演化代數越大，方法求解的割切最小值越小。⑵在相同的演化代數情況下，割切平均值隨著接受劣解的概率變小而變小。表明接受劣解的概率越小，方法求解的割切平均值越小。⑶在相同的演化代數情況下，割切最小值即使發生個別的變化，其趨勢也是隨著接受劣解的概率的變小而變小。⑷在相同的接受劣解概率情況下，割切平均值隨著演化代數的增加而變小。實驗結果展示了基於元胞自動機和賦權超圖的大規模集成電路劃分方法良好的性能⑴相比賦權無向圖劃分方法，賦權超圖劃分方法取得的劃分有了較大的改進；⑵相比遷移方法，元胞自動機具備相同的逃離局部最優能力，並降低了其時空複雜度和實現難度；(3)本發明基於元胞自動機的賦權超圖劃分方法的演化代數決定了割切最小值發現的概率，接受劣解的概率決定了割切平均值變小的傾向。
權利要求
1.一種基於元胞自動機和賦權超圖的大規模集成電路劃分方法，其特徵在於，具體步驟如下 步驟I，用硬體描述語言描述該電路，生成該電路的原始碼； 步驟2，詞法分析，從左到右一個個讀入該電路的原始碼，對構成原始碼的字符流進行掃描和分解，從而識別出一個個單詞； 步驟3，語法分析，在詞法分析的基礎上將單詞序列分解成各類語法短語，依據硬體描述語言的語法規則，確定整個字符流是否構成一個語法上正確的硬體描述語言程序； 步驟4，語義分析，在語法分析的基礎上審核原始碼有無語義錯誤，為中間代碼生成階段收集類型信息； 步驟5，中間代碼生成，在語法分析和語義分析的基礎上，將原始碼生成中間代碼，用內部中間格式表示； 步驟6，賦權超圖文件生成，基於中間代碼構造文本描述的電路對應的線網，經過電路線網到賦權超圖的轉換之後，保存為賦權超圖文件； 步驟7，賦權超圖劃分，啟動基於元胞自動機的賦權超圖劃分程序，讀取賦權超圖文件，採用基於元胞自動機的壓縮存儲格式對賦權超圖進行存儲，對生成的賦權超圖進行劃分，將最終得到的劃分結果存儲在賦權超圖劃分文件中； 步驟8，修改線網，在檢測到基於元胞自動機的賦權超圖劃分程序完成劃分之後，從賦權超圖劃分文件中讀取相應的劃分結果，根據劃分結果修改電路對應的線網； 步驟9，電路輸出，遍歷修改後的線網，將得到的電路劃分結果以硬體描述語言存儲在電路描述文件中； 上述的步驟6中，所述的賦權超圖文件生成的步驟如下 步驟6. 1，基於中間代碼構造電路原始碼描述電路對應的線網，生成完整電路線網；一個完整的電路線網看作是一個根模塊，它由層次化的子模塊實例和電路邏輯單元通過信號互連構成，且每個子模塊內部由埠、電路邏輯單元、嵌套子模塊的實例通過信號連接構成； 步驟6.2，從根模塊開始，遞歸遍歷層次化線網的模塊，為每個電路邏輯單元編號；步驟6. 3，從根模塊開始，遞歸遍歷層次化線網的模塊，為每個電路邏輯單元之間的信號編號，並確立每個信號X的連接方式，實現到賦權超圖的轉換；其中，電路線網中的電路邏輯單元用賦權超圖的結點表示，電路線網中的信號用賦權超圖的超邊表示；結點的權值代表電路邏輯單元的大小，超邊的權值代表電路邏輯單元之間信號連線的權值為賦權超圖中結點的編號，取值範圍為I到電路線網中電路邏輯單元的總個數n ;j為賦權超圖中超邊的編號，取值範圍為I到電路線網中信號的總個數m; 步驟6. 4，將轉換得到的賦權超圖保存為賦權超圖文件； 上述的步驟7中，所述的基於元胞自動機的賦權超圖劃分方法的步驟如下 步驟7. 1，讀取賦權超圖文件，採用基於元胞自動機的壓縮存儲格式對賦權超圖進行存儲，其中元胞對應於賦權超圖中的結點，鄰接元胞對應於賦權超圖中鄰接超邊所包含的結佔. 步驟7. 2,元胞初始化,遍歷每個元胞並隨機給定元胞所處的狀態O或I,分別代表元胞對應結點所處的劃分子集Vl或V2，從而得到初始劃分；步驟7. 3，初始化二維輔助數組EDG[2] [m]，依據初始劃分，初始化二維輔助數組EDG[2] [m]； 步驟7. 4， 計算初始劃分的割切值，依據二維輔助數組EDG[2] [m]，快速計算當前劃分的割切值； 步驟7. 5，循環初始化，初始化循環計數器COUNT為0 ; 步驟7. 6，遍歷每個元胞是否結束，如果訪問未結束，即存在當前元胞未被訪問，則轉步驟7. 7 ;否則訪問結束，轉步驟7. 13 ； 步驟7. 7，計算當前元胞的收益值，根據當前元胞的狀態和鄰接元胞的狀態，快速計算當前元胞的收益值； 步驟7. 8,演化當前元胞狀態,如果當前元胞的收益值大於零，當前元胞狀態一定從當前狀態from翻轉到翻轉狀態to，否則當前元胞狀態以一定概率從當前狀態from翻轉到翻轉狀態to ； 步驟7. 9，如果當前元胞狀態從當前狀態from翻轉到翻轉狀態to，則轉步驟7. 10，否則轉步驟7. 6 ； 步驟7. 10，更新二維輔助數組EDG [2] [m]，遍曆元胞的所有鄰接超邊e，執行EDG [from][e]減I操作，EDG [to] [e]加I操作； 步驟7. 11，更新當前劃分的割切值，依據二維輔助數組EDG[2] [m]，快速計算當前劃分的割切值； 步驟7. 12，更新已找到的最優劃分，轉步驟7. 6 ； 步驟7. 13，循環判斷，循環計數器COUNT加1，若滿足COUNT達到設定演化次數的條件I或者全部元胞都不再改變自身狀態的條件2時，執行步驟7. 14，否則返回步驟7. 6 ； 步驟7. 14，運行基於FM-EE方法的賦權超圖劃分程序，由於在基於元胞自動機的賦權超圖劃分過程中，可能違背賦權超圖劃分問題的平衡約束條件，因此在基於元胞自動機的賦權超圖劃分所求解的基礎上，運行基於FM-EE方法的賦權超圖劃分方法，使劃分解滿足平衡約束條件，從而得到賦權超圖劃分問題的劃分解； 步驟7. 15，將最終得到的賦權超圖劃分結果存儲在賦權超圖劃分文件中； 上述的步驟6. 3中，所述的確立信號X連接方式的步驟如下 步驟6. 3. 1，依次處理信號X的每個管腳連接，支持跨層次連接，尋找到連接端的電路邏輯單元I ; 步驟6. 3. 2，如果電路邏輯單元y已經存在信號X的連接中，則忽略該電路邏輯單元y ;否則在信號X的連接中增加該電路邏輯單元y ； 上述的步驟7. I中，所述的賦權超圖的基於元胞自動機的壓縮存儲格式如下 步驟7. I. 1，使用ID數組存儲元胞對應於賦權超圖中結點的編號信息，且ID數組的大小為賦權超圖中的結點個數； 步驟7. I. 2,使用state數組存儲元胞的狀態信息,且state數組的大小為賦權超圖中的結點個數； 步驟7. I. 3,使用vwgts數組存儲元胞對應於賦權超圖中結點的權值信息,且vwgts數組的大小為賦權超圖中的結點個數； 步驟7. I. 4，使用xadj數組存儲每個結點所有鄰接超邊列表的起始位置信息，即第i條結點的終止位置為第i+1條結點的起始位置減1，且xadj數組的大小為賦權超圖中的結點個數加1，xadj數組最後一個元素用於存放最後一條結點的終止位置； 步驟7. I. 5，使用adjncy數組存儲每個結點所有鄰接超邊的列表信息，第i條結點的鄰接超邊列表存儲在 adjncy 數組中，從 adjncy [xadj [i]]到 adjncy [xadj [i+1] _1]； 步驟7. I. 6，使用eptr數組存儲每條超邊所包含的結點列表的起始位置信息，即第j條超邊的終止位置為第j+1條超邊的起始位置減I,且eptr數組的大小為賦權超圖中的超邊個數加1，eptr數組最後一個元素用於存放最後一條超邊的終止位置； 步驟7.1.7，使用eind數組存儲每條超邊所包含結點的列表信息，第j條超邊的鄰接結點列表存儲在 eind 數組中，從 eind[eptr[j]]到 eind [eptr [j+1]-I]； 步驟7. 1.8,使用hewgts數組存儲超邊的權值信息,且hewgts數組的大小為賦權超圖 中的超邊個數； 上述的步驟7. 3中，所述的初始化二維輔助數組EDG[2] [m]的步驟如下 步驟7. 3. 1，二維輔助數組EDG [2] [m]清零； 步驟7. 3. 2,讀取eptr數組和eind數組存儲的每條超邊所包含的結點信息,基於初始劃分計算每條超邊在劃分子集Vl和V2的結點個數，即二維輔助數組EDG[2] [m]的兩行分別存放每條超邊在劃分子集Vl和V2的結點個數； 上述的步驟7. 4和步驟7. 11中，所述的快速計算當前劃分的割切值的步驟如下 步驟7. 4. I，劃分割切值清零； 步驟7. 4. 2，遍歷每條超邊是否結束，如果訪問未結束，即存在超邊e未被訪問，則轉步驟7. 4. 3 ;否則訪問結束，返回劃分割切值； 步驟7. 4. 3，如果滿足EDG
[e]彡I的條件I和EDG[I] [e]彡I的條件2時，意味著超邊e在劃分子集Vl和V2的結點個數都大於等於1，即可判定超邊e是兩棲邊，並將劃分割切值累加上當前超邊的權值；否則判定超邊e不是兩棲邊，劃分割切值不變； 步驟7. 4. 4，轉步驟7. 4.2 ； 上述的步驟7. 7中，所述的快速計算當前元胞收益值的步驟如下 步驟7. 7. I，元胞收益值清零； 步驟7. 7. 2，讀取元胞的當前狀態from和翻轉狀態to ； 步驟7. 7. 3，遍曆元胞的所有鄰接超邊e，若二維數組EDG[from] [e]值為1，則將收益值加上超邊e的權值；若二維數組EDG[to] [e]值為0，則將收益值減去超邊e的權值； 步驟7. 7. 4，返回元胞收益值。
全文摘要
本發明涉及一種基於元胞自動機和賦權超圖的大規模集成電路劃分方法，其採用賦權超圖對電路進行數學建模，將電路線網轉換到賦權超圖，並保存為賦權超圖文件；然後啟動基於元胞自動機的賦權超圖劃分程序，對生成的賦權超圖進行劃分；最後依據賦權超圖的劃分結果，修改電路對應的線網，並通過遍歷修改後的線網，將得到的電路劃分結果以硬體描述語言存儲在電路描述文件中。採用本發明的基於元胞自動機和賦權超圖的大規模集成電路劃分方法，不僅僅有效地提高了電路劃分的效率，還顯著地提高了電路劃分的性能，具有較好的實用性。
文檔編號G06F17/50GK102682176SQ20121015457
公開日2012年9月19日 申請日期2012年5月18日 優先權日2012年5月18日
發明者冷子陽, 冷明, 孫凌宇 申請人:冷子陽, 冷明, 孫凌宇