生物信息处理专用计算机研究与开发曙光4000H验收报告.ppt

谢谢！ * 编辑距离算法核心逻辑电路 Matrix-PCI型加速卡 Matrix-PCI型加速卡 编辑距离算法在加速卡的性能测试 编辑距离算法在加速卡上的测试结果分析 Xeon 2.8GHz CPU进行得分矩阵的计算时，每完成1个分值的计算需要约45个汇编指令，同时可以统计出该CPU的平均CPI＝0.6，所以每个循环将消耗约27个CPU周期，则该CPU的计算能力折合为103.7MCUPS。 而加速卡的每个PE完成该计算过程则只需要1个周期，工作在133.33MHz的3072个PE阵列的峰值计算能力为409.6GCUPS，所以理论上的加速比最高可以达到3950倍。 实际测试最高加速比3800倍 ClustalW多序列联配算法 ClustalW是目前使用最广泛的多序列联配程序。它是一种渐进的联配方法，计算过程主要包括以下三个步骤： 使用动态规划算法计算所有两两序列最优联配的分值，基于最优联配得到序列的两两之间的相似度，根据相似度再进一步构造距离矩阵。 从距离矩阵出发，采用NJ计算产生系统进化指导树（Guide Tree），对关系密切的序列进行加权。 从引导树的叶节点出发，遍历整个树直到根节点，逐步得到最终的多序列联配结果。 该程序的第一个步骤需要对所有的序列进行两两联配，如果序列的数量为n，序列的长度为l，则这一步过程的计算时间复杂度为O(n2l2)，这也是整个程序中最耗时的部分，为加速计算提供了可能。 多序列联配整体加速比测试 多序列联配程序串行部分比例 多序列联配整体加速比测试结论 从图中可以看出，在一定范围内，多序列联配整体加速比与序列数量基本上成正比关系，即序列的数量越多，整体上得到的加速比越大。 加速比的增长应该有一个极限，但由于多序列联配的时间非常之长，我们在测试过程中没有测到增长曲线的拐点。 实际上，序列的数量越多，ClustalW中的串行部分即不可加速部分所占的百分比越低，随着序列数量的增长，程序中串行部分的比例迅速降低，但随着序列数量的进一步增长，程序中串行部分的比例逐步趋于极限，这也暗示了加速比的增长也将趋于极限。 局部最优序列联配 局部联配在某些生物信息学中的应用可能要比全局联配更有实际的意义。在蛋白质序列的比较中，由于亲缘关系较远的蛋白质序列可能只有一些相互独立的相同片段，所以对其进行局部相似性分析更为重要也更为合理。 另一方面，前面介绍的编辑距离算法中较少地考虑到序列的生物学意义，但实际上，在生物序列联配过程中，某些字符的匹配可能比另外一些字符的匹配更为重要，而不是仅仅考虑两个字符是否相同。因此，生物学家在统计分析的基础上建立了一套专门的替换矩阵(substitution matrices)用于联配的计算 序列局部联配算法PE设计 数据宽度为20位 序列的长度为32K 由硬件逻辑控制加减法器的下溢问题 Max电路由比较器和二选一电路两级电路来实现 关键路径：从F-in、E-out和H-out到H-out上包括了1级减法器、1级寄存器、3级比较器和3级二选一，共计8级电路，这条关键路径的延迟依赖于FPGA器件的特性 局部联配算法PE在FPGA中的实现 LUT部分用于实现?(S[i],T[i])功能项，即查找替换矩阵。 这个模块共有10位输入和4位输出，如果使用普通的组合逻辑来实现需要消耗很多逻辑资源。 用RAM来实现该LUT：10位输入和4位输出的LUT可以等价于一个有10位地址线的4位宽度的ROM，该ROM可以使用Altera FPGA中的M4K RAM配置来实现，ROM中的数据可在FPGA上电时有Flash加载进去。 使用ROM来替代LUT，不仅节省了FPGA中的逻辑资源，而且对该ROM的访问可以在1个周期内完成，也能够提高系统的工作速度。 PE中的其它逻辑，将消耗约270个LE，其中约有190个LE中使用了寄存器，其他LE则只使用了查找表。 Stratix 1S30共有一共有32470个LE，除了接口逻辑和其他控制逻辑，还可以实现约80个PE。 上述的关键路径中的从输入到加减法中间结果一级需要约5ns，剩下的路径需要约13ns，通过优化，PE阵列的最高工作频率可以达到80MHz，其峰值计算能力为6.4GCUPS。 局部联配算法在加速卡的性能测试 40kbp×（4kbp、20kbp、40kbp、60kbp、80kbp）（时间单位，秒） 序列长度 PCI_LSW Xeon2.8GHz 加速比 4 0.027 9.170 340.14 20 0.132 45.679 347.45 40 0.126 91.332 349.66 60 0.394 137.861 349.48 80 0.525 184.302 351.79 取得的主要成果 (3) 提出了ST