摘要 基于FPGA" title="FPGA">FPGA基本數(shù)據(jù)流的下載控制方式，利用遺傳算法" title="遺傳算法">遺傳算法,，通過(guò)單片機(jī)" title="單片機(jī)">單片機(jī)控制數(shù)據(jù)流的方式對(duì)FPGA進(jìn)行編程配置,，實(shí)現(xiàn)自身重構(gòu)，使系統(tǒng)具有自適應(yīng),、自組織和自修復(fù)的特性,。
關(guān)鍵詞 FPGA；遺傳算法,；動(dòng)態(tài)重構(gòu)" title="動(dòng)態(tài)重構(gòu)">動(dòng)態(tài)重構(gòu),；單片機(jī)
可重構(gòu)計(jì)算的概念是在20世紀(jì)60年代由美國(guó)加利福尼亞大學(xué)的Geraid Estrin提出，并研制了系統(tǒng)原型,。70年代末,，Suetlana P Kartas-hev和Steven I．Kartashev博士提出了動(dòng)態(tài)可重構(gòu)系統(tǒng)的概念。進(jìn)入90年代,，可重構(gòu)技術(shù)成為了研究熱點(diǎn),，近幾年，可重構(gòu)計(jì)算和軟硬件協(xié)同設(shè)計(jì),，是當(dāng)前計(jì)算機(jī)科研領(lǐng)域的兩大核心,，其任務(wù)建模平臺(tái)大多是基于FPGA的動(dòng)態(tài)可重構(gòu)系統(tǒng)，是最近幾年該領(lǐng)域研究的熱點(diǎn)話題,，并在多領(lǐng)域得到廣泛應(yīng)用,。
本文實(shí)現(xiàn)了基于遺傳算法的硬件演化過(guò)程,。通過(guò)Mcu隨機(jī)產(chǎn)生種群,，選擇好的基因進(jìn)行交叉變異產(chǎn)生后代，然后將合適的基因通過(guò)測(cè)試找到最佳重構(gòu)方案,。選擇最佳方案應(yīng)用于硬件,，實(shí)現(xiàn)自我修復(fù)和自適應(yīng),。
1 軟件算法
遺傳算法(Genetic Algorithm，GA)是由美國(guó)密執(zhí)安大學(xué)John Holland教授于20世紀(jì)70年代提出并逐步發(fā)展起來(lái)的一種自適應(yīng)全局優(yōu)化搜索算法,。他模擬自然選擇和自然遺傳過(guò)程發(fā)生的繁殖,，交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解,，并按某種指標(biāo)從群解中選取較優(yōu)個(gè)體,，利用遺傳算子對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群,，直到滿(mǎn)足某種收斂指標(biāo),，最終得到問(wèn)題的最優(yōu)解或近似解。
基本遺傳算法由4部分組成：(1)編碼(產(chǎn)生初始種群),。(2)適應(yīng)度函數(shù)計(jì)算,。(3)遺傳算子(選擇、交叉,、變異),。(4)運(yùn)行參數(shù)。
1．1 選擇
遺傳算法首先要產(chǎn)生初始種群,，通常叫做染色體,。染色體由基因組成，如11001,，每位二進(jìn)制數(shù)就是一個(gè)基因變量,，然后通過(guò)適應(yīng)度函數(shù)檢測(cè)合格的染色體，選擇合格染色體進(jìn)行下一步的交叉,、變異,，得到新個(gè)體。
遺傳算法中的適應(yīng)度,，是表示某一個(gè)體對(duì)環(huán)境的適應(yīng)能力,，也表示該個(gè)體繁殖后代的能力。遺傳算法的適應(yīng)度函數(shù)也叫評(píng)價(jià)函數(shù),，是用以判斷群體中個(gè)體優(yōu)劣程度的指標(biāo),，它是根據(jù)所求問(wèn)題的目標(biāo)函數(shù)進(jìn)行評(píng)估的。
此處適應(yīng)度選擇函數(shù)的模式通過(guò)一種反饋模式,，將產(chǎn)生的個(gè)體經(jīng)過(guò)仿真檢測(cè)評(píng)估,。如果達(dá)到要求，經(jīng)評(píng)估結(jié)果存入存儲(chǔ)模塊,，然后以輪盤(pán)賭的方式對(duì)所有的函數(shù)結(jié)果加權(quán),，判斷每個(gè)基因的適應(yīng)度與加權(quán)和的比值，即介于(0，1)的小數(shù),，選擇大于—個(gè)值比如0.8為合格,，當(dāng)評(píng)估完群體中所有個(gè)體的適應(yīng)度后，選擇適應(yīng)度大于0.8的個(gè)體存儲(chǔ),，然后等待由交叉變異模塊產(chǎn)生出的新個(gè)體,。
1．2 交叉變異
交叉變異模塊得到來(lái)自選擇模塊的兩個(gè)個(gè)體，根據(jù)隨機(jī)數(shù)模塊產(chǎn)生的隨機(jī)數(shù)與交叉概率作比較,，判斷是否進(jìn)行交叉操作,。交叉算子根據(jù)交叉率將種群中的兩個(gè)個(gè)體隨機(jī)交換某些基因，能夠產(chǎn)生新的基因組合,，期望將有益基因組合在一起,。
如找到兩個(gè)父代基因，需要進(jìn)行交叉,，找到基因的交叉點(diǎn),，將各個(gè)基因的交叉點(diǎn)交叉基因變量形成新的基因變量，變異就是每個(gè)基因找到基因變異點(diǎn),，試圖通過(guò)基因變異找到合適的方案,，如圖1所示。
1．3 基因下載
得到的優(yōu)良基因就是所需的方案,，將這個(gè)方案直接下載,，最后實(shí)現(xiàn)可控制，可重構(gòu),，自適應(yīng),。如圖2所示。
基本遺傳算法是通過(guò)某種編碼機(jī)制把對(duì)象抽象為由特定符號(hào)按一定順序排成的串,，就像染色體都是由基因排成的串,，此處是使用二進(jìn)制編碼，得到的是5 bit二進(jìn)制字符串,。程序如下：
2 FPGA基本結(jié)構(gòu)
目前主流FPGA均采用基于SRAM工藝的查找表結(jié)構(gòu),，也有些軍品和宇航級(jí)FPGA，采用Flash或熔絲與反熔絲工藝的查找表結(jié)構(gòu),。通過(guò)燒寫(xiě)文件改變查找表內(nèi)容的方法來(lái)實(shí)現(xiàn)對(duì)FPGA的重復(fù)配置,。
查找表(Look-Up-Table)簡(jiǎn)稱(chēng)為L(zhǎng)UT，目前FPGA中多使用4輸入的LUT,，所以每個(gè)LUT可以看成一個(gè)有4位地址線的RAM,。這樣，每輸入一個(gè)信號(hào)進(jìn)行邏輯運(yùn)算就等于輸入一個(gè)地址進(jìn)行查表,，找出地址對(duì)應(yīng)的內(nèi)容,，然后輸出,。
2．1 多路復(fù)用器(Multiplexer)
基于這種4輸入LUT結(jié)構(gòu)的原理，采用了4輸入的復(fù)用選擇器,，在多路數(shù)據(jù)傳送過(guò)程中，能夠根據(jù)需要將其中任意一路選出,，也稱(chēng)多路選擇器或多路開(kāi)關(guān),。本文將控制器產(chǎn)生的5位數(shù)據(jù)流通過(guò)移位寄存器來(lái)控制4個(gè)輸入端口的選擇，如圖3所示,。
2．2 移位寄存器(Shift Register)
在數(shù)字電路中,，通常會(huì)用寄存器存放二進(jìn)制數(shù)據(jù)或代碼，如圖4所示,。Mux的選擇位由控制器產(chǎn)生的數(shù)據(jù)流經(jīng)緩存后輸出,，SelA[1，0],，SelB[1,，O]分別作用于兩個(gè)多路復(fù)用器。移位寄存器中輸出控制多路復(fù)用器的控制位如表1所示,。
2．3 與非門(mén)
與非門(mén)是組成各種電路的基礎(chǔ)門(mén),，可根據(jù)需要，用與非門(mén)搭建不同的門(mén),，如圖5所示,，將不同的與非門(mén)結(jié)構(gòu)實(shí)現(xiàn)與門(mén)或門(mén)等其他功能，實(shí)現(xiàn)動(dòng)態(tài)可重構(gòu),。
3 可重構(gòu)系統(tǒng)的單元結(jié)構(gòu)搭建
根據(jù)4輸入LUT的結(jié)構(gòu)原理,，本電路選用2個(gè)4輸入的MUX用來(lái)選擇與非門(mén)的輸入端口，然后用1個(gè)2輸入的MUX選擇數(shù)據(jù)的輸出,，3個(gè)MUX的選擇位分別用SelB[1,，0]，SelA[1,，0],，Sel-out控制，移位寄存器作為5位串行二進(jìn)制數(shù)的緩存,，如圖6所示,。可知,，與非門(mén)可以通過(guò)東西南北4輸入的選擇組成各種數(shù)字電路,，這種單元結(jié)構(gòu)可以繼續(xù)擴(kuò)展為2×2或更多單元，實(shí)現(xiàn)復(fù)雜的數(shù)字電路,。這里演示單元結(jié)構(gòu)形成的與門(mén)和或門(mén)的簡(jiǎn)單結(jié)構(gòu),，進(jìn)一步說(shuō)明可重構(gòu)的可實(shí)現(xiàn)性,。
當(dāng)產(chǎn)生數(shù)據(jù)流經(jīng)過(guò)緩存進(jìn)行重構(gòu)電路后，可以看到新的熟悉電路所實(shí)現(xiàn)的功能,，如圖7所示,。通過(guò)觀察輸入和輸出端的關(guān)系，測(cè)試得到所需電路的最佳方案,，即可下載到硬件,，完成所需任務(wù)。
4 硬件平臺(tái)結(jié)構(gòu)
硬件結(jié)構(gòu)是基于單片機(jī)與FPGA的通信,。Mcu選擇MSP430,，通過(guò)RS232和FPGA進(jìn)行通信，PC機(jī)通過(guò)JTAG接口向中心芯片下載程序,。外圍設(shè)備中,，選擇2個(gè)8位LED，4位輸入按鍵,，1個(gè)12864液晶顯示,，預(yù)留32位的擴(kuò)展接口。如圖8所示,，F(xiàn)PGA選擇的是Ahera的EP1C16Q240C8,。
5 結(jié)束語(yǔ)
實(shí)施電路可重構(gòu)技術(shù)，已成為計(jì)算系統(tǒng)研究中的新熱點(diǎn),，使硬件逐漸軟件化,，通過(guò)微處理器結(jié)合多個(gè)FPGA對(duì)其進(jìn)行配置，實(shí)現(xiàn)動(dòng)態(tài)局部可重構(gòu),，具有較強(qiáng)的通用性和自適應(yīng)性,，適用于模塊化設(shè)計(jì)。本文基于5 bit數(shù)據(jù)流,，實(shí)現(xiàn)了FPGA的部分動(dòng)態(tài)可重構(gòu),，可以實(shí)時(shí)生成所需要的硬件結(jié)構(gòu)。動(dòng)態(tài)可重構(gòu)可以充分利用可重配置硬件,，尤其是可重配置計(jì)算方面,。該技術(shù)在理論上有較大發(fā)展，F(xiàn)PGA未來(lái)的發(fā)展方向之一就是做支持動(dòng)態(tài)可配置的SOPC硬件,。