閆利平，陳慶奎,2

(1. 上海理工大學(xué)光電信息與計算機學(xué)院，上海 200093；2. 上?，F(xiàn)代光學(xué)系統(tǒng)重點實驗室，上海 20009 3)

一種基于布局布線協(xié)同的PCB設(shè)計算法

閆利平1，陳慶奎1,2

(1. 上海理工大學(xué)光電信息與計算機學(xué)院，上海 200093；2. 上?，F(xiàn)代光學(xué)系統(tǒng)重點實驗室，上海 20009 3)

針對印刷電路板(PCB)設(shè)計中布局造成散熱性差和布線造成抗噪聲性差，導(dǎo)致PCB的抗干擾性弱的問題，提出一種布局布線協(xié)同算法，基于元胞自動機思想，以溫度為基準(zhǔn)，對元件進(jìn)行位置調(diào)動，使元件的放置符合演化規(guī)則的定態(tài)要求，從而使布局的散熱性能達(dá)到要求，同時運用優(yōu)化蟻群算法對當(dāng)前布局以路徑最短及通孔數(shù)最小化為目標(biāo)進(jìn)行布線，并評價其抗噪聲性能。實驗結(jié)果表明，從散熱性方面調(diào)整布局，散熱性能提高14%左右，從抗噪聲性能方面考慮布線，平均路徑長度與通孔數(shù)下降明顯，

PCB板的總平均溫度降低14%左右。

散熱性；抗噪聲性；蟻群算法；元胞自動機；抗干擾性；印刷電路板設(shè)計

1 概述

抗干擾性是印刷電路板(Printed Circ uit Boar d, P CB)設(shè)計中最重要的因素。PCB設(shè)計主要涉及布局布線2個方面。設(shè)計一個抗干擾性強的PCB，要做到布局的散熱性好以及布線抗噪聲能力強。通過布局與布線之間相互協(xié)同，以達(dá)到上述目的。針對PCB布局布線優(yōu)化設(shè)計有大量成熟的研究成果，文獻(xiàn)[1-2]提出一種無網(wǎng)格布線算法，在給定布局平面上采用優(yōu)化迷宮算法完成布線。文獻(xiàn)[3-4]從布線方面考慮，解決了布線尋找最短路徑及通孔數(shù)最少的問題[5]。文獻(xiàn)[6-7]分別從啟發(fā)式算法提出了布局優(yōu)化的方法，文獻(xiàn)[6]運用改進(jìn)遺傳算法僅對元件在布局中的位置優(yōu)化并沒有對元件之間干擾做出比較，文獻(xiàn)[7]用模擬退火算法優(yōu)化電子元件的布局，盡管旨在降低電子設(shè)備的最大溫度值，為電子元件的散熱優(yōu)化問題提供了方法，但沒有考慮布局單方面最優(yōu)可能會造成布線布通率低及內(nèi)部噪聲干擾強的問題。文獻(xiàn)[8]基于雙層線板布線提出元胞螞蟻算法對布線進(jìn)行優(yōu)化，但是這種布線算法計算量比較大，而且僅對已定布局適用，缺乏通過調(diào)整布局使布線路徑更優(yōu)的靈活性。本文從PCB抗干擾性[9-10]出發(fā)，運用布局布線的協(xié)同對PCB優(yōu)化設(shè)計進(jìn)行分析。提出布局與布線協(xié)同優(yōu)化算法，利用基于元胞自動機思想的算法調(diào)整布局中元件的位置及蟻群算法對布線路徑尋優(yōu)和通孔個數(shù)控制。

2 布局布線問題描述

PCB設(shè)計主要考慮：布局和布線設(shè)計。通過布局和布線協(xié)同過程完成對PCB的設(shè)計。從布局考慮，以優(yōu)化PCB散熱性為目的，通過基于元胞自動機思想并遵循將不同種類的元器件分散交錯排列的原則，實現(xiàn)對元件的合理布置；從布線考慮，運用蟻群算法對當(dāng)前布局以路徑最短、通孔數(shù)最小化為目的做布線設(shè)計。通過綜合評估當(dāng)前布局的散熱性能及布線后產(chǎn)生噪聲的大小，使得PCB設(shè)計的抗干擾性最優(yōu)穩(wěn)定性最好。

2.1 P CB干擾評估描述

在對PCB干擾性探討中，主要考慮布局的散熱性和布線的噪聲干擾。在通常情況下，PCB抗干擾性與布局散熱性呈正比，而與布線產(chǎn)生噪聲呈反比，故PCB干擾值評估函數(shù)Dis可定義為：

其中，α和β分別表示為布局的散熱性和布線中的噪聲干擾權(quán)值；T表示為布局溫度衡量函數(shù)；L表示為布線噪聲衡量函數(shù)。

在PCB設(shè)計中，干擾越小則穩(wěn)定性越好，即可簡述為：在確定T和L情況下，使得目標(biāo)函數(shù)Dis( T, L)取最小值。PCB設(shè)計數(shù)學(xué)模型描述為：

由于元件的性質(zhì)不同，其產(chǎn)生熱量及耐熱值均不同，為衡量元件的溫度閾值Q，通過如下公式定義：

其中，m表示元件的鄰居個數(shù)；P表示元件的功率；t表示時間；d'表示兩元件之間的距離；A表示分別以元件為圓心，半徑為d'圓區(qū)域的重疊面積。

2.2 布局定義描述

對布局而言，考慮其散熱性問題，對單個元件而言，其溫度受自身和周圍鄰居元件熱輻射[11-12]的影響，而整個PCB板的溫度受板上所有元件溫度的影響，PCB板的溫度越高其散熱性越差。因此，本文引入布局溫度衡量函數(shù)T，散熱性能函數(shù)K，函數(shù)T的值越大則其散熱性越差即函數(shù)K的值越小，描述如下：設(shè)元件由普通元件(CE)、發(fā)熱元件(HE)和熱敏元件(AE)組成，令溫度集合N={Tx(CE), Tx(HE), Tx(AE)}，Tx(CE)，Tx(HE)，Tx(AE)分別表示普通、發(fā)熱和熱敏元件的溫度衡量函數(shù)，則溫度衡量函數(shù)：

設(shè)布局散熱性能函數(shù)為：

其中，μ是衡量PCB板整體溫度與其散熱性能關(guān)系的常量系數(shù)。

2.3 布線定義描述

對布線而言，通常是使布線路徑最短，通孔數(shù)最小。由于需要對這2個目標(biāo)進(jìn)行優(yōu)化，因此布線屬于多目標(biāo)優(yōu)化問題，則：

其中，x1、x2分別表示元件節(jié)點的坐標(biāo)；d表示元件之間的安全距離；f1( x1, x2)表示導(dǎo)線產(chǎn)生噪聲函數(shù)；f2(x1, x2)表示為通孔產(chǎn)生噪聲函數(shù)。主要是搜索F( x1, x2)非劣解過程，求解F( x1, x2)最小值，因此，采取了蟻群這種啟發(fā)式算法來解決這種多目標(biāo)優(yōu)化問題。

3 PCB算法設(shè)計描述

3.1 總體描述

對布局運用元胞自動機的思想實現(xiàn)3類元件的分散交錯排列，并用函數(shù)K衡量其散熱性，隨之進(jìn)入布線循環(huán)運用優(yōu)化蟻群算法使路徑最短通孔數(shù)最小化并用噪聲評估函數(shù)L衡量布線的噪聲影響，用式(1)對當(dāng)前布局布線的干擾性進(jìn)行評估。將干擾性最小的設(shè)計作為當(dāng)前符合電路性能要求，穩(wěn)定性高的PCB設(shè)計。

整體算法描述：

Step1初始定義存儲元件溫度表AT，全局溫度變量Temperature；布線噪聲變量Noise；狀態(tài)干擾變量Ps，Ps +1；路徑長度變量Length；通孔個數(shù)變量hole。

Step2定義循環(huán)變量n，設(shè)while循環(huán)迭代條件為n≤N，其中N為尋找到當(dāng)前干擾性最優(yōu)的布局布線設(shè)計算法執(zhí)行次數(shù)的期望值；轉(zhuǎn)入Step 3。

Step3調(diào)用基于元胞自動機思想的算法調(diào)整布局；根據(jù)Tx(CE)、Tx(HE)、Tx(AE)計算3種元件的溫度值，存到AT中，用式(3)計算T( AT)的值并賦值給Temperature；轉(zhuǎn)入Step4。

Step4調(diào)用蟻群算法對當(dāng)前布局優(yōu)化布線，并將最優(yōu)路徑長度賦給變量Length，最優(yōu)通孔個數(shù)存到變量hole；調(diào)用噪聲干擾評估函數(shù)式(6)衡量當(dāng)前布線對整體設(shè)計的噪聲干擾情況并將其賦給Noise；轉(zhuǎn)入Step5。

Step5調(diào)用函數(shù)干擾值評估函數(shù)式(1)，將Temperature值和Noise值分別傳到T、L中，衡量整體設(shè)計的干擾值并賦值給Ps；轉(zhuǎn)入Step3；可獲得下一個狀態(tài)干擾的衡量值Ps+1，然后比較即ifPs＞Ps +1，then將Ps+1賦給Ps，使n=n+1；else轉(zhuǎn)入Step3 并執(zhí)行n=n+1；if n≤N，then 轉(zhuǎn)入 St ep2；else 結(jié)束循環(huán)。

3.2 布局實現(xiàn)算法

3.2.1 元胞自動機演化規(guī)則描述

設(shè)四元組集合A={Ld, S, M, f }，定義Ld( d=2)表示二維空間，S表示任意元件狀態(tài)轉(zhuǎn)移的狀態(tài)集合S={上移(Sa)，下移(Sd)，左移(Sl)，右移(Sr)，左上移(Sla)，左下移(Sld)，右上移(Sra)，右下移(Srd)，定態(tài)(Sw)}，狀態(tài)轉(zhuǎn)移標(biāo)志用0、1表示。當(dāng)允許轉(zhuǎn)移時置狀態(tài)標(biāo)志變量Flag為1，其他為0，M表示元件鄰居集合M={M1,M2,…,Mi}，i表示鄰居節(jié)點個數(shù)，f是狀態(tài)的演化規(guī)則，其定義如下：由于當(dāng)前布局每個元件受鄰居元件熱輻射及其自身溫度影響，其目標(biāo)函數(shù)：

(1)在上下左右4個方向都有元件的情況下，對于上移(Sa)狀態(tài)轉(zhuǎn)移的定義：對中心元件相鄰位置正下方元件對其熱輻射的溫度Ts判斷，若Ts＞Q，則狀態(tài)轉(zhuǎn)移標(biāo)志Flag= 1，對應(yīng)元件向上移動，同時將Flag清0，并判斷此次位置調(diào)整后該元件對鄰居元件影響是否大，若在影響允許范圍內(nèi)則接受當(dāng)前調(diào)整，否則判斷其他方向的元件。

同理，對狀態(tài)集合S中其他狀態(tài)即下移(Sd)、左移(Sl)、右移(Sr)進(jìn)行位置調(diào)整。

(2)在斜對角4個方向情況下，對于左上移(Sla)狀態(tài)轉(zhuǎn)移的定義：對中心元件相鄰位置正右、下、右下方3個元件對其熱輻射的溫度之和sT判斷，運用和(1)同樣的方法。

同理，對狀態(tài)集合S中其他狀態(tài)即左下移(Sld)、右上移(Sra)、右下移(Srd)用同樣的方法調(diào)整。

(3)對于狀態(tài)集合S中定態(tài)(Sw)的定義：若對上述8種情況均判斷不滿足條件，則是定態(tài)(Sw)的標(biāo)志變量Flag置1，表示該元件不需要移動。

3.2.2 布局算法描述

布局算法步驟如下：

Step1設(shè)一個狀態(tài)集合為S，初始狀態(tài)轉(zhuǎn)移標(biāo)志Flag均為0，當(dāng)Flag為1時則選取該狀態(tài)，存儲鄰居元件節(jié)點的集合M={M1,M2,…,Mi}。

Step2從溫度表AT中取出當(dāng)前中心元件溫度值，判斷其溫度及鄰居元件對其的影響，并改變狀態(tài)集合中相應(yīng)Flag的值，根據(jù)f，實現(xiàn)布局的調(diào)整。

Step3設(shè)Ni( xi, yi)為第i個元件的坐標(biāo)，根據(jù)鄰居集合M計算中心元件No(xo. yo)到鄰居元件Ni( xi, yi)的距離：

To、Ti分別表示中心元件及鄰居元件的溫度，根據(jù)公式：

其中，T(s)表示當(dāng)前狀態(tài)溫度，返回溫度值Temperature= T( s)，并存儲Temperature。

3.2.3 布線算法描述

蟻群算法被證明在多目標(biāo)優(yōu)化問題上，表現(xiàn)出很好的并行特性和魯棒性，并且成功地用于求解多種NP難的問題，以下給出蟻群算法描述：

Step1設(shè)時刻變量time置0；迭代步數(shù)nc置0，對各邊D(i,j)：置τij為常數(shù)c(c趨于無窮小)；置Δτij為0；Lbest置空(儲存當(dāng)前最好的路徑隊列)；hole置0存儲通孔個數(shù)；置Length常數(shù)a(a是較大的正數(shù)，Length用來儲存當(dāng)前最短的路徑長度)。

Step2將m只螞蟻隨機置于n個結(jié)點上；對于每個螞蟻：初始化禁忌表；置空路徑隊列Lbest。

if 邊E(i,j)上沒有障礙，then移動螞蟻k至結(jié)點j than else 調(diào)用避障程序；

if 選擇通孔，則hole++；than else避線繞點；

j加入禁忌表；Dij置入隊列Lengthk；end計算路徑Lengthk長度，將最好的結(jié)果存入Lbest。

Step3for k=1 to m

Step4if nc ＜預(yù)定迭代次數(shù)且無退化行為，則循環(huán)結(jié)束。

4 實驗結(jié)果與分析

4.1 布局散熱測試

在NS2中對網(wǎng)絡(luò)規(guī)模為20的拓?fù)浣Y(jié)構(gòu)仿真，并用CFD軟件對整個拓?fù)浣Y(jié)構(gòu)進(jìn)行熱分析。通過對優(yōu)化布局前后結(jié)點平均溫度的對比驗證該方法的優(yōu)越性。分析如圖1所示。圖1顯示了布局優(yōu)化前后各元件平均溫度的對比。經(jīng)計算比較得，優(yōu)化后平均溫度低于優(yōu)化前的平均溫度，整體性能提高14%。

圖1 布局優(yōu)化前后對比

4.2 布線實驗

布線結(jié)果從不斷增加布局元件個數(shù)的角度出發(fā)，突出了這種布線算法的優(yōu)越性，結(jié)果如圖2所示。實驗通過不斷增加PCB板元件的個數(shù)來驗證。圖2顯示了隨著元件的增多布線路徑長度個數(shù)及通孔個數(shù)的優(yōu)化率在不斷提高，元件個數(shù)相當(dāng)大時通孔個數(shù)的優(yōu)化率明顯高于路徑長度的優(yōu)化率；當(dāng)元件個數(shù)增加到一定程度基本趨于一個穩(wěn)定狀態(tài)下的優(yōu)化。

圖2 布線優(yōu)化過程

4.3 干擾性測試

本次實驗從布局布線2個方面表現(xiàn)PCB干擾性的大小，圖3表示每1 s后抽取一次優(yōu)化布局后PCB板的總體平均溫度值，如圖描繪出每1 s后對PCB整體溫度的觀測，隨著對布局的優(yōu)化，其總體平均溫度呈現(xiàn)下降趨勢，起初每隔1 s的下降趨勢很平緩，隨著時間的增長其總體平均溫度下降很明顯，總體下降幅度約20%。

圖3 布局優(yōu)化后總平均溫度變化

布線優(yōu)化后的平均噪聲值如圖4所示。

圖4 布線優(yōu)化后的平均噪聲值

圖4表示每1 s后優(yōu)化布線產(chǎn)生噪聲值的優(yōu)化情況，整體走勢：在10 s之前平均噪聲值下降幅度大約0.008 dB/s，10 s之后下降幅度比較平緩，當(dāng)達(dá)到平衡狀態(tài)時其平均溫度也隨著達(dá)到平衡，整體的溫度平均下降14%左右，運用式(1)可以計算出在20 s左右干擾值趨于較小，直到布線達(dá)到一個平衡狀態(tài)時設(shè)計達(dá)到最優(yōu)。

在基于20臺刀片服務(wù)器模擬20個元器件情況下，將本文算法與當(dāng)前經(jīng)典布局布線算法進(jìn)行比較，如表1所示。

表1 算法性能比較

5 結(jié)束語

本文提出了一種基于布局布線協(xié)同的PCB設(shè)計算法，主要是圍繞基于元胞自動機的思想對PCB上的元件設(shè)計布局，協(xié)同運用優(yōu)化蟻群算法設(shè)計布線，平衡布局的散熱性能和布線的抗噪聲干擾，使設(shè)計的PCB具有較強的抗干擾性。實驗結(jié)果證明了算法的有效性，今后將進(jìn)一步對PCB設(shè)計中影響抗干擾性能的電磁干擾源進(jìn)行研究，以適應(yīng)電子行業(yè)與時俱進(jìn)的發(fā)展要求。

[1] 王書江, 葛海通, 嚴(yán)曉浪. 超大規(guī)模集成電路無網(wǎng)格布線算法研究[J]. 電路與系統(tǒng)學(xué)報, 2002, 7(4): 13-16.

[2] 謝滿德. 一種自適應(yīng)多層無網(wǎng)格布線算法[J]. 計算機工程, 2006, 32(14): 11-13.

[3] 黃訓(xùn)誠, 莊奕琪, 耿阿囡. 基于粒子群優(yōu)化算法的集成電路無網(wǎng)格布線[J]. 西安電子科技大學(xué)學(xué)報, 2007, 34(1): 34-37.

[4] 馬 力, 張忠濤, 張 妍. 高速電路PCB布線中參考層的設(shè)計與實現(xiàn)[J]. 計算機工程, 2008, 34(增刊): 88-92.

[5] 鄒志強. 嵌入式雙Pentium Ⅲ單板的高速PCB設(shè)計[J].計算機工程, 2003, 29(9): 163-165.

[6] 劉孝保, 杜平安. 面向元器件的PCB板布局優(yōu)化方法[J].電子科學(xué)技術(shù)大學(xué)學(xué)報, 2011, 40(4): 630-633.

[7] 王玉蘭, 云和明. 基于退火算法的PCB電子元件散熱布局優(yōu)化分析[J]. 信息技術(shù)與信息化, 2007, (1): 75-77.

[8] 魯宇明, 黎 明, 李 凌. 一種具有演化規(guī)則的元胞遺傳算法[J]. 電子學(xué)報, 2010, 38(7): 1603-1609.

[9] 暢藝峰, 楊銀堂. 多芯片組件布局布線設(shè)計的新途徑[J].西北大學(xué)學(xué)報: 自然科學(xué)版, 2006, 36(4): 547-550.

[10] Hanreich G, Nicolics J, M usiejovsky L. High Resolution Thermal Simulation of Electronic Compone nts[J]. Microelectronics Reliability, 2000, 40(12): 2069-2076.

[11] Zhao C Y, Kim T. Modeling on Thermal Trans- port in Cellular Metal Foams[C]//Proc. of Joint Thermo Physics and Heat Transfer Conference. St. Louis, USA: [s. n.], 2002.

[12] Wen T, Tian J, Lu T J, et a l. Forced Convection in Metallic Honeycomb S tructures[J]. Interna tional Journal of Heat and Mass Transfer, 2006, 49(19/20): 3313-3324.

編輯 顧逸斐

A PCB Design Algorithm Based on Collaboration Between Layout and Wiring

YAN Li-ping1, CHEN Qing-kui1,2

(1. School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China; 2. Shanghai Key Lab of Modern Optical System, Shanghai 200093, China)

It is the problem that weak immunity of Printed Circuit Board(PCB) resulted by the low thermal dissipation performance with unreasonable layout and the low noise immunity performance w ithout optimization wiring. To attack the problem, an al gorithm based on collaboration between the layo ut and the wiring is proposed. The algorithm adopts the rule based on Cellular Automata(CA) transfers the position of components according to temperature limitat ion for layout so that the h eat dissipation performance of layout can be more reasonable and the method is proposed based on Ant Colony Algorithm(ACA) looks for the shorte st routing length and the minimum number of holes and evaluates PCB noise immunity performance for wiring. Experimental result shows that performance of heat dissipation is increased by 14% on the aspect of heat dissipation for the layout, the average routing length and number of holes are decreased obviously on the aspect of noise immunity for the wiring and the PCB total average temperature is decreased by 14%.

heat dissipation; noise immunity; Ant Colony Algorithm(ACA); cellular automata; interference immunity; Printed Circuit Board(PCB) design

10.3969/j.issn.1000-3428.2014.05.064

國家自然科學(xué)基金資助項目(60970012)；教育部博士學(xué)科點專項科研博導(dǎo)基金資助項目(20113120110008)；上海教委創(chuàng)新基金資助重點項目(13ZZ112)；上海信息技術(shù)領(lǐng)域重點科技攻關(guān)計劃基金資助項目(09511501000, 09220502800)；上海市教育科學(xué)研究基金資助項目(B11042)；上海市一流學(xué)科建設(shè)基金資助項目(XTKX2012)。

閆利平(1990－)，女，碩士研究生，主研方向：電路設(shè)計；陳慶奎，教授、博士、博士生導(dǎo)師。

2013-03-18

2013-05-17E-mail：yanliping1990@sohu.com

1000-3428(2014)05-0309-04

A

TP314