宋文斌

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

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

1 引言

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

2 并行遺傳算法

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

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

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

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

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

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

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

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

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

3.1 總體構(gòu)想

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

3.2 并行中的消息傳遞機(jī)制

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

參考文獻(xiàn)

[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] 萊維尼，先進(jìn)計(jì)算機(jī)體系結(jié)構(gòu)與并行處理[M].電子工業(yè)出版社,2005.