[發明專利]一種基于剪枝策略的關鍵性電路單元定位方法

在審

• 申請號: 201910311923.1
• 申請日: 2019-04-18
• 公開（公告）號: CN110135005A
• 公開（公告）日: 2019-08-16
• 發明（設計）人: 肖杰;諸瑋東;施展輝;胡海根;周乾偉;季奇甌;孫紫文
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 杭州斯可睿專利事務所有限公司 33241
• 代理人: 王利強

1.一種基于剪枝策略的關鍵性電路單元定位方法，其特征在于，所述方法包括以下步驟：

步驟1：網表解析及相關量的初始化，讀取網表，構建電路的完整性鏈表LC，并提取電路的原始輸入端數PI及電路的單元個數Ng，其中完整性鏈表LC指鏈表中任意節點的輸入端信息均可從該節點的前序節點的輸出端信息中提取得到；

步驟2：構建滿足均勻非伯努利序列分布特點的輸入向量；

步驟3：檢測在指定輸入向量下LC中第t個電路單元第j1個輸入端的關鍵性Crtl_t，j1，過程如下：

3.1)初始化循環變量i2，提取輸入向量siv(i2)，利用SCA算法，初始化LC中所有電路單元的理想輸入信號、理想輸出信號及其關鍵性，且初始化t＝1；

3.2)若t≤Ng，則讀取LC中的第t個單元g_t，并提取其類型type、理想輸入信號iipt_t、理想輸出信號iopt_t及其輸入端個數mt，并初始化循環變量j1＝1，并轉至3.3)；否則，轉至步驟4；

3.3)若j1>mt，則執行t＝t+1，并轉至3.2)；否則，轉至3.4)；

3.4)將g_t第j1個輸入端的理想信號iipt_t(j1)取反，再計算該單元與之相對應的輸出信號tfopt_t(j1)；

3.5)若tfopt_t(j1)＝iopt_t，則認為g_t第j1個輸入端非關鍵，執行Crtl_t，j1＝0；否則，則認為g_t的該輸入端為關鍵，執行Crtl_t，j1＝1，執行j1＝j1+1，轉至3.3)；

步驟4：提取指定輸入向量下的關鍵性電路單元，過程如下：

4.1)從LC中提取電路的原始輸出端及其所關聯的電路單元g_Ng；

4.2)從g_Ng開始通過反向深度優先搜索算法提取由步驟3所標識的關鍵性互連線所串聯的電路單元，它們構成了指定輸入向量下的關鍵性電路單元集；

步驟5：量化各電路單元的關鍵性，過程如下：

5.1)初始化第t個電路單元的關鍵性CrtVlts_t＝0，初始化循環變量r＝1，t＝1,2,…,Ng；

5.2)若r≤D，提取siv(r)，并通過步驟4提取在siv(r)下的關鍵性電路單元及其個數Nr，及由SCA算法所計算的相對應的關鍵性值CrtVl_r，并轉至5.3)；否則，轉至5.6)；

5.3)量化在該輸入向量下各關鍵性單元的關鍵性CrtAvg_r＝CrtVl_r/Nr；

5.4)若g_t是siv(r)下的關鍵性電路單元，則執行式(4)，t∈{1,2,…,Ng}；

CrtVls_t＝CrtVlts_t+CrtAvg_r (4)

5.5)執行r＝r+1，轉至5.2)；

5.6)根據式(4)所獲取的關鍵性對各電路單元進行排序并輸出。

2.如權利要求1所述的一種基于剪枝策略的關鍵性電路單元定位方法，其特征在于，所述步驟2的過程如下：

2.1)初始化主序列長度D，輔助序列長度T，子序列長度H＝T，循環變量i＝1，創建規模為PI×D的矩陣input_vector；

2.2)利用超素數優選因子法生成主序列d，過程如下：

2.2.1)產生不等于1與D的隨機種子x₀，初始化優選因子λ，初始化循環變量j＝0；

2.2.2)若j＝0，則利用式(1)計算d的第j個元素d_j；否則，通過式(2)計算循環因子x_j后，再根據式(1)計算d_j；

d_j＝x_jmod 2 (1)

x_j＝λ×x_j-1mod D (2)

其中，mod表示取余運算；

2.2.3)若j＝D-1，則轉至2.3)；否則，執行j＝j+1，轉至2.2.2)；

2.3)利用滿周期線性同余法生成輔助序列a，過程如下：

2.3.1)初始化乘數因子α，增量因子β，循環變量k＝0，產生隨機種子a₀；

2.3.2)利用式(3)計算a的第k個元素a_k，若k＝T-1，則轉至2.4)；否則，執行k＝k+1，轉2.3.2)；

a_k+1＝((4×α+1)×a_k+2×β+1)mod T (3)

2.4)產生合成序列c，過程如下：

2.4.1)將d按順序拆分成ceil(D/H)個子序列，ceil()是取上整運算，其中ds_h＝d(1,(h-1)×H+1:h×H)，它是d被拆分后的第h個子序列，h∈{1,2,…,ceil(D/H)}；

2.4.2)若D/H≠ceil(D/H)，則對ds_ceil(D/H)補充相同數量的0和1使其長度為H，初始化循環變量h＝1，k＝0；

2.4.3)若k＞T-1，轉至2.4.4)；否則循環執行ds_h(k+1)＝ds_h(a_k)，k＝k+1；

2.4.4)提取c的第h個子序列c_h＝ds_h，若h＝ceil(D/H)，則轉至2.4.5)；否則，執行h＝h+1與k＝0，并轉至2.4.3)；

2.4.5)若i<PI，則執行input_vector(i,:)＝c與i＝i+1，并轉至2.2)；否則，轉至2.5)，其中，input_vector(i,:)指input_vector的第i行，ds_h(k)指ds_h的第k個元素；

2.5)創建電路的輸入向量siv，過程如下：

2.5.1)初始化循環變量i1＝1；

2.5.2)若i1≥D，轉到步驟3；否則，循環執行siv(i1)＝input_vector(:,i1)，i1＝i1+1，其中，siv(i1)指siv的第i1個元素，input_vector(:,i1)指input_vector的第i1列元素。