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

閆利平，陳慶奎,2

(1. 上海理工大學(xué)光電信息與計(jì)算機(jī)學(xué)院，上海 200093；2. 上海現(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，上海 20009 3)

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

閆利平1，陳慶奎1,2

(1. 上海理工大學(xué)光電信息與計(jì)算機(jī)學(xué)院，上海 200093；2. 上海現(xiàn)代光學(xué)系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，上海 20009 3)

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

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

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

1 概述

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

2 布局布線問題描述

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

2.1 P CB干擾評估描述

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

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

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

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

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

2.2 布局定義描述

對布局而言，考慮其散熱性問題，對單個(gè)元件而言，其溫度受自身和周圍鄰居元件熱輻射[11-12]的影響，而整個(gè)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個(gè)目標(biāo)進(jìn)行優(yōu)化，因此布線屬于多目標(biāo)優(yōu)化問題，則：

其中，x1、x2分別表示元件節(jié)點(diǎn)的坐標(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è)計(jì)描述

3.1 總體描述

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

整體算法描述：

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

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

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

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

Step5調(diào)用函數(shù)干擾值評估函數(shù)式(1)，將Temperature值和Noise值分別傳到T、L中，衡量整體設(shè)計(jì)的干擾值并賦值給Ps；轉(zhuǎn)入Step3；可獲得下一個(gè)狀態(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 布局實(shí)現(xiàn)算法

3.2.1 元胞自動(dòng)機(jī)演化規(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)移時(shí)置狀態(tài)標(biāo)志變量Flag為1，其他為0，M表示元件鄰居集合M={M1,M2,…,Mi}，i表示鄰居節(jié)點(diǎn)個(gè)數(shù)，f是狀態(tài)的演化規(guī)則，其定義如下：由于當(dāng)前布局每個(gè)元件受鄰居元件熱輻射及其自身溫度影響，其目標(biāo)函數(shù)：

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

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

(2)在斜對角4個(gè)方向情況下，對于左上移(Sla)狀態(tài)轉(zhuǎn)移的定義：對中心元件相鄰位置正右、下、右下方3個(gè)元件對其熱輻射的溫度之和sT判斷，運(yùn)用和(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，表示該元件不需要移動(dòng)。

3.2.2 布局算法描述

布局算法步驟如下：

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

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

Step3設(shè)Ni( xi, yi)為第i個(gè)元件的坐標(biāo)，根據(jù)鄰居集合M計(jì)算中心元件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è)時(shí)刻變量time置0；迭代步數(shù)nc置0，對各邊D(i,j)：置τij為常數(shù)c(c趨于無窮小)；置Δτij為0；Lbest置空(儲存當(dāng)前最好的路徑隊(duì)列)；hole置0存儲通孔個(gè)數(shù)；置Length常數(shù)a(a是較大的正數(shù)，Length用來儲存當(dāng)前最短的路徑長度)。

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

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

if 選擇通孔，則hole++；than else避線繞點(diǎn)；

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

Step3for k=1 to m

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 布局散熱測試

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

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

4.2 布線實(shí)驗(yàn)

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

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

4.3 干擾性測試

本次實(shí)驗(yàn)從布局布線2個(gè)方面表現(xiàn)PCB干擾性的大小，圖3表示每1 s后抽取一次優(yōu)化布局后PCB板的總體平均溫度值，如圖描繪出每1 s后對PCB整體溫度的觀測，隨著對布局的優(yōu)化，其總體平均溫度呈現(xiàn)下降趨勢，起初每隔1 s的下降趨勢很平緩，隨著時(shí)間的增長其總體平均溫度下降很明顯，總體下降幅度約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)時(shí)其平均溫度也隨著達(dá)到平衡，整體的溫度平均下降14%左右，運(yùn)用式(1)可以計(jì)算出在20 s左右干擾值趨于較小，直到布線達(dá)到一個(gè)平衡狀態(tài)時(shí)設(shè)計(jì)達(dá)到最優(yōu)。

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

表1 算法性能比較

5 結(jié)束語

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

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

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

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

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

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

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

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

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

[9] 暢藝峰, 楊銀堂. 多芯片組件布局布線設(shè)計(jì)的新途徑[J].西北大學(xué)學(xué)報(bào): 自然科學(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é)基金資助項(xiàng)目(60970012)；教育部博士學(xué)科點(diǎn)專項(xiàng)科研博導(dǎo)基金資助項(xiàng)目(20113120110008)；上海教委創(chuàng)新基金資助重點(diǎn)項(xiàng)目(13ZZ112)；上海信息技術(shù)領(lǐng)域重點(diǎn)科技攻關(guān)計(jì)劃基金資助項(xiàng)目(09511501000, 09220502800)；上海市教育科學(xué)研究基金資助項(xiàng)目(B11042)；上海市一流學(xué)科建設(shè)基金資助項(xiàng)目(XTKX2012)。

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

2013-03-18

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

1000-3428(2014)05-0309-04

A

TP314