軟硬件協(xié)同的遺傳算法設(shè)計與實現(xiàn)

聶鑫，羅劍

（1.武漢工程大學(xué)計算機科學(xué)與工程學(xué)院，武漢430205；2.武漢晴川學(xué)院計算機學(xué)院，武漢430205）

0 引言

遺傳算法[1]是一種從生物界繁衍進化中學(xué)習(xí)得到的一種隨機搜索算法。這種算法具有很好的魯棒性，具有天然的內(nèi)在并行性，并且算法無需豐富的先驗知識。目前絕大多數(shù)遺傳算法均使用純軟件實現(xiàn)，這類軟件方式在求解實際問題時由于效率較低，運行時間較長，無法應(yīng)用于實時性要求較高的場合。考慮到遺傳算法中編碼基本采用二進制編碼，而二進制編碼在硬件系統(tǒng)中具有操作快捷，實現(xiàn)簡單的特點，不少學(xué)者使用純硬件實現(xiàn)了遺傳算法[2]。使用硬件方式[3]實現(xiàn)的遺傳算法已經(jīng)證明了具有更高的運算效率與速度。但是純硬件的設(shè)計一旦實現(xiàn)，硬件結(jié)構(gòu)就不能改變，所以也就只能對一個問題進行求解，缺乏了軟件所具有的通用性。

軟硬件協(xié)同設(shè)計（Hardware/Software Co-Designing）的思想是在硬件和軟件設(shè)計過程中盡最大限度的利用其協(xié)同作用來滿足系統(tǒng)的要求。自從軟硬件協(xié)同思想提出以后，一直備受國內(nèi)外研究者的關(guān)注，關(guān)于軟硬件協(xié)同設(shè)計領(lǐng)域的研究也十分活躍。到目前為止，國內(nèi)外學(xué)者已經(jīng)在此方面做過很多研究[4-6]，例如在遙感影像的實時效應(yīng)、音頻編碼算法、Lattice譯碼算法、數(shù)字電路仿真、系統(tǒng)的模擬、仿真和調(diào)試等一些方面都使用過軟硬件協(xié)同設(shè)計方法，并且獲得比使用傳統(tǒng)的設(shè)計方法更好的效果。因此利用軟硬件協(xié)同設(shè)計方法不僅可以提高求解問題的效率，同時可以擴寬其應(yīng)用領(lǐng)域，進一步推動軟硬件協(xié)同設(shè)計的發(fā)展等。FPGA的快速發(fā)展，也為軟硬件協(xié)同工作搭建了平臺，使得軟硬件協(xié)同處理成為了可能。

1 軟硬件協(xié)同的系統(tǒng)設(shè)計

1.1 硬件劃分

綜合軟硬件各自的優(yōu)點，采用軟硬件協(xié)同的工作方式實現(xiàn)的系統(tǒng)[7-8]，將系統(tǒng)中一些底層簡單而重復(fù)，特別是能夠并行化的工作交由硬件完成，將具有通用性、串行的工作交由軟件完成，不僅可以是系統(tǒng)的效率得提升，縮短了系統(tǒng)的開發(fā)周期，并且使得系統(tǒng)具有可重用性。在軟硬件協(xié)同中，如何劃分軟硬件具體工作是一件重要的事。因為這涉及到設(shè)計的運行效率以及具體實現(xiàn)的功能。我們對遺傳算法軟硬件劃分確定，硬件部分為總控模塊、選擇模塊、編譯模塊、雜交模塊。軟件部分為隨機數(shù)模塊、適應(yīng)值評價模塊。整個系統(tǒng)的設(shè)計圖為圖1所示。

圖1 系統(tǒng)設(shè)計圖

1.2 交互協(xié)議

由于在設(shè)計平臺中，CPU（PowerPC）時鐘頻率（300MHz）與FPGA提供的時鐘頻率（100MHz）不一致，并且在CPU上運行的軟件程序完成所需要的時鐘周期數(shù)是不確定性的。由于在本設(shè)計中存在許多軟件層面與硬件層面的信息交互，為了保證信息交互的同步性，可靠性，必須設(shè)計一個通信協(xié)議來確保數(shù)據(jù)的正確性。

圖2描述的為硬件端向軟件端請求數(shù)據(jù)的操作。整個操作的流程如下，首先由硬件發(fā)出請求（request）信號，該信號為高信號。在軟件端收到這個請求信號之后，開始進行正常的工作。此時硬件端為阻塞狀態(tài)。當軟件端處理完成之后，給硬件端發(fā)送完成信號（done），該信號電平同樣為高。此時軟件端進入阻塞狀態(tài)。至此完成一次握手，這該次握手操作中確保了軟件能正確地響應(yīng)硬件的請求，并且能正確地通知硬件何時完成操作。在硬件端收到電平為高的done信號之后，硬件解除阻塞并且獲取從軟件發(fā)過來的數(shù)據(jù)，之后再發(fā)送低電平的request信號并且進入阻塞狀態(tài)。此時完成了該協(xié)議的第二次握手，這次握手確保了硬件能夠正確地獲取所需信息并且進行標記信號的重置。在軟件獲得低電平的request之后，發(fā)送低電平的done信號并且解除阻塞。此時軟硬件的工作基本完成，為了防止重復(fù)響應(yīng)以及再次爭取的響應(yīng)，必須將交互信號進行重置。重置這些信號就需要該協(xié)議的第三次握手來確保雙方同時重置。硬件端收到低電平的done信號之后，解除阻塞。至此，一次軟硬件的信息交互結(jié)束。

圖2 通信協(xié)議

在本設(shè)計中，在雜交模塊，變異模塊，初始化模塊以及總控模塊中都是用了該協(xié)議來確保軟硬件雙方信息交互的正確性。

2 軟硬件協(xié)同的平臺實現(xiàn)

2.1 硬件模塊

如圖3所示，本模塊中共有6個狀態(tài)：

圖3 系統(tǒng)運行狀態(tài)機

●IDLE：空閑狀態(tài)，系統(tǒng)啟動以及復(fù)位后則進入該狀態(tài)。空閑狀態(tài)由硬件層面的總控模塊進行控制處理。模塊對系統(tǒng)的所有控制信號進行復(fù)位操作。系統(tǒng)在FPGA時鐘上升沿時檢查是否有外部（如開關(guān)、按鈕等）電平為高的運行信號（START）。在系統(tǒng)獲得高電平啟動信號之后開始進行狀態(tài)的轉(zhuǎn)換（以下模塊轉(zhuǎn)換中如無特殊說明，均是高電平有效），否則一直在IDLE狀態(tài)循環(huán)等待處于空閑。系統(tǒng)開始運行之后即轉(zhuǎn)入初始化狀態(tài)（INIT）。

●INIT：初始化狀態(tài)。在初始化狀態(tài)中完成系統(tǒng)中的初始化操作。具體操作為總控模塊發(fā)送啟動信號通知初始化模塊開始工作。之后在該狀態(tài)等待初始化操作的完成。在收到初始化模塊的完成信號之后，進入CROSS狀態(tài)。

●CROSS：雜交狀態(tài)。在雜交狀態(tài)中完成系統(tǒng)中的雜交操作。具體操作為總控模塊發(fā)送啟動信號通知雜交選擇模塊開始工作。之后在該狀態(tài)等待雜交操作的完成。在收到雜交模塊的完成信號之后，進入MUT狀態(tài)。

●MUT：變異狀態(tài)。在變異狀態(tài)中完本系統(tǒng)中的變異操作。具體操作為總控模塊發(fā)送啟動信號通知變異選擇模塊開始工作。之后在該狀態(tài)等待變異操作完成。在收到變異模塊的完成信號之后，進入VALUE狀態(tài)。

●VALUE：評估狀態(tài)。在評估狀態(tài)中完成本系統(tǒng)中的評估和停機判斷工作。具體操作為總控模塊發(fā)送啟動信號通知評價模塊開發(fā)工作。之后在該狀態(tài)中等待評價操作完成。直到收到評價模塊的完成信號之后，模塊根據(jù)反饋信號的不同決定下一個狀態(tài)。當STOP信號為0時，系統(tǒng)轉(zhuǎn)入CROSS狀態(tài)進行下一代遺傳操作。當STOP信號為1時，系統(tǒng)轉(zhuǎn)入STOP狀態(tài)。

●STOP：停機狀態(tài)。在停機狀態(tài)中完成本系統(tǒng)停止過程中的相關(guān)操作。具體操作就是模塊將算法獲得的最優(yōu)個體及其適應(yīng)值進行輸出操作，即將個體、適應(yīng)值、運行代數(shù)、運行周期從模塊的輸出端口輸出，軟件層面獲取輸出數(shù)據(jù)之后將其反饋給用戶。最后再將整個設(shè)備狀態(tài)轉(zhuǎn)入IDLE狀態(tài)，并且重置片上內(nèi)存。

2.2 軟件模塊

（1）隨機數(shù)模塊

隨機數(shù)模塊由軟件端實現(xiàn)。該模塊提供了遺傳算法流程中初始化模塊中個體生成、雜交選擇模塊的個體選擇和雜交點選擇、變異選擇模塊的個體選擇和變異點選擇。該模塊采用Xilinx公司擴展的C語言實現(xiàn)。具體實現(xiàn)表現(xiàn)為一個函數(shù)。函數(shù)有一個控制參數(shù)。函數(shù)返回為所需求的隨機數(shù)值。軟硬件交互協(xié)議的部分由調(diào)用該函數(shù)的部分控制實現(xiàn)。函數(shù)的內(nèi)部具體實現(xiàn)為根據(jù)控制參數(shù)來判斷硬件所需的隨機數(shù)的范圍。函數(shù)實現(xiàn)為調(diào)用C語言中自帶的rand（）函數(shù)，通過取模操作來選擇隨機數(shù)范圍。雖然C語言rand函數(shù)實現(xiàn)同樣可以使用硬件實現(xiàn)，但是在軟件實現(xiàn)的rand函數(shù)的隨機數(shù)種子是根據(jù)系統(tǒng)時間獲得，而硬件實現(xiàn)的隨機數(shù)的種子在每次產(chǎn)生隨機數(shù)時是固定不變的。

（2）適應(yīng)值評價模塊

適應(yīng)值評價模塊由軟件端實現(xiàn)。該模塊的功能為完成遺傳算法整個流程中的適應(yīng)值評估工作，也就是所需要解決問題的具體描述。該模塊采用Xilinx公司擴展的C語言實現(xiàn)。具體實現(xiàn)表現(xiàn)為一個函數(shù)。函數(shù)的參數(shù)為控制參數(shù)以及需要進行適應(yīng)值評價的個體（具體表現(xiàn)為一個50維數(shù)組）。函數(shù)返回為該個體的適應(yīng)值。軟硬件交互協(xié)議的部分由調(diào)用該函數(shù)的部分控制實現(xiàn)。函數(shù)的內(nèi)部具體實現(xiàn)為針對所求問題對二進制編碼形式的個體進行相應(yīng)的計算。由于軟硬件交互時使用的是IP核內(nèi)置寄存器，寄存器大小為32位。每個個體使用兩個寄存器，第一個寄存器32位全部使用，第二個寄存器只使用前18位。所以從寄存器中獲得個體計算適應(yīng)值前，必須對寄存器中的數(shù)據(jù)進行處理。本設(shè)計中使用split函數(shù)進行該操作，輸入為兩個int類型，輸入為50維數(shù)組。函數(shù)通過移位和與操作完成。

3 數(shù)值計算應(yīng)用實例

在科學(xué)研究中，數(shù)值計算是一類經(jīng)常遇到的問題，通常這類問題的復(fù)雜度較高，使用普通的算法計算時間較長。使用遺傳算法解決數(shù)值問題可以起到較好的效果。但是軟件實現(xiàn)的遺傳算法執(zhí)行效率低下，所以可以使用軟硬件協(xié)同工作的方式在不改變算法通用性的基礎(chǔ)上加快算法的收斂速度。

二進制問題是一類可以有效驗證遺傳算法功能正確性的基本問題。設(shè)計中使用的問題為計算二進制串中“1”的個數(shù)。1的個數(shù)越多，效果最優(yōu)。由于初始化個體為隨機初始化。所以在初始化個體中0與1的比例接近1:1，必須通過不斷的雜交和變異才可以獲得最優(yōu)解。因為個體串長為50，所以最優(yōu)解為50個1。使用軟硬件協(xié)同的遺傳算法解決該問題只需要改寫軟件端的適應(yīng)值函數(shù)。無需對硬件進行修改。

二進制問題運行效果見圖4所示。

圖4 二進制問題運行效果圖

從圖4中我們可以看出算法可以正確找到最優(yōu)解，運行的代數(shù)為1272，去除用于判斷終止條件的500代，算法共運行700多代。整個算法運行時間為4.2秒。

因為遺傳算法是一個隨機搜索算法，算法的性能受初始化種群的好壞以及雜交變異的隨機性影響較大。而以上實驗截圖均是試驗中隨機獲取的數(shù)據(jù)，并不能代表設(shè)計的性能以及效果。

為了對軟硬件協(xié)同遺傳算法平臺的性能進行分析。本設(shè)計還利用開發(fā)板上PowerPC實現(xiàn)了一種純軟件實現(xiàn)的遺傳算法。為了驗證本設(shè)計的性能，這種實現(xiàn)方式的遺傳算法在流程和遺傳算子上設(shè)計都是和本設(shè)計完全一致的。為了避免由于隨機數(shù)帶來的偶然性誤差，本實驗得到大量數(shù)據(jù)之后，再對數(shù)據(jù)平均進行數(shù)據(jù)統(tǒng)計。其中二進制問題的對比數(shù)據(jù)如表1所示。

表1 兩種不同環(huán)境下算法運行效率對比

從表1中我們可以看到，本設(shè)計實現(xiàn)的算法和其他方式實現(xiàn)的算法都可以獲得最優(yōu)解，并且收斂速度基本一致。本設(shè)計相比軟件實現(xiàn)性能卻有了10倍的提高。我們可以得出結(jié)論，使用軟硬件協(xié)同方式的遺傳算法在保留了軟件的可移植性的基礎(chǔ)上還可以提升數(shù)倍的運行效率。

4 結(jié)語

本文介紹了算法平臺設(shè)計中的軟硬件劃分的依據(jù)、軟硬件劃分的結(jié)果以及設(shè)計中模塊之間的連接關(guān)系。隨后對設(shè)計中的各個硬件模塊的具體實現(xiàn)做了詳細的介紹。設(shè)計了軟硬件之間進行信息交互所需要的協(xié)議，最后分別介紹了將硬件化模塊整合成整體遺傳算法IP核、FPGA開發(fā)平臺搭建、軟件平臺搭建、整個系統(tǒng)整合。該方法具有軟件的通用性以及硬件的運算高效性，理論上使用到遺傳算法的地方均可以使用該方法提高運行效率，尤其適合在實時性要求較高的場合（例如工業(yè)控制）應(yīng)用。