[發明專利]基于結點屬性函數的大規模集成電路的核值計算方法

無效

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

技術領域

本發明涉及一種大規模集成電路劃分用的基于結點屬性函數的大規模集成電路的核值計算方法。

背景技術

電路劃分在使用硬件描述語言設計大規模集成電路中占有重要的地位。隨著集成電路技術的快速發展，在一個芯片上集成幾百萬門甚至幾千萬門電路已成為現實，因此在大規模集成電路設計中使用電路劃分，可有效地降低對集成電路進行模擬或綜合的復雜性等要求。研究出一個好的電路劃分方法是提高大規模集成電路設計性能的必要條件。

目前，現有的電路劃分大多采用多水平劃分法的技術方案。首先，采用隨機匹配將某些電路邏輯單元結合在一起，得到下一水平層的粗化電路圖，重復此過程直到粗化電路圖足夠小為止，即得到一個最小電路圖。然后，采用劃分法對最小電路圖進行對分，得到一個初始二劃分。之后，將最小電路圖投影回初始電路圖，在每一水平層的細化電路劃分中，按照貪心原則選擇收益值最大的電路邏輯單元進行遷移優化，得到最后的電路劃分結果。

2008年中國專利局公告的由冷明，郁松年和孫凌宇申報，中國專利號為：200710043765.3號《基于多水平劃分法的大規模集成電路劃分方法》的發明專利，針對現有技術方案中因采用隨機策略進行匹配和貪心原則進行遷移優化，導致無法逃離局部最優的劃分，提供了一種改進的基于多水平劃分法的大規模集成電路劃分方法，有效地提高了大規模集成電路劃分的效率和性能。該發明專利在多水平劃分法的粗化階段，通過對結點屬性進行賦權無向圖中所有結點的核值求解排序，按照基于結點核值的非嚴格降序訪問處于未匹配狀態的結點，依據一定規則對其進行匹配，從而將連接性好的結點合并在一起；在多水平劃分法的優化階段，采用免疫克隆優化程序改進貪心原則的局部搜索方法，對在每一水平層投影的劃分進行優化，借助克隆操作、克隆變異操作、接種免疫疫苗操作、克隆選擇操作，使得改進后的方法在利用啟發信息搜索局部最優解的同時，更大自由地對具有潛力的解空間進行搜索，增加全局搜索能力。然而，由于該發明專利采用賦權無向圖作為大規模集成電路劃分問題的數學模型，因此存在著賦權無向圖最優劃分和大規模集成電路最優劃分的不一致性。

本發明采用賦權超圖對電路進行數學建模，其中電路單元表示為賦權超圖中的結點，電路單元間的連線表示為賦權超圖中的超邊。相比賦權無向圖而言，賦權超圖為電路提供了更為精確的模型：每條超邊可以連接兩個以上的結點，對應于電路單元間的信號可以連接兩個以上的電路單元。

然而，在多水平劃分法的粗化階段，需要依據結點屬性對賦權超圖中所有結點的核值進行求解排序，進而基于結點核值的非嚴格降序進行結點匹配，使相應的結點匹配算法在最大化減少超邊的數目以及超邊權值之和的同時，將連接性好的結點合并在一起，使之得到的粗化超圖中粗化結點的權值趨向于大小一致。

發明內容

本發明的目的在于針對已有技術存在的不足，提供一種基于結點屬性函數的大規模集成電路的核值計算方法，為大規模集成電路多水平劃分的后續階段提供更優的粗化超圖。為達到上述目的，本發明的構思如下：采用賦權超圖對電路進行數學建模，將電路線網轉換到賦權超圖，并保存為賦權超圖文件，然后啟動賦權超圖的核值計算程序，采用改進的壓縮存儲格式對賦權超圖進行存儲，并基于結點屬性函數計算結點的核值，將所有結點的核值結果存儲在賦權超圖核值文件中。

?根據上述的發明構思，本發明的技術方案是這樣實現的：一種基于結點屬性函數的大規模集成電路的核值計算方法，其特征在于，具體步驟如下。

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

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

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

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

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

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

步驟7，賦權超圖核值計算，啟動賦權超圖核值計算程序，讀取賦權超圖文件，采用改進的壓縮存儲格式對賦權超圖進行存儲，對生成的賦權超圖中每個結點，基于結點屬性函數計算其核值，將所有結點的核值結果存儲在賦權超圖核值文件中。