[發(fā)明專利]一種最短沖突路徑搜索方法、裝置及存儲介質(zhì)

在審

• 申請?zhí)枺?/td>: 202211235499.5
• 申請日: 2022-10-10
• 公開（公告）號: CN115600547A
• 公開（公告）日: 2023-01-13
• 發(fā)明（設(shè)計）人: 胡渲;于士濤;馬海南;吳登輝
• 申請（專利權(quán)）人: 成都華大九天科技有限公司
• 主分類號: G06F30/398
• 分類號: G06F30/398;G06T11/00
• 代理公司: 北京紅花知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 16030
• 代理人: 林樂飛

1.一種最短沖突路徑搜索方法，其用于集成電路物理版圖雙重曝光中指定掩膜的全局最短沖突路徑搜索，所述方法的特征在于，包括：

a.將原始集成電路的版圖劃分為多個版圖區(qū)塊，對劃分后的所述多個版圖區(qū)塊中的各版圖區(qū)塊的圖形進行二著色；

b.將二著色后的各所述版圖區(qū)塊的圖形轉(zhuǎn)換為相對應(yīng)的節(jié)點拓撲圖：

c.針對各所述節(jié)點拓撲圖中的所有沖突連接，自各沖突連接的兩端分別進行廣度優(yōu)先遍歷，找到對于每一個沖突連接而言經(jīng)過該沖突連接且兩端是人為指定著色點的最短沖突路徑，其中，經(jīng)過各沖突連接的每條所述最短沖突路徑滿足下列條件：(1)路徑兩端為人為指定著色點；(2)路徑至少經(jīng)過一個沖突連接；(3)路徑內(nèi)部不能重復(fù)經(jīng)過一個圖形；(4)路徑之間不能重復(fù)經(jīng)過一個圖形；

e.基于針對各沖突連接找到的所有最短沖突路徑獲取各所述節(jié)點拓撲圖的全局最短沖突路徑。

2.根據(jù)權(quán)利要求1所述的最短沖突路徑搜索方法，其特征在于，

將獲取到的各所述節(jié)點拓撲圖的全局最短沖突路徑涉及的圖形和連接在數(shù)據(jù)集中設(shè)置為不可訪問。

3.根據(jù)權(quán)利要求1所述的最短沖突路徑搜索方法，其特征在于，

所述步驟c包括：對于每個沖突連接，從連接的兩端分別進行廣度優(yōu)先搜索，找到兩端分別能夠到達的所有人為指定著色點，并分別記錄兩端各自到達所有人為指定著色點到距離，將所記錄的一端到達所有人為指定著色點的距離與另一端到達所有人為指定著色點的距離兩兩組合，找到經(jīng)過該沖突連接且兩端是人為指定著色點的最短沖突路徑。

4.根據(jù)權(quán)利要求2所述的最短沖突路徑搜索方法，其特征在于，在將已獲取到的所述節(jié)點拓撲圖的全局最短沖突路徑設(shè)置為不可訪問后，針對可訪問的數(shù)據(jù)集中的其他沖突連接的兩端重復(fù)所述廣度優(yōu)先遍歷，在可訪問的圖形和沖突連接中尋找所述節(jié)點拓撲圖的全局次短路徑。

5.根據(jù)權(quán)利要求1所述的最短沖突路徑搜索方法，其特征在于，還包括：輸出所獲取到所述節(jié)點拓撲圖的全局最短沖突路徑。

6.根據(jù)權(quán)利要求5所述的最短沖突路徑搜索方法，其特征在于，輸出所獲取到所述節(jié)點拓撲圖的全局最短沖突路徑包括將所述全局最短沖突路徑在版圖中進行圖形或色彩標(biāo)注。

7.一種最短沖突路徑搜索裝置，其用于集成電路物理版圖雙重曝光中指定掩膜的全局最短沖突路徑搜索，所述裝置的特征在于，包括；

著色部，其將對原始集成電路版圖劃分得到的多個版圖區(qū)塊中的各版圖區(qū)塊的圖形進行二著色；

節(jié)點拓撲圖生成部，其基于二著色后的各所述版圖區(qū)塊的圖形來生成與二著色后的各所述版圖區(qū)塊的圖形相對應(yīng)的節(jié)點拓撲圖；

搜索部，其針對各所述節(jié)點拓撲圖中的所有沖突連接，自各沖突連接的兩端分別進行廣度優(yōu)先遍歷，找到對于每一個沖突連接而言經(jīng)過該沖突連接且兩端是人為指定著色點的最短沖突路徑，其中，每條所述最短沖突路徑滿足下列條件：(1)路徑兩端為人為指定著色點；(2)路徑至少經(jīng)過一個沖突連接；(3)路徑內(nèi)部不能重復(fù)經(jīng)過一個圖形；(4)路徑之間不能重復(fù)經(jīng)過一個圖形；

獲取部，其基于針對各沖突連接找到的所有最短沖突路徑獲取各所述節(jié)點拓撲圖的全局最短沖突路徑。

8.根據(jù)權(quán)利要求7所述的最短沖突路徑搜索裝置，其特征在于，還包括：

設(shè)定部，其將獲取到的所述節(jié)點拓撲圖的全局最短沖突路徑涉及的圖形和連接在數(shù)據(jù)集中設(shè)置為不可訪問。

9.根據(jù)權(quán)利要求7所述的最短沖突路徑搜索裝置，其特征在于，

所述搜索部對于每個沖突連接，從連接的兩端分別進行廣度優(yōu)先搜索，找到兩端分別能夠到達的所有人為指定著色點，并分別記錄兩端各自到達所有人為指定著色點到距離，將所記錄的一端到達所有人為指定著色點到距離與另一端到達所有人為指定著色點的距離兩兩組合，找到經(jīng)過該沖突連接且兩端是人為指定著色點的最短沖突路徑。