摘要 基于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硬件。