并行遺傳算法在器件模型參數提取中的應用

宋文斌

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

關鍵詞：MOS器件；模型參數；參數提取；器件模型

1 引言

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

2 并行遺傳算法

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

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

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

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

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

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

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

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

3 基于MPI的主從式遺傳算法的的實現

3.1 總體構想

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

3.2 并行中的消息傳遞機制

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

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

3.3 共享內存多處理器主從式并行環境搭建

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

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

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

為了在微機環境下使用MPI構成分布式內存并行環境，只要將PC機聯接局域網，然后在每臺PC機上安裝相應操作系統，并安裝MPI軟件包即可。分布式內存即種群被一個處理器存儲。這個主處理器負責將個體發送給其它從處理器進行評估，并收集計算結果，進行遺傳操作來生成下一代。

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

4 實驗結果分析

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

5 結論

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

參考文獻

[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] 康立山，非數值并行算法(第一冊)-并行遺傳算法[M].科學出版社,2003.

[6] 萊維尼，先進計算機體系結構與并行處理[M].電子工業出版社,2005.