（機械設計及理論專業(yè)論文）電路cad中pcb的自動布線算法研究.pdf

兩北工業(yè)大學碩士論文摘要 電路c a d中p c b的自 動布線算法研究 摘要 首先介紹了計算機輔助設計的發(fā)展概況和電子電路 c a d軟件的基本類型和 荃本 構成。 接著闡述了自 動布線技術的發(fā)展和分類， 對自 動布線理論進行綜合分 析研究。 給出了一種m d 模型上的 布線算法 智能識點法。首先， 提出了m d 模型上 的 廣義 線段的概念: 其次，依據(jù)人工智能的思維 給出繞障點的定義方法; 最后， 以繞障點和待布點組成布線點集合， 以布線點集合中的所有點為頂點構造帶邊權 值的完全圖， 將布線問 題轉(zhuǎn) 化為在帶邊權值的 完全圖中求布線點間的最短路徑， 從而得到最優(yōu)布線路徑。實驗證明算法的性能良好。 關鍵詞: m d布線模型，廣義線段， 繞障點， 布線算法，完 全圖 西北業(yè)大學碩 卜 論文摘賈 s tudy on pri nted ci rcui t board auto r o u t i n g i ng琴 c u i t c a d ab s t ra ct t h i s p a p e r i n t r o d u c e s t h e g e n e r a l d e v e l o p m e n t a l s i t u a t i o n o f t h e c o m p u t e r - a i d e d d e s i g n ( c a d ) a n d t h e c l a s s a n d p r i m a r y s t r u c t u r e o f t h e c i r c u i t c a d s o ft w a r e . t h e d e v e l o p me n t a l s i t u a t i o n a n d c l a s s o f t h e a u t o r o u t i n g a r e a l s o d e s c r i b e d , t h e t h e o r y o f a u t o r o u t i n g i s s t u d i e d s y n t h e t i c a l l y . a a u t o m a t i c r o u t i n g a l g o r i t h m 一一i n t e l l i g e n t d i s c e r n p o i n t s a l g o r i t h m i s p r e s e n t e d i n ma n h a t t a n - d i a g o n a l ( md ) mo d e l w i t h t r a c k s i n h o r i z o n t a l , v e r t i c a l , a n d 士 4 5 d i r e c t i o n s . f i r s t , t h e c o n c e p t o f g e n e r a l iz e d l i n e s e g m e n t i s p r e s e n t e d i n m d m o d e l . s e c o n d , b y m e a n s o f a r t i fi c i a l i n t e l l i g e n c e t h e o r y ,t h e w a y o f d e c i d i n g t h e p o s i t i o n o f d e t o u r i n g p o i n t s i s p r o p o s e d . f i n a l l y , a s e t o f p o i n t w h i c h i s m a d e u p o f d e t o u r i n g p o i n t s a n d p i n s i s f o r m e d . b y u s i n g t h e p o i n t s o f t h e s e t a s t h e v e rt i c e s , a w e i g h t e d c o m p l e t e g r a p h i s f o r m e d .t h e q u e s t i o n o f r o u t i n g i s t r a n s f o r me d i n t o f i n d i n g s h o r t e s t - p a t h p r o b l e m i n t h e w e i g h t e d c o m p le t e g r a p h . t h e r e b y ,t h e o p t imi z a t i o n o f r o u t i n g i s f o u n d . i t i s p r o v e d b y e x p e r i me n t a t i o n t h a t t h e a l g o r i t h m p e r f o r ma n c e i s e f f i c i e n t . k e y wo r d s : ma n h a t t a n - d i a g o n a l m o d e l ; g e n e r a l iz e d l i n e s e g m e n t ; d e t o u r i n g p o i n t ; r o u t i n g a l g o r i t h m; c o m p l e t e g r a p h 西 比工 業(yè) 大 學 碩 卜 論 文第一章緒論 第一章 緒 論 電子電路c a d技術 電子電路 c a d技術的概念及特點 計算機輔助設計 ( c a d : c o m p u t e r a i d e d d e s i g n )是指以計算機系統(tǒng)作為主 要技術手段來生成和運用各種數(shù)字信息與圖形信息， 幫助設計人員從事產(chǎn)品的開 發(fā)、修改、分析、和優(yōu)化設計的一門技術。c a d 技術本身是一項綜合性的、技術 復雜的系統(tǒng)工程， 涉及許多學科領域， 如計算機科學與工程、 計算數(shù)學、 計算力 學、幾何造型、計算機圖形學、數(shù)據(jù)結構和數(shù)據(jù)庫、仿真技術、人工智能等。 電子電路c a d技術是指以計算 機硬件和系統(tǒng)軟件為 基本工作平臺 ， 繼承和 借鑒前人在電路和系統(tǒng)、圖論、拓撲邏輯優(yōu)化和人工智能理論等多學科的最新科 技的成果而研制成的電 子電 路 c a d通用支撐軟件和應用軟 件包。 其目 的 在于幫 助電子設計工程師開發(fā)新的電 子系 統(tǒng)與電路、 1 c . p c b( 印 刷電路板) . f p g a( 現(xiàn) 場可 編程門陣列) 、 c p l d( 復雜可編程邏輯器件) 等產(chǎn)品。 實現(xiàn)在計算機上調(diào)用 元器件庫、 連線畫圖、 編制激勵信號文件、 確定跟蹤點、調(diào)用參數(shù)庫以及模擬程 序等手段去設計電路 電子電路設計任務:電子電路的設計 就是根據(jù)給定的功能和特性指標要求 ( 設 計要求) ， 采取一定的方法來確定采用什么 樣的電路拓撲結構及電路中的各個元器件 應該采用什么樣的參數(shù)，進一步將設計好 的電路轉(zhuǎn)換成印刷電路板圖設計。電子電 路設計工作流程如圖 1 . 1 所示。 電 子電路設計中 采用 c a d技術有很 多優(yōu)點比如縮短了設計周期，節(jié)省設計費圖 1 . 1電路設計t作流程li d 提高設計質(zhì)量，共享設備資源以及很強的數(shù)據(jù)處理能力。隨著電子技術的發(fā) t 西 比工 業(yè) 大 學 碩 卜 論 文第一章緒論 第一章 緒 論 電子電路c a d技術 電子電路 c a d技術的概念及特點 計算機輔助設計 ( c a d : c o m p u t e r a i d e d d e s i g n )是指以計算機系統(tǒng)作為主 要技術手段來生成和運用各種數(shù)字信息與圖形信息， 幫助設計人員從事產(chǎn)品的開 發(fā)、修改、分析、和優(yōu)化設計的一門技術。c a d 技術本身是一項綜合性的、技術 復雜的系統(tǒng)工程， 涉及許多學科領域， 如計算機科學與工程、 計算數(shù)學、 計算力 學、幾何造型、計算機圖形學、數(shù)據(jù)結構和數(shù)據(jù)庫、仿真技術、人工智能等。 電子電路c a d技術是指以計算 機硬件和系統(tǒng)軟件為 基本工作平臺 ， 繼承和 借鑒前人在電路和系統(tǒng)、圖論、拓撲邏輯優(yōu)化和人工智能理論等多學科的最新科 技的成果而研制成的電 子電 路 c a d通用支撐軟件和應用軟 件包。 其目 的 在于幫 助電子設計工程師開發(fā)新的電 子系 統(tǒng)與電路、 1 c . p c b( 印 刷電路板) . f p g a( 現(xiàn) 場可 編程門陣列) 、 c p l d( 復雜可編程邏輯器件) 等產(chǎn)品。 實現(xiàn)在計算機上調(diào)用 元器件庫、 連線畫圖、 編制激勵信號文件、 確定跟蹤點、調(diào)用參數(shù)庫以及模擬程 序等手段去設計電路 電子電路設計任務:電子電路的設計 就是根據(jù)給定的功能和特性指標要求 ( 設 計要求) ， 采取一定的方法來確定采用什么 樣的電路拓撲結構及電路中的各個元器件 應該采用什么樣的參數(shù)，進一步將設計好 的電路轉(zhuǎn)換成印刷電路板圖設計。電子電 路設計工作流程如圖 1 . 1 所示。 電 子電路設計中 采用 c a d技術有很 多優(yōu)點比如縮短了設計周期，節(jié)省設計費圖 1 . 1電路設計t作流程li d 提高設計質(zhì)量，共享設備資源以及很強的數(shù)據(jù)處理能力。隨著電子技術的發(fā) t 兩 匕1 業(yè)人幸碩 卜 論文第一章緒論 展，需設計的電路越來越復雜，規(guī)模也越來越大，在這種情況下，離開 c a d技 術幾乎無法完成現(xiàn)代的電子電路設計任務。 1 . 1 .2 電子電路 c a d軟件系統(tǒng)的基本構成 根據(jù)各個電子電路 c a d軟件的用途和設計任務的要求，通常在設計過程中 所用的c a d軟件系統(tǒng)主要包括以下幾類軟件: ( i )通用邏輯模擬軟件:用來對一般數(shù)字電路進行模擬驗證。該軟件可根 據(jù)用戶提供的數(shù)字電路結構和所用基本邏輯單元的特性， 模擬分析該電路的邏輯 功能、 延遲特性以及電 路中是否存在冒 險競爭情況等。 ( 2 )通用電 路模擬軟件: 用來對一 般電子電路進行模擬驗證。該軟件可根 據(jù)給出 的電 路拓撲結構和電路中 所用的元器件參數(shù)， 模擬分析該電路的直流、 交 流和瞬態(tài)等各種特性， 并進而進行靈敏度分析、 成品率模擬和最壞情況分析等特 殊類型的分析。 ( 3 )專用電 路設計軟件: 專門 用于 某些特定類型電 路的設計軟件。 例如由 p a l( 可編程陣列邏輯) 和f p g a( 現(xiàn)場可編程門 陣列)等可編程器件構成的電 路。 與通用模擬軟件相比， 這類軟件適用面窄， 但是在其適用范圍內(nèi)功能則更強， 往往還具有優(yōu)化設計的功能。 ( 3 ) 印刷電 路板 ( p c b : p r i n t e d c i r c u i t b o a r d ) 布局布線軟件: 該類軟件具 有自動布局布線功能， 一般只需用戶進行少量的人工干預就可完成印刷電路板的 設計任務。 ( 4 )電路圖繪制和后處理軟件: 為了 運行上述四類軟件，需要 提供電路的 拓撲結構。 目前， 常用方法是利用繪制電路圖的計算機軟件將電路圖送入計算機， 然后再調(diào)用相應的 后處理程序， 生成能 完全表征電路拓撲結構的 連接網(wǎng)表文件， 作為上述幾類軟件的輸入。 同時后處 理程 序還可 對繪出的電 路圖 進行電連接規(guī)則 檢驗和各種統(tǒng)計報表生成等。 ( 5 )數(shù)據(jù)庫建庫軟件:繪制電路圖和運行印刷 電路板布局布線軟件時需調(diào) 用多種型號的器件符號， 運行通用邏輯模擬和電路模擬軟件時也需要使用不同型 號的特性參數(shù)值。 這些器件符號和元器件參數(shù)值都是存放在專用的數(shù)據(jù)庫中提供 給用戶的。 此外電子電路c a d軟 件還提供有數(shù)據(jù)庫建庫軟件，以 便于 用戶在使 兩 匕1 業(yè)人幸碩 卜 論文第一章緒論 展，需設計的電路越來越復雜，規(guī)模也越來越大，在這種情況下，離開 c a d技 術幾乎無法完成現(xiàn)代的電子電路設計任務。 1 . 1 .2 電子電路 c a d軟件系統(tǒng)的基本構成 根據(jù)各個電子電路 c a d軟件的用途和設計任務的要求，通常在設計過程中 所用的c a d軟件系統(tǒng)主要包括以下幾類軟件: ( i )通用邏輯模擬軟件:用來對一般數(shù)字電路進行模擬驗證。該軟件可根 據(jù)用戶提供的數(shù)字電路結構和所用基本邏輯單元的特性， 模擬分析該電路的邏輯 功能、 延遲特性以及電 路中是否存在冒 險競爭情況等。 ( 2 )通用電 路模擬軟件: 用來對一 般電子電路進行模擬驗證。該軟件可根 據(jù)給出 的電 路拓撲結構和電路中 所用的元器件參數(shù)， 模擬分析該電路的直流、 交 流和瞬態(tài)等各種特性， 并進而進行靈敏度分析、 成品率模擬和最壞情況分析等特 殊類型的分析。 ( 3 )專用電 路設計軟件: 專門 用于 某些特定類型電 路的設計軟件。 例如由 p a l( 可編程陣列邏輯) 和f p g a( 現(xiàn)場可編程門 陣列)等可編程器件構成的電 路。 與通用模擬軟件相比， 這類軟件適用面窄， 但是在其適用范圍內(nèi)功能則更強， 往往還具有優(yōu)化設計的功能。 ( 3 ) 印刷電 路板 ( p c b : p r i n t e d c i r c u i t b o a r d ) 布局布線軟件: 該類軟件具 有自動布局布線功能， 一般只需用戶進行少量的人工干預就可完成印刷電路板的 設計任務。 ( 4 )電路圖繪制和后處理軟件: 為了 運行上述四類軟件，需要 提供電路的 拓撲結構。 目前， 常用方法是利用繪制電路圖的計算機軟件將電路圖送入計算機， 然后再調(diào)用相應的 后處理程序， 生成能 完全表征電路拓撲結構的 連接網(wǎng)表文件， 作為上述幾類軟件的輸入。 同時后處 理程 序還可 對繪出的電 路圖 進行電連接規(guī)則 檢驗和各種統(tǒng)計報表生成等。 ( 5 )數(shù)據(jù)庫建庫軟件:繪制電路圖和運行印刷 電路板布局布線軟件時需調(diào) 用多種型號的器件符號， 運行通用邏輯模擬和電路模擬軟件時也需要使用不同型 號的特性參數(shù)值。 這些器件符號和元器件參數(shù)值都是存放在專用的數(shù)據(jù)庫中提供 給用戶的。 此外電子電路c a d軟 件還提供有數(shù)據(jù)庫建庫軟件，以 便于 用戶在使 西北工業(yè)大學碩士論文第-奄緒論 用軟件時根據(jù)需要擴展數(shù)據(jù)庫內(nèi)容，添加新的器件符號等。 通常， 微機級電 子電 路 c a d軟件系統(tǒng)如下圖 1 . 2” 所示。 系統(tǒng)中每一部分 既可根 據(jù)需要單獨使用， 相互之間 又有聯(lián)系， 共同組成一個完整的電子電路c a d 系統(tǒng)。 其中電 路圖繪制軟件是該系統(tǒng)的基礎， 后處理程序是系統(tǒng)中 聯(lián)系各部分軟 件的紐帶。 電 路 圖 繪 制軟 件 電路符號圖形庫 原理圖元器件庫)州巫 囚 圖1 .2微機級電子電路 c a d軟件系統(tǒng)構成 電 路c a d 軟 件 應具 備以 下條 件2 3 1 ， 有開發(fā)結構的框架環(huán)境: 通過開 放結構和二次開發(fā)工具， 允許用戶把自己的 應用程序集成到軟件環(huán)境中，和原有的工具一樣處理設計數(shù)據(jù) 。 2 、有友好的用戶界面:提供的菜單形式應方便實用， 便于人機對話，且具有她 盤、宏命令、鼠 標等多種訪問 命令的方法。 3 、軟件功能強大:能提供圖形調(diào)入、網(wǎng)表生成和 p c b布局、布線等多種功能， 自 動化程度較高， 支持從電路圖 輸入到p c b生成全過程。 4 、 軟件的 建庫方法方便:對可能 遇到 擴充圖形庫和封裝庫的 情況時， 建庫方 法 一定要方便、簡單。 5 、與其他軟件接 日較好:便于與不同軟件之間進行數(shù)據(jù)交換。 g .升級發(fā)展有保證:軟件開發(fā)公司應具有使軟件更新升級的技術力量。 西北工業(yè)火學碩十論文第 一 章緒論 我國電路 c a d軟件市場，國外產(chǎn)品占據(jù)了大部分市場份頒。從軟件的使用 率來看，最知名的供應商是 p r o t e l ( 現(xiàn)己更名為 a l t i u m )，在中國大陸擁有 7 3 %的用戶， o r c a d , s y n o p s y s 和 c a d e n c e 各 擁有較多的用戶， p c a d , p a d s 也 有 一 些用戶。而在該領域的國產(chǎn)軟件，無論從技術上，功能上，還是從用戶數(shù)量 上，都難于和外國軟件相爭高下。 .3 p c b布局布線軟件 p c b 是英文 “ p r i n t e d c i r c u i t b o a r d ” 的 縮寫， 直譯是印刷電 路板， 其含義是: 以絕緣材料為基板加工成一定尺寸的板， 上面至少有一個導電圖形及所設計好的 孔， 以實現(xiàn)電 子元器件之間的電 氣連接， 這樣的 板稱為印 刷電路板， 圖1 . 3 1 3 給 出了 p c b的實物圖。1 9 3 6年，英國e i s l e r 博士提出印制電路 ( p r i n t e d c i r c u i t ) 這 個概念， 他首創(chuàng)在絕緣基板上全面覆蓋金 屬箔， 在其金屬箔上涂上耐 蝕刻油墨 后，再將不需要的金屬箔腐蝕掉的 p c b制造基本技術，1 9 4 2年，e i s l e r 博士制 造出 世界第一塊紙質(zhì)層壓絕緣基板， 用于收 音機的印制板。 5 0年代初， 這種技 術開始廣泛應用，并迅速得到發(fā)展。印制電路是電子產(chǎn)品的關鍵電子互連件， 無 論在市場領域，應用數(shù)量和技術水平等各方面都占 有極重要的地位并在快速發(fā) 展。一方面印 刷電路板是各種消費 類電子產(chǎn)品和投資類電 子產(chǎn)品的基本零組件， 目前， 消費類 電子產(chǎn)品和投資類電子產(chǎn)品要求其所對應的電子機器具有 “ 輕， 薄， 短， 小” 化， 多樣化，多功能， 高速， 高 可靠， 研制周期短和價廉等特點， 這就 促 使所設計出的印刷電 路板朝著小 孔徑. 細線條， 輕薄型的方向發(fā)展。 另一方面 在電子工業(yè)領域，隨著現(xiàn)代科學技術 日新月異地發(fā)展， 大規(guī)模、超大規(guī)模集成電 路的使用使印刷電路板的走線愈加精密和復雜。 在這種情況下， 傳統(tǒng)的手工設計 方式已越來越難以適應 當前的形勢， 因此計算機來輔助設計電路板己成為電路板 設計制作的必然趨勢。 p c i3 的制造過程 ， 簡單來說， 首先把集成電 路用陶瓷或塑料管殼 封裝， 然 后再安裝在印刷電路板上，目 前的 集成電 路封裝方法主要有三種:雙列直插式 d i p 、引腿陣列式 p g a和表面封裝 ( s u f a c e m o u n t e d d e v i c e，s m d )，封裝好的 器件的引腿插入、 安放在印制電路板表面， 這個過程叫布局，再根據(jù)布局測試布 線的可能性，然后在各個元器件之間進行連線，實現(xiàn)元件之間的電氣連接關系， 兩l 匕丁業(yè)火學順卜論文第一章緒論 我同電路c a d 軟件市場，國外產(chǎn)品占據(jù)了大部分市場份額。從軟件的使用 率來看，最知名的供應商是p r o t e l ( 現(xiàn)已更名為a l t i u m ) 。在中國大陸捌有7 3 的用戶，o r c a d ，s y n o p s y s 和c a d e n c e 各擁有較多的用戶，p c a d ，p a d s 也 有一些用戶。而在該領域的國產(chǎn)軟件，無論從技術上，功能上，還是從用戶數(shù)量 上，都難于和外國軟件相爭高下。 1 1 3p c b 布局布線軟件 p c b 是英文“p r i n t e d c i r c u i t b o a r d ”的縮寫，直譯是印刷電路板，其含義是： 以絕緣材料為基板加工成一定尺寸的板，上面至少有一個導電圖形及所設計好的 孔，以實現(xiàn)電子元器件之間的電氣連接，這樣的板稱為印刷電路板，圖1 3 ”1 給 出了p c b 的實物圖。1 9 3 6 年，英國e i s l e r 博士提出印制電路( p r i n t e dc i r c u i t ) 這個概念，他首創(chuàng)在絕緣基板上全面覆蓋金屬箔，在其金屬箔上涂上耐蝕刻油墨 后，再將不需要的金屬箔腐蝕掉的p c b 制造基本技術，】9 4 2 年，e i s l e r 博士制 造出世界第一塊紙質(zhì)層壓絕緣基板，用于收音機的印制板。5 0 年代初，這種技 術開始廣泛應用，并迅速得到發(fā)展。印制電路是電子產(chǎn)品的關鍵電子互連件，無 論在市場領域，應用數(shù)量和技術水平等各方面都占有極重要的地位并在快速發(fā) 展。一方面印刷電路板是各種消費類電子產(chǎn)品和投資類電子產(chǎn)品的基本零組件， 目前，消費類電子產(chǎn)品和投資類電子產(chǎn)品要求其所對應的電子機器具有“輕，薄 短，小”化，多樣化，多功能，高速高可靠，研制周期短和價廉等特點，這就 促使所沒計出的印刷電路板朝著小孔徑細線條，輕薄型的方向發(fā)展。另一方面 在電子工業(yè)領域，隨著現(xiàn)代科學技術日新月異地發(fā)展，大規(guī)模、超大規(guī)模集成電 路的使用使印刷電路板的走線愈加精密和復雜。在這種情況下，傳統(tǒng)的手工設計 方式已越來越難以適應當前的形勢，因此計算機來輔助設計電路板已成為電路板 設計制作的必然趨勢。 p c i 3 的制造過程“+ ”簡單來說，首先把集成電路用陶瓷或塑料管殼封裝，然 后再安裝在印刷電路板上，目前的集成電路封裝方法主要有三種：雙列直插式 d i p 、引腿陣列式p g a 和表面封裝( s u f a c em o u n t e dd e v i c e ，s m d ) ，封裝好的 器件的引腿插入、安放在印制電路板表面，這個過程叫布局，再根據(jù)布局測試布 線的可能性，然后在各個元器件之間進行連線，實現(xiàn)元件之間的電氣連接關系， 第章緒論 這個過程叫布線。最后再制作導線，將封裝件插入并焊接在鍍錫的孔中，或焊接 在印制電路板表面。圖1 4 日1 給出了p c b 的布線樣式。 圈1 3 標準p c b 的實物圈 圖1 4 標準p c b 的導線圈 自動布線是p c b 軟件設計的最主要的功能，印刷電路板自動布線就是止程 序根掘用戶設定的有關參數(shù)和布線規(guī)則，依照一定的程序算法，自動在各個元器 件之間進行連線實現(xiàn)元件之間的電氣連接關系，從而完成印刷電路板的布線工 作。自動布線算法是衡量p c b 設計軟件好壞的標準，布線算法選擇對印刷電路板 布線的布通率有很大的影響。 隨著計算機工業(yè)的飛速發(fā)展和大規(guī)模，超大規(guī)模集成電路的出現(xiàn)，芯片的集 成度越來越高，印刷電路越來越復雜，布線的難度也越來越大，已非人工布線所 能及，自動布線的研究工作也應運而生。自動布線是電子c a d 領域中的一個經(jīng) 典課題，在近四十年的研究過程中，其理論、技術和方法均取得很大的進步。然 而，自動布線問題的本身是復雜的，盡管人們?yōu)樘岣咦詣硬季€的布通率和速度， 提出了各種很好的方法，但由于高密度引腳及引腳尺寸臼趨物理極限，導致低的 前i 通率，或雖然布通但不能滿足設計要求，自動布線仍然需要大量的人工干預時 問。就目前的情況來看，在印制電路板自動布線方面，有李氏算法，線探索法， 最優(yōu)通道法，h i t c h e o o k 的細胞結構法，h a d h i m o t o 及s t e v e n s 的通道分配法， m a h 及s t a i n b e r g 的拓撲類并法，j s o u k u p 的快速迷路法等各種方法。近年來， 又提出了朝向目標的線探索法。雖然方法很多，但都有各自的缺點和局限性。而 且目前的幾大p c b 布線工具雖然它們的布通率都還差強人意，但在系統(tǒng)自動稚 完線完成后還得靠手工修改后才能達到預期效果，而且電路愈復雜，所要的手工 兩北丁業(yè)大學傾士論文第一章緒論 修改量就愈大。因此采用什么樣的方法能使布線在符合設計要求的前提下，布通 率更高，速度更快，讓系統(tǒng)自動布線后所做的手工修改最少，仍然是一個沒有被 完滿解決的課題。 1 2 研究內(nèi)容 本論文研究內(nèi)容是針對實用要求，研究印刷電路板的自動布線的算法理論 和實現(xiàn)以及算法的優(yōu)化。它是西北工業(yè)大學機電學院廖達雄副教授正在開發(fā)的電 路c a d 軟件的一部分，同時也是該軟件的幾個核心技術之一。 本文首先介紹了電路c a d 的概念和電路c a d 軟件的結構以及p c b 布線軟件在 電路c a d 軟件中的地位和作用；第二章介紹已有的布線算法，并分析各算法的優(yōu) 點和缺點及適用情況；第三章，簡要介紹本論文所涉及到的基礎知識，為后續(xù)章 節(jié)的展開做必要的準備，其中的知識涉及到圖論、動態(tài)規(guī)劃、斯坦納樹的構造等； 第四章，在分析已有算法的基礎上，結合圖論知識和人工智能解決問題的思路提 出了更符合實際要求的速度快，具有高布通率的布線算法智能識點法的布線 理論。這部分是本文的核心也是本文的創(chuàng)新之處，在這部分中，首先給出線網(wǎng)排 序的算法；其次，結合人工智能解決問題的思路，提出m d 布線模型下的廣義線 段的概念及m d 線長的計算方法；再次，提出繞障點的概念，給出詳細定義繞障 點的方法；最后，給出以廣義線段為邊，以繞障點和待布點為頂點的帶邊權值的 完全圖構造方法及在圖中搜索最短路徑的算法。第五章，首先，給出智能識點法 的實現(xiàn)的數(shù)據(jù)結構：其次，指出了算法實現(xiàn)過程中的幾個關鍵問題，并給出了解 決的詳細方案：最后，給出算例，并根據(jù)實驗數(shù)據(jù)和對數(shù)據(jù)的分析，總結出算法 的特點，指出智能識點法布線的有待改進之處和今后的努力方向。第六章結束語。 6 西 北 下 業(yè) 大 學 碩 士論 文第一章緒論 修改量就愈大。 因此采用什么樣的方法能使布線在符合設計要求的前提下， 布 通 率更高，速度更快，讓系統(tǒng)自動布線后所做的手工修改最少， 仍然是一個沒有被 完滿解決的課題。 1 . 2研究內(nèi)容 本論文研究內(nèi)容是針對實用要求，研究印刷電路板的 自 動布線的算法理論 和實現(xiàn)以 及算法的優(yōu)化。 它是西北工業(yè)大學機電 學院 廖達雄副教授正在開發(fā)的電 路c a d軟件的一部分，同時 也是該軟 件的幾個核心技術之一。 本文首先介紹了電 路c a d 的 概念和電路c a d 軟件的結構以 及p c b 布線軟件在 電路c a d 軟件中的 地位和作用; 第二章介紹已 有的布線算法， 并分析各算法的優(yōu) 點和缺點及適用情況; 第三章， 簡要介紹本論文所涉及到的基礎知識， 為 后續(xù)章 節(jié)的展開做必要的準備， 其中的知識涉及到圖論、 動態(tài)規(guī)劃 、 斯坦納樹的構造等; 第四章， 在分析已有算法的基礎上， 結合圖論知識和人工智能解決問題的思路提 出了 更符合實際要求的速度快， 具 有高布 通率的布線算法智能識點法的布線 理論。這部分是本文的核心也是本文的創(chuàng)新之處， 在這部分中，首先給出線網(wǎng)排 序的算法;其次，結合人工智能解決問題的思路，提出m d 布線模型下的廣義線 段的 概念及 m d 線長的計算方法; 再次， 提出繞障點的概念，給出詳細定義繞障 點的 方法: 最后， 給出以廣義線段為 邊， 以 繞障點和待布點 為頂點的帶邊權值的 完 全圖構造方法及在圖中搜索最短路徑的 算法。 第五章， 首先， 給出智能識點 法 的實 現(xiàn)的數(shù) 據(jù)結構: 其次， 指出了 算法實現(xiàn)過 程中的幾個關鍵問題， 并給出了 解 決的 詳細方案: 最后， 給出 算例， 并根據(jù)實驗數(shù)據(jù)和對數(shù)據(jù)的分析， 總結出算法 的特點， 指出智能識點法布線的有待改進之處和今后的努力方向。 第六章結束語。 丙北工業(yè)大學碩_ l - 論文 第二章p c b自動布線理論研究概祝 第二章 p c b自 動布線理論研究概況 2 . 1印刷電 路板自 動布線在電路c a d軟件中的作用 在電 子電 路c a d 軟件設計系統(tǒng)中， 印 刷電路板的設計系統(tǒng)結構如圖2 . 1 所示。 網(wǎng) 絡 表 圖2 . 1 印 刷電路板設計系統(tǒng)結構圖 其中， 電路原理圖繪制程序和印 刷電 路板布線程序可以 分別作為兩個獨立的 軟件來完成各自 對應的功能。 而網(wǎng)絡表則是聯(lián)系電 路原 理圖和印 刷電路板布線的 紐帶。印刷電路板的設計工序流程圖如圖2 . 2 所示。對比兩圖就可以看出其中的 對應關系:電路圖繪制程序是p c b設計流程中的 前段處理程序，主要是負責繪 制電 路原理圖、 各元件屬性與仿真參數(shù)的 設置。 電 路原理圖經(jīng)過后處理程序的處 理產(chǎn)生網(wǎng) 絡表， 也可以 根據(jù)需要產(chǎn)生其它文本文件如: 元件列表等， 接下來就是 根據(jù)網(wǎng)絡表所提供的數(shù)據(jù)信息和 p c b布線程序進行印刷電路板的設計，其中包 括: 電路板的規(guī)劃、 設置參數(shù)、 裝入網(wǎng)絡表和元件封裝外形、 元件布局、自 動布 線以及存盤打印等步驟。在整個印刷電路板的設計過程中自動布線是核心技術， 也就是本論文的主要研究內(nèi)容。 丙北工業(yè)大學碩_ l - 論文 第二章p c b自動布線理論研究概祝 第二章 p c b自 動布線理論研究概況 2 . 1印刷電 路板自 動布線在電路c a d軟件中的作用 在電 子電 路c a d 軟件設計系統(tǒng)中， 印 刷電路板的設計系統(tǒng)結構如圖2 . 1 所示。 網(wǎng) 絡 表 圖2 . 1 印 刷電路板設計系統(tǒng)結構圖 其中， 電路原理圖繪制程序和印 刷電 路板布線程序可以 分別作為兩個獨立的 軟件來完成各自 對應的功能。 而網(wǎng)絡表則是聯(lián)系電 路原 理圖和印 刷電路板布線的 紐帶。印刷電路板的設計工序流程圖如圖2 . 2 所示。對比兩圖就可以看出其中的 對應關系:電路圖繪制程序是p c b設計流程中的 前段處理程序，主要是負責繪 制電 路原理圖、 各元件屬性與仿真參數(shù)的 設置。 電 路原理圖經(jīng)過后處理程序的處 理產(chǎn)生網(wǎng) 絡表， 也可以 根據(jù)需要產(chǎn)生其它文本文件如: 元件列表等， 接下來就是 根據(jù)網(wǎng)絡表所提供的數(shù)據(jù)信息和 p c b布線程序進行印刷電路板的設計，其中包 括: 電路板的規(guī)劃、 設置參數(shù)、 裝入網(wǎng)絡表和元件封裝外形、 元件布局、自 動布 線以及存盤打印等步驟。在整個印刷電路板的設計過程中自動布線是核心技術， 也就是本論文的主要研究內(nèi)容。 西 北 f 業(yè) 人學 碩 七論 文第二章p c 日自動布線理論湃究概況 圖2 .2 印刷電路板設計工序流程圖 網(wǎng)絡表所提供的信息主要包括兩個方面: 一方面是電路原理圖中所有元器件 的 屬性信息，另一方面是元器 件之間的電氣連接關系。 這些數(shù)據(jù)恰恰是 p c b布 線所需要的 關鍵條件。 由此也可以 看出， 網(wǎng) 絡表是電 路原理圖和印 刷電路板之間 的 一座橋梁，是實現(xiàn)p c b自 動布線的基礎。 西北 7 業(yè)大學碩_ 1 論文 第_帝p cb自動布線理論研究溉沉 2 . 2印刷電路板自動布線的基本概念和分類 2 .2 .1印刷電路板的基本概念 印刷電路板是構建電路系統(tǒng)的基礎技術， 將設計電路中各元件間的電氣連接 線作成實體銅膜連接線， 在一層或數(shù)層絕緣板 子上作出信號板層， 并適當?shù)匚g刻 成元件外形的焊點和銅膜走線 來安裝與連接各個電 子元件。 早期的 絕緣板都是使 用電木為材料，現(xiàn)在則大多都改用玻璃纖維材料， 厚度更薄，而彈性和韌度都更 好 。 所謂元件外形主要就是一群根據(jù)實際元件包裝尺寸而定義好的焊點， 另外還 附加一些屬性和展示元件外觀的符號。元件外形符號與屬性符號主要是供人看 的， 不具備特殊的電 氣或?qū)嶓w 銅膜意義。 所謂焊點 ( 或焊盤) 就是提供外界用焊接方式來連接元件引腳與電路板走線 的銅膜接點。 在 p c b制作流程中蝕刻出各焊點間的 連接銅線就是銅膜走線。 在 鋪布銅膜走線時， 如果有別的 走線或是 元件擋 住了去向， 就得在絕緣板上鉆孔形 成所謂的導孔 ( v i a ， 又稱貫孔)， 然后通過導 孔的連接使銅膜走線可以切換到 另外一個布線板層繼續(xù)完成連接焊點的工作， 如圖2 . 3 所示。 元件外形序號屬性 元件外形批注屬性 u i ，d i ps 元件外形符號 焊點 銅膜走線 ; . 了 。一 、 廠 一2 . 7 k _ i 黔 目目翻 粉 導孔 夕萬 焊點元件外形符號 圖2 . 3元件外形、焊點、銅膜走線與導孔 西北 7 業(yè)大學碩_ 1 論文 第_帝p cb自動布線理論研究溉沉 2 . 2印刷電路板自動布線的基本概念和分類 2 .2 .1印刷電路板的基本概念 印刷電路板是構建電路系統(tǒng)的基礎技術， 將設計電路中各元件間的電氣連接 線作成實體銅膜連接線， 在一層或數(shù)層絕緣板 子上作出信號板層， 并適當?shù)匚g刻 成元件外形的焊點和銅膜走線 來安裝與連接各個電 子元件。 早期的 絕緣板都是使 用電木為材料，現(xiàn)在則大多都改用玻璃纖維材料， 厚度更薄，而彈性和韌度都更 好 。 所謂元件外形主要就是一群根據(jù)實際元件包裝尺寸而定義好的焊點， 另外還 附加一些屬性和展示元件外觀的符號。元件外形符號與屬性符號主要是供人看 的， 不具備特殊的電 氣或?qū)嶓w 銅膜意義。 所謂焊點 ( 或焊盤) 就是提供外界用焊接方式來連接元件引腳與電路板走線 的銅膜接點。 在 p c b制作流程中蝕刻出各焊點間的 連接銅線就是銅膜走線。 在 鋪布銅膜走線時， 如果有別的 走線或是 元件擋 住了去向， 就得在絕緣板上鉆孔形 成所謂的導孔 ( v i a ， 又稱貫孔)， 然后通過導 孔的連接使銅膜走線可以切換到 另外一個布線板層繼續(xù)完成連接焊點的工作， 如圖2 . 3 所示。 元件外形序號屬性 元件外形批注屬性 u i ，d i ps 元件外形符號 焊點 銅膜走線 ; . 了 。一 、 廠 一2 . 7 k _ i 黔 目目翻 粉 導孔 夕萬 焊點元件外形符號 圖2 . 3元件外形、焊點、銅膜走線與導孔 西北t.業(yè)大學碩十淪文 第二章p c b自動布線理論研究概況 由于印刷電路板所使用的實體元件可分為針腳式和表面粘著式 ( s md : s u r f a c e mo u n t d e v i c e )兩種，所以焊點的形式也可以區(qū)分為針腳式焊點和 s md 式焊 點。 2 .2 .2 布線設計的目標 在布圖設計中，布線設計的目 標可描述為:根據(jù)電路的連接關系描述 ( 網(wǎng)絡 表)， 在滿足設計、工藝規(guī)則的要求和滿足電學性能的要求的條件下， 在限定區(qū) 域 ( 面積、 形狀、 層次等)內(nèi)1 0 0 %地完成所需的互 連?；蛘呤窃?1 0 0 完成所 需互連時，使所需的 p c b( 或芯片)面積最小化。同時要求盡可能優(yōu)化其設計 結果 ( 如連線長度最小化， 通孔數(shù)最小化等)。 2 . 2 .3 布線設計所面臨的問題及布線方法的分類 布線設計所面臨的問題: 在平面上實現(xiàn)一條線網(wǎng)的 布線并不困 難， 但當需 布線網(wǎng)數(shù)足夠多時， 如需求 其連線總長最短的布線方案則是一個復雜的難題。 而在實際問題中， 線網(wǎng)數(shù)一般 相當多，有些線網(wǎng)還是多端點線網(wǎng) ( 即一條線網(wǎng)聯(lián)結著多于兩個接點的情況)， 情況將更加復雜。除了必須考慮線網(wǎng)需滿足的電學、工藝要求外，當?shù)?i 條線網(wǎng) 布線時， 為了不與同平面的己 布線 交叉， 不僅需要考慮線網(wǎng)自 身各接點間的關系， 而且還必須考慮己布線的影響及對今后其它線網(wǎng)布線的影響。 此時， 是否存在一 條實現(xiàn)互連的路徑，如何找到互連的路徑，如何找到一條最短的路徑，或找到一 條對今后布線最有利的路徑，都成為相當困難的問題。同時，對于每個線網(wǎng)，又 有幾百種甚至更多種布線方案，這樣就使得布線問題異常復雜。 布線方法的分類: 通常有兩種策略實現(xiàn)布線， 即直接的區(qū)域布線和分兩步實現(xiàn)的總體布線和詳 細布線。 就布線的對象來分， 布線問題也可以分為面向線網(wǎng)的布線和面向區(qū)域的 布線。 面向 線網(wǎng)的布線主要以 線網(wǎng)作為 考慮對象， 如總體布線和區(qū) 域布線都 屬于 面向 線網(wǎng)的布線: 而面向區(qū) 域的布線主要以 布線區(qū)域作為 考慮對象， 如兩邊通道 布線和開關盒布線都屬于面向區(qū)域的布線問題。 根據(jù)本課題的實用背景。本文主要討論面向線網(wǎng)的布線算法。 西北t.業(yè)大學碩十淪文 第二章p c b自動布線理論研究概況 由于印刷電路板所使用的實體元件可分為針腳式和表面粘著式 ( s md : s u r f a c e mo u n t d e v i c e )兩種，所以焊點的形式也可以區(qū)分為針腳式焊點和 s md 式焊 點。 2 .2 .2 布線設計的目標 在布圖設計中，布線設計的目 標可描述為:根據(jù)電路的連接關系描述 ( 網(wǎng)絡 表)， 在滿足設計、工藝規(guī)則的要求和滿足電學性能的要求的條件下， 在限定區(qū) 域 ( 面積、 形狀、 層次等)內(nèi)1 0 0 %地完成所需的互 連?；蛘呤窃?1 0 0 完成所 需互連時，使所需的 p c b( 或芯片)面積最小化。同時要求盡可能優(yōu)化其設計 結果 ( 如連線長度最小化， 通孔數(shù)最小化等)。 2 . 2 .3 布線設計所面臨的問題及布線方法的分類 布線設計所面臨的問題: 在平面上實現(xiàn)一條線網(wǎng)的 布線并不困 難， 但當需 布線網(wǎng)數(shù)足夠多時， 如需求 其連線總長最短的布線方案則是一個復雜的難題。 而在實際問題中， 線網(wǎng)數(shù)一般 相當多，有些線網(wǎng)還是多端點線網(wǎng) ( 即一條線網(wǎng)聯(lián)結著多于兩個接點的情況)， 情況將更加復雜。除了必須考慮線網(wǎng)需滿足的電學、工藝要求外，當?shù)?i 條線網(wǎng) 布線時， 為了不與同平面的己 布線 交叉， 不僅需要考慮線網(wǎng)自 身各接點間的關系， 而且還必須考慮己布線的影響及對今后其它線網(wǎng)布線的影響。 此時， 是否存在一 條實現(xiàn)互連的路徑，如何找到互連的路徑，如何找到一條最短的路徑，或找到一 條對今后布線最有利的路徑，都成為相當困難的問題。同時，對于每個線網(wǎng)，又 有幾百種甚至更多種布線方案，這樣就使得布線問題異常復雜。 布線方法的分類: 通常有兩種策略實現(xiàn)布線， 即直接的區(qū)域布線和分兩步實現(xiàn)的總體布線和詳 細布線。 就布線的對象來分， 布線問題也可以分為面向線網(wǎng)的布線和面向區(qū)域的 布線。 面向 線網(wǎng)的布線主要以 線網(wǎng)作為 考慮對象， 如總體布線和區(qū) 域布線都 屬于 面向 線網(wǎng)的布線: 而面向區(qū) 域的布線主要以 布線區(qū)域作為 考慮對象， 如兩邊通道 布線和開關盒布線都屬于面向區(qū)域的布線問題。 根據(jù)本課題的實用背景。本文主要討論面向線網(wǎng)的布線算法。 西北丁業(yè)大學碩上論文 第二章p c b自動布線理論研究概況 2 . 3 面向線網(wǎng)自動布線算法的概況及分析 而向線網(wǎng)的自 動布線算法主要有迷宮 算法和線 探索法兩類。 2 . 3 . 1迷宮算法 自 動布線 印 刷電路板是焊盤、 過孔、 走線 和銅區(qū) 等物體的組合， 每種物體可有任意形 狀。單純從電器特性、經(jīng)濟因素和制造關系考慮，好的 p c b設計應使走線區(qū)的 總 面積和過孔數(shù)目盡可能減少， 從而可保證最少的 面板完成設計， 使產(chǎn)量得以 提 局 。 世 界 上 最 早的 布線 器 當 推 1 9 6 1 年 發(fā) 布 的l e e 算 法 6 ， 它 實 際 上 是圖 論 中 最 小路徑算法在矩形網(wǎng)格上的 一種應用。 其算法的思想也可以描述為對波傳遞過程 的模擬。在一個存在障礙的湖面上，若需尋找連接點 a和 b之間的最短路徑， 可以在點 a處投下一個小石子，然后觀察所引起的水波的傳播情況。 假定水波 的傳播過程中能量沒有損失， 則當遇到障礙時， 波發(fā)生繞射 ， 最先到達目標點的 波前所經(jīng)過的路徑必是一條最短路徑，而且只要二點間存在通路，則從點 a 開 始擴展傳播的水波一定將波傳播到點 b ， 也即只要通路存在就一定能找到這條通 路。這個過程可以形象地在計算機中進行模擬。 李氏算法地布線過程大致可分為 ( 1 )數(shù)據(jù)準備 ( 2 )擴展過程 ( 3 )回找過 程，圖2 . 4 所示就是李氏算法布線的原理。 廠臼曰曰曰曰廠曰 而 曰 arm _ 曰 卜 目 月口口口 _ l回! _曰曰 _ _1 _ 日日口口岡口岡門 口口口回口回團國 日日困回口 口 . 口口 口口巨 口口巨 曰口口巨巨 口口口口口曰曰口 ( a) ( b) 西北丁業(yè)大學碩上論文 第二章p c b自動布線理論研究概況 2 . 3 面向線網(wǎng)自動布線算法的概況及分析 而向線網(wǎng)的自 動布線算法主要有迷宮 算法和線 探索法兩類。 2 . 3 . 1迷宮算法 自 動布線 印 刷電路板是焊盤、 過孔、 走線 和銅區(qū) 等物體的組合， 每種物體可有任意形 狀。單純從電器特性、經(jīng)濟因素和制造關系考慮，好的 p c b設計應使走線區(qū)的 總 面積和過孔數(shù)目盡可能減少， 從而可保證最少的 面板完成設計， 使產(chǎn)量得以 提 局 。 世 界 上 最 早的 布線 器 當 推 1 9 6 1 年 發(fā) 布 的l e e 算 法 6 ， 它 實 際 上 是圖 論 中 最 小路徑算法在矩形網(wǎng)格上的 一種應用。 其算法的思想也可以描述為對波傳遞過程 的模擬。在一個存在障礙的湖面上，若需尋找連接點 a和 b之間的最短路徑， 可以在點 a處投下一個小石子，然后觀察所引起的水波的傳播情況。 假定水波 的傳播過程中能量沒有損失， 則當遇到障礙時， 波發(fā)生繞射 ， 最先到達目標點的 波前所經(jīng)過的路徑必是一條最短路徑，而且只要二點間存在通路，則從點 a 開 始擴展傳播的水波一定將波傳播到點 b ， 也即只要通路存在就一定能找到這條通 路。這個過程可以形象地在計算機中進行模擬。 李氏算法地布線過程大致可分為 ( 1 )數(shù)據(jù)準備 ( 2 )擴展過程 ( 3 )回找過 程，圖2 . 4 所示就是李氏算法布線的原理。 廠臼曰曰曰曰廠曰 而 曰 arm _ 曰 卜 目 月口口口 _ l回! _曰曰 _ _1 _ 日日口口岡口岡門 口口口回口回團國 日日困回口 口 . 口口 口口巨 口口巨 曰口口巨巨 口口口口口曰曰口 ( a) ( b) 西北一 業(yè)大學碩十論文第二章p c b白動布線理論研究概況 困口回口回口回回 口回口回口回口回 岡曰 4 . 2 國回回 口 6 5 l 699 r 2 口團 日口 k 崢 國國 團國口曰 口口口口回囚口國 曰 i巨巨巨口口口 口巨口巨口回園口 口口口圈口 圈口口 口團口 回口口 口巨口口 門巨!口口 ( ) ( d ) 圖 2 . 4李氏布線算法的原理圖 圖中黑 格為配線禁區(qū)，空格為可配線區(qū)， s . t為待連接的兩個端點。s - t 兩點間的連線過程是: ( 1 )確定起始單元為 s ( t為終止單元)，圖 ( a )所示; ( 2 ) 將 s點的相鄰單元設為 “ 1 ” 單元， 再設 “ 1 ”單元的相鄰單元為 “ 2 ， 依此類推 ，直至某單元 ( 圖中為 “ 9 ”單元)的相鄰單元為配線終止單元為 i r ,圖 ( b )