（微电子学与固体电子学专业论文）基于fpga的可进化系统的设计与研究.pdf

摘要 摘要 可进化硬件 e h w e v o l v a b l eh a r d w a r e 是指在与外部环境相互作用时 能够自主 动态地改变其自身结构和行为的硬件电路 可进化硬件的基本特征是 具有自组织 自适应 自修复的能力 在智能化通信网络 智能感知 模式识别 与人工智能等方面有广泛的应用前景 由于可编程器件f p g a f i e l dp r o g r a m m a b l eg a t ea r r a y 的电路功能可以通 过对其底层结构加载不同的配置位串而灵活地改变 因此 早在1 9 9 2 年 国际 人工智能专家h u g od eg a r i s 博士就提出基于f p g a 的e h w 这一概念 3 1 当前 基于f p g a 的建立的可进化硬件系统已经成为了可进化硬件研究的主要方法 本文介绍了可进化硬件的基本概念 分析了基于f p g a 的可进化系统的研究 现状 从可进化系统的基本组成部分 可重构电路模型 基因算法 可重构电路 部分配置等方面 提出了优化和改进基于f p g a 的可进化系统的方法 设计并验 证了基于f p g a 的完整的可进化系统 首先本文对于当前主流的基于f p g a 的可进化硬件实现方法 虚拟可重构电 路模型 v r c v i r t u a lr e c o n f i g u r a b l ec i r c u i t 进行了介绍和分析 从电路功能单 元以及互连等方面提出并验证了基于3 输入l u t 的直接互连线型的v r c 结构模 型 并且在a l t e r a d e 2 开发板上进行了可进化实验 证实了该模型 其次 针对于可进化系统的基本组成部分 基因算法 电路配置两方面进行 了分析 参与设计验证了适合于进化的c p u f p g a 可重构系统芯片 f d p 2 0 0 9 2 s o p c 该芯片从3 个方面优化了可进化系统的实现 第一 专门设计f p g a 配置控 制接v i 可以实现通过c p u 对f p g a 进行快速部分配置 实现单芯片 o nc h i p 硬件进化 第二是针对进化过程中每次只有少量位流改变的情况 f p g a 的位 流配置结构采用了行列双译码方式 可以以1 数据字为单位对f p g a 进行配置读 写 提高了部分重配置速度 第三 针对基因算法的特点 专门设计基因算法加 速器 改善基因算法的实现时间 最后基于上述可重构系统芯片 我们建立了完整的芯片级可进化系统 实现 了完整的单芯片可进化流程 并在此基础上验证了基因算法加速器以及部分配置 等硬件部分对于片上可进化系统的改进程度 关键词 进化硬件 虚拟可重构电路模型 芯片级进化系统 f p g a 进化加速 器 部分配置 中图分类号 t n 4 7 a b s t r a c t a b s t r a c t e v o v a b l eh a r d w a r ei st h eh a r d w a r et h a t c a nd y n a m i c a l l ya n di n d e p e n d e n t l y c h a n g ei t ss t m c t u r ea n db e h a v i o u rw h e ni n t e r a c t sw i t ht h ee n v i o r e m e n t t h e b a s i c c 1 a r a c t e ro fe h wi s s e l f o r g n i z a t i o n s e l f a d a p t i o n s e l f r e s t o r e t h e r e a r ew i d e p r o s p e c to fe h w i ni n t e l l i g e n tc o m m u n i c a t i o nn e t w o r k i n t e l l i g e n ts e n s o r p a t t e r n r e c o g n i t i o na n da r t i f i c i a li n t e l l i g e n c e f o rt 1 1 ef p g ac a nc h a n g ei t sf u n c t i o nc o n v e n i e n t l yt h r o u g h d i f f e r e n t c o n f i g u r a t i o nb i ts t r e a m e a r l yi n19 9 2i n t e r n a t i o n a le x p e r t si na r t i f i c i a li n t e l l i g e n c ed r h u g od eg a f f sp r o p o s e dt h ec o n c e p to fe h w b a s e do nf p g a c u r r e n t l y e h wb a s e do n f p g ah a sb e c o m et h em o s tp o p u l a rw a yi nt h ee v o l v a b l eh a r d w a r er e s e a r c h i nt h i sp a p e r t h ec o n c e p to fe h wi si n t r o d u c e d a n dt h er e c e n tr e s e a r c ho fe h w b a s e do nf p g ai sa n a l y s e d f r o ma n a l y s i so ft h eb a s i cp a r to fe h w r e c o n f i g u r a b l e c i r c u i tm o d e l g e n e t i ca l g o r i t h m a n dc o n f i g u r a t i o no fr e c o n f i g u r a b l ec i r c u i t t h e s o l u t i o nt oi m p r o v ee h wb a s e do nf p g ai sp r o p o s e da n dc o m p l e t ee v o l u t i o ns y s t e m b a s e df p g ai sd e s i g n e da n dv e r i f i e d f i r s t t h em a i n s t r e a mi m p l e m e n t a t i o no fe h wb a s e d o nf p g a v i r t u a l r e c o n f i g u r a b l ec i r c u i tm o d e l v r c i si n t r d u c e da n da n a l y s e di nt h i sp a p e r o n ev r c m o d e lb a s e do n3 i n p u tl u tw i t hd i r e c tc o n n e c t i o ni sp r o p o s e df r o mt h ev i e wo f f u n c t i o nc e l la n di n t e r c o n n e c t i o n a n dt h i sm o d e li sv e r i f i e dt h r o u g ht h ee v o l u t i o n e c p e r i m e n to n a l t e r ad e 2 p l a t f o r m s e c o n d a n a l y s et h e b a s i cp a r t so fe h w g e n e t i ca l g o r i t h m a n dc i r c u i t c o n f i g u r a t i o n a n dp a r t i c i p a t e i n d e s i g n a n dv e r i f i c a t i o no ft h ec p u f p g a r e c o n f i g u r a b l es y s t e mc h i pf d p 2 0 0 9 2 s o p c t h i sc h i pi m p r o v et h ei m p l e m e n t a t i o no fe v o l u t i o ns y s t e mf r o m3a s p e c t s o n ei s t h es p e c i a lc o n f i g u r a t i o np o r to ff p g aw h i c hc a ni m p l e m e n tf a s tp a r t i a lc o n f i g u r a t i o n t of p g at h r o u g hc p u c a nr e a l i z eo n c h i pe v o l u t i o n t h es e c o n do n ei s c o n f i g u r a t i o n o ff p g ai no r l ew o r dc a nb ei m p l e m e n t e dw h e nf e wb i t s t r e a mi sc h a n g e di ne v e r y i n t e r a t i o no fe v o l u t i o n f o rr o w c o l u m nd e c o d e ri nb i t s r e a ms t r c t u r eo ff p g a i tc a n i m p r o v et h et i m e o fp a r t i a lc o n f i g u r a t i o n t h el a s to n ei st h eg e n e t i ca l g o r i t h m a c c e l e r a t o rd e s i g n e df o rc h a r a c r t e r i s t i c o fg e n e t i c a l g o r i t h m t h ea c c e l e r a t o rc a n i m p r o v et h ei m p l e m e n t a t i o nt i m eo fg e n e t i ca l g o r i t h m a tl a s t o n ec o m p l e t e o n c h i p e v o l u t i o n s y s t e m i sb u i l tb a s e do nt h e i i a b s t r a c t r e c o n f i g u r a b l es y s t e mc h i pa b o v e a n dt h ee x p e r i m e n t st ov e r i f yt h ei m p r o v e m e n to f e v o l u t i o ns y s t e mc a u s e db yg e n e t i ca c c e r l e r a t o ra n dp a r t i a lr e c o n f i g u r a t i o na r ed i d k e y w o r d e h w v r c o n c h i pe v o l u t i o ns y s t e m f p g a g e n e t i ca l g o r i t h m a c c e r l e r a t o r p a r t i a lc o n f i g u r a t i o n i i i 第l 章绪论 1 1 可进化硬件 第1 章绪论 随着电路系统所要求解决的问题日趋复杂 而复杂性的提高导致了电路系统 稳定性和可靠性的降低 传统的硬件电路设计方法由于是一种自上而下的设计方 法 即必须先有该类电路的理论 设计方法 才能进行具体设计 严重依赖于设 计者的经验和固定的设计方法 影响了电路设计的效率和实现能力 不能解决日 趋复杂的电路系统设计问题 而通过硬件进化设计硬件则是一种自下而上的方法 将基因算法应用到硬件 电路设计的产品 不依赖于先验知识 能处理传统方法难以胜任的复杂电路设计 问题且能根据环境变化进行动态调整 这种方法自动化程度较高 可显著降低设 计成本 还可以开拓设计思路 找到很多人类难以通过正向思维方法得到的设计 方案n 儿刳 提供了解决上述问题的有效途径 因此基于硬件进化的电路设计方法 是一种在设计成本 设计思路等多方面优于传统电路设计方法的新型电路设计技 术 而硬件进化的研究正是这种设计方法的基础 进化硬件d 儿钉 也称演化硬件 的起源最早可追溯到上世纪五十年代 计算 机之父首先提出了研制具有自繁殖与自修复能力的机器的设想 但是由于当时技 术条件的限制使这一设想未能实现 直到基因算法和大规模可编程器件的出现 这一设想才成为可能 基于基因算法和大规模可编程器件的出现 进化硬件将基因算法与电子学有 效的结合在一起 理想的可进化硬件不但具有自我诊断能力 能够通过自我的重 构来消除错误 而且可以在设计要求或系统工作环境发生变化的情况下 还可以 通过自我重构来使电路适应这种变化而继续正常工作 目前进化硬件主要应用领 域巧3 包含有 1 电路设计 2 容错系统 自适应和自修复系统 3 自动控制系统 4 智能机器人 5 模式识别与人工智能等 而主要的研究方向可以分为着重点在 数字电路的硬件进化和着重于模拟电路的硬件进化 在进化硬件领域中 数字电路的硬件进化作为其中的一个主要的研究方向 早在在1 9 9 2 年t e t s u y ah i g u c h i 和h u g od eg a r i s 就开始致力于实现数字电路 的硬件进化障 7 并提出了使用基因算法重新配置硬件结构实现进化的方法 其 后在大规模可编程逻辑器件的基础上 数字电路进化的研究领域越来越广泛 s e k a n i n a 等人则致力于函数级的数字电路进化 如滤波器嘲 并表明这些滤波器 在多种滤波的情况下比传统的滤波器表现更好 而g a r v i e 等人实现了一些基本 逻辑功能如加法器 乘法器的数字电路 并表明在资源占用上更有优势 1 如下 第l 章绪论 图1 1 数字硬件进化结果 2 b i t 乘法器 上图1 1 是g a r v i e 等人通过硬件进化的方法得到的2 b i t 乘法器 其中 a 0 b 0 a l b 1 是乘法器的输入 而x 0 一x 3 是乘法器的输出端 实验结果证明该乘 法器消耗的资源比人工直接设计的乘法器更少 除了数字电路进化 进化硬件另一大领域是模拟进化硬件 在模拟进化领域 中 很多有效的应用研究也在进行中 比如z e b u k u m n 阳等人在f p t a f i e l d p r o g r a m m a b l et r a s n s i s t o ra r r a y 的可重构平台上实现了信号的分离 k a s a i 等人u 则展示了基于f t p a 以及基因算法完成的自适应型波形的控制 s e k a n i n a 则基于该平台实现了振荡器n 引 其中f p t a 平台如下图 圈图 圈图 圈圈 国图 圈圈 圈图 圈圈 囹囵 圈囵 囡国 囵囡 图图 图圈 嚣 图图 图囹 曩圈 圈囡 囵圈 图囵 园圈 图圈 圈囝 图 圈囝 圈囵 圈 圉 图1 2 模拟硬件进化平台f p t a 上图中f p t a 是由多个基本单元组成的 其中基本单元的结构如上图右所示 是由多个可以改变参数的m o s 管组成的 1 2 进化硬件原理 进化硬件主要由3 部分组成n 引 可重构的硬件 基因算法 电路的评估部分 如上图所示 第1 章绪论 图1 3 硬件进化的组成 基因算法是进化硬件中的核心部分n4 也是硬件进化的初始步骤 在算法中 电路的结构和参数等配置信息在编码后作为算法中的染色体 一个个体的染色体 则对应一种具体的配置信息 可重构硬件负责接收基因算法给予的染色体 并且 根据染色体改变自身的结构和功能 而电路评估部分则是根据进化的目标对可重 构硬件部分进行评估 得到当前染色体配置情况下可重构硬件与进化目标的符合 程度 给予相应的评估结果 这个评估结果就是适应度 而整个进化的过程正如上图所示 是由这三个部分组成的循环迭代过程构 成 1 从基因算法部分开始 首先根据设计的目的 产生初步的方案 包括设 定基因算法的中种群大小 基因操作的概率 染色体数目等具体参数 并将每个 染色体作为一个个体 而每个个体表示的是设计的一部分 在确定了基因算法的 各个具体参数后 基因算法开始初始化 产生多个包含染色体的个体 即产生了 多组可重构硬件的配置信息 2 可重构硬件接收染色体转化成的控制数据流 从而确定可重构硬件内 部各单元的联结和功能 形成了初步的硬件系统 其中用来设计进化硬件的可重 构器件应该可以接受任意组合的数据流下载 而不会导致器件的损害 3 电路的评估部分将设计结果与进化目标的要求进行比较 并根据适应度 的衡量准则计算该个体的适应度 并将适应度信息传递给基因算法 其中实现适 应度的评估需要一定的检测手段和评估软件的支持 4 基因算法根据适应度再对新的个体组进行统计 并根据统计结果挑选一 些个体 基因算法根据这些个体的适应度进行相应的修改 如进行基因操作 产 生新一代染色体 基因操作的目的是为了产生更具适应性的下一代 5 重复上述2 4 步骤 这三个组成部分轮流工作 并且不断地产生新的数 代个体 直到新的个体表示的设计方案表现出接近要求的适应能力为止 第l 章绪论 一般来说通过基因算法 可重构硬件 以及电路评估这三部分的协作 最后 会得到一个或数个设计结果 最后设计方案具有对设计要求和系统工作环境的最 佳适应性 这一过程即上文提到的内部进化或硬件进化 1 3 本文重点 本文简要的概述了进化硬件的研究背景 对于当前基于f p g a 的进化硬件的 多个方面的研究进行了分析 并且提出了相应的解决方法 本文的工作重点如下 1 介绍进化硬件的基本概念 以及硬件进化的基本原理 2 针对于当前主流的数字电路的硬件进化研究进行了介绍 并针对于该研 究领域 如可重构电路模型 芯片级进化 以及基因算法等多个问题进 行了分析 3 基于当前的基于f p g a 的可重构电路模型研究 提出了在a l t e r a d e 2 平 台上进行可重构电路模型的互连的探讨 比较了当前可重构电路模型中 主流的两种互连的在一般规模的组合逻辑进化时的硬件进化速度 4 基于当前数字电路硬件进化的主要问题 参与了项目组自主设计的 f d p 2 0 0 9 2 一s o p c 芯片中适合于进化的基因算法加速器 自配置 部分 配置等模块的设计和验证工作 该芯片经过流片测试功能正常 5 基于f d p 2 0 0 9 2 s o p c 芯片搭建了芯片级进化进化流程 芯片级进化的 硬件平台 并在该平台上进行了芯片级进化系统的研究 测试和验证了 f d p 2 0 0 9 2 s o p c 芯片中针对硬件进化的各个模块 并在芯片级进化中 测试了这些模块对于芯片级进化速度的影响 6 在以上芯片级进化系统的实现和研究后 对于芯片级进化的发展进行了 展望和总结 1 4 文章结构 本文共分为6 个章节 其中第2 章介绍了数字电路的硬件进化的研究现况 并根据当前数字电路硬件进化的研究提出了针对于当前芯片级进化的优化和改 进 诸如 基因算法加速 自配置 部分配置等方面 第3 章介绍了当前基于 f p g a 的可重构电路模型的研究状况 并且基于a l t e r ad e 2 的开发板实现了基于 可重构电路模型的进化系统 针对于可重构电路模型的互连方面进行深一步的研 究 第4 章详细介绍了课题组自主设计的片上系统芯片f d p 2 0 0 9 2 s o p c 的架构 以及f d p 2 0 0 9 2 s o p c 芯片中适合于硬件进化的多个模块 基因算法加速器 编 4 第1 章绪论 程下载 以及p o w e r p c 与f p g a 的通信接口 并且介绍了在系统芯片中这些部 分的测试方法和结果 第5 章在f d p 2 0 0 9 2 s o p c 芯片的基础上搭建了芯片级进 化的流程 以及芯片级进化的硬件平台 并基于该进化平台和进化流程针对 f d p 2 0 0 9 2 一s o p c 芯片中适合于进化硬件的部分在芯片级进化中的作用进行了测 试 第6 章总结了本论文的研究成果并对基于芯片级进化实验和测试对于芯片级 进化进行了总结和展望 第2 章数字进化硬件的研究 2 1 数字可进化硬件分类 第2 章数字进化硬件的研究 当前进化硬件研究方向广泛 本文主要着重于数字电路进化硬件 其中数字 进化硬件涉及到基因算法 可重构硬件 实现优化等研究方面 数字进化硬件按 照进化硬件中基本组成 可重构硬件 基因算法 电路评估等部分的不同实现方 式就可以有不同的分类 如下所示 1 按照硬件实验方式可以分为两种 一种是外部进化 1 5 e x t r i n s i c e v o l v a b l e 也被称为离线进化 另一种是内部进化 1 6 i n t r i n s i ce v o l v a b l e 也称在线进化 这种分类方法被普遍认可 并对进化电路的评估方法起着重要的 作用 外部进化是通过建立电子器件的模型 将由基因算法产生的染色体在模型上 进行评价 当达到预期目标时 再将这组染色体下载到重构硬件中去 这种方法 进化过程都在计算机内通过软件完成 虽然灵活方便 可以简单快捷的修改进化 模型 评估函数等 但是计算机通过仿真的速度慢 如果进化模型比较复杂 则 很难建模 内部进化是将基因算法每一代产生的每一条染色体都实际下载到可重构器 件中去 并对每一种电路结构的输出直接进行评价 它对硬件本身有很高的要求 由于早期演化硬件的研究中 用到的是结构比较简单的p a l 或g a l 等p l d 器件 这些器件不能无限次编程 配置时间也较长 结构简单 因此在早期通常 采用外部进化方式 但它只能实现较小规模的电路 在工程应用中限制较大 当 出现f p g a 以后 由于器件结构和功能比先前有了很大的改进和提高 且f p g a 本身有其独有的特性 如有可无限次重复编程 可重构功能 这些特性都为实现 内部进化提供了很有利的条件 2 按照可进化平台中使用的芯片分类 硬件进化可以分为专用芯片 专 用系统 f p g a 等 专用芯片指的是针对进化目标专门设计的一种芯片 这样可 以达到比较高的进化速度 但是这样的芯片设计比较复杂 相应的成本也高 而 并且只能针对专用领域 如在m o r e n o 等人设想的p o e t i c 平台上 1 7 b a r k e r 等 人在针对容错硬件时就需要重新设计专用的p o e t i c t l 8 专用系统则是则指根据 进化目标而设计的复杂的板级系统 该系统一般是由很多的c p u d s p f p g a 等可编程芯片构成 如a n d r e w 的r i s a 平刨1 9 等 但在上述平台中 研究最多 的还是基于f p g a 的进化硬件研究 2 0 1 一方面f p g a 拥有大量的逻辑资源 能 第2 章数字进化硬件的研究 够实现较复杂的功能电路 另一方面f p g a 可以无限次地重新编程 通过重新编 程改变原有的功能 这一部分在2 4 节将着重介绍 基于上述的分类 本文的研究重点依次属于上述分类中的 1 内部进化 3 基于f p g a 实验平台的进化 在内部进化的研究中 可重构电路模型一直是区别 内部进化和外部进化的标志 本文将针对基于f p g a 的可重构电路模型进行进一 步的研究 除此之外 本文还将针对基于f p g a 的实验平台的单芯片进化进行进 一步的分析 2 2 虚拟可重构电路模型 在内部进化硬件的研究中 大部分研究是基于f p g a 实现的 f p g a 逻辑资 源十分丰富 配置位串高达数百万位 可以在不同的配置位串的控制下实现不同 的功能 但是一般由于其商业秘密其底层结构往往不予公开 用户很难直接操纵 底层逻辑资源 因此 当前主流的可进化硬件研究中可重构电路部分一般是使用 虚拟的可重构电路模型的实现方法 v i r t u a lr e c o n f i g u r a b l ec i r c u i t 即v r c 2 1 1 v r c 作为主流的可进化硬件研究的实现方式 至今为止很多的进化硬件研 究中使用了多种v r c 下面将基于一个简单的实例介绍v r c 的组成 j u l i a nf m i l l e r 在研究2 位乘法器实现中的逻辑门级的v r c 实例 2 2 1 如下图所示 f 0 0 0 0 x y f 1 0 0 l x n y f 2 0 1 0 x f 3 0 1 l x l y f 4 1 0 0 1 f 5 1 0 1 y l f 6 1 1 0x y f 7 1 1 lx k 一 图2 1 j u l i a nfm i l l e rv r c 模型 在图中 可以看到虚拟电路模型一般是由多个功能单元以及功能单元的互连 资源组成的 该模型中有1 9 共9 个功能单元 每个功能单元有两个输入和两个 输出 可以选择上图中的8 种基本的门级逻辑函数之一 而单元之间的互连是固 定的 是每个功能单元的输出连接到向右和向上的功能单元 该v r c 的实现方法是通过 1 通过高层语言如 v h d l 等 在逻辑门级 函数级建立电路模型 即上述的逻辑函数阵列 2 将该电路模型综合为f p g a 上的配置位串 并两层的f p g a 结构建模的方法来实现的 如图所示 7 第2 章数字进化硬件的研究 图2 2 两层建模方法 而包含该v r c 模型的整个进化的系统则如下所示 o 函 图2 3 基于v r c 的进化系统 如上图 v r c 模型和电路评估部分均通过配置f p g a 的逻辑资源实现 这 种实现方法不但降低了在进化时f p g a 的资源利用率和进化速度 同时由于v r c 模型中基本单元通常是针对一个具体目标来选择一系列基本逻辑函数 如 与 或 非等 作为进化的基本单元 比如上面j u l i a nf m i l l e r 在2 位乘法器作为进 化目标时选择的基本逻辑功能的集合 因此 传统的v r c 模型的通用性和灵活 性比较差 2 3 基于f p g a 的可进化硬件 由于可编程门阵列 f p g a 的电路结构可动态进行配置和改变 因此可编 程门阵列 f p g a 以其独有的优点为国外多数研究人员用作硬件进化和可重构 第2 章数字进化硬件的研究 研究的平台 早在1 9 9 2 年 国际人工智能专家h u g od eg a f f s 博士就提出基于 f p g a 的e h w 这一概念 6 1 f p g a 属于高容量的 可编程性的逻辑器件 依据当前的制造工艺 主要可 分为s r a m f l a s h 以及反熔丝三种类型 而基于s r a m 的f p g a 是当代最主流 应用最广泛的的类型 一方面是因为基于s r a m 的f p g a 在配置速度上快 另 一方面则是因为其可重构的编程能力 基于f p g a 的e h w 一般就是利用f p g a 的在线可编程技术及其可重构技 术 将f p g a 的配置信息作为染色体 并通过基因算法 g e n e t i ca l g o r i t h m 对 其进行反复的基因算法的操作 最终得出符合环境要求的个体 这个个体就对应 着相应的正确的电路配置 从而使电路适合环境的变化 当所使用的环境发生变 化时 或被放置于未知的环境中时 这种基于f p g a 的e h w 就会自动地再次启 动基因算法 调整电路配置 将f p g a 重构为在当前环境下能够符合要求的功能 当前基于f p g a 的e h w 研究根据其实现方式 又可以分为板问 i n t e r b o a r d f p g a 进化 板级芯片间 i n t e r c h i p f p g a 进化 芯片级 o nc h i p f p g a 进 化 2 3 基于f p g a 的板间进化t z 4 j 女l l 下图所示 计算机来实现基因算法 并通过配 置接口板给f p g a 芯片配置 通过数据接口进行适应度和染色体数据等大量数据 的通信 这种方法优点是实现简单 灵活 缺点是平台要求高 需要p c 机的支 持 在传输大量数据时速度会变慢 板间f p g a 进化 平台 图2 4 板间进化 而板级芯片间f p g a l 2 5 进化则使用芯片代替了计算机 降低了平台要求 但 是损失了基因算法的运行性能 并没有改善大量数据传输的速度问题 板级f p g a 进化 平台 图2 5 板级进化 下面将举例说明一种板问进化系统 s e k a n i n a 在 o nr o u t i n ei m p l e m e n t a t i o n o f v i r t u a le v o l v a b l ed e v i c e su s i n gc o m b 0 6 2 6 1 中使用的板间进化实例 9 第2 章数字进化硬件的研究 图2 6 板问进化系统 从上图 可以看到s e k a n i n a 实现的板间进化由三大部分组成 处理器 x i n l i n x s p a r t a n i i 芯片 以及v i r t e x i i 芯片 该进化系统未使用p c 机或者嵌入式c p u 芯片来实现基因算法 这样一方面不能使用复杂的基因算法 另一方面在基因算 法的性能上也受了限制 除此以外 需要使用处理器来实现j b i t s 2 7 工具进行 f p g a 的配置位串的转换 并且通过r i b b o nc a b l e 传输大量的数据 因此需要额 外耗费大量的时间在不同模块的通信上 我们可以看到板间f p g a 进化需要外部的控制和配置 在平台要求上比较高 耗费的资源也较多 而芯片级进化 2 9 1 贝4 是通过嵌入式c p u 电路来实现基因算法 控制芯片内部的f p g a 的可重构部分完成进化流程 如下图 在这样的可重构电 路和c p u 电路组成的可进化系统芯片平台上 硬件进化时不再需要外界的控制 和数据通信 能够在单芯片上完成进化流程 在平台要求上均优于另外两种平台 而且节省了大量数据通信所耗费的时间 在速度上不再受限于数据通信 因此芯 片级的进化系统是可进化系统的趋势 芯片级f p g a 进化平台 图2 7 芯片级进化 但是芯片级进化系统在进化速度上仍然有所欠缺 如基于嵌入式c p u 实现 的基因算法速度问题 以及基因算法对于可重构电路的配置速度 这些方面将在 下面详细介绍 1 0 第2 章数字进化硬件的研究 2 3 1 基因算法 基因算法作为进化硬件的核心部分 贯穿了整个的硬件进化的流程 基因算 法是模仿生物进化机制而发展出来的集合了随机全局搜索以及优化的一种算法 这种算法作为一种高效搜索 全局搜索的方法 能够在众多的解决方案中选择搜 索解决方案 并且自主地产生新的解决方案 逐次产生越来越接近于最优结果的 方案 最终得到近视最优解 当前基因算法在速度上急需优化 至今为止已经有众多针对基因算法的速度 研究 如 e m a n u e l es t o m e o 针对3 输入5 输出的逻辑函数 2 9 1 通过调整基因算 法的参数对基因算法迭代代数改进了接近4 0 而k o n s t a n t i nm o v s o v i c 针对2 b i t 乘法器作为进化目标的变异概率进行分析 3 0 将5 0 0 0 代内成功进化的概率提升 1 2 但是这些措施均依赖于具体的进化目标 在进化目标改变时均需要进行相 应的更改 缺乏通用性 为了更加有通用性的优化基因算法的速度 下面将针对于基因算法流程的进行分 析 一 图2 8 基因算法流程 如上图2 8 所示 基本的基因算法分为以下步骤 1 初始化 在初始化的过程中通过对于随机数的判断 逐位得出染色体的每一 位 最终得到一个包含有多个个体的种群 第2 章数字进化硬件的研究 2 3 1 基因算法 基因算法作为进化硬件的核心部分 贯穿了整个的硬件进化的流程 基因算 法是模仿生物进化机制而发展出来的集合了随机全局搜索以及优化的一种算法 这种算法作为一种高效搜索 全局搜索的方法 能够在众多的解决方案中选择搜 索解决方案 并且自主地产生新的解决方案 逐次产生越来越接近于最优结果的 方案 最终得到近视最优解 当前基因算法在速度上急需优化 至今为止已经有众多针对基因算法的速度 研究 如 e m a n u e l es t o m e o 针对3 输入5 输出的逻辑函数 2 9 1 通过调整基因算 法的参数对基因算法迭代代数改进了接近4 0 而k o n s t a n t i nm o v s o v i c 针对2 b i t 乘法器作为进化目标的变异概率进行分析 3 0 将5 0 0 0 代内成功进化的概率提升 1 2 但是这些措施均依赖于具体的进化目标 在进化目标改变时均需要进行相 应的更改 缺乏通用性 为了更加有通用性的优化基因算法的速度 下面将针对于基因算法流程的进行分 析 一 图2 8 基因算法流程 如上图2 8 所示 基本的基因算法分为以下步骤 1 初始化 在初始化的过程中通过对于随机数的判断 逐位得出染色体的每一 位 最终得到一个包含有多个个体的种群 第2 章数字进化硬件的研究 2 选择个体 在初始化完成后 基因算法从种群中选择两个个体作为父代染色 体 其中个体选择是采用轮盘赌的方式 即适应度越高 被选到的几率越大 3 基因操作 在选择了两个个体后 基因算法根据这两个染色体的适应度执行 基本的基因操作 交叉和变异操作 其中交叉操作根据当前交叉概率p 对于两个父代染色体中的每一位生成一 个0 1 之间的随机数m 若m p 则交叉模板中该位为1 相应的两个父代 染色体的这一位执行交换操作 交叉模板 玉 i 亘 i 玉 二 i 雯 图2 9 交叉操作 变异操作根据当前变异概率q 分别针对由交叉操作产生的两个染色体的每 一位生成0 1 之间的随机数m 若m 根据染色体的配置位流对应在f p g a 中的具体位置 将f p g a 中 逻辑资源按照配置的单位划分为多个部分 针对这些部分单独进行 配置 在配置位流中添加针对于f p g a 中的不同部分进行部分配 置的配置命令 配置位置等信息 在染色体对应的配置位流的基础上 填充原有f p g a 其他部分的 配置位流 组合成f p g a 的整体位流 即针对于f p g a 整体进行 重新配置 3 使用f p g a 支持的配置方式 根据上一步生成的配置命令和配置位流对 f p g a 进行配置 在上述流程中 我们可以看到影响配置速度的有两个方面 a 从染色体到配置位流的转换 b 配置方式 如 部分配置 划分时配置的单位 以及全部配置 当前基于f p g a 的可进化硬件研究大部分是使用商用f p g a 进行的研究 由于商业限制 无法得到f p g a 的具体底层配置位流和结构 不能自主地产生 和改变配置位流 必须借助于比如j b i t s i c c a p 等间接手段实现对f p g a 的位流 的转换 则耗费了大量的时间来转换和产生位流 如果能实现芯片内部对于 f p g a 的自主配置 则可以节省上述基于j b i t s 等软件工具所需要的时间 另一方面由于商用f p g a 在配置方式的限制 可进化硬件研究中无法针对 于底层细粒度的配置位流进行有效的部分配置 在目前主流的f p g a 厂商的产 品如x i n l i n x 的v i r t e x 2 v i r t e x 4 3 4 等中的f p g a 的配置部分均实现了以数据帧 为单元的局部配置功能 而在实际的进化流程中可重构电路需要重新配置的部 分并不一定是完整的一个数据帧 可能是1 个数据字 3 2 位的编程点单位 甚至单独的一个编程点 如图所示 第2 章数字进化硬件的研究 需要修改 编程点信 图2 1 3 可重构电路的部分配置 在这种情况下 以一个数据帧为基本单位就不够灵活 花费了很多时间来重新配 置一些并不需要配置的部分 急需一种更小的配置单位来实现更加灵活的部分配 置 从以上的分析 这两个方面均影响了配置的速度 需要在自主配置 以及 配置单位方面来优化进化系统 2 4 小结 本章介绍了数字电路的硬件进化的研究现况 其中包括当前的v r c 模型 以及v r c 模型的实现方式 并对当前v r c 模型进行了分析 其次根据当前数字 电路硬件进化的研究中的必要组成部分 基因算法 对可重构电路的重新配置等 方面分别进行了详细的介绍 针对于当前芯片级进化中基因算法的现状提出了从 硬件角度优化基因算法的实现 并且提出了从自主配置 以及部分配置两方面优 化芯片进化中对可重构电路的配置过程 1 6 第3 章虚拟f p g a 结构模型 第3 章虚拟f p g a 结构模型 3 1 虚拟f p g a 结构模型的研究 虚拟可重构电路模型 vrc 一般是由两部分组成的 基本功能单元 以及功能单元之间的互连 其中基本功能单元一般可以包含有很多种功能 可以 根据基因算法对与可重构电路阵列的配置相应地选择其功能 基本单元之间的互 连则在基因算法的配置下 负责连接不同的功能单元 形成一条从输入到输出的 数据通道 这两部分均是v1 tc 模型的必要组成部分 缺一不可 下面将先介绍基于f p g a 的v r c 虚拟f p g a 结构模型 的基本功能单元 的研究 对比于门级的传统虚拟可重构电路 v r c 3 5 的基本功能单元均是由基本 的逻辑门构成的 虚拟f p g a 结构模型的基本功能单元是由n 输入的l u t 组成 的 其中基于f p g a 的vrc 3 6 中基本功能单元的设计主要是为了考虑在有限 的r l 输入的情况下各种功能的实现 在n 变量输入的情况下 最小项的集合包含 了所有2 2 种逻辑函数 从这个意义上讲 最小项表达形式是最有效率的编码方 式 因此在选择可进化基本功能单元时 直接使用查找表是合理而有效率的 虚拟f p g a 结构模型的基本阵列结构如下图3 1 所示 涸l 泗佃l 泗 驷i 洄 图3 1 虚拟f p g a 结构模型 如上图3 1 所示 虚拟f p g a 结构模型中 基本功能单元是n 输入的lu t 而阵列中互连为 每一个基本单元的输入都是上一列所有基本单元的输出经过选 择器 m u x 选择所得到的结果 这n 个的输入端对应着n 个4 选1 的m i y x 而这r 1 个m u x 的4 个输入端均对应上一列所有基本单元的输出 虚拟f p g a 结构模型研究表明 在基于以上的vrc 基本结构下 对比于基 第3 章虚拟f p g a 结构模型 于2 5 输入lut 的可进化电路模型和以基本逻辑门为基本功能单元的可进 化电路模型 在以任意3 输入到5 输入的组合逻辑函数为进化目标时 3 输入l ut 的可进化电路模型是最有效率的 在适应度上均优于其他模型 其中比门级 模型平均高出8 0 3 如下图所示 一5 0 0os o o1 0 0 01 5 0 02 0 0 02 5 0 d 3 0 0 03 5 0 04 0 0 0 4 5 0 0 时钟屉 图3 2 v r c 模型进化过程 上图中横轴为可进化系统运行的时间 纵轴为适应度值脯意的适应度值 由 于针对于组合逻辑的进化在2 0 万代时就已经能看出明显的差异 图中所有的 v r c 模型均停止在2 0 万代 这些v r c 模型中 2 l u t 3 l u t 4 l u t 5 l u t 均为基于不同输入的l u t 的虚 拟f p g a 结构模型 而v r c l v r c 2 中互连结构是与基于l u t 的v r c 模型相 同的 功能单元实现的是从八种基本门逻辑中选择一种功能 下面分别是 v r c t 3 7 1 v r c 2 1 2 2 1 中基本功能单元包含的八种功能 v r c s 逻辑函数集合 v r c l s i n m a n 1 a a a b a l b a b v a b a 陋 v r c 2 s e k a n i n a a b a b a l b a b a b a b 表3 1v r c l 与v r c 2 的基本功能单元 3 2 虚拟f i g a 结构模型的互连研究 在上述虚拟f p g a 结构模型研究中 为了便于研究 互连结构为每一个基本 单元的输入都是上一列所有基本单元的输出经过选择器 m l 选择所得到的 结果 该模型并没有深入的研究虚拟f p g a 结构模型的互连情况 本文针对于vrc 模型中常见的互连结构进行了分析 当前大部分互连 2 6 第3 章虚拟f p g a 结构模型 分为两种 1 固定连接型互连 2 任意连接型互连 图3 3 固定型互连 图3 4 任意型互连 上面两图分别是固定型互连和任意连接型互连的实例 其中功能单元均为l 输入1 输出的基本单元 在固定型互连中每一个功能单元的输出是连接到固定的 单元上的 而任意性互连则给予了更大的自由度 每一个功能单元的输出属于互 连线的集合 可以连接到任意单元的输入端 这两种互连各有优势 固定性互连在染色体的复杂度上低于任意型互连 对 于基因算法来讲需要搜索的解空间更小 但是能够完成的功能受固定互连的限制 也比较少 而任意性互连由于功能上的自由性比较高 能够完成的功能比较多 但是染色体复杂度高 基因算法中解空间大 下面我们将比较这两种互连的优劣 本文将依次描述不同互连的虚拟f p g a 结构模型及包含有这些模型的完整进化平台的实现和实验 3 2 1 不同互连的虚拟f p g a 结构模型 首先两种互连的v r c 模型分别如下图所示 1 9 第3 章虚拟f p g a 结构模型 分为两种 1 固定连接型互连 2 任意连接型互连 图3 3 固定型互连 图3 4 任意型互连 上面两图分别是固定型互连和任意连接型互连的实例 其中功能单元均为l 输入1 输出