[發(fā)明專利]一種快速單磁通量子RSFQ電路布線方法和裝置

有效

• 申請?zhí)枺?/td>: 202010728098.8
• 申請日: 2020-07-23
• 公開（公告）號: CN111914507B
• 公開（公告）日: 2022-09-20
• 發(fā)明（設(shè)計）人: 蔡懿慈;翟建旺;周強
• 申請（專利權(quán)）人: 清華大學(xué)
• 主分類號: G06F30/394
• 分類號: G06F30/394;G06F30/3312
• 代理公司: 北京安信方達(dá)知識產(chǎn)權(quán)代理有限公司 11262
• 代理人: 蔣冬梅;栗若木

1.一種快速單磁通量子RSFQ電路布線方法，其特征在于，包括：

讀入待布線的快速單磁通量子RSFQ電路的門級網(wǎng)表、布局信息和單元庫信息，并依據(jù)所述門級網(wǎng)表和布局信息解析所述RSFQ電路的邏輯單元位置和線網(wǎng)連接關(guān)系；所述單元庫信息包括：邏輯單元信息和約瑟夫森傳輸線JTL單元信息；

根據(jù)所述邏輯單元位置和線網(wǎng)連接關(guān)系進(jìn)行虛擬布線；

使用所述JTL單元替換所述虛擬布線后獲得的虛擬導(dǎo)線，并根據(jù)時序分析結(jié)果調(diào)整JTL單元以進(jìn)行時序優(yōu)化；所述方法還包括：在進(jìn)行虛擬布線時，使用兩個虛擬布線層完成線網(wǎng)連接，所述兩個虛擬布線層分別用于水平和垂直方向布線；

和/或，

所述根據(jù)所述邏輯單元位置和線網(wǎng)連接關(guān)系進(jìn)行虛擬布線包括：對于RSFQ電路的每個布線區(qū)域分別執(zhí)行以下操作：

當(dāng)相鄰線網(wǎng)主干之間以及線網(wǎng)主干與邏輯門列之間設(shè)置的間隔Xspace小于或等于預(yù)設(shè)數(shù)值時，采用預(yù)設(shè)的左邊算法均勻分配線網(wǎng)主干；所述線網(wǎng)主干為線網(wǎng)的垂直部分；

對當(dāng)前布線區(qū)域內(nèi)的全部線網(wǎng)根據(jù)線長進(jìn)行排序，并將全部線網(wǎng)按照從短到長的順序依次壓入布線隊列中；

從所述布線隊列中依次取線網(wǎng)，使用預(yù)設(shè)的迷宮布線算法進(jìn)行布線。

2.根據(jù)權(quán)利要求1所述的快速單磁通量子RSFQ電路布線方法，其特征在于，所述預(yù)設(shè)的左邊算法為改進(jìn)的左邊算法；所述采用預(yù)設(shè)的左邊算法均勻分配線網(wǎng)主干包括：

獲取待當(dāng)前布線區(qū)域內(nèi)全部待分配線網(wǎng)，并根據(jù)每條線網(wǎng)各端點的縱坐標(biāo)確定每條線網(wǎng)主干的最大y坐標(biāo)ymax以及最小y坐標(biāo)ymin，進(jìn)而確定每條線網(wǎng)主干的縱坐標(biāo)范圍[y_min，y_max]；

依據(jù)所述縱坐標(biāo)范圍將每條導(dǎo)線映射到y(tǒng)軸上獲取相應(yīng)的線網(wǎng)主干；

將獲得的線網(wǎng)主干依據(jù)每個線網(wǎng)主干的最小y坐標(biāo)y_min的大小在x坐標(biāo)方向依次進(jìn)行排序，其中，y_min越小，對應(yīng)的x坐標(biāo)越小，在y_min相同時依據(jù)線網(wǎng)主干長度進(jìn)行排序，主干長度越短，對應(yīng)的x坐標(biāo)越小；在y坐標(biāo)方向上，每個線網(wǎng)主干的最小y坐標(biāo)y_min和最大y坐標(biāo)y_max均對應(yīng)到相應(yīng)的坐標(biāo)值處；

遍歷排序后的每條線網(wǎng)主干，當(dāng)一條線網(wǎng)主干的最大y坐標(biāo)y_max以及最小y坐標(biāo)y_min與當(dāng)前布線區(qū)域內(nèi)的另外一條線網(wǎng)主干的最大y坐標(biāo)y_max和最小y坐標(biāo)y_min所確定的y坐標(biāo)線段完全不同，使得該線網(wǎng)主干與所述另外一條線網(wǎng)主干的y坐標(biāo)不重疊時，將該線網(wǎng)主干與所述另外一條線網(wǎng)主干移動到兩者中對應(yīng)的x坐標(biāo)較小的一列上；

線網(wǎng)主干分配完畢后，以單位長度將當(dāng)前布線區(qū)域劃分為均勻網(wǎng)格，并在相鄰的每列線網(wǎng)主干之間添加間隔Xspace，初始間隔Xspace為單位長度。

3.根據(jù)權(quán)利要求1所述的快速單磁通量子RSFQ電路布線方法，其特征在于，所述預(yù)設(shè)的迷宮布線算法為用于連接多端線網(wǎng)并在擴(kuò)展和回溯階段加入形狀約束的改進(jìn)的迷宮布線算法；

所述改進(jìn)的迷宮布線算法包括：

確定迷宮擴(kuò)展的起點和終點之后，把起點坐標(biāo)加入構(gòu)造的有序鏈表openList中；

取出所述有序鏈表openList中的第一個元素作為當(dāng)前要擴(kuò)展的網(wǎng)格點current；基于所述當(dāng)前要擴(kuò)展的網(wǎng)格點current循環(huán)擴(kuò)展出新的網(wǎng)格點，并將擴(kuò)展出的新的網(wǎng)格點加入所述有序鏈表openList中；

當(dāng)擴(kuò)展過程中發(fā)現(xiàn)終點時，回溯并根據(jù)形狀約束確定起點和終點之間的路徑是否合法，并根據(jù)確定結(jié)果對起點和終點之間的路徑進(jìn)行處理；

如果直至所述有序鏈表openList為空仍未發(fā)現(xiàn)終點，則確定擴(kuò)展失敗，并確定線網(wǎng)布線失敗；

對于多端線網(wǎng)，當(dāng)線網(wǎng)中每個端點均連接成功時，確定線網(wǎng)布線成功；當(dāng)線網(wǎng)中任意一個端點連接失敗時，確定線網(wǎng)布線失敗。