[發明專利]一種基于有向網格點的布線存儲結構及其布線方法

有效

• 申請號: 201110320434.6
• 申請日: 2011-10-20
• 公開（公告）號: CN103064992A
• 公開（公告）日: 2013-04-24
• 發明（設計）人: 夏吉運
• 申請（專利權）人: 臺達電子企業管理（上海）有限公司;中達光電工業（吳江）有限公司
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 北京律誠同業知識產權代理有限公司 11006
• 代理人: 曾紅

技術領域

本發明涉及PCB自動布線技術，尤其涉及一種基于有向網格點的布線存儲結構及其布線方法。

背景技術

當前，PLC(Programmable?Logic?Controller，可編程邏輯控制器)在工業自動化領域應用相當廣泛，用戶通過PLC編程軟件來編寫邏輯控制程序，并編譯、下載至PLC，即可實現用戶的個性化控制要求。一般地，PLC開發環境為用戶提供了多種編程語言，如IL(Instruction?List，指令集)、ST(Structured?Text，結構化文本)、LD(Ladder?Diagram，梯形圖)、FBD(Function?Block?Diagram，功能方塊圖)、SFC(Sequential?Function?Chart，順序功能圖)以及CFC(Continuous?Function?Chart，連續功能圖表)。

就CFC編程語言來說，因其靈活、直觀和較為簡潔，已被用戶廣泛接受。在CFC編程語言模塊中，當用戶新建程序窗口即創建了一個布線平面，通過添加、刪除、移動功能塊以便對自動布線系統中的障礙塊進行操作，當用戶執行從一指令引腳到另一指令引腳的連接操作時，這兩點之間的連接路徑由自動布線模塊完成。現有技術中，布線算法大致采用迷宮算法、線探索法或這兩種算法上的改進算法，但無論上述哪種算法，其布線存儲結構均須對障礙塊集進行存儲，即，采用鏈表存儲方式，將已布通的走線和障礙塊分別存儲到線鏈表和障礙塊鏈表中，線鏈表記錄所有已布通的線，且每條線由該線的折點所構成的點鏈表而表示，障礙塊鏈表則記錄所有布線平面中所有障礙塊的位置和大小信息。

然而，依照現有布線系統的存儲結構，假設需完成從A點到B點的自動布線，并且線鏈表中包括n個節點，每條線平均有m個折點，障礙塊鏈表中有k個節點，布線算法實現A點到B點的自動布線需對L個網格點判斷是否屬于障礙塊集，即，需遍歷鏈表節點的最大次數N表示為L×k×n×m，則遍歷次數N與障礙塊集的復雜度(即障礙塊鏈表的節點數量)成正相關，進而布線速度與障礙塊集的復雜度成負相關。此外，隨著障礙塊集復雜度增加，存儲結構所占用的存儲空間也會快速增加，從而導致布線效率急劇降低。

有鑒于此，如何設計一種更高效的布線存儲結構，以便降低或消除自動布線算法受障礙塊集復雜度的影響，并盡可能地壓縮存儲結構占用的存儲空間，提升布線效率，是業內相關技術人員亟待解決的一項課題。

發明內容

針對現有技術中的自動布線系統在布線時所存在的上述缺陷，本發明提供了一種基于有向網格點的布線存儲結構及其布線方法。

依據本發明的一個方面，提供了一種基于有向網格點的布線存儲結構，包括：

一網格矩陣，具有N×M個網格點，且用于存儲每一網格點對應的一網格標識符，其中，N、M均為自然數；

一網格值獲取模塊，用于在布線操作時從所述網格矩陣中獲取當前網格點所對應的網格標識符；以及

一網格值設置模塊，用于將布線平面中的障礙塊所包含的網格點和/或布線途經的網格點依據預定的設置規則來設置為相應的網格標識符。

優選地，該布線存儲結構還包括一判斷模塊，用于根據所述當前網格點所對應的網格標識符，來判斷布線是否能夠經過所述當前網格點。

優選地，所述網格矩陣包括n×m個子矩陣，并且每一子矩陣對應于k×k個網格點，其中，n、m、k均為自然數。

優選地，該布線存儲結構還包括一更新模塊，用于根據所述網格值設置模塊所設置的網格標識符，更新所述網格矩陣。

優選地，布線平面中的任一走線由多個網格點依次連接而成，并且所述走線采用與所述多個網格點所對應的一網格標識符序列進行表示。更優選地，所述網格標識符為一數值或一圖形符號。

在一實施例中，當一走線經過當前網格點時，以黑色箭頭表示達到該當前網格點之前的走線方向，以白色箭頭表示從該當前網格點去往的走線方向。在另一實施例中，當一走線經過當前網格點時，以空心點表示該當前網格點處無邏輯相交，以實心點表示該當前網格點處有邏輯相交。

依據本發明的另一個方面，提供了一種基于有向網格點進行自動布線的方法，該方法包括以下步驟：

a?建立一網格矩陣，并對所述網格矩陣中的網格點和障礙塊進行初始化，以便設置所述網格點和所述障礙塊各自所對應的網格標識符；

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

c?在所述多條試探路徑中選擇一優化路徑，其中，所述優化路徑的長度最短且折點最少；