一位全加器優(yōu)化設(shè)計算法的研究

羅文靜 范進高 會 丹 王娜娜 顏雪松

（中國地質(zhì)大學(xué)（武漢）計算機學(xué)院，湖北武漢 430074）

電路優(yōu)化技術(shù)是電路設(shè)計領(lǐng)域不可忽略的一個部分，電路優(yōu)化能提高效率、降低能耗從而節(jié)約現(xiàn)實成本。近年來也出現(xiàn)越來越多的電路優(yōu)化方法被運用到電路硬件設(shè)計領(lǐng)域。盡管如此，傳統(tǒng)電路優(yōu)化技術(shù)仍然存在幾個方面的挑戰(zhàn)：（1）如何讓電路優(yōu)化自動化；（2）設(shè)計平臺的可編程性（3）如何能在較短時間內(nèi)達到理想優(yōu)化結(jié)果；（4）如何減少電路器件門數(shù)。

一位加法器電路優(yōu)化設(shè)計屬于電路硬件設(shè)計范疇，用傳統(tǒng)電路設(shè)計方法明顯達不到理想的結(jié)果。為了優(yōu)化一位加法器設(shè)計，引入演化硬件技術(shù)（Evolvable Hardware，EHW ）。演化硬件技術(shù)是一種能夠被用來替代傳統(tǒng)電路設(shè)計的方法，用自可編程門陣列（Field Programmable Gate Arrays，F(xiàn)PGA）作為硬件演化平臺，能通過演化算法自動生成數(shù)字電路。

對于一位加法器硬件電路的算法設(shè)計與優(yōu)化，我們采用改進遺傳算法（Modified Genetic Alogrothm，MGA）來設(shè)計組合數(shù)字電路。簡單的遺傳算法效率較差，我們通過引入跨世代精英機制和其他策略對簡單遺傳算法進行改進，設(shè)計了一種改進遺傳算法以提高演化效率。本文采用的編碼方式為矩陣單元三元組整數(shù)編碼，采用的個體評估策略為貪婪策略；設(shè)計各種不同的選擇、交叉、變異策略等其他算子，運用到各種算法中去。本文采用的算法策略以及優(yōu)化方法對于設(shè)計數(shù)字濾波器、乘法器、多態(tài)數(shù)字電路等同樣適用。

1 算法編碼

1.1 矩陣單元三元組整數(shù)編碼

采用演化硬件技術(shù)自動設(shè)計數(shù)字電路，先要將電路表示成便于演化算法設(shè)計的編碼方式。該編碼方式依據(jù)硬件平臺Virtex－II系列FPGA的邏輯單元結(jié)構(gòu)（見圖1）構(gòu)建的。

圖1 可編程邏輯門陣列結(jié)構(gòu)

經(jīng)過下面的建模過程，體現(xiàn)基于FPGA電路設(shè)計自動化問題的可演化性，只與邏輯單元功能和其互聯(lián)關(guān)系相關(guān)。將已知的電路輸入作為邏輯單元矩陣的輸入資源，對于一個N輸入的邏輯電路，就有N個輸入資源，每一個單元都有自己的輸出。這樣矩陣單元可以成為其他單元的輸入，或者整個電路的輸出。對所有資源進行編號，以便表示整個電路單元的互連關(guān)系，作如下三元組模式的編碼：（Ai，Bi，Ci）。Ai表示將資源編號 Ai的輸出連接到邏輯單元的的第一個輸入，Bi表示將資源編號Bi的輸出連接到邏輯單元的第二個輸入，Ci用于標(biāo)識邏輯單元的功能，Ci具體數(shù)字與其對應(yīng)邏輯功能關(guān)系，見表1。

表1 染色體中的負數(shù)對應(yīng)的邏輯門功能

引入連接度的方法來動態(tài)控制所有邏輯單元的輸入，實現(xiàn)動態(tài)的控制搜索空間。連接度是指：在矩陣單元Mmn（m表示矩陣的行數(shù)，n表示矩陣的列數(shù)）中，若某個單元Cij（表示該單元在矩陣的第i行、第j列）的輸入信號能與前k列單元的輸出信號相連，即在第j－k列——第j－1列位置上所有單元的輸出信號都能為該單元的輸入信號，則稱該單元Cij的連接度D為K.假設(shè)n為矩陣單元的總列數(shù)，nr和nc分別是矩陣的單元行數(shù)和列數(shù)。ni代表目標(biāo)電路系統(tǒng)輸入數(shù)目，若第c列某單元的連接度為k；其中c∈［1，n］，定義 V（c）為整數(shù)v的集合，所以：

后面的列其連接度呈遞增趨勢，這樣通過控制k的值能夠縮小電路的搜索空間，提高演化效率。

擴展約束編碼規(guī)則即可避免染色體在個體初始化或變異時單元間連接形成回路，同時可動態(tài)調(diào)整單元的連接度，使得算法在運行時能動態(tài)調(diào)節(jié)單元的搜索空間，從而在某種程度上提高演化效率。

2 選擇策略

2.1 選擇輸出端邏輯單元

采用貪婪策略來確定電路的輸出單元，即根據(jù)給定電路功能的真值表，對于每一種電路輸入組合，將各矩陣單元輸出值與真值表各輸出值進行比較，若匹配則加1，這樣可構(gòu)造出各矩陣單元對應(yīng)各輸出端的匹配度；再針對每個輸出，我們分別選取匹配度最大的單元，將該單元作為該電路對應(yīng)的輸出端。與盲目隨機選取輸出單元相比，貪婪策略能防止同一染色體因輸出單元選取的不同，使得它們的適應(yīng)度評估值存在很大差異的缺陷，同時能更好的將有效個體電路保留下來，從而提高了演化效率。

2.2 確定每個邏輯單元的變異概率

首先將每個邏輯單元賦一個初始值P＿MUTATION。對于輸出端的變異概率，若某個輸出端已經(jīng)正確輸出，則變異概率為0，否則輸出端概率為0.5＊P＿MUTATION。若相關(guān)聯(lián)邏輯單元的變異概率比該輸出單元小，則不變；否則，將輸出單元的變異概率賦給該邏輯單元。

3 遺傳操作

3.1 交叉操作

采用子電路交叉法。子電路交叉法是基于多目標(biāo)技術(shù)，若將數(shù)字電路的每個輸出端信號單獨作為一個目標(biāo)，一個多輸出數(shù)字電路的設(shè)計即為一個帶約束的多個目標(biāo)優(yōu)化問題。由于一個多輸出組合邏輯電路可分解為多個輸出端信號子電路，因此，一個多輸出組合邏輯電路可由所有單輸出端信號子電路構(gòu)成。該文基于多目標(biāo)與局部優(yōu)化技術(shù)，提出子電路雜交策略。新個體電路的每個輸出端子電路產(chǎn)生規(guī)則為：根據(jù)兩父體電路中同一輸出端信號的功能評價值，選取較優(yōu)的子電路作為新個體電路對應(yīng)輸出端信號子電路，然后將新產(chǎn)生的所有輸出端信號子電路組合形成新個體電路。若某邏輯單元產(chǎn)生沖突，則直接用后續(xù)輸出單元的相關(guān)邏輯單元賦值。

3.2 變異操作

采用自適應(yīng)變異。在三元組的三個位置中隨機產(chǎn)生一個變異位置和該位置的變異概率，若該變異概率小于該邏輯單元的初始變異概率，則變異。變異的原則是：隨機產(chǎn)生該位置滿足條件的值，直到不與原來的值相等。

3.3 個體保留策略

采用跨世代精英機制。上一代種群與通過交叉變異操作產(chǎn)生的新種群混合起來，從中按一定概率選擇較優(yōu)的個體。具體操作過程如下：

第一步：將規(guī)模為N的當(dāng)前種群P1通過交叉變異操作產(chǎn)生下一代子種群P2。

第二步：將當(dāng)前種群P1和下一代子種群P2混合形成臨時種群。

第三步：對臨時種群按適應(yīng)度值降序排序后，保留最優(yōu)的N個個體形成新一代種群P1。

跨世代精英機制在健壯性和遺傳多樣性保持以及排序方法上都有著一定的特質(zhì)，即使當(dāng)交叉變異操作產(chǎn)生較劣個體偏多時，由于原種群大多數(shù)個體殘留，不會引起個體的評價值降低；由于大種群操作，可以更好地保持種群演化過程中的遺傳多樣性，最后它很好的克服了比列適應(yīng)度計算的尺度問題。

4 實驗與分析

采用改進的遺傳算法進行一位加法器的優(yōu)化設(shè)計，其實驗運行參數(shù)見表2（使用“與”門、“或”門和“非”門）。

表2 算法運行參數(shù)

在以上算法參數(shù)設(shè)置下，獨立運行算法5次，實驗結(jié)果統(tǒng)計如表3。

表3 5次實驗結(jié)果統(tǒng)計表

對表3實驗結(jié)果統(tǒng)計表進行分析，得出如表4實驗結(jié)果分析表。

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

實驗結(jié)果分析表明，進行5次實驗，設(shè)計最優(yōu)電路的邏輯門數(shù)為9，設(shè)計有效電路的頻率達到100%，設(shè)計電路的平均邏輯門數(shù)為5。實驗數(shù)據(jù)說明電路演化優(yōu)化設(shè)計能較好地用于一位加法器的演化優(yōu)化設(shè)計。

5 結(jié) 語

將演化算法引入到硬件設(shè)計技術(shù)中，已經(jīng)成為一門新興技術(shù)，引起許多學(xué)者的廣泛關(guān)注與深入研究。本文首先在人工設(shè)計電路的基礎(chǔ)上，引入基于硬件設(shè)計的演化算法。采用的是矩陣單元三元組整數(shù)編碼，編碼規(guī)則為擴展約束編碼規(guī)則，采用貪婪策略來確定電路的輸出單元，在產(chǎn)生新一代時，采用輪盤賭算法進行隨機選擇，交叉采用子電路交叉法，變異采用自適應(yīng)變異，最后的最優(yōu)個體保留機制采用跨世代精英機制。實驗結(jié)果表明，演化算法在電路優(yōu)化設(shè)計上有效實用，在采用適當(dāng)?shù)乃惴ǖ幕A(chǔ)上，能獲得比較優(yōu)化的電路，這些電路可作為基本模塊用于設(shè)計更復(fù)雜的硬件系統(tǒng)，這將會在大型硬件系統(tǒng)設(shè)計中占據(jù)重要的地位。

1 .F.Miller，P.Thomson，and T.Fogarty.Designing Electronic Circuits Using Evolutionary Algorithms.Arithmetic Circuits：A Case Study，chapter 6，in Genetic Algorithms and Evolution Stategies in Engineering and Computer Science：Recent Advancements and Industrial Applications.Wiley Press，1997（November）：36－60.

2 Thompson A.Hardware Evolution：Automatic design of electronic circuits in reconfigurable hardware by artificial evolution.Doctoral thesis，University of Sussex，UK，1996.

3 Coello C Carlos A.An Empirical Study of Evolutionary Techniques for Multiobjective Optimization in Engineering Design，PhD thesis，Tulane University，New orleans，1996.

4 Kalganova T.Evolvable Hardware Design for Combinational Logic Circuits.PhD thesis，Napier University，Edinburgh，UK，2000.

5 Zebulum R S.Synthesis of Electronic Circuits Through Artificial Evolutionary Systems.PhD Thesis，Catholic University of Rio，Portuguese，1998.