论文部分内容阅读
本文主要的研究内容是生物大数据在多种高性能异构计算架构下的并行计算方法,主要解决了三方面的挑战:(ⅰ)在有限的内存空间中对大规模数据集执行计算的方法,(ⅱ)基于异构计算的多层级的算法并行化设计方法和(ⅲ)对不同架构计算设备的硬件抽象建模方法。在这三方面的研究中,抽象硬件模型是最重要的贡献,提供了一个良好的抽象硬件底层,将框架设计和具体硬件分离,简化了软件框架,可以使软件框架快速扩展覆盖多种硬件架构,并能够以简便抽象的方式控制内存布局。同时提供了一个简化的硬件视角,抽象出影响性能的关键因素,进而在此基础上设计效率更高的并行方法。由于高通量测序技术的快速进展,在过去的十年中,生物序列数据的数量出现了爆炸性增长。生物学家存在分析和理解这些数据的强烈需求,因为基因序列决定了蛋白质的生物结构以及功能。但是,生物数据的可用性并不随着数据库的膨胀而增加。事实上,目前生物数据库的数据量如此之大以至于传统的数据分析方法已不足以快速执行涉及多种数据类型的生命科学查询。另一方面,近年来的计算力增长主要体现在新兴体系结构上,如GPU,Xeon Phi和基于Alpha指令集的国产申威众核处理器上。新兴体系结构呈现如下两方面的趋势:异构化和众核化。其中异构化意味着系统中可能存在多种架构的芯片,每种芯片均为特定的任务设计以提升能效。众核化是由于处理器的顺序执行性能的提升遇到瓶颈,转而增加核心数目,提升并行计算能力。因此传统计算方法面临数据规模和架构变化两方面的挑战。在数据规模方面,本文提出了一种异步执行的方法,利用数据/任务的并行特性进行切分,通过分批处理其数据/任务子集,构建处理流水,从而实现了在少量内存占用的基础上,执行对大规模数据集的计算。异步执行方法具备良好的可扩展性,本文分别展示了将成对序列比对和多序列比对两类问题分别扩展到大规模数据集和计算集群上的方法,在同样的硬件设备上成功处理了其他生物序列计算工具无法处理的大数据集,并得到了比小数据集上更高的计算效率。在异构计算方面,本文展示了基于Xeon Phi与CUDA异构架构和Knights Landing众核同构架构的多层级并行优化方法。对硬件的架构特点进行了探索并建立了理论性能模型,在理论性能模型的指导下发展了对一大类动态规划算法适用的高效并行化方法。特别的,在Xeon Phi平台上我发现并定位了关键的性能瓶颈,并通过重构计算顺序、解构数据依赖提升数据访问的局部性,大幅提升了缓存命中率,达到了该平台上目前最高的性能,并接近理论计算峰值。在设备抽象模型方面,本文首先从执行层面的角度统一了 SIMD与SIMT两类编程模型,并在该模型基础上将所涉及计算设备划分为低延迟顺序处理器和高通量向量处理器两大类。我基于统一的抽象设备模型对应设计了一组C++类层级,通过分析抽象计算设备的共性和特性,最小化架构特定部分的代码,并对架构共性的工作流程进行了高度优化,充分利用了异构架构中不同处理器的异步执行性能,并根据设备的抽象模型为系统中的每个计算设备提供理论上最优的数据布局和统一的数据访问接口。同时,抽象的设备模型有助于不同架构之间的核心计算函数与并行方法互相借鉴,进而在多种架构上达到更好的性能。在上述三方面的贡献的共同作用下,本文中的方法已经支持CUDA、KNC、SSE、AVX2、AVX512等架构与指令集,,并在上述架构与指令集上均能够超过其他最先进方法的性能。同时能够扩展到更多节点快速搜索接近40GB的蛋白质数据库,并具备扩展到更大数据库的能力。因此,本文所述的工作成功地解决了传统计算机算法算法和软件架构面对大规模数据集和新兴计算机体系结构的挑战,其方法可以扩展到更多算法与体系结构上。