[發明專利]基于多水平劃分法和賦權超圖的大規模集成電路劃分方法

無效

• 申請號: 201210155738.6
• 申請日: 2012-05-19
• 公開（公告）號: CN102693340A
• 公開（公告）日: 2012-09-26
• 發明（設計）人: 冷明;孫凌宇;冷子陽
• 申請（專利權）人: 孫凌宇;冷明;冷子陽
• 主分類號: G06F17/50
• 分類號: G06F17/50;G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.本發明的技術方案是這樣實現的：一種基于多水平劃分法和賦權超圖的大規模集成電路劃分方法，其特征在于，具體步驟如下：

步驟1，用硬件描述語言描述該電路，生成該電路的源代碼；

步驟2，詞法分析，從左到右一個個讀入該電路的源代碼，對構成源代碼的字符流進行掃描和分解，從而識別出一個個單詞；

步驟3，語法分析，在詞法分析的基礎上將單詞序列分解成各類語法短語，依據硬件描述語言的語法規則，確定整個字符流是否構成一個語法上正確的硬件描述語言程序；

步驟4，語義分析，在語法分析的基礎上審核源代碼有無語義錯誤，為中間代碼生成階段收集類型信息；

步驟5，中間代碼生成，在語法分析和語義分析的基礎上，將源代碼生成中間代碼，用內部中間格式表示；

步驟6，賦權超圖文件生成，基于中間代碼構造文本描述的電路對應的線網，經過電路線網到賦權超圖的轉換之后，保存為賦權超圖文件；

步驟7，賦權超圖劃分，啟動基于多水平劃分法的賦權超圖劃分程序，讀取賦權超圖文件，采用基于多水平劃分法的壓縮存儲格式對賦權超圖進行存儲，對生成的賦權超圖進行劃分，將最終得到的劃分結果存儲在賦權超圖劃分文件中；

步驟8，修改線網，在檢測到基于多水平劃分法的賦權超圖劃分程序完成劃分之后，從賦權超圖劃分文件中讀取相應的劃分結果，根據劃分結果修改電路對應的線網，將劃分結果對應的電路邏輯單元搬移到指定的劃分子集V1或V2中；

步驟9，電路輸出，遍歷修改后的線網，將得到的電路劃分結果以硬件描述語言存儲在電路描述文件中；

上述的步驟6中，所述的賦權超圖文件生成的步驟如下：

步驟6.1，基于中間代碼構造電路源代碼描述電路對應的線網，生成完整電路線網；一個完整的電路線網看作是一個根模塊，它由層次化的子模塊實例和電路邏輯單元通過信號互連構成，且每個子模塊內部由端口、電路邏輯單元、嵌套子模塊的實例通過信號連接構成；

步驟6.2，?從根模塊開始，遞歸遍歷層次化線網的模塊，為每個電路邏輯單元編號；

步驟6.3，從根模塊開始，遞歸遍歷層次化線網的模塊，為每個電路邏輯單元之間的信號編號，并確立每個信號x的連接方式，實現到賦權超圖的轉換；其中，電路線網中的電路邏輯單元用賦權超圖的結點表示，電路線網中的信號用賦權超圖的超邊表示；結點的權值代表電路邏輯單元的大校滑超邊的權值代表電路邏輯單元之間信號連線的權值；i為賦權超圖中結點的編號，取值范圍為1到電路線網中電路邏輯單元的總個數n；j為賦權超圖中超邊的編號，取值范圍為1到電路線網中信號的總個數m；

步驟6.4，?將轉換得到的賦權超圖保存為賦權超圖文件；?

上述的步驟7中，所述的基于多水平劃分法的賦權超圖劃分方法的步驟如下：

步驟7.1，讀取賦權超圖文件，采用基于多水平劃分法的壓縮存儲格式對賦權超圖進行存儲；

步驟7.2，進入到多水平劃分法的粗化階段，采用賦權超圖的結點匹配程序將某些結點結合在一起，得到下一水平層的粗化賦權超圖，重復此過程直到粗化賦權超圖足夠小為止，即得到一個最小賦權超圖；

步驟7.3，進入到多水平劃分法的初始劃分階段，運行基于FM方法的賦權超圖劃分程序，得到最小賦權超圖的初始二劃分；

步驟7.4，進入到多水平劃分法的優化階段，從最小賦權超圖投影回初始賦權超圖，在每一水平層的細化賦權超圖中，采用禁忌搜索程序對細化賦權超圖的投影劃分進行優化；

步驟7.5，進入到平衡階段，運行基于FM-EE方法的賦權超圖劃分程序，由于在基于多水平劃分法的賦權超圖劃分過程中，可能違背賦權超圖劃分問題的平衡約束條件，因此在基于多水平劃分法的賦權超圖劃分所求解的基礎上，運行基于FM-EE方法的賦權超圖劃分方法，使劃分解滿足平衡約束條件，從而得到賦權超圖劃分問題的劃分解；

步驟7.6，將最終得到的賦權超圖劃分結果存儲在賦權超圖劃分文件中；

上述的步驟6.3中，所述的確立信號x連接方式的步驟如下：

步驟6.3.1，依次處理信號x的每個管腳連接，支持跨層次連接，尋找到連接端的電路邏輯單元y；

步驟6.3.2，如果電路邏輯單元y已經存在信號x的連接中，則忽略該電路邏輯單元y；否則在信號x的連接中增加該電路邏輯單元y；

上述的步驟7.1中，所述的賦權超圖的基于多水平劃分法的壓縮存儲格式如下：

步驟7.1.1，使用vwgts數組存儲賦權超圖中結點的權值信息，且vwgts數組的大小為賦權超圖中的結點個數；

步驟7.1.2，使用xadj數組存儲每個結點所有鄰接超邊列表的起始位置信息，即第i條結點的終止位置為第i+1條結點的起始位置減1，且xadj數組的大小為賦權超圖中的結點個數加1，?xadj數組最后一個元素用于存放最后一條結點的終止位置；

步驟7.1.3，使用adjncy數組存儲每個結點所有鄰接超邊的列表信息，第i條結點的鄰接超邊列表存儲在adjncy數組中，從adjncy[xadj[i]]到adjncy[xadj[i+1]-1]；

步驟7.1.4，使用eptr數組存儲每條超邊所包含的結點列表的起始位置信息，即第j條超邊的終止位置為第j+1條超邊的起始位置減1，且eptr數組的大小為賦權超圖中的超邊個數加1，?eptr數組最后一個元素用于存放最后一條超邊的終止位置；

步驟7.1.5，使用eind數組存儲每條超邊所包含結點的列表信息，第j條超邊的鄰接結點列表存儲在eind數組中，從eind[eptr[j]]到eind[eptr[j+1]-1]；

步驟7.1.6，使用hewgts數組存儲超邊的權值信息，且hewgts數組的大小為賦權超圖中的超邊個數；

上述的步驟7.2中，所述的當前水平層粗化賦權超圖的結點匹配程序的步驟如下：

步驟7.2.1，標注當前水平層粗化賦權超圖中所有結點處于未匹配狀態；

步驟7.2.2，運行賦權超圖的結點核值計算程序，基于結點屬性函數值進行當前水平層粗化賦權超圖中所有結點的核值求解，并按照結點的核值進行非嚴格降序排序；

步驟7.2.3，按照結點核值的非嚴格降序訪問處于未匹配狀態的結點v；如果結點v還有鄰接結點未匹配，那么選取處于沒有匹配狀態的且權值最大的鄰接超邊的鄰接結點u和結點v匹配，且標注這兩個結點為匹配狀態；如果結點v所有鄰接匹配結點處于匹配狀態，那么結點v仍處于未匹配狀態，在粗化過程中直接拷貝到下一水平層的粗化賦權超圖中；

步驟7.2.4，步驟重復上一步，直至所有結點訪問結束；

上述的步驟7.4中，所述的禁忌搜索程序的步驟如下：

步驟7.4.1，初始化二維輔助數組EDG[2][m]，依據當前水平層細化賦權超圖的投影劃分，初始化二維輔助數組EDG[2][m]；

步驟7.4.2，計算當前水平層細化賦權超圖的投影劃分的割切值，依據二維輔助數組EDG[2][m]，快速計算當前水平層細化賦權超圖的投影劃分的割切值；

步驟7.4.3，計算所有邊界結點的收益值，根據當前水平層細化賦權超圖的投影劃分，找出所有邊界結點，并快速計算每個邊界結點的收益值；

步驟7.4.4，將所有邊界結點的收益值插入到所在劃分子集V1或V2的自由狀態散列結構中；

步驟7.4.5，循環初始化，初始化循環計數器COUNT為0；

步驟7.4.6，選擇遷移方向和遷移結點，依據當前劃分以及平衡容忍度參數，選擇遷移方向(假設遷移方向是劃分子集A遷移到劃分子集B)和遷移結點(假設遷移結點是結點v)；

步驟7.4.7，刪除結點v遷移前的收益值，將結點v遷移前的收益值從結點v遷移前所在的劃分子集A的自由狀態散列結構或禁忌狀態散列結構中刪除；

步驟7.4.8，更新二維輔助數組EDG[2][m]，遍歷遷移結點v的所有鄰接超邊e，執行EDG[A][e]減1操作，EDG[B][e]加1操作；

步驟7.4.9，更新當前劃分的割切值，依據二維輔助數組EDG[2][m]，快速計算當前劃分的割切值；

步驟7.4.10，更新已找到的最優劃分；

步驟7.4.11，計算結點v遷移后的收益值，根據結點v所在劃分子集B和所在劃分子集的另一側劃分子集A，快速計算結點v遷移后的收益值；

步驟7.4.12，插入結點v遷移后的收益值，將結點v遷移后的收益值插入到結點v遷移后所在的劃分子集B的禁忌狀態散列結構中；

步驟7.4.13，更新結點v的鄰接結點u的收益值，遍歷遷移結點v的所有鄰接超邊e中所有鄰接結點u，快速計算鄰接結點u的收益值，并更新相應的散列結構；

步驟7.4.14，重復步驟7.4.6、7.4.7、7.4.8、7.4.9、7.4.10、7.4.11、7.4.12、7.4.13，直至循環計數器COUNTER到達給定的上限；

上述的步驟7.2.2中，所述的賦權超圖的結點核值計算程序的步驟如下：

步驟7.2.2.1，計算出所有結點的屬性函數值；

步驟7.2.2.2，對所有結點的屬性函數值進行非嚴格降序的計數排序；

步驟7.2.2.3，按照結點屬性函數值的非嚴格降序次序訪問每個結點，計算每個結點v的核值；

上述的步驟7.2.2.3中，所述的結點v的核值計算的步驟如下：

步驟7.2.2.3.1，將結點v的屬性函數值作為核值輸出；

步驟7.2.2.3.2，將結點v從所在的超邊e中刪除；

步驟7.2.2.3.3，如果超邊e刪除結點v后，仍包含兩個及以上結點，則超邊e仍然存在，否則刪除超邊e；

步驟7.2.2.3.4，重新計算結點v的鄰接結點u的屬性函數值；

步驟7.2.2.3.5，更新鄰接結點u屬性函數值的非嚴格降序計數排序的次序；

上述的步驟7.4.1中，所述的初始化二維輔助數組EDG[2][m]的步驟如下：

步驟7.4.1.1，二維輔助數組EDG[2][m]清零；

步驟7.4.1.2，讀取eptr數組和eind數組存儲的每條超邊所包含的結點信息，基于當前水平層細化賦權超圖的投影劃分，計算每條超邊在劃分子集V1和V2的結點個數，即二維輔助數組EDG[2][m]的兩行分別存放每條超邊在劃分子集V1和V2的結點個數；

上述的步驟7.4.2和步驟7.4.9中，所述的快速計算當前劃分的割切值的步驟如下：

步驟7.4.2.1，劃分割切值清零；

步驟7.4.2.2，遍歷每條超邊是否結束，如果訪問未結束，即存在超邊e未被訪問，則轉步驟7.4.2.3；否則訪問結束，返回劃分割切值；

步驟7.4.2.3，如果滿足EDG[0][e]?≥1的條件1和EDG[1][e]≥1的條件2時，意味著超邊e在劃分子集V1和V2的結點個數都大于等于1，即可判定超邊e是兩棲邊，并將劃分割切值累加上當前超邊的權值；否則判定超邊e不是兩棲邊，劃分割切值不變；

步驟7.4.2.4，轉步驟7.4.2.2；

上述的步驟7.4.3、7.4.11和7.4.13中，所述的快速計算結點v收益值的步驟如下：

步驟7.4.3.1，結點v的收益值清零；

步驟7.4.3.2，讀取結點v的所在劃分子集from和所在劃分子集的另一側劃分子集to；

步驟7.4.3.3，遍歷結點v的所有鄰接超邊e，若二維數組EDG[from][e]值為1，則將收益值加上超邊e的權值；若二維數組EDG[to][e]值為0，則將收益值減去超邊e的權值；

步驟7.4.3.4，返回結點v的收益值；

上述的步驟7.4.6，所述的選擇遷移方向和遷移結點的步驟如下：

步驟7.4.6.1，計算當前劃分的平衡狀態；

步驟7.4.6.2，如果當前劃分的平衡狀態滿足平衡容忍度參數，則在劃分子集V1或V2的自由狀態散列結構中，選擇收益值最大的邊界結點為被遷移結點v，遷移方向為結點v所在的劃分子集A到另一側劃分子集B；

步驟7.4.6.3，如果當前劃分的平衡狀態不滿足平衡容忍度參數，則遷移方向為當前劃分較重的劃分子集A到另一側較輕的劃分子集B，如果劃分子集A的自由狀態散列結構不為空，在劃分子集A的自由狀態散列結構中，選擇收益值最大的邊界結點v為被遷移結點；否則在劃分子集A的禁忌狀態散列結構中，選擇收益值最大的邊界結點v為被遷移結點；

上述的步驟7.4.13中，所述的更新相應的散列結構的鄰接結點u的收益值的步驟如下：

步驟7.4.13.1，如果鄰接結點u因為結點v的遷移成為邊界結點，那么將鄰接結點u的新收益值插入到鄰接結點u所在的劃分子集的自由狀態散列結構中；

步驟7.4.13.2，如果鄰接結點u因為結點v的遷移成為非邊界結點，那么將鄰接結點u的舊收益值從鄰接結點u所在的劃分子集的自由狀態散列結構或禁忌狀態散列結構中刪除；

步驟7.4.13.3，如果鄰接結點u在結點v的遷移前后始終為邊界結點，且在結點v遷移前，鄰接結點u的收益值已插入至所在劃分子集的自由狀態散列結構中，則只需將鄰接結點u所處劃分子集的自由狀態散列結構的舊收益值更新為新收益值；

步驟7.4.13.4，如果鄰接結點u在結點v的遷移前后始終為邊界結點，且在結點v遷移前，鄰接結點u的收益值已插入至所在劃分子集的禁忌狀態散列結構中，則將禁忌狀態散列結構中鄰接結點u的舊收益值刪除，然后將鄰接結點u的新收益值插入到鄰接結點u所在的劃分子集的自由狀態散列結構中。