一种新的MPI_Allgather算法及压缩查询并行算法研究

摘要

消息传输界面MPI是目前使用最广泛的并行程序设计平台，包括点到点通信和集合通信两种模式。作为并行计算的基础，通信的性能对于并行应用程序性能有着重要的影响。MPIAllgather是MPI库中使用频率最高的集合通信函数之一，目前广泛使用的实现算法有环(Ring)、递归倍增(RecursiveDoubling)和Bruck算法(Bruckalgorithm)。针对以太网上TCP/IP通信的特性，本文提出一种新的MPIAllgather的算法——邻居交换算法(NeighborExchange)。本文还提出平均逻辑通信距离的概念和计算公式，可以有效地衡量通信的局部性。通过分析，发现在四种算法中，邻居交换和环算法均具有最优的通信局部性。我们在万亿次机群深腾6800、曙光4000A和华云神箭HYSJ-1000上对四个MPIAllgather算法进行了性能测试和分析，测试结果表明，邻居交换算法的长消息通信性能最优，中长消息通信性能不稳定，短消息通信性能次于递归倍增和Bruck算法。本文还将MPIAllgather近邻通信的思想进行扩展，设计了MPIAllreduce邻居交换算法。 本文另一部分研究工作集中在压缩查询并行化算法设计与实现方面。gzip是现今流行的无损数据压缩软件，压缩大文件时需要较长的时间。为提高压缩/解压缩速度，我们开发了一种新的基于OpenMP的并行压缩软件Ompgzip，与gzip完全兼容，能够在稍微损失一点压缩比的情况下大大提高压缩速度，加速比平均达到4，并行解压缩速度也有所提高。本文详细介绍了Ompgzip的并行思想、实现框架、软件实现和优化技术、软件测试效果、在实现中遇到的难题、可能的解决办法和对未来工作的展望。Ompgzip具有良好的应用前景。 压缩查询支持在不解开压缩文件的情况下对源文件进行查询，是一个较新的研究领域，目前还没有很成熟的算法。本文研究了压缩查询索引FM-Index的文件格式和算法原理，针对FM-Index压缩和建立索引过程种内存需求过大的问题，提出了分块的FM-Index设计，给出了分块设计下压缩、建立索引和查询的方法，并设计了分块方式下FM-Index的并行化算法，这些设计提高了FM-Index处理大文件的能力，使它具有良好的应用前景。

目录

文摘

英文文摘

论文说明：图目录及表格目录

第1章 绪论

第2章MPI_ Allgather算法研究

第3章通信算法的局部性

第4章 数据压缩及压缩查询

第5章 并行gzip压缩软件的设计与实现

第6章 解决FM-Index大内存需求问题的思考

第7章结束语

参考文献

致谢

发表论文情况