摘要  基于FPGA" title="FPGA">FPGA基本數據流的下載控制方式，利用遺傳算法" title="遺傳算法">遺傳算法，通過單片機" title="單片機">單片機控制數據流的方式對FPGA進行編程配置，實現自身重構，使系統具有自適應、自組織和自修復的特性。
關鍵詞  FPGA；遺傳算法；動態重構" title="動態重構">動態重構；單片機

    可重構計算的概念是在20世紀60年代由美國加利福尼亞大學的Geraid Estrin提出，并研制了系統原型。70年代末，Suetlana P Kartas-hev和Steven I．Kartashev博士提出了動態可重構系統的概念。進入90年代，可重構技術成為了研究熱點，近幾年，可重構計算和軟硬件協同設計，是當前計算機科研領域的兩大核心，其任務建模平臺大多是基于FPGA的動態可重構系統，是最近幾年該領域研究的熱點話題，并在多領域得到廣泛應用。
    本文實現了基于遺傳算法的硬件演化過程。通過Mcu隨機產生種群，選擇好的基因進行交叉變異產生后代，然后將合適的基因通過測試找到最佳重構方案。選擇最佳方案應用于硬件，實現自我修復和自適應。

1 軟件算法
    遺傳算法(Genetic Algorithm，GA)是由美國密執安大學John Holland教授于20世紀70年代提出并逐步發展起來的一種自適應全局優化搜索算法。他模擬自然選擇和自然遺傳過程發生的繁殖，交叉和基因突變現象，在每次迭代中都保留一組候選解，并按某種指標從群解中選取較優個體，利用遺傳算子對這些個體進行組合，產生新一代的候選解群，直到滿足某種收斂指標，最終得到問題的最優解或近似解。
    基本遺傳算法由4部分組成：(1)編碼(產生初始種群)。(2)適應度函數計算。(3)遺傳算子(選擇、交叉、變異)。(4)運行參數。
1．1 選擇
    遺傳算法首先要產生初始種群，通常叫做染色體。染色體由基因組成，如11001，每位二進制數就是一個基因變量，然后通過適應度函數檢測合格的染色體，選擇合格染色體進行下一步的交叉、變異，得到新個體。
    遺傳算法中的適應度，是表示某一個體對環境的適應能力，也表示該個體繁殖后代的能力。遺傳算法的適應度函數也叫評價函數，是用以判斷群體中個體優劣程度的指標，它是根據所求問題的目標函數進行評估的。
    此處適應度選擇函數的模式通過一種反饋模式，將產生的個體經過仿真檢測評估。如果達到要求，經評估結果存入存儲模塊，然后以輪盤賭的方式對所有的函數結果加權，判斷每個基因的適應度與加權和的比值，即介于(0，1)的小數，選擇大于—個值比如0.8為合格，當評估完群體中所有個體的適應度后，選擇適應度大于0.8的個體存儲，然后等待由交叉變異模塊產生出的新個體。
1．2 交叉變異
    交叉變異模塊得到來自選擇模塊的兩個個體，根據隨機數模塊產生的隨機數與交叉概率作比較，判斷是否進行交叉操作。交叉算子根據交叉率將種群中的兩個個體隨機交換某些基因，能夠產生新的基因組合，期望將有益基因組合在一起。
    如找到兩個父代基因，需要進行交叉，找到基因的交叉點，將各個基因的交叉點交叉基因變量形成新的基因變量，變異就是每個基因找到基因變異點，試圖通過基因變異找到合適的方案，如圖1所示。

1．3 基因下載
    得到的優良基因就是所需的方案，將這個方案直接下載，最后實現可控制，可重構，自適應。如圖2所示。

    基本遺傳算法是通過某種編碼機制把對象抽象為由特定符號按一定順序排成的串，就像染色體都是由基因排成的串，此處是使用二進制編碼，得到的是5 bit二進制字符串。程序如下：
   
     

2 FPGA基本結構
    目前主流FPGA均采用基于SRAM工藝的查找表結構，也有些軍品和宇航級FPGA，采用Flash或熔絲與反熔絲工藝的查找表結構。通過燒寫文件改變查找表內容的方法來實現對FPGA的重復配置。
    查找表(Look-Up-Table)簡稱為LUT，目前FPGA中多使用4輸入的LUT，所以每個LUT可以看成一個有4位地址線的RAM。這樣，每輸入一個信號進行邏輯運算就等于輸入一個地址進行查表，找出地址對應的內容，然后輸出。
2．1 多路復用器(Multiplexer)
    基于這種4輸入LUT結構的原理，采用了4輸入的復用選擇器，在多路數據傳送過程中，能夠根據需要將其中任意一路選出，也稱多路選擇器或多路開關。本文將控制器產生的5位數據流通過移位寄存器來控制4個輸入端口的選擇，如圖3所示。

2．2 移位寄存器(Shift Register)
    在數字電路中，通常會用寄存器存放二進制數據或代碼，如圖4所示。Mux的選擇位由控制器產生的數據流經緩存后輸出，SelA[1，0]，SelB[1，O]分別作用于兩個多路復用器。移位寄存器中輸出控制多路復用器的控制位如表1所示。

2．3 與非門
    與非門是組成各種電路的基礎門，可根據需要，用與非門搭建不同的門，如圖5所示，將不同的與非門結構實現與門或門等其他功能，實現動態可重構。

3 可重構系統的單元結構搭建
    根據4輸入LUT的結構原理，本電路選用2個4輸入的MUX用來選擇與非門的輸入端口，然后用1個2輸入的MUX選擇數據的輸出，3個MUX的選擇位分別用SelB[1，0]，SelA[1，0]，Sel-out控制，移位寄存器作為5位串行二進制數的緩存，如圖6所示。可知，與非門可以通過東西南北4輸入的選擇組成各種數字電路，這種單元結構可以繼續擴展為2×2或更多單元，實現復雜的數字電路。這里演示單元結構形成的與門和或門的簡單結構，進一步說明可重構的可實現性。

    當產生數據流經過緩存進行重構電路后，可以看到新的熟悉電路所實現的功能，如圖7所示。通過觀察輸入和輸出端的關系，測試得到所需電路的最佳方案，即可下載到硬件，完成所需任務。

4 硬件平臺結構
    硬件結構是基于單片機與FPGA的通信。Mcu選擇MSP430，通過RS232和FPGA進行通信，PC機通過JTAG接口向中心芯片下載程序。外圍設備中，選擇2個8位LED，4位輸入按鍵，1個12864液晶顯示，預留32位的擴展接口。如圖8所示，FPGA選擇的是Ahera的EP1C16Q240C8。

5 結束語
    實施電路可重構技術，已成為計算系統研究中的新熱點，使硬件逐漸軟件化，通過微處理器結合多個FPGA對其進行配置，實現動態局部可重構，具有較強的通用性和自適應性，適用于模塊化設計。本文基于5 bit數據流，實現了FPGA的部分動態可重構，可以實時生成所需要的硬件結構。動態可重構可以充分利用可重配置硬件，尤其是可重配置計算方面。該技術在理論上有較大發展，FPGA未來的發展方向之一就是做支持動態可配置的SOPC硬件。