论文部分内容阅读
大规模图算法是移动互联网、物联网、大数据和生物信息处理等新兴应用的核心计算模式。本论文主要围绕两个大规模数据处理的基础算法开展研究:第一个是图遍历算法，是生物信息学、数据挖掘和计算社会学的核心算法;第二个是DNA序列匹配算法，对于微生物学和医疗信息学等学科有着重要的意义。 另一方面，结合计算机体系结构的算法优化一直是高性能计算的重要课题，并行体系结构尤其是多核和机群是大规模数据处理算法优化的主要挑战，例如，如何有效发掘多核机群的并行性来提高数据处理吞吐率，以及如何优化在大规模机群环境下的通信从而提高程序的可扩展性等。 本论文围绕在大规模多核机群上并行性发掘和通信优化展开研究。论文主要的创新性工作包括: 面向多核机群提出了一种多层并行图遍历算法。该算法发掘了处理器核级并行、指令级并行以及流水线并行，提高了访存带宽和负载平衡，在384核机器规模下性能是Graph500纯MPI版本的1.9倍，在6，144核机器规模下性能是ComBLAS纯MPI版本的1.49倍; 面向大规模机群提出了一种分布式图遍历算法中通信优化的方法。该算法使用分布式目录和实时压缩通信数据的方法，有效减少了算法的通信量。实验结果显示在6，144核机器规模下该算法对比Graph500原算法减少了79.0％的通信时间，性能是原算法的2.2倍，每秒能够遍历121亿条边。 定义了DNA序列分析算法中序列重叠计算的编程模型，降低了序列分析程序开发的难度并提高了程序可移植性。同时针对分布式计算环境实现了一个面向超大规模的DNA序列分析软件库，最多可以支持上百亿条DNA序列的存储、索引和查询，其中关键的优化包括分布式数据划分以及非阻塞查询设计。在IBM BlueGene/Q系统上的实验表明该库在65，536核机器规模下对11.92 TB随机DNA序列数据的查询性能可以达到每秒3.79亿次。另外，我们基于该库改写了一个名叫Kiki的元基因组从头测序软件，新Kiki的性能是原版本的6倍以上。