基于MPI的矩阵运算算法研究与实现

发布时间：2018-05-20 12:41

本文选题：并行计算 + MPI　；参考：《吉林大学》2014年硕士论文

【摘要】：科学技术发展至今，科学理论、科学计算、科学实验、全球气侯预报、核聚变等粒子模型、大型计量经济模型、人类基因等，这些重要的科学技术课题中爆炸式增长的数据计算量必然向传统的Von Neuman串行计算技术提出挑战，对高性能计算提出巨大的需求。在如图形图像处理和分析、数字信号滤波计算、数值天气预报、网络路由选择、智能交通系统最短路径、线性规划、傅里叶变换等众多数值处理问题的理论模型中，矩阵是描述和存储大规模数据最常用的逻辑结构，相关应用中，和矩阵紧密相连的求解问题不胜枚举，因此，有关矩阵的运算是许多科学和工程计算中最重要也是最基本的技术之一，近二十年来这方面的并行算法研究一直十分活跃。本文运用虚拟机技术、网络技术、操作系统等有关理论构建了一个由以太网互联四台虚拟机的机群系统，每个虚拟机的操作系统为Linux的ubuntu版本，整个并行平台为MPICH2并行环境。全文的并行算法研究工作都是以此平台为基础进行的。文中详细介绍了并行编译系统、并行算法的含义和结构、MPI并行编程技术、并行性能评价指标和并行基础应用。本文基于抽象的计算模型，通过并行化串行算法，改进已有并行算法，以及直接从问题本身出发研究新的算法这三种方式对矩阵乘的并行算法进行研究，并以不同的数据划分方式将算法分为带状划分算法和棋盘划分算法两大类，详细阐明了带状划分算法中的行列、行行、列列、列行划分算法和棋盘划分算法中的Fox、Cannon算法。在算法的实现过程中，本文着眼于对并行程序性能的不断优化。并行程序的优化分为串行部分的优化和并行部分的优化两方面。将并行程序在构建的机群环境中进行测试，分析和对比运行效率。本文构建了一个完整的小型虚拟机群系统，并以其为平台运用并行技术解决了具体的应用问题。通过调用并行库，，将矩阵乘算法的设计思路应用到最短路径的求解以及卷积运算中去，设计并实现相应的并行算法，取得了较好的效果。
[Abstract]:So far, scientific theories, scientific calculations, scientific experiments, global weather forecasting, nuclear fusion and other particle models, large-scale econometric models, human genes, etc. The explosive increase of data computation in these important scientific and technological subjects will inevitably challenge the traditional Von Neuman serial computing technology and bring forward a huge demand for high performance computing. In the theoretical models of many numerical processing problems, such as graphic image processing and analysis, digital signal filtering calculation, numerical weather forecast, network routing, intelligent transportation system shortest path, linear programming, Fourier transform, etc. Matrix is the most commonly used logical structure to describe and store large scale data. The computation of matrices is one of the most important and basic techniques in many scientific and engineering computations. The study of parallel algorithms in this field has been very active in the past two decades. This paper constructs a cluster system of four virtual machines interconnected by Ethernet using virtual machine technology, network technology and operating system theory. The operating system of each virtual machine is ubuntu version of Linux, and the whole parallel platform is MPICH2 parallel environment. The research work of parallel algorithms is based on this platform. The parallel compiling system, the meaning and structure of parallel algorithm, MPI parallel programming technology, parallel performance evaluation index and parallel basic application are introduced in detail in this paper. Based on the abstract computing model, this paper studies the parallel algorithm of matrix multiplication by parallelizing the serial algorithm, improving the existing parallel algorithm, and studying the new algorithm directly from the problem itself. The algorithms are divided into two categories: banded partition algorithm and chessboard partition algorithm by different data partitioning methods. The row, column, column row partition algorithm and the Fox-Cannon algorithm in the chessboard partitioning algorithm are expounded in detail. In the implementation of the algorithm, this paper focuses on the continuous optimization of the performance of parallel programs. The optimization of parallel program is divided into two aspects: the optimization of serial part and the optimization of parallel part. The parallel program is tested in the cluster environment, and the efficiency is analyzed and compared. In this paper, a complete small virtual machine swarm system is constructed, and the parallel technology is used to solve the specific application problem. By calling the parallel library, the design idea of matrix multiplication algorithm is applied to the solution of shortest path and convolution operation, and the corresponding parallel algorithm is designed and implemented, and good results are obtained.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：O151.21;TP302

【参考文献】