（信息与通信工程专业论文）基于遗传算法的可重构fir滤波器研究与设计.pdf

摘要 摘要 可重构计算系统是在通用计算机和专用a s i c 的基础上发展起来的，它结合了 通用计算机的灵活性和专用a s i c 的高效性的优点，在加解密、信号处理以及模式 识别等诸多领域有着重要应用。算法级功能可重构电路是一种新型的可重构数字 体系。这种电路能在外界条件和参数的刺激下，自动地、有机地发生变形、进化， 形成具有某种意义的智能硬件电路。 目前在算法级功能可重构电路研究中，可进化电路的设计是其中最典型也是 研究最多的一种硬件设计方法，它结合了进化算法和可编程逻辑器件的优点。但 是进化电路大多是由全硬件形式实现，不但增加了进化算法的实现难度，而且大 大降低了算法级功能可重构的应用灵活性。 针对上述进化硬件的不足，本文通过对典型可重构系统结构的深入研究提出 了一种改进方法。将遗传算法能有效解决系统最优化问题的思想应用于可编程片 上系统，以内嵌处理器作为重构控制单元，针对不同的应用，采用相应的进化模 型和染色体编码方式，使得算法克服了进化硬件的缺点，并在此基础上设计实现 了基于遗传算法的可重构f i r 数字滤波器系统。 论文首先介绍了目前可重构计算技术的研究现状和意义，分析了存在的问题。 其次对遗传算法及其改进算法进行了研究，进而分析了现有的典型算法级功能可 重构电路结构的特性，提出了基于遗传算法的自重构片上系统。它通过可重构逻 辑器件内嵌的处理器实现基于遗传算法的进化计算，完成对具有可重构功能的i p 核结构单元的自动配置过程，形成了一种算法级功能可重构片上系统。 通过自重构f i r 系统的设计与实现，验证了本论文所提设计方法的有效性。 包括对现有的f i r 的算法及硬件实现结构进行分析，提出了一种粗粒度的新型高 速可重构的f i r 处理器结构；根据本文提出的可重构f i r 系统的重构策略，按照 算法级可重构的需求，进行系统部件的选型，搭建了系统硬件平台；利用遗传算 法进行了f i r 滤波器的优化设计，实现了可重构f i r 滤波器。最后对整体设计进 行了性能测试和分析。 关键词：可重构，遗传算法，片上系统，f i r 滤波器 摘要 a b s t r a c t r e c o n f i g u r a b l ec o m p u t i n gs y s t e md e v e l o p e do nt h eb a s i so fa l l p u r p o s ec o m p u t e r a n ds p e c i a l p u r p o s ea p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t ( a s i c ) i th a sc o m b i n e dt h e a d v a n t a g e s o f f l e x i b i l i t y o ft h e a l l - p u r p o s ec o m p u t e r a n dt h e e f f i c i e n c y o f s p e c i a l p u r p o s ea s i c t h e r ei si m p o r t a n ta p p l i c a t i o ni nag r e a td e a lo ff i e l d ss u c ha s d e c i p h e r i n g ，s i g n a lp r o c e s s i n g a n dp a r e m - r e c o g n i t i o n a l g o r i t h m l e v e lf u n c t i o n r e c o n f i g u r a b l ec i r c u i ti san e wr e c o n f i g u r a b l ed i g i t a ls y s t e m u n d e rt h es t i m u l u sb y e x t e r n a lc o n d i t i o na n dt h ep a r a m e t e r , t h i sk i n do fc i r c u i tc a nm e t a m o r p h o s ea n de v o l v e a u t o m a t i c a l l y , o r g a n i c a l l y , t of o r mi n t e l l e c t u a lh a r d w a r ec i r c u i tw i t ha c e r t a i nm e a n i n g p r e s e n t l y , i nt h er e s e a r c h o na l g o r i t h m l e v e lf u n c t i o nr e c o n f i g u r a b l ec i r c u i t ， e v o l v a b l ec i r c u i t sd e s i g ni st h em o s tt y p i c a lh a r d w a r ed e s i g nm e t h o da n db ew i d e l y s t u d i e d i th a sc o m b i n e dw i t ht h e a d v a n t a g e so fe v o l u t i o n a r ya l g o r i t h m a n d p r o g r a m m a b l el o g i cd e v i c e ，b u te v o l v a b l eh a r d w a r ei sm o s t l yr e a l i z e db yf u l lh a r d w a r e f o r m t h ef u l lh a r d w a r ei m p l e m e n t a lm e t h o dh a sn o to n l yi n c r e a s e dd i f f i c u l t yo f r e a l i z i n gt h ee v o l u t i o n a r ya l g o r i t h mb u ta l s og r e a t l yr e d u c e dt h ea p p l i c a t i o nf l e x i b i l i t yo f t h ea l g o r i t h m - l e v e lf u n c t i o nr e c o n f i g u r a b l ec i r c u i t o v e r c o m i n gt h ed e f i c i e n c i e so fe v o l u t i o n a r yh a r d w a r ed e s c r i b e da b o v e ，t h i sp a p e r p r o p o s e da ni m p r o v e dm e t h o db yd e e p l yr e s e a r c h i n gt h et y p i c a lr e c o n f i g u r a b l es y s t e m c o n f i g u r a t i o n t h e i d e at h a t g e n e t i ca l g o r i t h m c a ne f f e c t i v e l ys o l v et h es y s t e m o p t i m i z a t i o np r o b l e mh a s b e e n a p p l i e dt op r o g r a m m a b l es y s t e m o n c h i p t h e s h o r t c o m i n g so ff u l lh a r d w a r ei m p l e m e n t a lm e t h o dh a db e e no v e r c o m e db yu s i n g e m b e d d e d p r o c e s s o r s a sar e c o n f i g u r a b l ec o n t r o l u n i t ，a d o p t i n gc o r r e s p o n d i n g e v o l u t i o n a r ym o d e l sa n dc h r o m o s o m ee n c o d i n gm o d ea c c o r d i n gt od i f f e r e n ta p p l i c a t i o n s ， a n dt h e nt h er e c o n f i g u r a b l ef i n i t ei m p u l s er e s p o n s e ( f i r ) d i g i t a lf i l t e rs y s t e mh a sb e e n d e s i g n e db a s e do nt h eg e n e t i ca l g o r i t h m i nt h i sp a p e r , t h ec u r r e n tr e s e a r c hs i t u a t i o n ，t h em e a n i n go fr e c o n f i g u r a b l e c o m p u t i n gt e c h n o l o g ya n dt h ee x i s t i n gp r o b l e mh a sb e e ns u m m a r i e da tf i r s t t h e nw e s t u d yt h eg e n e t i ca l g o r i t h ma n di t si m p r o v e dm e t h o d s ，a n a l y s et h ec h a r a c t e r i s t i co ft h e e x i s t i n gt y p i c a la l g o r i t h m l e v e lr e c o n f i g u r a b l ec i r c u i ts t r u c t u r e ，a n dp u tf o r w a r dt h e s e l f - r e c o n f i g u r a b l es y s t e m - o n c h i pb a s e do ng e n e t i ca l g o r i t h m b ye m b e d d e dp r o c e s s o r i nr e c o n f i g u r a b l el o g i cd e v i c e ，i tc a na c h i e v ee v o l u t i o n a r yc o m p u t a t i o nb a s e do nt h e g e n e t i ca l g o r i t h m ，i m p l e m e n ta u t o c o n f i g u r a t i o np r o c e s sw i m t h ei pc o r ew h i c hh o l do n r e c o r t f i g t t r a b l eu n i t ， a n d t h e n a n a l g o r i t h m 1 e v e l f u n c t i o n a l r e c o n f i g u r a b l e i i 摘要 s y s t e m o n - c h i pi sc o n s t r u c t e d t h r o u g ht h ed e s i g na n di m p l e m e n t a t i o no ft h ef i rs e l f - r e c o n f i g u r a b l es y s t e m ，t h e v a l i d i t yo ft h ed e s i g nm e t h o dm e n t i o n e di nt h i sp a p e ri sv e r i f i e d an e wh i g h s p e e d r e c o n f i g u r a b l ef i rp r o c e s s o rs t r u c t u r ew i t hc o a r s eg r a i n sh a sb e e np r o p o s e da f t e r a n a l y z i n gt h ef i ra l g o r i t h ma n di t si m p l e m e n t a r yh a r d w a r es t r u c t u r e t h ee x p e r i m e n t a l h a r d w a r ep l a t f o r mw h i c hi m p l e m e n t st h e r e c o n f i g u r a b l ef i rw i t ha l g o r i t h m 1 e v e l r e c o n f i g u r a t i o nh a sb e e nc o n s t r u c t e dw i t hp r o p e rd e v i c e s t h er e c o n f i g u r a b l eo p t i m a l f i rh a db e e ni m p l e m e n t e di nt h e p l a t f o r mu s i n gg e n e t i ca l g o r i t h ma n dt h et e s t p e r f o r m a n c ei n d i c a t et h a tt h ea l r i t h ma n dd e s i g nm e t h o da r er e a s o n a b l ea n ds u c c e s s f u l k e y w o r d s ：r e c o n f i g u r a b l e ，g e n e t i ca l g o r i t h m ，s y s t e m o n - c h i p ，f i rf i l t e r i i i 缩略词表 英文缩写 a l u a s i c a p i e d a e h w f i f 0 f i r f p g a h d l l u t m u x r c s o c s o p c s r a m 英文全称 缩略词表 a r i t h m e t i cl o g i eu n i t a p p l i c a t i o ns p e c i f i ci n t e g r a t e dc i r c u i t a p p l i c a t i o np r o g r a m m i n gi n t e r f a c e e l e c t r o n i cd e s i g na u t o m a t i o n e v o l v a b l eh a r d w a r e f i r s ti nf i r s t0 t i t f i n i t ei m p u l s er e s p o n s e f i e l dp r o g r a m m a b l eg a t ea r r a y h a r d w a r ed e s c r i p t i o nl a n g u a g e l o o ku pt a b l e m u l t i p l e x o r r e c o n f i g n r a b l ec o m p u t i n g s y s t e mo nc h i p s y s t e mo np r o g r a m m a b l ec h i p s t a t i cr a n d o ma c c e s sm e m o r y i x 中文释义 算术逻辑单元 专用集成电路 应用编程接口 电子设计自动化 进化电路 先进先出内存 有限长单位脉冲响应 现场可编程门阵列 硬件描述语言 查找表 多路选择器 可重构计算 片上系统 片上可编程系统 静态随机存储器 图表目录 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图2 8 图2 9 图2 1 0 图2 1 1 图2 1 2 图2 1 3 图3 1 图3 2 图3 3 图3 - 4 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图4 8 图4 。9 图4 1 0 图4 1 1 图5 1 图5 2 图5 3 图5 4 图5 5 图5 - 6 图目录 通用处理器系统、可重构计算系统和专用计算系统的比较一7 可重构计算系统硬件架构及其支持环境8 可重构互连资源9 可重构计算资源9 s r a m 基本单元结构9 多可重构处理器系统互连拓扑。1 0 静态重构方式1 l 动态重构方式1 1 运行时可重构1 2 细粒度可重构逻辑块结构1 3 粗粒度可重构逻辑块结构13 几种不同的重构策略15 可重构单元r p u 和主处理器的耦合关系图1 6 遗传算法基本操作流程图2 2 算法级功能可重构数字电路框架图2 4 进化硬件实现框图2 6 基于遗传算法的自重构片上系统的设计流程2 9 基于并行乘法器的直接型结构3 3 基于并行乘法器的转置型结构3 3 字符串列处理结构3 4 基于分布式算法结构3 4 细粒度数据处理单元( d p u ) 3 5 基于( b c s e ) 算法的可重构结构3 6 可重构计算单元( p c u ) 结构3 9 新型可重构滤波器架构3 9 n 位c s a 加法器结构4 l e l m 算法实现结构4 3 4 位基于多路器的e l m 加法器4 4 自重构f i r 滤波器系统基本结构4 5 x i l i n xe d k 设计嵌入式系统基本流程4 7 基于遗传算法的自重构f i r 片上系统整体硬件结构5 0 m i c r o b l a z e 处理器内部结构图5l c o r e c o n n e e t 总线逻辑结构5 2 o p bd s c 控制器的整体结构5 3 v l i 图目录 图5 7 图5 8 图5 - 9 图5 一l o 图5 1 1 图5 1 2 图5 1 3 图5 1 4 图5 1 5 图5 1 6 图5 1 7 图6 1 图6 2 图6 3 图6 4 图6 - - o p b 基本的读操作时序图5 5 o p b 基本的写操作时序图o 5 5 专用接口模块i p i f 总体结构5 6 基于o p b 总线的i p i f 接口模块仿真波形5 7 系统基本硬件平台信息5 9 f i ri p 模块综合后网表5 9 系统硬件集成结构6 0 系统软件实现流程6 l 配置l i n k e rs c r i p t 界面6 2 设置编译器环境6 2 系统软件编译信息6 3 滤波器幅频响应仿真图6 6 s p a r t a n 3 es t a r t e rk i tb o a r d 开发系统6 7 系统布局布线后网表6 8 可重构f i r 系统硬件资源消耗6 8 自重构f i r 系统幅频响应6 9 表目录 表4 1优先数据译码表4 0 表5 1o p b 总线接口信号5 4 表5 2i p i f 内部端口表5 7 表5 3控制端口a p i 函数6 1 表6 1本文可重构f i r 滤波器芯片主要指标6 4 表6 - 2可重构f i r 滤波器性能比较6 5 v i l i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其它人已经发表或撰写过的研究成果，也不包含为 获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 签名：立4 堡篮一日期：矽：肄岁月? 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘， 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全 部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：导师签名： 眺哆 年s 月弓f 日 第一章绪论 第一章绪论帚一早 三：百下匕 本章简要介绍了可重构计算、遗传算法及相关技术的研究发展现状，对本课 题的研究意义进行了分析，概括了本论文的研究内容。 1 1 课题背景及意义 本论文研究的课题来源于国家自然科学基金项目“算法级功能可重构的数字 硬件体系结构及实现方法研究 ( n o 6 0 6 7 6 0 1 4 ) 以及四川省应用基础研究项目“基 于f p g a 动态可重构的a s i c 设计方法研究 。本论文着重研究基于遗传算法的可 重构f i r 滤波器设计及其实现。 可重构计算( r e c o n f i g u r a b l ec o m p u t i n g ) 是当前计算机系统结构领域的发展趋势 之一，它利用可重构逻辑器件的在线编程能力以硬连线逻辑高效地实现逻辑操作， 在信号处理、神经网络、加解密等领域有着重要应用【l j 。 自重构计算系统( s e l f - r e c o n f i g u r a b l e ) 是一类新型的可重构计算系统，它利用 可重构逻辑器件内嵌的控制单元对系统的重构过程进行控制，无需采用传统的板 级重构方法，具有更加高速和更加灵活的重构能力，是未来可重构计算系统的发 展趋势之。 遗传算法作为进化算法中最重要的一种理论基础是模拟生物在自然环境中的 遗传和进化过程而形成的一种自适应全局优化概率搜索算法【2 】。它提供了一种求解 复杂系统优化问题的通用框架，不依赖于实际问题的领域和种类，具有较强的鲁 棒性，可以采用相应的方式来设计遗传算法以保证其收敛到全局最优解。这样可 以克服基于迭代原理的各种数值方法对适用问题的局限以及无法保证可以收敛到 全局最优解的缺点，在可重构技术方面有相当广泛的应用前景。 滤波器设计是信号处理领域的核心问题之一。数字滤波器相比于模拟滤波器， 具有精度高、灵活性好、便于大规模集成等突出优点【3 】。数字滤波器和模拟滤波器 有同样的滤波功能，但具有不同的实现方式。数字滤波器是利用有限精度算法来 实现，精度高，稳定性强，实现灵活，在诸多方面都优于模拟滤波器。由于现在 软件无线电( s d r ) 等技术在无线通信领域的越来越多的被关注t 4 1 ，要求在滤波器 结构设计方面充分考虑到可重构的灵活性，以满足不同应用场合，同时也需要高 电子科技大学硕士学位论文 速的处理速度以满足现在实时系统的要求。 近年来，超大规模集成电路不断发展，尤其片上系统( s o c ) 、片上可编程系统 ( s o p c ) 及可重构s o c 技术发展突飞猛进。现场可编程重构可实现很多以往只有专 用芯片才能完成的功能，使得设计应用灵活方便【5 j 。 针对实现具有多功能特点的系统，传统的设计方法是将不同标准的相应电路 集成起来，系统规模是基于各种逻辑功能模块的组合。从时间轴上来看，系统中 的各个功能模块并不是任何时刻都在工作，而是根据系统外部的整体要求，轮流 或者循环地停止或工作。随着系统规模的扩大，单片电路的资源利用率反而下降。 随着需要兼容的标准越多，电路就越复杂，功耗也越大，甚至超过系统能承受的 极限。因此，系统设计要从传统的追求大规模、高密度的设计理念转向如何提高 资源利用率上来，要用有限的资源去实现更大规模的逻辑设计。 自重构片上系统不同于普通的基于可重构逻辑器件的嵌入式片上系统【6 】，它不 仅在设计时利用可重构逻辑器件的可重构属性将各种逻辑功能配置到器件上构成 系统硬件平台，而且自重构计算系统不需要借助位于可重构逻辑器件外部的控制 单元对重构过程进行监控，以及数据交互通信，而是通过集成在可重构逻辑器件 内部的控制逻辑单元如通用处理器在系统运行时生成或修改器件的配置数据文 件，然后对可重构功能模块进行重新配置。专用自重构片上系统芯片设计已成为 目前嵌入式系统设计的核心技术之一。 1 2 相关技术研究现状及意义 1 2 1 可重构技术发展概述 早在2 0 世纪6 0 年代，美国加利福尼亚大学的g e r a i de s t r i n 就提出了可重构计 算( r c ，r e c o n f i g u r a b l ec o m p u t i n g ) 的概念【7 1 ，对中大规模集成电路的可重构系统软、 硬件实现的可能性进行了研究。限于当时的技术条件，只实现了一个粗糙的原型 系统，但这种结构奠定了以后可重构计算系统的核心基础。 直到上世纪9 0 年代，可重构技术才真正开始受到人们的重视，1 9 9 3 年i e e e 出版物索引第一次出现了可重构体系结构( r e c o n f i g u r a b l ea r c h i t e c t u r e ) 这一主题关 键词。在一些年度性的国际研讨会上，关于系统可重构技术的研究成果和有关论 文数量逐年增加，数字可重构系统引起国际上数字系统设计研究者的关注。现在 采用静态闪存技术，具有高集成度的现场可编程门阵y u ( f i e l dp r o g r a m m a b l eg a t e a r r a y ，f p g a ) 为主流的可重构逻辑器件能够为各种计算和应用提供及其丰富的计 2 第一章绪论 算资源。 目前，可重构硬件结构的主要发展趋势是粗粒度硬件、异构功能和软核瞵】。伴 随可重构硬件技术的进步，一方面，互连部分的代价( 包括速度和功耗) 随之上 升，逻辑块的粒度必需相应增加才能减少所需的互连数量。另一方面，可以将复 杂的不可编程或部分可编程的功能块嵌入到芯片上，建立固定功能嵌入模块的异 质结构。此外软核部分提供了某种功能的可综合版本，由用户使用可重构硬件实 现这种功能。a l t e r a 和x i l i n x 都提供了大量的软核，包括软指令处理器n i o s 和 m i c r o b l a z e 。尽管软核的面积和速度不如硬核，但在灵活性和集成的方便性方面具 有很大的吸引力。 目前可重构计算技术已经成为当前国际研究热门课题，许多国家有关大学、 研究所都有学者加入到系统可重构技术的研究工作之中。研究方向主要分布于计 算机、集成电路、信号处理、电子设计、软件开发等各领域，从不同的角度开展 研究。国际上某些知名大学和公司还成立了专门的研究机构，如美国杨伯翰大学 的可重构计算实验室，以及日本、英国、瑞士、捷克等国一些大学的专门研究组【l 】， 这些研究机构相继得到了一些较为基础的研究成果，为进一步进行相关研究提供 了较好的示范。在国内，由于集成电路设计和工艺技术方面研究的滞后性，目前 开展的这方面的研究还不多，只有部分大学的少数人员和机构开始了初步的研究。 其中比较有代表性的包括：深圳大学、浙江大学、华中科技大学和复旦大学等。 1 2 2 遗传算法的研究现状 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是近几年发展起来的一种模拟自然界生 物进化过程与机制的自组织、自适应的人工智能技术。其理论基础是达尔文的自 然选择和门德尔的遗传变异理论【2 】。早在2 0 世纪5 0 ，6 0 年代就提出了所谓的“人 工进化系统 ，其出发点就是进化的思想可以发展为许多工程问题的优化工具，形 成了遗传算法的雏形。求解优化问题的基本思想是：把优化的目标函数解释为生 物种群对环境的适应性，把优化变量对应为生物种群的个体，由当前种群出发， 采用合适的复制、交叉、变异与选择操作生成新一代种群，反复这个过程，直到 求得合乎要求的种群停止。遗传算法作为一种随机的优化与搜索方法，它被广泛 地应用于智能学习、神经网络测试、程序自动生成、专家系统知识库维护等一系 列大规模、高度非线性、不连续无目标表达式的函数的优化。 3 电子科技大学硕士学位论文 1 2 3f i r 滤波器实现方法 f i r 数字滤波器有明显的优点：系统总是稳定的、易于实现线性相位及允许设 计多通带( 或多阻带) 滤波器，因此f i r 滤波器在数字信号处理中得到广泛的应用。 当前f i r 滤波器的实现主要采用d s p ( d i g i t a ls i g n a lp r o c e s s i n g ) 处理器、面向 d s p 的各类专用a s i c 芯片及f p g a ( f i e l dp r o g r a m m a b l eg a t e 岫) 的方法【9 】【1 0 1 。 d s p 处理器能够通过软件设计实现适用于不同功能要求的应用，但其固定的 硬件结构特别不适合于当前许多要求能进行结构特性随时变更的应用场合，即所 谓可重构型的d s p 应用系统，如软件无线电、医用设备、导航、工业控制方面。 至于在满足速度要求方面，由于采用了顺序执行的c p u 架构，d s p 处理器运算速 度相对较慢。 而面向数字信号处理的各类专用a s i c 芯片虽然可以解决并行性和速度的问 题，但是高昂的开发设计费用、耗时的设计周期及不灵活的纯硬件结构，使得用 于数字信号处理的 a s i c 解决方案具有很大的局限性。 用f p g a 来实现数字信号处理可以很好地解决并行性和速度问题，而且其灵 活的可配置特性，使得f p g a 构成的d s p 系统易于修改、易于测试及硬件升级。 1 2 4 课题研究意义 传统的可重构电路实现方式是由外部产生硬件配置数据，只能够通过器件的 外部配置端口例如j t a g 端口、s e l e c t m a p 端口，使用编程电缆对目标器件进行配 置从而实现逻辑功能变换。传统可重构电路自身不能产生特定功能所需的配置数 据。 算法级功能可重构电路是一种新型的可重构数字硬件体系。它能在外界条件 和参数的刺激下，自动地、有机地发生变形、进化，形成具有某种意义的智能硬 件电路。能够不借助外部运算，而是通过自身的进化运算得到最终的硬件配置数 据，并由内部配置端口实现目标功能电路。为硬件设计自动化、并最终实现硬件 自组织、自适应和自修复开辟了一条新途径【l 。 进化电路提供了一种有效的实现算法级功能可重构电路的方法。它是一种完 全硬件的自治独立系统。将整个演化过程包括遗传操作、选择、适应值评测都在 硬件上实现，从而形成一个完全自治的独立系统。但是进化硬件由于采用全硬件 形式来实现遗传算法，也存在着明显的缺陷，主要表现为以下几点： ( 1 ) 由于遗传算法所采用的种群并行搜索方式，虽然采用硬件实现可以提高算 4 第一章绪论 法的执行速度，但是需要采用很复杂的数据控制方法，使得进化硬件的设 计具有很大难度。 ( 2 ) 全硬件实现的遗传算法不利于特定问题的进化模型和染色体编码方式。固 化的算法实现结构使得在处理不同具体问题上，算法执行的效率不同。 ( 3 ) 由于遗传算法核心是根据目标函数选择适应度函数，用固化的硬件电路来 实现适应度函数的计算，大大地降低了应用的灵活性。 本文将遗传算法可以有效解决系统最优化问题的思想应用于可编程片上系统 ( s o p c ) 中，实现了基于遗传算法的自重构片上系统。这种系统具有以下特点： ( 1 ) 内嵌处理器作为重构控制单元。系统不借助外部运算，而是在外界条件和 参数的刺激下，由内嵌处理器实现的进化运算得到最终的硬件配置数据。 ( 2 ) 从片上系统内部直接对可重构i p 核功能模块进行配置。这使得在器件重 构过程中，配置数据文件无需经过板级端口( 例如j t a g 端口) 就能够被 配置到器件上，实现了片内自重构，缩短了重构过程的时间延迟，减少了 系统为板级重构准备的相关外设。 ( 3 ) 通过内嵌处理器实现遗传算法的方式，使得算法不会像进化硬件那样局限 于特定问题的进化模型和染色体编码方式，能够针对不同的应用，采用不 同的遗传计算模式。本文所提出的自重构系统中，遗传算法是针对具有可 重构功能结构的i p 核单元进行染色体编码操作，可以通过优化设计可重 构i p 核单元，相应减少配置位所需的染色体编码数目，从而减小了遗传 算法运算量，加快功能进化设计和实现的速度。 本课题的研究重点不仅在于设计可重构f i r 数字滤波器本身，而是通过对可 重构的f i r 数字滤波器系统的设计，对基于遗传算法及其它进化理论的新型功能 级可重构电路的体系构架等构成的可重构数字硬件设计及实现方法进行研究。 1 3 论文主要研究内容 本论文的主要研究工作和创新特色如下： ( 1 ) 阅读关于可重构系统方面的资料，了解目前国际上在此方面的研究进展， 掌握可重构系统的设计思想及可重构性的实质； ( 2 ) 对遗传算法及其改进算法进行了研究，分析了现有的典型算法级功能可重 构电路结构的特性，针对其中的不足，结合嵌入式系统的特点，提出了一 种基于遗传算法的可重构片上系统的设计方法； 5 电子科技大学硕士学位论文 ( 3 ) 对现有的f i r 的算法及硬件实现结构进行分析，在可重构f i r 处理器的结 构设计上进行了深入地研究工作。以可重构性为目标，提出一种粗粒度的 新型高速可重构的f i r 处理器结构； ( 4 ) 对f i r 滤波器优化设计方法进行研究，将遗传算法应用于f i r 优化设计中； ( 5 ) 在算法级自重构片上系统设计方法的基础上，确定自重构f i r 片上系统的 配置方案及整体结构，进行系统部件的选型与软硬件设计，实现了基于遗 传算法的自重构f i r 片上系统。通过可重构f i r 系统的设计与实现验证了 本论文所提设计方法的有效性，也体现出了自重构计算系统具有的重构性 能优势。 1 4 本论文的安排 第一章为绪论，主要介绍本课题的来源及研究意义，相关技术的发展和研究 现状，以及论文的工作和内容安排并介绍了课题的主要研究内容。 第二章介绍了可重构技术的概念、可重构计算系统的硬件基础、分类及可重 构技术的应用领域等 第三章对广泛用于算法级可重构电路设计中的遗传算法基本思想，特点及其 改进算法实现流程作简要介绍，分析了现有的典型算法级功能可重构电路结构的 特点，针对其中的不足，提出了一种基于遗传算法的自重构片上系统的设计方法。 第四章提出了一种新型的可重构f i r 滤波器总体架构，并详细描述了各个模 块的设计，为后面实现自重构f i r 片上系统打下基础。 第五章具体设计与实现了自重构f i r 片上系统。首先确定了所提出的可重构 系统的重构策略，按照算法级可重构的需求，进行系统部件的选型，搭建了系统 硬件平台，最后利用遗传算法进行了f i r 滤波器的优化设计，实现了可重构f i r 滤波器。 第六章分别对已设计的可重构f i r 滤波器i p 核结构进行了性能分析，并且对 所设计的遗传算法的有效性进行了验证与算法仿真，最后对整体基于遗传算法的 可重构f i r 片上系统进行了性能测试与分析。 第七章为结论和展望。陈述了本论文所做工作的价值和作用，并指出下一步 的工作与以后的研究方向。 6 第二章可重构技术概述 第二章可重构技术 本章介绍了可重构计算技术的一些基本概念，包括可重构技术的概念、可重 构计算系统的硬件基础、可重构系统的分类和可重构技术的应用领域等。 2 1 可重构计算简介 1 9 6 3 年g e r a i de s t r i n 提出了重构计算的概念，即“固定+ 可变结构计算机， 其核心是由非柔性但可编程的处理器和柔性的由程控重构的数字逻辑部件两部分 组成【7 1 。这种结构奠定了以后可重构计算系统的核心基础。 所谓的可重构计算【1 2 1 ( r e c o n f i g u r a b l ec o m p u t i n g ，r c ) 简单来说就是对结构 固定的硬件计算平台，根据应用的不同需要进行配置，并在辅助设备包括外围控 制硬件和软件的协同下完成相应的计算任务，达到接近专用硬件设计的高性能。 具有可重构计算特征的系统称为可重构计算系统【l3 1 。 我们可以把计算功能的实施看成是由时间和空间构成的二维结构。传统的微 处理器在空间维上是固定不变的，而在时间维上是可变的或者说是可编程的。处 理器功能能够发生改变，是因为其时问维上的可变性。a s i c 的特点是功能固定， 即空间维和时间维都是不可变的。可重构计算系统是一种新的计算体系结构。它 的架构介于通用处理器和a s i c 之间，并且综合了二者长处。它通过对可重构设备 进行配置，可以使之由一个通用的计算平台转化为一个专用的硬件系统，以完成 具体的计算任务，相当于计算任务同时在时间和空间上展开，显示出了应用的灵 活性和很高的计算性能【l4 1 。三种不同的计算系统的架构比较如图2 1 所示。 通用处理器系统可重构计算系统专用计算系统 图2 1通用处理器系统、可重构计算系统和专用计算系统的比较 7 电子科技大学硕士学位论文 典型的可重构计算系统结构包括可重构计算部件( 提供可编程逻辑) 、运行控制 部件( 提供运行控制机制) 和运行时的软件环境( 涉及任务及数据的动态调度) u 副，如 图2 2 所示。如同可重构计算部件要随着应用要求的不同而进行不同配置一样，运 行控制系统也会因为其计算方式的不一样而不同，因此这样的体系结构需要有一 套完整的开发系统来支持架构的整体配置。其中包括设计方法( 包括应用描述语 言、设计流程) 、编译子系统( 将高层的应用描述转化为对硬件平台的配置数据) 。 应用任务 l 软件环境 l 配置管理 i 调度控制 开发系统 h d l 编译器 c a d 工具 可重构计算系统支持环境 图2 - 2可重构计算系统硬件架构及其支持环境 2 2 可重构层次分类 可重构的产生是为解决硬件结构与应用的不匹配。按解决问题的层次不同， 可将可重构分为电路级可重构，指令级可重构和芯片级可重构三种类型1 1 6 1 。 2 2 1 电路级重构 从基本门级构成重构计算系统，即将逻辑部件的功能用可编程器件实现，当 应用要求改变时，通过改变可编程器件的配置数据来改变其功能。这种重构也称 为门级可重构。 改变或重构可编程硬件的逻辑功能通常是通过两种方式来实现的：一种是重 构互连资源，包括传输门方式和多路选择器等方式；另一种是重构数据处理单元， 典型的包括算术逻辑单元( a l u ) 、查找表( l u t ) 和多路选择器( m 1 x ) 等方式。 通过控制传输门来重构互连资源的典型例子如图2 3 左所示( 这在现场可编程 门阵列( f p g a ) 中用得最多【 1 1 1 8 1 ) ，编程位控制传输门的连通或者断开来重构联 8 第二章可重构技术概述 机通路；通过控制m u x 来重构互连资源的典型例子如图2 3 右所示，编程位控制 m u x 在处理单元的不同输入或者不同输出之间进行选择。 卜 图2 - 3可重构互连资源 在a l u 处理单元结构中，作为控制信号的编程位可以决定一个算术处理单元 对输入信号执行何种逻辑运算，而在l u t 结构中，配置信息本身就形成单元计算 结果( 通过改变2 n 个编程位，l u t 几乎可以实现n 个输入信号的任何函数) 。除此 之外，还可以基于m u x 来产