[發(fā)明專利]一種基于有向網(wǎng)格點(diǎn)的布線存儲結(jié)構(gòu)及其布線方法

有效

• 申請?zhí)枺?/td>: 201110320434.6
• 申請日: 2011-10-20
• 公開（公告）號: CN103064992A
• 公開（公告）日: 2013-04-24
• 發(fā)明（設(shè)計(jì)）人: 夏吉運(yùn)
• 申請（專利權(quán)）人: 臺達(dá)電子企業(yè)管理（上海）有限公司;中達(dá)光電工業(yè)（吳江）有限公司
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 北京律誠同業(yè)知識產(chǎn)權(quán)代理有限公司 11006
• 代理人: 曾紅

1.一種基于有向網(wǎng)格點(diǎn)的布線存儲結(jié)構(gòu)，其特征在于，所述布線存儲結(jié)構(gòu)包括：

一網(wǎng)格矩陣，具有N×M個(gè)網(wǎng)格點(diǎn)，且用于存儲每一網(wǎng)格點(diǎn)對應(yīng)的一網(wǎng)格標(biāo)識符，其中，N、M均為自然數(shù)；

一網(wǎng)格值獲取模塊，用于在布線操作時(shí)從所述網(wǎng)格矩陣中獲取當(dāng)前網(wǎng)格點(diǎn)所對應(yīng)的網(wǎng)格標(biāo)識符；以及

一網(wǎng)格值設(shè)置模塊，用于將布線平面中的障礙塊所包含的網(wǎng)格點(diǎn)和/或布線途經(jīng)的網(wǎng)格點(diǎn)依據(jù)預(yù)定的設(shè)置規(guī)則來設(shè)置為相應(yīng)的網(wǎng)格標(biāo)識符。

2.根據(jù)權(quán)利要求1所述的布線存儲結(jié)構(gòu)，其特征在于，還包括一判斷模塊，用于根據(jù)所述當(dāng)前網(wǎng)格點(diǎn)所對應(yīng)的網(wǎng)格標(biāo)識符，來判斷布線是否能夠經(jīng)過所述當(dāng)前網(wǎng)格點(diǎn)。

3.根據(jù)權(quán)利要求1所述的布線存儲結(jié)構(gòu)，其特征在于，所述網(wǎng)格矩陣包括n×m個(gè)子矩陣，并且每一子矩陣對應(yīng)于k×k個(gè)網(wǎng)格點(diǎn)，其中，n、m、k均為自然數(shù)。

4.根據(jù)權(quán)利要求1所述的布線存儲結(jié)構(gòu)，其特征在于，還包括一更新模塊，用于根據(jù)所述網(wǎng)格值設(shè)置模塊所設(shè)置的網(wǎng)格標(biāo)識符，更新所述網(wǎng)格矩陣。

5.根據(jù)權(quán)利要求1所述的布線存儲結(jié)構(gòu)，其特征在于，所述布線平面中的任一走線由多個(gè)網(wǎng)格點(diǎn)依次連接而成，并且所述走線采用與所述多個(gè)網(wǎng)格點(diǎn)所對應(yīng)的一網(wǎng)格標(biāo)識符序列進(jìn)行表示。

6.根據(jù)權(quán)利要求5所述的布線存儲結(jié)構(gòu)，其特征在于，所述網(wǎng)格標(biāo)識符為一數(shù)值或一圖形符號。

7.根據(jù)權(quán)利要求6所述的布線存儲結(jié)構(gòu)，其特征在于，當(dāng)一走線經(jīng)過當(dāng)前網(wǎng)格點(diǎn)時(shí)，以黑色箭頭表示達(dá)到該當(dāng)前網(wǎng)格點(diǎn)之前的走線方向，以白色箭頭表示從該當(dāng)前網(wǎng)格點(diǎn)去往的走線方向。

8.根據(jù)權(quán)利要求6所述的布線存儲結(jié)構(gòu)，其特征在于，當(dāng)一走線經(jīng)過當(dāng)前網(wǎng)格點(diǎn)時(shí)，以空心點(diǎn)表示該當(dāng)前網(wǎng)格點(diǎn)處無邏輯相交，以實(shí)心點(diǎn)表示該當(dāng)前網(wǎng)格點(diǎn)處有邏輯相交。

9.一種基于有向網(wǎng)格點(diǎn)進(jìn)行自動(dòng)布線的方法，其特征在于，該方法包括以下步驟：

a?建立一網(wǎng)格矩陣，并對所述網(wǎng)格矩陣中的網(wǎng)格點(diǎn)和障礙塊進(jìn)行初始化，以便設(shè)置所述網(wǎng)格點(diǎn)和所述障礙塊各自所對應(yīng)的網(wǎng)格標(biāo)識符；

b?采用一預(yù)定的布線演算法來生成多條試探路徑；

c?在所述多條試探路徑中選擇一優(yōu)化路徑，其中，所述優(yōu)化路徑的長度最短且折點(diǎn)最少；

d?獲取所述優(yōu)化路徑上的網(wǎng)格點(diǎn)所對應(yīng)的網(wǎng)格標(biāo)識符，并根據(jù)所獲取的網(wǎng)格標(biāo)識符更新所述網(wǎng)格矩陣；以及

e?繪制出所述優(yōu)化路徑。

10.根據(jù)權(quán)利要求9所述的方法，其特征在于，所述布線演算法包括迷宮演算法或線探索法。

11.根據(jù)權(quán)利要求9所述的方法，其特征在于，所述步驟a還包括：獲取所述障礙塊所包圍的區(qū)域中的所有網(wǎng)格點(diǎn)，并對所述網(wǎng)格點(diǎn)進(jìn)行初始化，以實(shí)現(xiàn)對所述障礙塊的初始化。

12.根據(jù)權(quán)利要求9所述的方法，其特征在于，所述布線平面中的任一走線由多個(gè)網(wǎng)格點(diǎn)依次連接而成，并且所述走線采用與所述多個(gè)網(wǎng)格點(diǎn)所對應(yīng)的一網(wǎng)格標(biāo)識符序列進(jìn)行表示。

13.根據(jù)權(quán)利要求12所述的方法，其特征在于，所述網(wǎng)格標(biāo)識符為一數(shù)值或一圖形符號。

14.根據(jù)權(quán)利要求12所述的方法，其特征在于，所述步驟c中的優(yōu)化路徑為一直線或一折線。

15.根據(jù)權(quán)利要求12所述的方法，其特征在于，所述方法適用于CFC(Continuous?Function?Chart，連續(xù)功能圖表)編程環(huán)境。