基于SSE2的Smith-Waterman算法

Smith-Waterman动态规划算法是生物信息学使用最广泛的序列匹配算法,由于存在严重的数据依赖关系,该算法的细粒度数据并行性开发受到了很大限制。文章从简化数据依赖关系出发,采用前驱计算思想,提出了基于X86处理器多媒体指令集SSE2的Smith-Waterman细粒度并行算法SWSSE2,在相似性显著的情况下比普通的SW算法性能提高5倍,且与测试集无关。一般相似性不显著的情形下,同目前最好的动态规划细粒度并行算法SWMMX相比可以获得1.5倍的加速比。     

面向FPGA的RNA二级结构预测并行算法研究

动态规划是RNA二级结构预测最主要的算法,文中提出一种对动态规划矩阵采用分块技术的细粒度并行算法,通过对数据依赖关系的分析,引入了流水的策略,提高了算法的效率,在时钟模拟器上验证了算法的正确性,获得了一系列关于并行加速比、空泡率、存储访问带宽等问题的模拟结果,确定了FPGAPE阵列设计中的基本参数,为FPGA成功实现奠定了基础。     

使用分布式De Bruijn图遍历基因拼接并行构建和化简

目前基因拼接软件中应用最广泛的技术是基于De Bruijn图的基因拼接算法,需要对长达数十亿BP长度的基因组测序数据进行处理.针对海量的基因测序数据,快速、高效和可扩展的基因拼接算法非常重要.虽然已出现一些并行拼接算法（如YAGA）开始研究这些问题,但是拼接过程中时间、空间消耗较大的构图和单链化简这两大步骤在海量数据的挑战下仍然是最主要的计算瓶颈.这是因为现有工作在处理这几个步骤时通常使用了并行的表排序（list ranking）,而该方法需要多次对De Bruijn图的海量顶点信息进行分布式的排序,产生了大量的计算节点间的通信.单链化简可由1次De Bruijn 图深度优先遍历完成而不再需要表排序,于是提出一种基于分布式海量图遍历方法对单链化简进行优化,极大地减少了处理器间的通信和计算节点之间的数据移动,因而取得较好的扩展性,其算法复杂度为O（g/p）,通信复杂度为O（g）,这里g为参考序列的长度,p为处理器的核数.当对E.coli和Yeast数据集进行测试,处理器的核数从8个增加到512个时,算法可以得到13倍和10倍的加速比;当对C.elegans和人类1号染色体（chr1）数据集进行测试,处理器的核数从32个增加到512个时,算法可以得到7倍和10倍的加速比.     

基于曙光4000A的BLAST并行算法

对BLAST启发式算法的实现做了优化：引入批处理的概念、并对整个库文件建立哈希表,实现了I／O延迟掩藏,提高了整个比对过程的速度,同时降低了内存消耗。优化的算法有利于并行化的实现：在并行系统中,将库文件广播到各个计算节点,由节点在局部分别建立哈希表。然后将查询文件分割发送到各个计算节点并行比对。计算结果可以在节点直接输出,不需要主结点收集,减少了通信开销。     

曙光4000H生物信息处理专用计算机的高性能算法研究

曙光4000H生物信息处理专用计算机基于现代计算机体系结构和可重构计算器件,分别通过I/O延迟隐藏、细粒度并行以及并行流水等技巧优化设计了BLAST、动态规划、RNA二级结构预测等有代表性的3类算法,并开发C模拟器进行了性能评价,结果表明,上述算法大幅度提高了计算机处理能力.     

IA机群节点内并行编程模式性能分析

该文分析了IA机群节点内并行应用性能的影响因素,深入研究编程模式对性能影响的机理,并指出Cache命中率是最显著的影响因素。     

TOChain:一种高性能虚拟网络安全服务功能链

为了优化基于网络功能虚拟化（NFV）的安全服务功能链（NS-SFC）的性能,提出了基于TCP Offloading的虚拟网络安全服务功能链（SFC）--TOChain,解决了重复收发网络包的问题;提出了面向吞吐率保证的强同步周期性CPU调度算法,在虚拟网络功能（VNF）与用户虚拟机混合部署的场景下实现网络吞吐率性能保证与调度公平性.基于KVM虚拟化平台实现了原型系统,并对由防火墙、入侵防御系统和应用层防火墙3种VNF构成的NS-SFC进行了不同负载下的性能测试.结果显示,与传统SFC相比,TOChain能够以较低的CPU资源占用率达到更高、更稳定的网络性能;在轻度和中度网络流量负载下,采用强同步周期性调度算法都能够达到与所设定的吞吐率极为接近的网络性能,即便是在重度负载下,也能实现用户虚拟机间的调度公平性.     

基于多安全机制的Linux应用沙箱的设计与实现

文章设计了一个具有自己独立工作目录的Linux应用沙箱,可为用户对不信任的应用程序提供一个独立和安全的运行环境,应用程序在沙箱中所做的操作对主机不会造成任何影响。该沙箱提供了文件系统隔离、系统资源隔离、物理资源隔离、权能限制和强制访问控制(Mandatory Access Control,MAC)等策略,添加了地址随机化、不可执行页保护等内存保护安全策略。与已有沙箱对比,文章设计的沙箱增加了多种安全机制,提高了系统的安全性,保护了系统的数据安全和用户的个人隐私等。     

RNA二级结构预测中动态规划的优化和有效并行

基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n⁴)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n²×k²)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n³)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.