[發(fā)明專利]代價均衡的門級電路圖的分割方法、計算機(jī)存儲介質(zhì)

在審

• 申請?zhí)枺?/td>: 202110385204.1
• 申請日: 2021-04-09
• 公開（公告）號: CN113516667A
• 公開（公告）日: 2021-10-19
• 發(fā)明（設(shè)計）人: 黃國勇;邵小春;趙巖;鄧聯(lián)文
• 申請（專利權(quán)）人: 國微集團(tuán)（深圳）有限公司
• 主分類號: G06T7/11
• 分類號: G06T7/11;G06T7/136;G06F30/32
• 代理公司: 深圳市康弘知識產(chǎn)權(quán)代理有限公司 44247
• 代理人: 尹彥

1.一種代價均衡的門級電路圖分割方法，其特征在于，包括：

步驟1，獲取門級電路對應(yīng)的無向圖的對稱鄰接矩陣、所述無向圖中頂點(diǎn)的代價矩陣、計劃分割的子圖塊數(shù)、允許的偏差比例；

步驟2，根據(jù)所述代價矩陣、子圖塊數(shù)以及允許的偏差比例計算得到所述門級電路被分割后的每一塊子圖的平均代價，以及偏差閾值范圍；

步驟3，隨機(jī)從所述偏差閾值范圍中選取一個偏差閾值，結(jié)合所述平均代價，得到每個子圖的當(dāng)前代價范圍；

步驟4，根據(jù)預(yù)設(shè)算法遍歷所述無向圖的頂點(diǎn)，對所述無向圖進(jìn)行分割，使得被分割得到的每一個子圖均符合當(dāng)前代價范圍，并將各子圖周圍因當(dāng)前代價范圍無法被分割到子圖中的孤立頂點(diǎn)進(jìn)行統(tǒng)計；

步驟5，重復(fù)步驟3至步驟4至預(yù)設(shè)次數(shù)，比較每一輪分割后孤立頂點(diǎn)的數(shù)量，選擇孤立頂點(diǎn)數(shù)量最少的一輪分割結(jié)果，并記錄該分割結(jié)果對應(yīng)的各子圖和當(dāng)前代價范圍；

步驟6，根據(jù)預(yù)設(shè)規(guī)則將孤立頂點(diǎn)分割至與其相鄰的子圖中，使得分割后的子圖塊數(shù)與所述計劃分割的子圖塊數(shù)一致。

2.如權(quán)利要求1所述的代價均衡的門級電路圖的分割方法，其特征在于，所述步驟6具體包括：

步驟6.1：判斷孤立頂點(diǎn)相鄰的頂點(diǎn)所在的子圖的所有頂點(diǎn)的代價之和是否小于記錄的當(dāng)前代價范圍的最大值，若是，則將孤立頂點(diǎn)移動至對應(yīng)的子圖，直至所有的孤立頂點(diǎn)被就近分割完畢；

步驟6.2，判斷當(dāng)前的各子圖的所有頂點(diǎn)的代價之和是否大于記錄的代價范圍的最大值，若是，則對該子圖進(jìn)行分割。

3.如權(quán)利要求1所述的代價均衡的門級電路圖的分割方法，其特征在于，還包括：

步驟7，計算步驟6最終得到的分割結(jié)果的所有頂點(diǎn)的增益；

步驟8，將當(dāng)前增益最大的頂點(diǎn)嘗試移動至其他子圖時，判斷移動后其他子圖的所有頂點(diǎn)的代價是否符合對應(yīng)的代價范圍，若是，則將該頂點(diǎn)移動至其他子圖，并重新計算與該頂點(diǎn)鄰接的所有頂點(diǎn)的增益；

步驟9，在當(dāng)前增益最大的頂點(diǎn)的移動記錄中選擇在該頂點(diǎn)移動到該子圖后子圖間分割代價減少最多或者增加最少的子圖，并將該頂點(diǎn)移動至該子圖中，作為該頂點(diǎn)的最終移動去向；

步驟10，重新計算所有頂點(diǎn)的增益，確定當(dāng)前增益最大的頂點(diǎn)，并返回步驟8，直至所有頂點(diǎn)都被移動過，或者所有頂點(diǎn)的增益均為負(fù)數(shù)。

4.如權(quán)利要求3所述的代價均衡的門級電路圖的分割方法，其特征在于，所述步驟10中，計算得到的增益最大的頂點(diǎn)被移動過時，則按照增益由大至小的順序，選擇還未被移動過的頂點(diǎn)中增益最大的頂點(diǎn)作為當(dāng)前增益最大的頂點(diǎn)。

5.如權(quán)利要求3所述的代價均衡的門級電路圖的分割方法，其特征在于，當(dāng)所有的頂點(diǎn)都被移動過，或者所有頂點(diǎn)的增益均為負(fù)數(shù)時，重復(fù)所述步驟7至步驟10，直至分割結(jié)果的分割代價無明顯變化。

6.如權(quán)利要求1所述的代價均衡的門級電路圖的分割方法，其特征在于，所述步驟4中往對稱鄰接矩陣中增加一列序號，所述序號為各行對應(yīng)的頂點(diǎn)的序號，形成最新的鄰接矩陣，從最新的鄰接矩陣的第一行對應(yīng)的頂點(diǎn)開始遍歷。

7.如權(quán)利要求1所述的代價均衡的門級電路圖的分割方法，其特征在于，所述對稱鄰接矩陣通過對門級電路的有向圖的鄰接矩陣轉(zhuǎn)換得到。

8.如權(quán)利要求1所述的代價均衡的門級電路圖的分割方法，其特征在于，所述預(yù)設(shè)算法為廣度優(yōu)先搜索算法。

9.如權(quán)利要求1所述的代價均衡的門級電路圖的分割方法，其特征在于，所述步驟3中的代價范圍的最小值為平均代價減去偏差閾值，最大值為平均代價加上偏差閾值。

10.一種計算機(jī)存儲介質(zhì)，用于存儲計算機(jī)程序，其特征在于，所述計算機(jī)程序執(zhí)行時實(shí)施如權(quán)利要求1至9任意一項所述的代價均衡的門級電路圖的分割方法。