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

無效

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

1.一種基于結點屬性函數的大規模集成電路的核值計算方法，其特征在于，具體步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

上述的步驟7中，所述的賦權超圖核值計算的步驟如下：

步驟7.1，讀取賦權超圖文件，采用改進的壓縮存儲格式對賦權超圖進行存儲；

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

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

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

步驟7.5，將所有結點的核值結果存儲在賦權超圖核值文件中；

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

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

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

上述的步驟7.1中，所述的賦權超圖的改進壓縮存儲格式如下：

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

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

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

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

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

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

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

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

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

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

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

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