（计算机系统结构专业论文）基于fpga的hmmer加速系统的设计与实现.pdf

c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo f m e n g t h e d e s i g na n di m p l e m e n t a t i o no f h m m e ra c c e l e r a t i o ns y s t e mo nf p g a c a n d i d a t e ： s u p e r v i s o r ： a c a d e m i cd e g r e ea p p l i e df o r ： s p e c i a l t y ： d a t eo fs u b m i s s i o n ： d a t eo fo r a le x a m i n a t i o n ： u n i v e r s i t y ： s u ny a n t e n g p r o f g ug u o c h a n g m a s t e ro f e n g i n e e r i n g c o m p u t e rs y s t e m so r g a n i z a t i o n j a n u a r y ，2 0 1 0 m a r c h ，2 0 1 0 h a r b i ne n g i n e e r i n gu n i v e r s i 够 l “ 乙 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献的引用 已在文中指出，并与参考文献相对应。除文中己注明引用的内 容外，本论文不包含任何其他个人或集体已经公开发表的作品 成果。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本人完全意识到本声明的法律结果由本人承 担。 作者( 签字) ：勰、廷嚆 日期： 力如年弓月j ) 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 为哈 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：确、延睛导师( 签字) ：专页田昌 日期：。fq 年弓月芦2 。年s 月l 譬日 台 二 哈尔滨t 程大学硕十学位论文 摘要 h m m e r 是广泛应用的生物信息学开源软件工具包，它提供了对基因和蛋 白质进行分类与匹配的一系列工具集。p 7 v i t e r b i 是h m m e r 的核心函数，由 两层嵌套循环实现了计算密集型算法p l a n 7h m m 。虽然算法具有很强的并行 潜力，但受限于c p u 的串行本质，h m m e r 在常规平台上运行十分耗时。 f p g a 技术近年来有了巨大的发展，基于f p g a 和c p u 的异构系统得到 了学术界的广泛关注，大量的学者正在对其计算能力、适用范围、开发流程、 耦合方式、应用前景进行广泛的研究。f p g a c p u 异构系统可以发掘p l a n 7 h m m 算法的并行性，目前主要有两类：( 1 ) 并行执行多个核心函数，( 2 ) 简化运算以实现对单个核心函数的并行运算。后者对单个函数进行并行运算， 但运算的简化导致精度的下降。因此，本文在不简化运算的前提下提出了一 种可以适应p l a n 7h m m 的数据依赖特性的基于脉动阵列的并行运算结构，并 且使用p c ie x p r e s s 总线以松耦合方式实现了加速系统。 本文首先总结了对h m m e r 进行加速的常用方法并分析其优缺点，并选 择并行度较高、加速潜力较大的c p u f p g a 协同工作方式作为加速方式；分 析了f p g a 实现高性能计算的可行性和c p u f p g a 耦合方式的优缺点，并选 择外部总线方式作为本文的耦合方式。其次，介绍了h m m e r 采用的p l a n 7 h m m 的基本原理；对h m m e r 进行性能分析，从而确定对p l a i l 7h m m 进行 实现的p 7 v i t e r b i 函数为系统的核心函数。然后，提出了适合数据依赖特性的 并行运算的脉动结构，提出了并行数据提供方案来解决数据的并行访问，提 出了运算切分机制来解决运算单元规模与计算规模不匹配的问题，提出了“自 动重算 机制来解决阻碍计算并行的“回边”问题。再次，在f p g a 实现过 程中，应用并行化、流水化和参数化技术提高了系统的吞吐率和可移植性。 最后，对系统的性能进行了分析并提出本文存在的不足与改进的方向。 实验表明，本文所设计的系统具有很高的效率和很好的可移植性。当采 用v i r t e x511 0 t 芯片时，每个运算单元的平均加速比相对于奔腾4 平台为4 4 倍、相对于酷睿2 平台为3 7 倍，系统的平均加速比相对于奔腾4 平台为1 0 9 倍、相对于酷睿2 平台为9 2 倍。 关键词：f p g a ；外部总线耦合；脉动阵列；p l a n 7h m m - 哈尔滨工程大学硕士学位论文 萱暑宣置宣宣i i ；i ；暑皇i i 置暑暑昌置宣昌置暑i 毒宣萱葺i i i i i i i i 置暑宣置誓i li | 葺暑葺寓i i i i 昌；篁；i i 置宣宣宣葺宣萱暑i 葺 a b s t r a c t h m m e ri saw i d e l yu s e db i o i n f o r m a t i c so p e ns o u r c es o f t w a r et o o l k i tt h a ti s c o m p o s e do fa s e r i a lo ft o o ls e t sw h i c hc a nb eu s e df o rc l a s s i f i c a t i o na n da n a l y s i s o fg e n i ea n dp r o t e i n p 7 v i t e r b ii st h ek e m e lf u n c t i o no fa m m e r ，w h i c hi s c o m p o s e d o ft w on e s t e d l o o p s t h a t i m p l e m e n tp l a n 7h m m ，at y p i c a l c o m p u t e i n t e n s i v ea l g o r i t h m a l t h o u g hp l a n 7h m mh a sh i g h l yp o t e n t i a lf o r o p e r a t i o np a r a l l e l i s m ，l i m i t e db yt h ec h a r a c t e ro fs e r i a li n s t r u c t i o ne x e c u t i o n , i ti s v e r yt i m e - c o n s u m i n gw h e nr u n n i n gh m m e r o nc p ub a s e dt r a d i t i o n a lp l a t f o r m s f p g at e c h n o l o g yh a sb e e nr a p i d l yd e v e l o p e dr e c e n t l y ，a n di t sp r o c e s s i n g s p e e da n dc h i pa r e ah a v er e a c h e dt h er e q u i r e m e n to fa p p l i c a t i o na c c e l e r a t i o n f p g a c p uh e t e r o g e n e o u sc o o p e r a t i v es y s t e m sa r eb e e nw i d e s p r e a dc o n c e r n e d ， a n di t sc o m p u t a t i o n a la b i l i t y ，a p p l i c a b l es c o p e ，d e v e l o p m e n tp r o c e s s ，c o u p l i n g m e t h o d s ，a n da p p l i c a t i o np r o s p e c ta r eb e e nr e s e a r c h e dw i d e l y t h e r ea r et w o k i n d s o ff p g a - c p uh e t e r o g e n e o u ss y s t e mt h a tc a l lb eu s e dt o e x p l o r et h e p a r a l l e l i s mo fp l a n 7i - - i i v i m ：( 1 ) p a r a l l e le x e c u t i n gm u l t i p l ek e r n e l s ，a n d ( 2 ) p a r a l l e lc a l c u l a t i n gs i m p l i f i e dk e r n e l n el a t t e rh a sf i n eg r a n u l a r i t ya n db e t t e r p e r f o r m a n c e ，b u tt h es i m p l i f i c a t i o nr e s u l t s i nl o s so fa c c u r a c y t h i sp a p e r p r o p o s e das y s t o l i ca r r a yb a s e da r c h i t e c t u r et h a tj u s t i f yd a t ad e p e n d e n c yo fp l a n 7 h m m ，a n da ne x t e r n a lb u sc o u p l e ds y s t e md e s i g nu s i n gp c ie x p r e s sb u s a f t e ra n a l y z i n gt h es t r u c t u r ea n dd a t ad e p e n d e n c yo fp l a l l 7h m m ，as y s t o l i c a r r a yb a s e da r c h i t e c t u r ei sp r o p o s e d ：t h ed a t as t r e a mo fs y s t o l i ca r r a yd e a l sw i t h d a t ad e p e n d e n c yb e t w e e nn o d e s ；ap a r a l l e ld a t ap r o v i d i n gu n i ti su s e dt op r o v i d e c o h e r e n tm a t c h i n gs c o r e ；ac a l c u l a t i o nd i v i s i o nm e c h a n i s mi su s e dt od i v i d eh u g e o p e r a t i o ni n t os m a l ls l i c e s ；aa u t o - r e c a l c u l a t i o nm e c h a n i s mi sd e v e l o p e dt o h a n d l et h ef e e d b a c ke d g et h a th i n d e r st h ep a r a l l e l i s m o p e r a t i o np a r a l l e l ，p i p e l i n e ， a n dp a r a m e t e r i z a t i o no p t i m i z a t i o nt e c h n i q u ea r ep r o p o s e df o rh i g hp e r f o r m a n c e a n dg o o dp o r t a b i l i t yw h e no nf p g a i m p l e m e n t a t i o n e x p e r i m e n t a lr e s u l t ss h o wt h a tu s i n gav i r t e x5l10 tc h i p s e t c o m p a r e dt o p e n t i u m4a n dc o r e2d u op l a t f o r m s ，a c c e l e r a t i o nr a t i op e rp r o c e s s i n gu n i ta r e4 4 a n d3 7t i m e sr e s p e c t i v e l y ，t o t a ls y s t e ma c c e l e r a t i o nr a t i oa l e10 9a n d9 2t i m e s r e s p e c t i v e l y k e yw o r d s ：f p g a ；e x t e r n a lb u sc o u p l e d ；s y s t o l i ca r r a y ；p l a n 7h m m 哈尔滨工程大学硕士学位论文 目录 第1 章绪论l 1 1 本课题的研究目的和意义。1 1 2 国内外研究发展现状2 1 3 本论文的主要工作4 1 4 本论文的组织结构。5 第2 章背景知识介绍6 2 1f p g a 简介6 2 2f p g a 与高性能计算9 2 2 1f p g a 的计算性能9 2 2 2f p g a 应用于高性能计算的挑战1 2 2 3 加速系统的耦合方式。1 4 2 4 本章小结16 第3 章h m m e r 算法的基本原理1 7 3 1m o t i f s 和p r o f i l e 分析1 7 3 2h i d d e nm a r k o vm o d e l 1 9 3 3p r o f i l eh i d d e nm a r k o vm o d e l 2 l 3 4p l a n 7h m 忑嗄2 3 3 5 本章小结2 4 第4 章系统的设计与实现2 5 4 1 算法分析2 5 4 1 1 程序性能分析2 5 4 1 2p 7 v i t e r b i 函数2 7 4 1 3 节点数据相关分析3 1 4 2 系统结构与设计3 2 4 2 1 脉动结构设计一3 2 4 2 2 并行数据提供单元设计3 4 4 2 3 计算的拆分3 6 4 2 4 自动重算3 7 4 2 5 系统整体结构4 0 4 3f p g a 实现41 4 3 1 运算的并行化4 1 4 3 2 运算的流水化4 3 4 3 3 参数化4 5 哈尔滨工程大学硕士学位论文 4 4 本章小结4 8 第5 章系统的仿真与测试4 9 5 1 性能分析4 9 5 1 1 资源占用情况4 9 5 1 2 软硬件运行时间5 1 5 1 3 核心加速效果5 3 5 1 4 整体加速效果5 7 5 2 存在的不足与改进5 7 5 3 本章小结5 8 结 论5 9 参考文献6 0 攻读硕士学位期间发表的论文及取得的科研成果6 3 致谢6 4 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 本课题的研究目的和意义 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 ) 是一种可以在出厂后被重新配置 的集成电路，能够实现任何a s i c 可以实现的逻辑功能。与a s i c 相比f p g a 具有在产品交付后还可以对产品的功能进行更新、重复开发代价低等优势， 因而在数字信号处理、软件无线电、a s i c 原型设计、医学图像处理、计算机 视觉、语音识别、密码学、生物信息学、计算机硬件模拟等领域中有很好的 应用【l j 。随着半导体制作工艺不断追随摩尔定律向前发展，f p g a 的芯片容 量越来越大，运行速度越来越快，完全有能力完成对整个应用算法的加速， 为基于f p g a 的加速系统的应用提供了客观条件。 f p g a 设计具有较高的并行性，但其运行频率一般比c p u 低一个数量级。 所以，需要根据代码的并行性和运算的类型进行相应的取舍，加速效果好的 代码在f p g a 中实现，余下的代码在c p u 中实现。对应用程序的加速一般需 要由f p g a 与c p u 组成的混合系统来完成：并行性高的代码转化为f p g a 中的硬件电路来实现，串行性高或逻辑复杂的代码由c p u 来执行。 由于c p u 的串行特性，计算密集型应用在常规平台上性能不佳，因而该 类应用通常需要在并行、混合系统中实现。为了得到较好的并行性，常规并 行、混合系统需要大量的节点参与系统的构建，因而硬件成本高、功耗大、 维护成本高。此外，由于这些系统需要保持一定的通用性，对于某一应用而 言，系统的计算资源会有一定的浪费。由于在f p g a 中实现的加速模块具有 很高的并行性和专用性，同时f p g a 器件具有较低的功耗，因而f p g a c p u 异构系统具有很高的资源利用率与性能价格比。 f p g a 设计的开发过程远快于a s i c 的开发过程，所以f p g a c p u 异构 系统可以快速的实现加速系统。由于f p g a 具有可重新配置的能力，所以还 可以对加速系统进行灵活的升级与维护。综上所述，基于f p g a 的应用算法 的加速系统具有很高的研究价值与商业价值。 哈尔滨。i ：稃人学硕十学f 7 = 论文 本课题来自哈尔滨工程大学计算机科学与技术学院与英特尔( 中国) 研究 中一t l , ( i n t e lc h i n ar e s e a r c hc e n t e r ) 通讯技术实验室合作开展的异构多核的可 重构计算体系结构研究项目，主要完成在异构系统中实现对h m m e r 的加速。 h m m e r l 2 , 3 】是用p h m m ( p r o f i l eh i d d e nm a r k o vm o d e l s 4 j ) 来进行生物信息学 分析的开源生物信息学软件包，主要用来对蛋白质或氨基酸序列的模式进行 查询。h m m e r 的应用十分广泛，共有1 6 种针对于不同操作系统的代码及多 种不同运行环境下的衍生版。本文所使用的h m m e r 软件版本为2 3 2 ，最新 的软件版本为3 0b e t a 版，j 下处于测试阶段。 本课题的研究目的是：1 ) 分析h m m e r 核心算法的数据依赖关系，提出 一种对其进行并行运算的结构；2 ) 在c p u f p g a 异构系统中以合适的耦合 方式实现该结构，完成对h m m e r 应用的加速；3 ) 使设计具有参数化功能， 通过参数来控制设计的规模，从而可以将设计移植到不同规模的芯片中。本 课题的研究意义是：1 ) 完成对h m m e r 应用的加速：2 ) 提出了并行运算结 构和相应的数据提供模块为嵌套循环的并行实现和数据依赖的满足提供了参 考；3 ) 提出了一种基于v h d l 语言的参数化方案；4 ) 实践了使用c p u f p g a 异构系统对应用进行加速的各个环节。 1 2 国内外研究发展现状 由于h m m e r 的重要性与运算复杂性，国内外有大量的学者在不同的层 面上采用并行技术对h m m e r 进行加速。目前存在的系统主要包括：常规c p u 系统、同构异构集群、g p u + c p u 异构系统、f p g a + c p u 异构系统。 ( 1 ) 常规c p u 系统 常规c p u 系统的并行性主要体现在通过s i m d ( s i n g l ei n s t r u c t i o n m u l t i p l ed a t a ) 指令集对数据进行向量运算。常见的s i m d 技术有a l t i v e c p j ， 3 d n o w ! 6 】和s s e 7 1 分别在p o w e r 系列，i n t e l 系列和a m d 系列c p u 中实现。 采用s i m d 技术【8 ，9 1 只需要对应用的软件实现进行修改便可以提高软件的运行 速度。但是，由于编译器对s i m d 指令支持不完善，通常需要使用汇编指令 对算法的源码进行修改，操作难度较大。同时，由于s i m d 指令的并行度与 操作类型有限，因而该方法的加速效果和适用性十分有限。 2 哈尔滨t 程大学硕十学何论文 ( 2 ) 同构异构集群 集群系统由大量通过专用总线相接的计算节点组成，把计算任务拆分到 多个节点中进行计算，具有很高的并行性。m p i ( m e s s a g ep a s s i n gi m e f f a c e ) 【lo 】是并行计算机和集群系统常用的软件编程接口，需要由程序员手工完成算 法的m p i 实现。使用更多的节点、将任务分解为更小的单元可以进一步提高 并行性，但加速比不j 下比于节点数目。单元规模的越小，节点间通信的开销 就越大，所以集群系统所能使用的节点个数和对应用的加速效果都有相应的 极限值。此外，集群系统有很高的功耗、维护成本高，能源利用率低。 m p i h m m e r l l1 1 和陈军【1 2 1 都采用集群对h m m e r 进行加速。 ( 3 ) g p u c p u 异构系统 g p u ( g r a p h i c sp r o c e s s i n gu n i t ) 是为图形显示所开发的专用运算芯片， 可以高效的进行图像的处理与渲染。为了满足图形显示的需要，g p u 具有高 度并行化的结构和高速的存储系统，可以对多组数据进行向量运算，具有很 高的内存带宽和计算能力。同时为了满足图像处理与渲染的需要，g p u 生来 就具有很强的浮点计算能力。将算法或算法的部分操作映射到g p u 的并行运 算架构中( 如n v i d i a 公司的c u d a ) 就可以使用g p u 的并行计算能力进行 算法加速。但是，目前g p u 只具备数据处理能力，不具备复杂的程序控制能 力，因而对算法的完整实现需要g p u 与c p u 组成异构系统：g p u 完成数据 的运算，c p u 完成事务的处理。此类系统也不需要额外的硬件设备，充分利 用了g p u 的富足计算能力。与使用s i m d 技术相似，设计者并不能对g p u 的结构进行定制，缺少灵活性与通用性，加速能力受限于g p u 的规格与结构。 c l a w h m m e r b 3 1 采用了该系统对h m m e r 进行加速。 ( 4 ) f p g a c p u 异构系统 f p g a 具有很高的可定制性与并行性，同时也具有较快的运行速度。可 以通过设计专用的硬件电路来实现对算法的加速。但是，因为f p g a 具有硬 件电路的特性，最适合算法的运算部分，所以也需要在c p u 的补充与协调下 才能完成对应用的加速。以f p g a 中实现的运算的粒度为依据可以将加速系 统分为“粗粒度系统”、“细粒度系统 和“混合系统”。 1 ) 粗粒度系统 “粗粒度系统以任务为并行操作的基本元素，同时运行多组任务，从 3 哈尔滨工程大学硕士学位论文 而提高系统的吞吐率。该系统还可以实现多线程应用，即同时运行多种不同 的任务来加快应用的运行。以任务为并行执行的对象操作比较容易，任务的 实现不需要具有并行性，只需要关注任务之间的相关性、满足多任务的数据 与控制需求。高i o 带宽是该类系统的主要特性，加速比受限于系统所能提供 的最大带宽。同时，虽然系统吞吐率有所提升，但无法提高单个任务的执行 速度。o l i v e t l l 4 1 所采用的方案在一个f p g a 芯片中实现了多套匹配单元，通 过共享多个h m m 模型的公用部分降低了系统对i o 带宽的需求。 2 ) 细粒度系统 “细粒度系统 并行执行一个任务的多组计算，从而减少单个任务的运 行时间。该类系统通过f p g a 内部数据通路进行数据的交互，对i o 带宽的 需求要远小于“粗粒度系统 ，有更大的加速空间【1 5 , 1 6 。其加速性能取决于 硬件设计的架构是否具有高的并行性和f p g a 芯片中是否有足够的资源。但 是，完成对单一任务的加速要求发掘算法内部的并行性，需要为算法设计相 应的并行架构。“细粒度系统”的开发难度要高于“粗粒度系统 。 3 ) 混合系统 “混合系统 混合使用多种载体进行加速，如嵌入式c p u 、d s p 、f p g a 等。“混合系统”一般采用片上网络( n o c ) 将各种硬件加速单元组合成异 构可重构系统( s o p c ) 。“混合系统”通过复杂的模型进行全局调度，可以 加速复杂的大型应用。混合系统所采用的f p g a 加速单元可以采用以上两种 组织形式，可以作为嵌入式c p u 的协处理器，也可以作为总线上独立的设备。 “混合系统”的加速效果取决于对数据和计算的合理分配，可以使用人工智 能算法进行多次迭代。m p i h m m e r b o o s t 1 7 】结合了m p i 与f p g a 两种技术。 1 3 本论文的主要工作 本论文的主要研究内容由以下几部分组成： ( 1 ) 对使用f p g a 进行h m m c r 加速的相关问题进行研究 对现有h m m e r 加速系统的基本结构进行分类，分析其加速手段、适用 范围及各自的优缺点；分析f p g a 的计算能力并总结其应用于高性能计算所 面临的挑战；总结f p g a 与c p u 的耦合方式并分析其加速能力及优缺点。 4 哈尔滨f ：稃人学硕十学位论文 ( 2 ) 对h m m e r 进行分析与研究 介绍h m m e r 的基本原理并对h m m e r 进行性能分析：介绍h m m e r 的核 心算法并对其数据依赖进行分析；选择了适合算法特性的耦合方式。 ， ( 3 ) 提出了一种细粒度加速模型并在f p g a 中实现 提出了基于脉动阵列的细粒度并行运算结构并为该结构设计相应的控制 模块和存储模块：通过“自动重算”机制解决阻碍计算并行的“回边”问题， 通过并行数据提供方案解决数据的并行访问问题，通过运算切分机制解决运 算单元规模与计算规模不匹配的问题；在f p g a 实现过程中通过并行化、流 水化技术提高系统的运行频率，通过参数化使系统具有可移植性。 1 4 本论文的组织结构 本论文的组织结构如下： 第1 章：对本课题的选题背景、目的、意义和国内外当前的研究现状进 行了综述； 第2 章：对f p g a 进行简单介绍；分析f p g a 的计算性能并总结其应用 于高性能计算领域所面临的问题：对基于f p g a 与c p u 的耦合方式进行分析。 第3 章：对h m m e r 算法中所应用的p r o f i l eh m m 原理进行介绍、分析， 选择适合用于h m m e r 加速的耦合方式。 第4 章：对算法进行性能分析及数据相关性分析；介绍系统的基本结构 与设计原理：介绍系统的f p g a 实现时所采用的优化方法。 第5 章：对系统进行仿真和性能分析并指出存在的不足与改进； 最后，对本论文的工作进行总结并指出本课题的进一步研究方向。 哈尔滨工程大学硕士学位论文 2 1f p g a 简介 第2 章背景知识介绍 f p g a 是由r o s sf r e e m a n 研制【l 驯的通过s r a m 进行逻辑功能编程的i c 器件。f p g a 主要由输入输出块i o b ( i n p u t o u t p u tb l o c k ) ，可配置逻辑块 c l b ( c o n f i g u r a b l el o g i cb l o c k ) 、可编程互连p i ( p r o g r a m m a b l ei n t e r c o n n e c t ) 三部分组成【l 刿。i o b 是芯片与外界电路的接口部分，用于完成不同电气特性 下对输入输出信号的驱动与匹配：c l b 是芯片逻辑功能单元部分，通过对 c l b 进行配置可以定制芯片的功能，是f p g a 最主要的资源；p i 是f p g a 各 种资源互联的媒介。现代f p g a ( 如图2 1 所示) 还整合了各种专用资源，如 存储器、算数运算器、d s p 等，从而进一步提高f p g a 的处理能力。 _ _ _ 曩曩口曩口 图2 1f p g a 结构 本文主要以x i l i n x 的v i r t e x 5 芯片【2 0 1 为例对f p g a 各个部分进行介绍。 c l b 是f p g a 逻辑功能的载体，采用e x p r e s sf a b r i c 技术的x i l i n xv i r t e x 5 芯 片的c l b ( 如图2 2 所示) 由2 个s l i c e 组成，1 个s l i c e 由多个l u t ( l o o p u p 6 置墨叠墨 置置墨曩 哈尔滨工程大学硕士学位论文 宣宣i i i 置i 葺i i 暑i 暑昌葺昌置宣i 宣暑昌i i | 葺暑置i i i i 宣葺i ii ii l l m t i _|宣毒 t a b l e ) 组成。l u t 由s r a m 组成，提供输入到输出的功能映射。s r a m 的 地址为l u t 的输入，内容为l u t 的输出。逻辑功能的配置实质上就是对l u t 中s r a m 内容的配置。自从1 9 世纪8 0 年代f p g a 问世以来，f p g a 一直使 用经典的4 输入l u t ，目前先进的高端f p g a 普遍采用6 输入u j t 。6 输入 l u t 可以实现更广泛的功能，具有更低的功耗，在关键路径延迟和芯片大小 之间的平衡方面有很好的表现。 图2 2v i r t e x 5c l b 结构 f p g a 的开发过程一般如图2 3 所示，包括设计、综合、实现、仿真、下 载与测试等主要步骤。 ( 1 ) 设计 设计环节完成算法到硬件设计的初步转换。该过程目前一般情况下由开 发人员手动完成，也可以由自动化编译工具自动完成。硬件设计的描述方法 有硬件描述语言和原理图输入两种方法。原理图直观且易于仿真，但可移植 性差；硬件描述语言比原理图更具有灵活性与可维护性，效率较高。自动化 编译工具一般将算法描述语言转换成硬件描述语言，目前该技术一般将算法 映射为规整、固定的硬件结构模型，只能转换功能简单的算法。但自动化编 译( 设计) 工具是现代f p g a 应用中很重要的环节。 ( 2 ) 综合 7 哈尔滨工程大学硕士学位论文 综合环节将高抽象层次的硬件设计转化成门级网表文件。网表文件是用 与门、非门、r a m 、触发器等基本逻辑单元对电路功能进行描述的文件，具 有统一格式标准，用于描述硬件系统的功能。该过程由综合工具自动完成， 可以使用多种优化方式和不同的综合工具以提高综合质量。经由不同的综合 工具生成的同一个硬件设计文件的网表文件内容不相同，但具有相同的功能。 ( 3 ) 实现 实现环节包括翻译、映射、布局与布线三个部分。翻译将网表文件转换 成x i l i n x 特有的底层结构和硬件原语。映射结合指定芯片的资源类型将翻译 后的结果映射到芯片结构上( 如l u t 、f f 等) 。布局与布线按照相应芯片的 结构将映射的结果布局到f p g a 芯片上，并将各种资源互联起来，同时根据 用户指定的约束( 如面积、时序等) 对结果进行约束。该过程与f p g a 的结 构密切相关，一般由芯片厂商提供的专用工具执行。 ( 4 ) 仿真 设计、综合、实现三个环节都有与之相对应的仿真阶段，分别为行为级 仿真、后综合仿真、后翻译仿真、后映射仿真、后布局布线仿真。其中，后 四种仿真通常称为后仿真。行为级仿真在h d l 级别上对设计的功能进行仿 真，仅能验证设计是否与预期相符。后布局布线仿真所包含的时延信息最全， 最贴切的反映设计在f p g a 中实际运行的结果，是必需要进行的仿真过程。 ( 5 ) 下载与测试 在后仿真正确之后就可以通过f p g a 设计工具生成比特流文件。比特流 文件是f p g a 的配置文件，每个设计都有与其功能相符合的比特流文件。将 比特流文件下载到f p g a 后，就可以在真实环境中实际运行设计，并采用相 应的测试方法对系统的功能及可靠性等方面进行测试。 8 困 马设计 囤日圈 8 综合 圈日圈 凸矧脒燃一槲 下载和测试 图2 3f p g a 开发过程 2 2f p g a 与高性能计算 2 2 1f p g a 的计算性能 受益于灵活的可配制性，f p g a 在起初的很长的一段时间内主要被用于 逻辑的粘合( g l u el o g i c ) 。随着制作工艺的进步，其高速和并行的特性得以 发挥，越来越多的f p g a 被应用于高性能计算领域。 表2 1v i r t e x 5l x 3 3 0 整数操作性能 d s p 4 8 el u t r e g i s t e r 运算类型流水级别最大频率m p s ( 1 9 2 ) ( 2 0 7 3 6 0 )( 2 0 7 3 6 0 ) 3 2 位乘法 433 22 5 2 5 z1 6 1 6 0 3 2 位乘法 47 4 63 6 7 2 4 2 6m h z6 7 4 3 3 3 2 位加法 13 29 63 7 7 3 z8 1 4 9 6 8 3 2 位减法 1 3 2 9 63 7 7 3 z8 1 4 9 6 8 9 哈尔滨工程大学硕士学位论文 表2 2f p g a 与c p u 整数运算能力对比 费用 m i p s m s 设备m i p s功耗 ：美元)美元nm i n t e l3 2g h zc o r e2 5 9 4 5 51 4 3 93 1 24 1 31 9 0 6 e x t r e m eq x 9 7 7 0 i n t e l3 2g h zc o r ei 79 6 5 7 6 3 8 39 7 52 4 57 8 33 1 1 8 e x t r e m ee d i t i o n a m d 3g h zp l l e n o m i i 4 2 8 2 03 1 01 4 7 1 3 8 2 9 1 3 x 49 4 0b l a c ke d i t i o n x i l i n xv i r t e x 5l x 3 3 08 3 5 9 3 8 1 4 9 6 81 2 3 4 63 06 8 6 6 02 7 8 6 4 2 7 1 6 5 6 f p g a 最擅长进行整数运算，其整数运算性能如表2 1 所示，l u t 用于 完成逻辑功能的实现，r e g i s t e r 用于完成数据的缓存从而实现流水功能，m i p s ( m i l l i o ni n s t m c t i o i l sp e rs e c o n d ) 是整数运算性能衡量标准。f p g a 的m i p s 指标数据是根据芯片的总资源数与实现运算所需要的资源数推导出的最大 值，在实际应用时的数值会有所下降。整数加减法运算是资源消耗最小的运 算，实现一个时序3 2 位整数加i 成法部件需要3 2 个l u t 和9 6 个r e g i s t e r 。 乘法运算的逻辑功能比加减法运算要复杂得多，实现一个4 级流水的3 2 位乘 法部件需要7 4 6 个l u t 和3 6 7 个r e g i s t e r 。现代f p g a 中整合大量的d s p 模 块，通过使用d s p 模块就可以用更少的逻辑资源来实现整数乘法运算，可以 用3 个d s p 4 8 e 和3 2 个r e g i s t e r 来实现一个4 级流水的3 2 位乘法部件。表 2 2 给出了f p g a 与c p u 整数运算能力的对比。因为c p u 工艺成熟、主频较 高，所以在m p s 美元的指标下，f p g a 表现不突出，特别是乘法运算的性 能远低于c p u 。但是，在m i p s w a t t 指标下f p g a 相对于c p u 有一个数 量级( 乘法运算) 到两个数量级( 加减运算) 的优势。 浮点计算十分复杂、耗时，实现浮点运算需要消耗极大的f p g a 资源， 所以从x i l i n xx c 4 0 8 5 x l 芯片开始才可以在f p g a 中实现浮点计算。虽然如 此，从表2 3 2 1 j 给出的f p g a 与c p u 浮点运算能力的对比可以看出，x i l i n x 和a l t e r a 的高端f p g a 芯片在计算能力上都高于i n t e l 和a m d 的高端芯片。 由于f p g a 芯片的功耗远低于c p u ，所以其g f l o p s 腑a t t 指标远高于 c p u 。虽然f p g a 芯片价格较高，但价格属于一次性成本，可以通过功耗方 1 0 哈尔滨工程大学硕士学位论文 面进行补偿。此外，s a u d i a 公司的k b i 也等人【2 2 j 对f p g a 和c p u 的浮点计算 能力进行了分析与对比：f p g a 每2 年有4 倍或5 倍的性能提升而c p u 每1 8 个月有2 倍的性能提升，f p g a 的峰值浮点计算能力已经赶超c p u 而且具有 更快的增长速度。至u 2 0 1 0 年f p g a 在峰值浮点计算上会有个数量级的优势。 表2 3f p g a 与c p u 浮点运算能力对比 理论峰值实际峰值功耗g f l o p s 费用m f l o p s 设备 ( g f l o p s )( g f l o p s )( 恰1 v r )彤4 玎( 美元)美元 a m d 2 8g h z d u a l c o r e“21 0 19 50 11 2 6 68 0 o p t e r o n8 2 2 0 i n t e l3g h z q u a d - c o r e 2 42 1 61 2 00 21 2 8 51 6 8 x e o nx 5 3 6 5 x i l i n xv i r t e x 4 1 5 9 9 12 50 41 0 5 8 90 9 l x 2 0 0( 1 8 5 m h z ) x i l i n xv i r t e x 55 8 1 63 0o 51 2 3 4 61 3 l x 3 3 0( 2 3 7 m h z ) a l t e r as t r a t i xh2 5 2 1 4 42 50 61 0 6 8 81 4 e p 2 s 1 8 0( 3 0 3 z ) a l t e r as t r a t i xi i 5 0 7 2 8 93 00 9 e p 3s