高级合成加速生物信息学应用其他[cs.OH]的研究

使用高级合成加速纳伊姆·阿巴斯引用此版本：纳伊姆·阿巴斯。使用高级合成加速生物信息学应用其他[cs.OH]。Cachan高等师范学校- ENSCachan，2012年。英语。NNT：2012DENS0019。电话：00847076HAL ID：电话：00847076https://theses.hal.science/tel-00847076提交日期：2013年HAL是一个多学科的开放存取档案馆，用于存放和传播科学研究论文，无论它们是否被公开。论文可以来自法国或国外的教学和研究机构，也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire论文/ENS CACHAN-英国由布列塔尼欧洲大学盖章要获得标题卡尚高等师范学校博士提及：信息学马蒂斯博士学校使用加速生物信息学应用高级合成提交人纳伊姆·阿巴斯在联合研究单位6074计算机科学研究所编写和随机论文答辩2012年5月22日陪审团由以下人员组成：菲利普·库西副教授-南布列塔尼大学/报告员迪内钦的弗洛朗高级讲师-ENS Lyon/报告员鲁门·安多诺夫大学教授-雷恩大学1/考官唐吉·里塞特，大学教授-INSA de Lyon/考官史蒂文·德里安副教授-雷恩大学1/论文主任帕特里斯·昆顿大学教授-ENS Cachan-Bretagne/博士生导师摘要生物信息学领域的进步为生物学和药理学的研究开辟了新的视野然而，像今天使用的算法这样的机器不再能够满足指数级增长的计算能力需求。因此，需要用于这种类型的处理的专用计算平台，其可以利用当前的并行计算技术（网格、多核、GPU、FPGA）的集合在这篇论文中，我们研究了如何使用高级合成工具来帮助设计大规模并行的专用硬件加速器。这些工具大大缩短了设计时间，但并不是为产生高效的大规模并行硬件体系结构而设计的本论文的工作重点是 为HLS类型的工具开发并行化技术以及有效表达这种并行性的方法我们将这些结果应用于一个名为HMMER的生物信息学该算法可能是硬件加速的我们提出了一个原始的并行执行方案，基于算法的数学重写，随后探索了FPGA上可能的硬件执行方案这一结果随后导致了在硬件加速器上的实现，并证明了令人鼓舞的加速因素这项工作还证明了HLS工具在设计生物信息学中高性能计算的硬件加速器方面的相关性摘要生物信息学领域的革命性进展为生物学和药物研究开辟了新的视野。然而，由于最近生物数据的指数增长，现有的生物信息学工具无法满足计算需求。因此，需要构建结合现代并行计算技术的未来生物信息学平台。在本文中，我们使用高级合成来研究这些应用中基于FPGA的加速。高级合成工具允许将抽象规范自动翻译为硬件设计，大大减少了设计工作。然而，使用这些工具生成高效的硬件对设计人员来说往往是一个挑战。 我们的研究工作包括对技术和实践的探索，这些技术和实践可以导致从这些高级综合工具中产生高效的设计。我们通过加速广泛使用的应用程序来说明我们的方法--HMMER--在生物信息学界。HMMER以其计算密集型内核和数据依赖性而闻名，这些内核和数据依赖性导致了顺序执行。我们提出了一个基于重写其数学公式的原始并行化方案，随后对这些内核的硬件映射技术进行了深入的探索，并最终在板上显示了加速结果。我们的研究工作证明了为生物信息学应用设计灵活的硬件加速器，使用的设计方法比传统方法更有效，并且由此产生的设计可扩展到足以满足未来的需求。订单号Cachan高等师范学校-布列塔尼分校Ker Lann校区-罗伯特·舒曼大道-35170 BRUZ电话：+33（0）2 99 05 93 00传真：+33（0）2 99 05 93 29内容物1简介11.1生物信息学的高性能计算 . . . . . . . . . . . . . . ...11.2基于FPGA的硬件加速 . . . . . . . . . . . . . . . . . . . . . .31.3 FPGA设计流程。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...31.3.1Sy n t e是高水位。 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...51.4在教育和教育的帮助下，通过教育实现教育化。 ... ... ... ... ... ... ... ...61.5本书的共同贡献。 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...72简介92.1生物信息学的高性能计算 . . . . . . . . . . . . . . ...92.2基于FPGA的硬件加速 . . . . . . . . . . . . . . . . . . . . . .102.3 FPGA设计流程。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...112.3.1高级合成 . . . . . . . . . . . . . . . . . . . . . . . . . . ...13使用还原和前缀利用并行性 . . . . . . . . . . . . ...142.5本工作的贡献。 . . . . . . . . . . . . . . . . . . . . . . . . . . ...153生物信息学算法173.1 DNA、RNA蛋白质： . . . . . . . . . . . . . . . . . . . . . . . . . . . . ...173.2序列对齐 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .193.2.1成对序列对齐。 . . . . . . . . . . . . . . . . . . . . . ...203.2.2多重序列对齐。 . . . . . . . . . . . . . . . . . . . . ...233.2.3HMMER工具套件。 . . . . . . . . . . . . . . . . . . . . . . . . ...273.2.4计算复杂性 . . . . . . . . . . . . . . . . . . . . . . ...293.3RNA结构预测。 . . . . . . . . . . . . . . . . . . . . . . . . . . ...303.3.1Nussinov算法。 . . . . . . . . . . . . . . . . . . . . . . . ...313.3.2Zuker算法。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...323.4高性能生物信息学。 . . . . . . . . . . . . . . . . . . . . . . ...333.5结论。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ... ... ...344个HLS基于加速：从C到电路354.1可重构计算。 . . . . . . . . . . . . . . . . . . . . . . . . . . .354.2生物计算加速器。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...384.3高级合成。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ... ... ... ...39我ii内容4.3.1HLS相对于RTL编码的优势。 . . . . . . . . . . . . . . . . ...394.4HLS设计步骤。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...414.4.1编译。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...414.4.2操作调度. . . . . . . . . . . . . . . . . . . . . . . . . ...414.4.3分配绑定。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...474.4.4世代。... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...504.5高级综合工具：概述4.5.1脉冲C514.5.2C-52弹射器4.5.3MMAlpha534.5.4 C2H544.6结论545使用HLS57高效生成硬件5.1位级转换575.1.1位宽窄化585.1.2位级优化595.2指令级变换605.2.1操作员力量降低605.2.2高度降低615.2.3运动代码635.3循环变换655.3.1展开655.3.2环路交换665.3.3循环移位665.3.4环剥离685.3.5环形摇摆685.3.6循环融合685.3.7C-慢速695.3.8循环倾斜露天采矿705.3.9内存拆分705.3.10 数据复制、重用和可扩展替换715.3.11 阵列收缩735.3.12 数据预取735.3.13 存储器复制745.4结论766在HMMER79中提取平行性6.1导言796.2背景806.2.1配置文件HMM806.2.2P7Viterbi算法描述6.2.3展望未来的计算826.3相关工作836.3.1早期实施836.3.2Viterbi算法85的推测执行6.3.3HMMER87的GPU实现6.3.4HMMER3和多个无间隙段启发式6.3.5加速完成HMMER3管道896.4重写MSV内核896.5重写P7Viterbi内核906.5.1寻找减少916.5.2数据依赖关系图93的影响6.6并行前缀网络946.7结论967HMMER97的硬件映射7.1硬件映射987.1.1具有单个组合数据路径的结构987.1.2C-慢流水线数据路径987.1.3最大前缀运算符997.1.4通过Tiling100管理资源限制7.1.5加速HMMER101管道的完整运行7.2通过高级综合实现1027.2.1循环变换1027.2.2循环展开&内存分区1037.2.3乒乓球记忆1037.2.4可扩展复制1037.2.5存储器复制1047.3实验结果1047.3.1MSV过滤器104的面积/速度结果7.3.2Max-Prefix网络的区域/速度结果1047.3.3P7 Viterbi过滤器105的面积/速度结果7.3.4系统级性能1077.3.5完整的系统级重新设计1087.3.6讨论1107.4结论1108&未来展望1138.1结论1138.2未来展望116iv内容1简介1.1用于生物信息学生物学和信息学是一个研究领域，但在过去的十年里，它引起了越来越多的研究，并在通信中发现了科学。 这个领域涵盖了c个领域，包括生物学、遗传学、计算机科学也是数学数学的。生物信息学的主要目标是为生物学家提供信息学工具，使他们能够分析遗传序列（如DNA、RNA和/或蛋白质）产生的礼物，以发现或揭示这些方程的生物学功能。标准生物学中的问题有很多，其中我们可以提到DNA序列中基因的遗传学，结构和功能的编辑（和分类），以及为研究关系而自动构建的基因树。此外，在过去的十年里，DNA笼技术'a'atopd'ebit，这是一个很大的错误（人类基因组[VA M+01]的完整笼子，pro plantes基因组注释的项目[ S R V + 07]）。如图2.1所示，这些进展反过来转化为基因组学（DNA、蛋白质）供体体积的爆炸式增长，这是NCBI基因库[NCB11]（DNA）UniProt值得注意的是，新的笼状技术并没有使从序列中提取巨大的量子变得更容易，而且肯定不会从现在起，这是一个很大的问题，也是一个很大的问题。 从这些数量庞大的捐赠中提取有用的信息，以帮助理解生物学中的ph enoenes。生物信息学委员会传统上使用的工具并不是为了在如此大量的捐赠上工作而设计的，在这些分析工具中发挥作用的计算量是一个瓶颈。1简介2基因库中碱基对的数量S300离子IIBI250200150100500(a)（b）图1.1：（a）基因库和（b）UniPortKB数据库的指数增长[NCB11，？].从no mbreuxtr av到seso nt，所以我用我的chinesparal来计算这些计算时间。如果说第一个tre av针对的是经典的超级计算机架构[SRG03，YHK09，CCSV04，GCBT10]（网格、集群），那么democ ra t就在多核架构上[Edd，LBP+08]，GPGP U 1 o n t的出现使这些tre a v x更加丰富。或者除了这些关于可编程架构的讨论之外，我们还必须考虑使用基于可编程逻辑[HM S + 07，SKD06，DQ07，LST]的交流运算器，因为可以利用交流运算的能力。我们的所有剩余部分都没有电力消耗，因此成本可能不太合理。L’augmen如果是气象条件[AT01]，则处理[LSK+05]，但也不生物信息学[DQ07，SKD06]。因 此 ，FPGAs中的AC 和 错 误 不 太 可 能 是 非 常 适 合 于 生 物 信 息 学 治 疗 的 实 施 的AR/C/T/T/T。它们在算法中提供了一种细粒度的算法，然后可以通过FPGA上的实现来有效地利用这种算法，从而实现了Exo事实上，生物信息学算法的一个重要部分是基于使用基于动态编程的技术，特别是比较序列。（SmithWAterman[SW81]、NeedlemanWunsch[NW70]和BLAST[AGM+90]），s序列的多重对齐（CLUSTALW[THG94]），在配置文件上查看（HMMER[编辑]），RNA序列的连接（MFOLD[Zuk03]）和基因树的构建（PHYLIP[Fel93]）。因此，在这些大算法中使用的处理和效果的规则性很容易在T Y PERE1其目的是使用计算能力t'esimportantes的图形卡pouraceerer的科学计算1.2 – FPGA based Hardware31.2基于FPGA的硬件加速FPGA电路并不像可编程逻辑单元的千兆阵列那样存在，因此它们不可能被配置为对我们的系统施加任何影响，也不可能被配置为对我们的系统施加任何影响，也不可能被配置为对我们的系统施加任何影响。因此，经济增长并不直接影响经济增长，也不直接影响经济增长。在FPGA中，这 种 paral elism 的 执 行 可 以 采 取 几 种 形 式 ： paral elism 在impla n ta n t p 的 几 个 计 算 核 心 中 的 t a hes 在 paral l ele 中 的 执 行 ， paralelism 在使用一个不复杂的pi p eli 的c hemins 的过程中的操作。由于FPGA的工作时钟频率比处理器低得多（平均为10倍），因此它们必须通过利用电路中的大规模冗余来补偿其相对n/e，同时确保为电路供电的p/t用于提高FPGA上的电路的并行程度和工作频率的技术之一是使用不精确的计算（e ntirersa在这里，生物信息学算法也可以很好地进行这种优化（例如，DNA碱基的编码可以在2位上完成，而不是在一个完整的字节上）。 因此，这些在TR'ESB上运行的特性使其在FPGA上具有更大的计算能力，特别是在T Y PEGPU上更接近于浮点NT计算。因此，在FPGA上实现的许多算法中，最常用的算法[HMS+07，SKD06，DQ07]的DAC误差非常小。这些人是第n个国家的Imp，他们不是emo不是facteursdac的一部分，他们鼓励的是迭代，它基于用HDL或Verilog编写的电路规范，并且对于非EE FPGA技术来说不是最佳的。 这使得问题变得更加复杂，从一个AC到另一个AC到FPGA误差的切换不需要使C的设计达到零。本问题的第二部分讨论了本节中高质量的synteseniveau工具的相关性。1.3FPGA设计流程FPGA电路的标准设计流程主要基于ASIC的设计流程。这个流程的主要步骤在F igure2.2a中并不代表，它们只涉及软件协同设计的硬件部分--m a er i e l，软件e m barq u e ta nte v elope，使用经典的编译方法。该流程的第一步是用高级语言（C、C++、MATLAB）对comp osa n ts的详细说明进行迭代，以确定sys teme的确切comp orteme。 一旦validee，设计者必须定义一个简介4合成合成地点路线地点路线验证行为模型C / C++ / MATLAB规范FPGA（a）FPGA（b）图1.2：FPGA设计流程：（a）传统设计流程基于硬件描述语言（HDL）的使用。HDL应用程序的要求是ELICATE，不需要验证效果。 （b）关于使用高无水工具的sy n t 'hesebae流：概念etapemanuelleauniveauRTL由高无水描述的comportementale替换，然后是描述RTL的自动ege阶段。这将是一个很好的解决方案，能够满足性能、成本和耗电量的要求，符合充电规范。一旦定义了架构，设计人员就可以使用硬件描述语言（Verilog或HDL）或计算机规范来创建该架构，以实现RTL（寄存器到逻辑）。然后在模拟的帮助下对该描述进行建模一旦验证了i'ee，电路的描述就是sy n t'eti s'ee，也就是说，将m 'ee转换为基于FPGA逻辑cib、eap e网表的表示。然后将该reesentation的表示放置在FPGA电路cib l'e上，并在昨天的位ream上设置一个fi，该fi将用于配置FPGA。这个流仍然是复杂的，并且不需要在没有太多迭代的情况下获得一个可操作的或可操作的配置。第一个困难是正确选择架构目标（FPGA的type、处理能力tt、存储等）， 因为它已经决定了大部分的设计选择。因此，最初的选择可能会对总体设计工作产生影响。第二个（主要的）困难是在AC错误的体系结构的寄存器到逻辑（TL）中的规范化，这是使用诸如HDL或V e r i log的描述语言来完成的。这个过程非常繁琐，需要很长的时间，没有太多的迭代，也没有太多的具体化和验证步骤。验证实施（VHDL /Verilog）定义体系结构验证行为模型C / C++ / MATLAB规范HLS规范。1.35电子系统的复杂性不断增加，这可以通过在单个FPGA电路上实现的功能的增加来说明，使得这种复杂性成为可能。更关键的是设计RTLP LUS[CD08]。事实上，用于实现4G无线通信统一的系统所使用的设计工具与GS M标准的设计工具并不相同，这与这两个标准之间的复杂性有很大的差异。因此，这是一个很好的例子 ，也是一个很好的例子目标是提供从高级语言到C或SystemC的算法规范的描述R TL 'a artir的自动生成。我们谈论的是1.3.1Synt'ese从高尼v水高勒夫西论文（HighLe velSy nthesis）的第一篇论文主要不是为了教育设计的基本原理，而是使用了高勒夫水的规范，而不是RTL描述中的应用程序所提供的规范。在严格意义上说，HLS工具也不会减少验证时间，在最小值中，不需要任何计算来获得一个有效的操作。此外，在时钟、资源共享和存储器的概念化时代，这些工具也不会降低从一种技术到另一种技术的RTL规范的加速是以性能下降和资源成本和基因消耗增加为代价的[Fin10]。因此，由于HLS规范是在功能上实现的，因此从平台到另一个平台的IP的调度是简单的，因为它是负责实现技术映射的HLS的节点。就我们而言，建筑师们并没有自动地从一个更抽象的规范中汲取灵感，也没有那么罕见，也没有像现代建筑师那样有效。因此，通过不使用这些工具获得的低性能在计算的共同文本中限制了nnn te高性能。这些低性能的原因是这些工具不能从水中提取任何东西，而不能充分利用水。 这些工具产生的错误实际上并没有用GPU架构和多核来实现V，而且它不应该依赖于较低的功能频率。这是不可能的，以解决这个困难，在mo修改n tt直接nt的源代码的应用程序的人我是'使appara t r e ni v水paralelism这将是可利用的工具. 当我们计算规则的计算时，这种技术上的ty pe是有效的，a是b循环的巢的形式。 事实上，有可能把它放在tra v的大qun t'e上，作为paral elisation的com munau t'e的结果。简介6x15 x14 x13 x12 x11x 10x9 x8x7 x6x5 x4x3 x2x1 x0x15 x14 x13 x12 x11x10x9 x8x7 x6x5 x4x3 x2x1 x0S第十五章S14 S13S12 S11 S10S9S8S7S6S5S4S3s2(a)（b）图1.3：还原（a）和扫描（b）的示例，以及可能的计算顺序。自动[Wol90，Wol96]。除了计算本身的计算能力之外，获得良好的性能还需要考虑到在syseme的differentsniveauxdehierarchiememoire（记忆hote，记忆lcalesurlacarte，记忆embarquee）中不存在的礼物的管理。Cetravail的一个贡献是presenter是对获得的变换的意义m ble的回顾有工具的sy n t h'ese从高或v水，建筑物merielless p'ecialis'ees不有效地利用了possibili tes的acc c错误的FPGAact uels.1.4Paralelization'在减少和P r'前缀的帮助下所使用的第n个算法被分为两个类别，即一般规则。在第一种情况下，计算结果r的大小与这些p的尾部l的大小是同一个数量级;例如，两个向量v的相加就是这种情况。在第二种情况下，re的大小是更多的beau更多的pétite（在ge中通常是一个标量值），因此r r o p o e由I verson [I v e62]还原的项，并且例如，它corres p d具有向量或矩阵的e e的和的运算。在这篇文章中，我们将讨论uxt y p的计算：r的约化运算和p的前缀s 2的运算。 这些操作不适用于O B喷气式飞机的集合，因此不适用于O操作员的使用，也不适用于commutativite和asociativite的适当性。因此，如果一个向量的约化不存在，那么这个向量的约化就不存在了。2也不包含在术语"扫描"下1.57M先生M先生o p erande（x1，x2，. ... ... x（n）ns=x i= x0x1 ... ... x n（1.1）i=0对于固定的p的运算，r的大小是p的mmequelll，并且是efinit，p的向量vp的向量（x1，x2，. ... ... 因此，我们有一个向量r是结果（s1，s2，... ... ... （sn）如：ks k=x i= x0x1。... ... x k（1.2）i=0在图2.3中，这两个运算不代表应该注意的是，这些运算，先验地说，在它们的定义中，可能是人的计算或多或少复杂的，而不是人的计算。 特别是，自20世纪60年代初以来，在超大规模集成电路上有效实现固定p 在许多结构中，没有一个结构能够快速、经济地探索折衷方案，或者不适合[LF80、BK82、KS73、HC87、Skl60]。一个算法的实际实现使用了p个前缀的n个运算，可以从这些结果中受益，通过探索实现t个项目的可能性来选择最有效的一个当设计是由a b s t r ac tio n完成时，这种探索就变得生物信息学中的序列对齐算法，以及动态规划算法和计算数学中的expot在那一章里？？在这里，我们展示了HMMER[Edd]工具中涉及的一些处理是如何被证明是减少和/或固定的操作，这将导致更有效的过滤。1.5这是一个很好的例子第三章对信息学领域提出了一个简短的建议，并提出了它的问题。特别是，我们将重点介绍主要算法，这些算法用于对齐、比较和复制序列，重点是它们在治疗方面的成本以及它们在大量捐赠中传递的能力。特别是，我们发现，大多数有用的应用程序并不通过，也不需要求助于建筑物，而建筑物利用了重要的3这是不正确的，并且可以用二进制加法运算是固定p的运算这一事实来解释。简介8第四章然后是关于技术和工具的飞行从高ni v水。这些工具不是从一个算法规范（例如，nC）中直接推导出来的，而是从一个算法规范（例如，n C）中推导出来的。因此，他们不可能在受孕的时候进行激烈的人的教育。第三章介绍了大量的HLS，并提出了在这些工具中使用的技术的最新水平。本章最后回顾了HLSaca d'emiques和商业行为工具。第5章如果没有其他的话，它将提高由Sy n t es e HLS获得的建筑的性能。这一部分的ma nuscrits'i n 'eresse en part i c u链接到b循环的转换pour la paral elization和优化的ac c' es的记忆，这是至关重要的p nt第6章和&第7章讨论了本研究的贡献，该研究涉及使用复杂的程序转换，以实现HMMER程序的实际执行。这个工具，你用在生物信息学的交流中，是基于两个n°y的calcul（MSV和P7Viterbi），这是很难的。这是一个很好的例子，说明了上帝的恩典是如何与上帝的恩典相一致的。在第6章中，我们讨论了在FPGA上实现HMMER的最新技术水平，并提出了MSV和P7Viterbi内核的重新表述，这使得有可能在还原和前缀操作的证据中引入一个既不存在也不存在的elism。当"a"在FPGA上实现交流和误差，并在商用HLS工具的帮助下，实现与HMMER并行的Co-PR架构时，就会出现第7章。原始的t e的appro c he vie n t的使用一个s c ema的calc u l复合体，利用了paral elism '一个细粒度（b oucles v ectori sees）和'一个大粒度（util i s at i on的一个宏观圆周率线t a c he）. 这些都不是在FPGA（XtremeData）板上实现的，我们已经为英特尔多核处理器的PID扩展提供了一个最佳的实现，这是一个很好的方式2简介2.1用于生物信息学生物信息学可以被定义为计算机科学、数学和统计学概念的应用，以分析生物数据（如DNA、RNA和蛋白质）并预测它们的功能和结构。生物信息学中发现的典型问题包括在DNA序列中寻找基因、分析新蛋白质、将相似蛋白质排列成家族以及生成系统发生树以揭示进化关系。在过去的十年里，随着DNA测序技术的进步，特别是人类基因组项目[VAM+01]和基因组注释的成功，可用的计划的打印机[SRV+07]。值得注意的例子是DNA序列的大小NCBI基因库[NCB11]中的信息和UniProt中蛋白质序列的生长[？] ]数据库，如图2.1所示。此外，下一代测序技术已经实现了大量基因组序列数据的提取，这将导致这些数据库的进一步增长。计算机科学家和生物医学研究人员现在面临着重大挑战 将大量的基因组数据转化为生物学知识。生物信息学中的传统工具和算法被设计用于处理非常小的数据库，因此在扩大规模以促进大型数据集和数据库的分析时，计算时间出现了瓶颈。最近，已经进行了大量的研究工作，使现代生物信息学工具能够利用并行计算环境的优势生物信息学应用在最新的最高核上的实现一般-纯p-osepro这些排序[Edd，LBP+08]，一般纯p-ose图形处理器（GPGPU）[WBKC09b、VS11、MV08]、网格技术[SRG03、YHK09、CCSV04、GCBT10]和可重构平台，如现场可编程光栅阵列（FPGA ）[HMS+07 、SKD06、DQ07、LST]，承诺加速并显著缩短许多生物算法在现场运行时的运行时间。9简介10基因库中碱基对的数量S300离子IIBI250200150100500(a)（b）图2.1：（a）基因库和（b）UniPortKB数据库的指数增长[NCB11，？].巨大的数据库。近年来，FPGAs的逻辑密度和时钟速度的大幅增加反过来又增加了使用FPGAs来简单计算密集型算法的趋势--来自不同领域的算法，如金融[ZL H+05，WV 08]、天气预报[AT01]、视频计算[L SK+05]和生物信息学[DQ 07，SKD 06]。 FPGA是生物信息学应用的一种有吸引力的目标架构，考虑到它们作为定制加速器的成本效益和它们利用许多生物信息学应用中可用的细粒度并行性的能力。广泛的生物信息学应用依赖于动态编程算法或其快 速 近 似 ， 包 括 序 列 数 据 库 搜 索 程 序 （ Smith-Waterman[SW 81] 、 Needleman-Wunsch[NW 70]和BLAST[AGM+90]）、多个序列对齐程序（CLUSTALW[THG 94]）、基于图谱的搜索程序（HMMER [Edd]）、RNA折叠程序（MFOLD[Zuk 03]），甚至系统发育推断程序（PHYLIP[F el 93]）。 FPGA架构非常适合于这种动态编程算法，因为它具有规则的结构，类似于动态编程算法中的数据依赖性，具有到近邻的通信网络。2.2基于FPGA的硬件加速FPGA只是可编程网关的广泛领域，因此它们可以被编程为许多并行硬件执行路径。由于它们的并行性质，不同的处理操作不必竞争相同的资源。设计人员可以在FPGA上映射任意数量的任务特定内核，所有内核同时作为并行电路运行。在FPGA上，设计人员可以在各种计算粒度（即细粒度和粗粒度并行性）、长计算路径和数据并行性的帮助下表现出并行性。并行粒度可以在非常细粒度的计算范围内（例如位级操作），细粒度操作，如在SID体系结构中（例如字级和指令级操作），以及粗粒度计算（例如高度计算密集型内核的多个独立实例2.311并行运行由于与CPU相比，FPGAs以非常低的频率（约10×低）运行，因此为了超越基于CPU的性能，应该有足够的计算可以并行计算。具有大规模固有并行性（例如，将彩色图像的每个像素转换为灰度）的Hence计算密集型应用非常适合基于FPGA的实现。类似地，具有减小的比特宽度数据的应用适合于FPGA，因为它们能够计算自定义比特宽度操作。大多数生物信息学算法甚至不需要全整数精度，因此现代CPUs上的浮点运算将是无效的。因此，这种应用的基于FPGA的实现可以利用可定制的精度和并行性，并且可以导致改进的速度和可用资源的更好利用。与其他加速方法（如集群和GPU）相比，生物信息学应用所具有的特性使其可用于基于FPGA的加速已经进行了大量的研究工作来加速使用传统硬语言（HDL和Verilog）的FPGAs上的这些应用[HM S+07，SKD06，DQ07]。 The由此产生的实现是非常有效的，并且所获得的速度是非常有价值的。然而，基于FPGA的实现很少有问题会导致设计者选择基于FPGA的实现，例如，设计流程非常容易出错，冗长的验证阶段经常成为设计项目中在下一节中，我们将通过讨论传统FPGA设计流程和通过高级合成解决这些问题的可能方法来强调2.3FPGA设计流程FPGA设计的标准设计流程取自ASIC，如图2.2a所示。在实践中，设计通常被划分为硬件和软件部分。图2.2a中显示的步骤仅与此类设计中硬件块的实现相关，而软件块将使用标准软件开发技术实现。设计流程的第一步是用C、C++、MATLAB或任何其他语言定义功能规范，经过测试后，设计人员需要定义一个最佳体系结构来实现所需的功能。体系结构选择定义了要实现的性能、面积和功耗目标定义架构后，设计团队以硬件描述语言（Verilog或Vhdl）或原理图设计的形式对这些决策进行手工编码。在此阶段，将进行功能模拟以验证所述功能的正确性。在功能验证之后，可以对设计进行综合，即将布尔运算符映射到查找表（LUT）模块，如图4.1b所示。逻辑合成的结果称为网表，它是一个描述要用于逻辑合成的模块的文件。