[發(fā)明專利]一種面向FPGA芯片的網(wǎng)表環(huán)路識別方法

有效

• 申請?zhí)枺?/td>: 202010167733.X
• 申請日: 2020-03-11
• 公開（公告）號: CN111353182B
• 公開（公告）日: 2023-05-05
• 發(fā)明（設(shè)計）人: 王堅;李桓;楊鍊;陳哲;郭世澤
• 申請（專利權(quán)）人: 電子科技大學(xué)
• 主分類號: G06F21/76
• 分類號: G06F21/76
• 代理公司: 北京正華智誠專利代理事務(wù)所(普通合伙) 11870
• 代理人: 李夢蝶

1.一種面向FPGA芯片的網(wǎng)表環(huán)路識別方法，其特征在于，包括以下步驟：

S1：提取FPGA芯片的網(wǎng)表文件；

S2：建立網(wǎng)表文件的有向圖模型；

S3：結(jié)合棧結(jié)構(gòu)對有向圖模型進(jìn)行深度優(yōu)先遍歷，識別有向圖模型的環(huán)路；

S4：識別環(huán)路中的嵌套環(huán)路；

所述步驟S4包括以下子步驟：

S41：設(shè)定嵌套環(huán)路的集合為Q，設(shè)定環(huán)路集合C＝(c₁，c₂，…c_n)中的標(biāo)志集合為F＝{f_ij|(f₁₁，f₁₂，…，f_1n，f₂₁，f₂₂，…f_nn)}，設(shè)定標(biāo)志集合F中的標(biāo)志序列為f_ij，其中i≤n，j≤m，n和m分別為環(huán)路集合C的兩個子集大小；

S42：初始化標(biāo)志集合F，使得標(biāo)志序列f_ij＝0；

S43：任選c_i，c_j∈C，根據(jù)c_i∩c_j的運(yùn)算結(jié)果輸出嵌套環(huán)路集合Q；

所述步驟S43包括以下子步驟：

S431：任選c_i，c_j∈C使得令嵌套環(huán)q_ij＝(c_i，c_j)；

S432：將嵌套環(huán)q_ij加入到嵌套環(huán)路集合Q中，使得c_j∈c都有標(biāo)志序列f_ij＝1；

S433：根據(jù)嵌套環(huán)路集合Q的運(yùn)算結(jié)果輸出嵌套環(huán)路集合；

S5：基于嵌套環(huán)路，利用分步循環(huán)聚合策略提取環(huán)路中的聚合環(huán)路，得到FPGA芯片的網(wǎng)表環(huán)路識別結(jié)果；

所述步驟S5包括以下子步驟：

S51：向網(wǎng)表文件輸入嵌套環(huán)路集合Q和環(huán)路集合C，設(shè)置聚合環(huán)路集合J；

S52：初始化標(biāo)志集合F，使得標(biāo)志序列f_ij＝0；

S53：將標(biāo)志序列f_ij加入標(biāo)志集合F，利用標(biāo)志集合F判斷初步聚合是否結(jié)束，若是則初步聚合結(jié)束，進(jìn)入步驟S54，否則結(jié)束循環(huán)；

S54：任選嵌套環(huán)路集合Q中的嵌套環(huán)路序列q_ij∈Q，令j＝c_i∪c_j，將j加入到聚合環(huán)路集合J中，進(jìn)入步驟S55；

S55：判斷標(biāo)志集合F是否應(yīng)該清空，若是進(jìn)入步驟S56，否則返回步驟S54；

S56：判斷聚合環(huán)路集合J是否應(yīng)該輸出，若是則輸出聚合環(huán)路，結(jié)束循環(huán)，否則進(jìn)入S57；

S57：初始化標(biāo)志集合F，使得標(biāo)志序列f_ij＝0；

S58：將標(biāo)志序列f_ij加入標(biāo)志集合F，利用標(biāo)志集合F判斷本步聚合是否結(jié)束，若是則進(jìn)入步驟S59，否則結(jié)束循環(huán)；

S59：任選j_i，j_j∈J，令j＝c_i∪c_j，將j加入到聚合環(huán)路集合J中；

S510：將j_i和j_j從聚合環(huán)路集合J移除，進(jìn)入S511；

S511：判斷標(biāo)志集合F是否應(yīng)該清空，若是返回步驟S56，否則返回步驟S59，完成聚合環(huán)路提取；

所述步驟S53中，若對于都有標(biāo)志序列f_ij＝1則初步聚合結(jié)束，進(jìn)入步驟S54；

所述步驟S55中，若對于都有標(biāo)志序列f_ij＝1，則清空標(biāo)志集合F；

所述步驟S56中，若使得則進(jìn)入S57，否則輸出聚合環(huán)路，結(jié)束循環(huán)；

所述步驟S58中，若對于都有標(biāo)志序列f_ij＝1則初步聚合結(jié)束，進(jìn)入步驟S59。

2.根據(jù)權(quán)利要求1所述的面向FPGA芯片的網(wǎng)表環(huán)路識別方法，其特征在于，所述步驟S2包括以下子步驟：

S21：設(shè)定網(wǎng)表文件的寄存器集合為R；

S22：根據(jù)寄存器集合構(gòu)建網(wǎng)表文件的頂點(diǎn)集合為V；

S23：根據(jù)寄存器集合構(gòu)建網(wǎng)表文件的有向邊集合為E，得到有向圖模型G＝(V，E)，完成有向圖模型的建立。