基于网络流模型的统计费用流相位解缠并行算法研究

发布时间：2018-03-06 16:25

本文选题：MPI　切入点：OpenMP　出处：《成都理工大学》2012年硕士论文　论文类型：学位论文

【摘要】：随着计算机应用的范围越来越广，处理问题的规模越来越大，计算机硬件得到了迅速发展，近年来已经进入到多核体系结构、个人高性能计算机、千万亿次并行机的发展阶段。为了适应迅速发展的计算机硬件和满足各应用领域对计算能力日益剧增的需求，并行计算技术得到了快速发展并广泛地应用于天体物理、流体力学、油藏建模、海洋环流、中长期天气预报、地震数据处理、生物信息处理、计算机辅助设计、数据库管理、图像处理以及商用搜索引擎等领域。根据处理器架构和存储器类型的不同，并行计算分为分布式并行计算和共享存储并行计算。分布式并行计算一般采用消息传递模型，MPI（消息传递接口）是当前的消息传递编程标准，具有可移植性好，高效率等优点。而OpenMP是共享存储模型的标准，对于描述单个SMP节点内部处理器之间的通信更加有效。目前结合两者优势的MPI+OpenMP多层次并行编程模型已成为主流编程技术，这种并行编程模型在多核体系结构中能够充分地发挥MPI与OpenMP之间的互补优势。本文以合成孔径雷达干涉测量（InSAR）技术中的基于网络模型的统计费用流相位解缠算法为应用基础，针对海量SAR数据处理面临计算资源不足和相对运算效率不高的问题，将统计费用流相位解缠算法进行并行化以提高相位解缠的运算效率，为InSAR数据处理中其他环节的并行处理奠定基础。本文首先研究了近几十年来国内外的并行计算技术以及一些经典的并行编程模型，然后选择MPI和OpenMP作为主要研究对象，分析它们的编程模型以及MPI+OpenMP多层次并行编程模型。在此基础上，分析研究了统计费用流相位解缠串行算法，挖掘该算法的内在并行性，设计与实现了基于MPI的统计费用流相位解缠并行算法，并进一步分析了统计费用流相位解缠串行算法中可细粒度并行计算的代码，实现了基于MPI+OpenMP多层次并行编程的统计费用流相位解缠并行算法。在研究过程中，分别对MPI环境和多层次并行编程MPI+OpenMP环境下的统计费用流相位解缠并行算法进行了不同计算规模的性能比较实验，验证了多层次并行编程具有良好的并行计算加速性能。在实现基于MPI的统计费用流相位解缠并行算法过程中，本文还研究了MPI-2中的并行I/O技术，根据相位解缠过程中I/O操作的特性，采用显示偏移量的并行I/O方式进行处理，，并通过实验验证了加入并行I/O技术的统计费用流相位解缠并行算法的性能更好。通过实验与分析表明，本文设计与实现的基于纯MPI和基于MPI+OpenMP多层次并行的两种统计费用流相位解缠并行算法均有效地增加了相位解缠的效率，减少了解缠过程中内存空间的开销，并且在一定条件下，相同计算规模的MPI+OpenMP多层次并行算法性能优于纯MPI的并行算法。
[Abstract]:With the wide application of computer, the scale of dealing with the problem is becoming larger and larger, the computer hardware has been rapidly developed, in recent years has entered the multi-core architecture, personal high-performance computer, In order to adapt to the rapid development of computer hardware and meet the increasing demand for computing power in various application fields, parallel computing technology has been rapidly developed and widely used in astrophysics. Fluid mechanics, reservoir modeling, ocean circulation, medium and long term weather forecasting, seismic data processing, biological information processing, computer aided design, database management, image processing and commercial search engines. Depending on the processor architecture and memory type, Parallel computing is divided into distributed parallel computing and shared storage parallel computing. Generally, distributed parallel computing adopts message passing model (MPI), which is the current message passing programming standard, and has good portability. OpenMP is the standard of shared storage model, which is more effective in describing the communication between the internal processors of a single SMP node. At present, the multilevel parallel programming model of MPI OpenMP, which combines the advantages of both, has become the mainstream programming technology. This parallel programming model can take full advantage of the complementary advantages between MPI and OpenMP in multi-core architecture. Based on the statistical cost flow phase unwrapping algorithm based on network model in synthetic Aperture Radar Interferometry (SAR) technology, this paper aims at the problems of insufficient computing resources and low relative computational efficiency for massive SAR data processing. The statistical cost flow phase unwrapping algorithm is parallelized to improve the efficiency of phase unwrapping. This paper first studies the parallel computing technology and some classical parallel programming models at home and abroad in recent decades, and then chooses MPI and OpenMP as the main research objects. Their programming models and MPI OpenMP multilevel parallel programming models are analyzed. Based on this, the statistical cost flow phase unwrapping serial algorithm is analyzed and the inherent parallelism of the algorithm is explored. A phase unwrapping parallel algorithm based on MPI is designed and implemented, and the code of fine-grained parallel computation in the phase unwrapping serial algorithm of statistical cost flow is analyzed. The phase unwrapping parallel algorithm of statistical cost flow based on MPI OpenMP multilevel parallel programming is implemented. The performance comparison experiments of statistical cost flow phase unwrapping parallel algorithms in MPI environment and multi-level parallel programming MPI OpenMP environment are carried out, and the results show that multi-level parallel programming has good parallel computing acceleration performance. In the process of implementing the phase unwrapping parallel algorithm based on MPI, the parallel I / O technique in MPI-2 is also studied. According to the characteristics of I / O operation during phase unwrapping, the parallel I / O method is used to display the offset. The performance of phase unwrapping parallel algorithm with parallel I / O technique is proved to be better by experiments. The experiments and analysis show that the two parallel algorithms of phase unwrapping based on pure MPI and MPI OpenMP, which are based on pure MPI and MPI OpenMP, both increase the efficiency of phase unwrapping effectively. Under certain conditions, the performance of MPI OpenMP multi-level parallel algorithm with the same computational size is superior to that of pure MPI parallel algorithm.
【学位授予单位】：成都理工大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP338.6;TN957.52

【参考文献】