并行遺傳算法在器件模型參數(shù)提取中的應(yīng)用

宋文斌

摘要：器件的模型和模型參數(shù)提取是電子設(shè)計自動化（EDA）領(lǐng)域的關(guān)鍵工作。采用遺傳算法進行器件模型參數(shù)提取工作是近年來興起并被廣泛使用的一種參數(shù)提取方法。本文討論了并行遺傳算法的特點，針對遺傳算法自身的耗時問題，提出了基于MPI的主從式遺傳算法，并證實了并行計算在參數(shù)提取工作中的可行性。該方法簡單易用，顯著提升了MOS器件模型參數(shù)提取的速度。

關(guān)鍵詞：MOS器件；模型參數(shù)；參數(shù)提取；器件模型

1 引言

器件的模型和模型參數(shù)提取是電子設(shè)計自動化（EDA）領(lǐng)域的關(guān)鍵工作[1]。采用遺傳算法進行半導(dǎo)體器件模型參數(shù)提取是近年來興起并被廣泛使用的一種參數(shù)提取方法[2-3]。遺傳算法全局搜索能力強、不需進行繁瑣的求導(dǎo)運算，不依賴參數(shù)初始值等特點，理論上來說只要有足夠的迭代次數(shù)種能找到最優(yōu)解[4]。但是，由于遺傳算法是一種搜索類算法,較之傳統(tǒng)的基于梯度進行迭代計算的解析算法, 每進行一次迭代所需要的時間較長，計算量有了顯著增加, 而且對許多復(fù)雜問題而言，例如采用的全局優(yōu)化策略提取復(fù)雜模型的大量參數(shù)時，標準遺傳算法的求解效果往往不是解決這個問題的最有效的方法，必須對算法進行修改與優(yōu)化，這些因素?zé)o疑大大增加了遺傳算法的計算量，為此必須考慮算法的耗時問題。本文針對遺傳算法自身的耗時問題，討論了并行遺傳算法的特點，并以主從式遺傳算法為例，證實了并行計算在參數(shù)提取工作中的可行性。

2 并行遺傳算法

為了有效的解決遺傳算法（GA）在模型參數(shù)提取過程中的耗時問題, 提高GA的運行速度，采用并行遺傳算法（PGA）是提高搜索效率的方法之一。并行遺傳算法[5-6]主要有主從式并行遺傳算法、粗粒度并行遺傳算法和細粒度并行遺傳算法。

2.1 全局PGA模型－主從式模型（master-slave model）

如圖1所示，主從式模型分為一個主處理器(master)和若干個從處理器(slaves)。主處理器監(jiān)控整個染色體種群，并基于全局統(tǒng)計執(zhí)行選擇等全局操作；從處理器接收來自主處理器的個體進行適應(yīng)度評估等局部操作，再把計算結(jié)果傳給主處理器。

主從式模型的優(yōu)點是簡單，保留了串行GA 的搜索行為，對計算機體系結(jié)構(gòu)沒有嚴格要求，適合運行在共享存儲和分布式存儲的并行計算機上。如果適應(yīng)度估值操作比其他遺傳算子計算量大的多時，這是一種非常有效的并行化方法。

2.2 粗粒度PGA模型－分布式模型（distributed model）

該模型又稱分布式、MIMD、島嶼模式遺傳算法模型。在處理器個數(shù)較少的情況下，我們可以將群體分為若干個子群體，每個子群體包含一些個體，每個子群體分配一個處理器，讓它們相互獨立地并行執(zhí)行進化。為了防止子群體早熟，每經(jīng)過一定的間隔(即若干進化代)，各子群體間會交換部分個體以引入其他子群體的優(yōu)秀基因，豐富各子群體的多樣性。除了基本的遺傳算子外，粗粒度模型引入了“遷移”算子，負責(zé)管理區(qū)域之間的個體交換。如圖2所示，通常存在兩種遷移實現(xiàn):島嶼模型、踏腳石模型。

2.3 細粒度PGA模型－分散型 (fine-grained model)

細粒度模型又稱為鄰域模型(neighborhood model)或細胞模型(cellular model)模型。如果并行計算機系統(tǒng)的規(guī)模很大，理想情況下處理器多到可以與染色體一一對應(yīng)，則我們可以將每個個體分配一個處理器，讓它們相互獨立地并行執(zhí)行進化，這樣就能獲得并行遺傳算法的最大可能的并發(fā)性。如圖3所示，在細粒度模型中，通常處理器被連接成平面網(wǎng)格(grid)，每個處理器上僅分配一個個體，選擇和交叉只在網(wǎng)格中相鄰個體之間進行，所以網(wǎng)格上的鄰域關(guān)系就限定了個體空間上的關(guān)系。由于對處理器數(shù)量的要求很高，所以細粒度模型的應(yīng)用范圍不廣。

3 基于MPI的主從式遺傳算法的的實現(xiàn)

3.1 總體構(gòu)想

我們采用的主從式并行模型分為一個主處理器(master)和若干個從處理器(slaves)。主處理器監(jiān)控整個染色體種群，并基于全局統(tǒng)計執(zhí)行選擇等全局操作；從處理器接收來自主處理器的個體進行適應(yīng)度評估等局部操作，再把計算結(jié)果傳給主處理器，其個體的分配過程是這樣的：假設(shè)種群規(guī)模為N, 優(yōu)化模型參數(shù)變量個數(shù)為M。適應(yīng)度評估時，程序傳給評價函數(shù)N個長度為M的向量。并行的任務(wù)是master處理器將這個N個長度為M的向量平均分配到各slaves處理器做適應(yīng)度計算，計算結(jié)束后，評價函數(shù)返回N個適應(yīng)度給master處理器。計算各處理器分得的染色體個數(shù)的方法是，首先計算出每個處理器至少分配到的染色體個數(shù)為AveNum=N/Size，如果處理器個數(shù)不能整除行數(shù)，這樣將有部分處理器分得到（AveNum+1）個染色體，規(guī)定多余的染色體分配到編號小的處理器上。

3.2 并行中的消息傳遞機制

另外，需要注意的是，僅僅依靠例如C，C++，java等編程語言所編寫的程序是無法實現(xiàn)上面敘述的染色體在各處理器之間的傳遞任務(wù)。因為，在并行計算環(huán)境中，每個進程均有自己獨立的地址空間，一個進程不能直接訪問其它進程中的數(shù)據(jù)，因而，在進行并行計算的任務(wù)之間進行的數(shù)據(jù)傳輸必須通過消息傳遞機制。消息傳遞機制，是指用戶必須顯式地通過發(fā)送和接收消息來實現(xiàn)處理器之間的數(shù)據(jù)交換。

本文采用的是MPI(Massage Passage Interface)消息傳遞接口。MPI是一個很好的數(shù)據(jù)傳遞軟件平臺，可以通過調(diào)用MPI庫函數(shù)來進行進程調(diào)度以及任務(wù)間的通信。它實際上是一個消息傳遞函數(shù)庫的標準說明，吸取了眾多消息傳遞系統(tǒng)的優(yōu)點，是目前國際上最流行的并行編程環(huán)境之一，其特點是通用性強(只要求網(wǎng)絡(luò)支持TCP/IP網(wǎng)絡(luò)協(xié)議)、系統(tǒng)規(guī)模小、技術(shù)比較成熟。本文通過調(diào)用MPI的庫程序來達到程序員所要達到的并行目的，使異構(gòu)的計算機群體作為一個緊湊、靈活、經(jīng)濟的計算機資源來使用的并行環(huán)境。

3.3 共享內(nèi)存多處理器主從式并行環(huán)境搭建

全局并行化模型并不限定計算機體系結(jié)構(gòu)，它可以在共享內(nèi)存和分布式內(nèi)存計算機中高效實現(xiàn)。現(xiàn)在簡單介紹一下兩種并行編程的方法：分布式內(nèi)存方法和共享式內(nèi)存方法。

對于分布式內(nèi)存的并行計算機，各個處理器擁有自己獨立的局部存儲器，不存在公用的存儲單元，顯然，這種方法的問題就產(chǎn)生于分布式內(nèi)存的組織。由于每個節(jié)點都只能訪問自己的內(nèi)存，如果其他節(jié)點需要訪問這些內(nèi)存中的數(shù)據(jù)，就必須對這些數(shù)據(jù)結(jié)構(gòu)進行復(fù)制并通過網(wǎng)絡(luò)進行傳送，這會導(dǎo)致大量的網(wǎng)絡(luò)負載。他的優(yōu)點是擁有很好的擴展性，有利于快速構(gòu)造超大型的計算系統(tǒng)。

在共享內(nèi)存多處理器計算機中構(gòu)成并行環(huán)境，在共享式內(nèi)存方法中，內(nèi)存對于所有的處理器來說都是通用的。這種方法并沒有分布式內(nèi)存方法中所提到的那些問題。而且對于這種系統(tǒng)進行編程要簡單很多，因為所有的數(shù)據(jù)對于所有的處理器來說都是可以使用的，這與串行程序并沒有太多區(qū)別。這些系統(tǒng)的一個大問題是擴展性差，不容易添加其他處理器。

為了在微機環(huán)境下使用MPI構(gòu)成分布式內(nèi)存并行環(huán)境，只要將PC機聯(lián)接局域網(wǎng)，然后在每臺PC機上安裝相應(yīng)操作系統(tǒng)，并安裝MPI軟件包即可。分布式內(nèi)存即種群被一個處理器存儲。這個主處理器負責(zé)將個體發(fā)送給其它從處理器進行評估，并收集計算結(jié)果，進行遺傳操作來生成下一代。

對于本文所采用的在共享內(nèi)存多處理器計算機中構(gòu)成主從式并行環(huán)境就更為簡單，只要在PC機上安裝操作系統(tǒng)（本文安裝linux操作系統(tǒng)）和MPI軟件包就可以實現(xiàn)并行環(huán)境了。在共享內(nèi)存多處理器計算機中，種群可以保存在共享內(nèi)存中，每個處理器可以讀取被分配到的個體信息并將適應(yīng)度寫回，不會有任何沖突。

4 實驗結(jié)果分析

將以上方法實現(xiàn)的基于MPI的主從式遺傳算法應(yīng)用于1.2um SOI MOS器件的閾值電壓模型參數(shù)提取工作中。如圖4所示，實驗結(jié)果表明曲線擬合的效果很好，轉(zhuǎn)移特性曲線最大誤差都低于5%。采用并行計算后，參數(shù)提取的速度提高了接近2.5倍。

5 結(jié)論

從實際的測試效果來看，以上方法實現(xiàn)的程序的簡潔有效，智能化程度很高，且具有較高的精確度。因此，本文提出的基于MPI的主從式遺傳算法可以解決遺傳算法在器件參數(shù)提取過程中的耗時問題。該方法簡單易用，適合推廣使用。

參考文獻

[1] J.Liou A,Analysis and Design of MOSFETS: Modeling,Simulation,and Parameter Extraction[M].KLUWER ACADEMIC PUBLISHERS,1998.

[2] Kondo M,Onodera H,Tamaru K.Model adaptable MOSFET parameter extraction method using an intermediate model[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1998,17(5):400-405.

[3] Yang P, Chatterjee P K, An optimal parameter extraction program for MOSFET models[J].IEEE Transaction on Electron Devices,1983,30(9):1214-1219.

[4] Li Yiming. An automatic parameter extraction technique for advanced CMOS device modeling using genetic algorithm.Microelectronic Engineering,2006,41(4): 1309-1321.

[5] 康立山，非數(shù)值并行算法(第一冊)-并行遺傳算法[M].科學(xué)出版社,2003.

[6] 萊維尼，先進計算機體系結(jié)構(gòu)與并行處理[M].電子工業(yè)出版社,2005.