基于MPI的海量数据拟合并行算法研究

论文摘要

随着计算机技术在各学科领域中的广泛应用,尤其是在天体物理、地质、石油、气象、医学等领域产生了大量的科学数据,为了解释这些数据或者根据这些数据做出预测、判断,需要寻找一个反映数据变化规律的函数；另外,随着现代计算机技术的发展,更多的领域需要对海量数据进行处理,并对计算机处理精度和处理速度提出了更高的要求。对于给定的一批离散海量数据,如何快速得到具有最佳逼近关系的函数模型是本课题的研究重点。面对多种多样的数学模型和海量数据,进行数据拟合时都需要计算机的大量计算和内存容量,在计算机单机系统中,相对的存在内存资源不足和计算速度慢的问题,使得现有的计算机处理能力不能满足实际的需要；而并行计算能够降低单个问题求解的时间,增加问题求解规模、提高问题求解精度,是进行大规模数值计算发展的必然趋势,故本文进行数据拟合并行算法的研究,具有一定的研究意义和较大的应用价值。近年来,集群系统以其低成本、高性能的特性提供了强大的并行计算能力和批处理能力,代表了高性能计算机发展的新方向。消息传递是目前集群系统广泛使用的一种程序设计模式,MPI则是其中最受欢迎的设计平台,被应用在各个领域中。本文基于MPI在集群环境下对数据拟合并行算法进行研究和实现。本文首先通过研究基于MPI和Linux的集群系统的构建和应用,在Red Hat Linux环境下,实现了基于MPICH集群系统的构建；其次给出了线性模型数据拟合的并行算法描述,分析了该并行算法的任务分配、通信开销、负载平衡等问题。对于给定的函数集合,将该集合中的元素以全组合方式线性生成不同的函数模型,把不同的函数拟合作为不同的子任务分摊到各个节点上,每个节点独立地进行拟合求解,再把拟合结果汇集,根据一定标准选择出最佳模型,并且采用接收者启动算法——动态负载平衡策略以实现模型的分配；通过多项式拟合在PC集群环境下的实现,比较串行多项式拟合与并行多项式拟合运算时耗的差别,并分析并行算法的性能,从而探索建立集群环境对于解决海量数据多项式拟合次数范围大、运算速度过慢等问题的可行性；最后从数据的预处理及数据分割、输入输出层的确定、隐含层数及隐含层节点数的确定等方面讨论了单节点BP网络模型的构建,进行并行BP神经网络算法的研究,并分析了算法性能,给出了一定的改进设想。

论文目录

• 基于MPI的海量数据拟合并行算法研究
• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.3 论文研究内容
• 1.4 论文组织结构
• 第2章 并行计算机系统及并行程序设计方法概述
• 2.1 并行计算机系统简介
• 2.2 并行计算机系统的分类
• 2.3 并行计算模型
• 2.4 并行程序设计的基本模式
• 2.5 并行程序的设计过程
• 2.6 并行程序设计的性能度量
• 2.7 小结
• 第3章 基于Linux和MPI的PC集群系统的构建
• 3.1 PC集群系统概述
• 3.2 MPI并行程序设计
• 3.2.1 MPI编程模式
• 3.2.2 MPI的六个基本函数
• 3.2.3 MPI通信方式
• 3.3 基于Linux和MPI构建PC集群系统
• 3.3.1 PC集群系统硬件环境的选择
• 3.3.2 PC集群系统操作系统的选择
• 3.3.3 PC集群系统编程环境的选择
• 3.4 MPI程序示例
• 3.5 小结
• 第4章 线性模型数据拟合的并行算法研究
• 4.1 数据拟合函数模型的确定及组合生成
• 4.2 线性模型数据拟合的并行算法
• 4.2.1 算法描述
• 4.2.2 任务划分
• 4.2.3 通信模式及通信开销
• 4.2.4 数学模型分配——动态负载平衡
• 4.2.5 算法性能分析
• 4.3 多项式拟合并行算法实现及算法性能分析
• 4.3.1 一般多项式拟合串行算法描述
• 4.3.2 多项式拟合并行算法设计及实现
• 4.3.3 正交多项式拟合
• 4.3.4 实验测试分析
• 4.3.5 程序中遇到的问题及解决
• 4.4 小结
• 第5章 非线性模型数据拟合的并行算法研究
• 5.1 单节点BP网络模型的构建
• 5.2 非线性数据拟合的BP网络并行算法
• 5.2.1 算法描述
• 5.2.2 算法性能分析
• 5.2.3 算法改进
• 5.3 小结
• 第6章 结束语
• 参考文献
• 攻读学位期间发表的学术论文和研究成果
• 致谢
• 并行计算及数据拟合的一些问题研究
• 第1章 并行计算机应用及国内外研究现状
• 第2章 并行计算机系统介绍
• 2.1 并行计算机系统简介
• 2.2 并行计算机系统的分类
• 第3章 基于PC集群的MPI编程环境的构建
• 3.1 PC集群系统特点及分类
• 3.2 PC集群系统硬件的选择与安装
• 3.3 PC集群系统操作系统的选择
• 3.4 PC集群系统编程环境的选择
• 第4章 并行程序设计方法及MPI并行算法应用
• 4.1 并行计算模型
• 4.2 并行程序设计的基本模式
• 4.3 并行程序的设计过程
• 4.4 并行程序设计的调试
• 4.5 并行程序设计的性能度量
• 4.6 MPI并行程序设计
• 4.6.1 MPI编程模式
• 4.6.2 MPI的六个基本函数
• 4.6.3 MPI通信方式
• 4.6.4 MPI程序的执行
• 4.7 基于MPI并行算法应用
• 4.8 小结
• 第5章 线性模型拟合
• 5.1 数据拟合问题
• 5.2 多项式线性最小二乘拟合
• 5.3 正交多项式线性最小二乘拟合
• 5.3.1 标准正交函数系定义
• 5.3.2 构造正交基函数的Gram-Schmidt方法
• 5.3.3 常用的正交多项式
• 5.3.4 正交多项式线性最小二乘拟合步骤
• 5.4 函数的最小二乘逼近多项式
• 5.5 函数式自动生成
• 5.6 线性模型拟合的并行算法
• 第6章 非线性模型拟合
• 6.1 问题描述
• 6.2 常用的非线性曲线模型及线性变换
• 6.3 迭代法
• 6.3.1 非线性模型的直接拟合原理
• 6.3.2 牛顿迭代法
• 6.4 遗传算法
• 6.5 神经网络法
• 6.5.1 BP神经网络
• 6.5.2 小波神经网络
• 6.6 其他方法
• 6.6.1 极大似然法
• 6.6.2 模拟退火法
• 6.6.3 缩张算法
• 参考文献
• Research on Parallel Altorithm of Mass Data Fitting Based on MPI
• Chapter 1 Introduction
• 1.1 Background of the research
• 1.2 the Study Status
• 1.3 Content of Research
• 1.4 Organizational Structure of the Paper
• Chapter 2 Introduction of Parallel Computer System and Parallel Program Design
• 2.1 The Introduction of Parallel Computer System
• 2.2 The Classification of the Parallel Computer System
• 2.3 Parallel Calculating Model
• 2.4 The Primary Modes of Parallel Program Designing
• 2.5 Parallel Programming Designing
• 2.6 The Measurements of Parallel programming performance
• 2.7 Summary
• Chapter 3 The MPI Programming Environment Construction in PC Clusters
• 3.1 The Features and Classification of the PC Cluster System
• 3.2 MPI Parallel Programming Designing
• 3.2.1 MPI Programming Model
• 3.2.2 Six Basic Functions of MPI
• 3.2.3 The Communicative Way of MPI
• 3.3 The Structures of PC Cluster Based on MPI and Linux
• 3.3.1 The Choice of PC Cluster System Hardware Environment
• 3.3.2 The Choice of PC Cluster System Operating System
• 3.3.3 The Choice of PC Cluster System Programming Environment
• 3.4 The Example of MPI Procedures
• 3.5 Summary
• Chapter 4 Research on Parallel Algorithm of Data Fitting in Linear Model
• 4.1 Determining Data Fitting Function and Generation
• 4.2 parallel Algorithm of Data Fitting in Linear Model
• 4.2.1 Description of the Algorithm
• 4.2.2 Division of Tasks
• 4.2.3 Communication Model and Cost
• 4.2.4 Mathematical Model Distribution-Dynamic Load Balancing
• 4.2.5 Analysis of Algorithm Performance
• 4.3 Implementation and Performance Analysis of Polynomial Fitting Parallel Algorithm
• 4.3.1 Description of Serial Algorithm in Universal Polynomial Fitting
• 4.3.2 Design and Implementation of Polynomial Fitting Parallel Algorithm
• 4.3.3 Orthogonal Polynomial Fitting
• 4.3.4 Test Analysis of the Experiments
• 4.3.5 Problems and Solutions Encountered in the Programs
• 4.4 Summary
• Chapter 5 Research on Nonlinear Model Data Fitting of Parallel Algorithm
• 5.1 The Construction of Single-node Neural Network Model
• 5.2 Nonlinear Fitting the BP Data Network Parallel Algorithm
• 5.2.1 Algorithm Description
• 5.2.2 Algorithm Performance Analysis
• 5.2.3 The Improvement of Algorithm
• 5.3 Summary
• Chapter 6 Conclusion
• Research on Some Problems of Parallel Computing and Data Fitting
• Chapter 1 Parallel Computer Applications and Study Status
• Chapter 2 The Introduction of Parallel Computer System
• 2.2 The Classification of the Parallel Computer System
• Chapter 3 The MPI Programming Environment Construction in PC Clusters
• 3.1 The Features and Classification of the PC Cluster System
• 3.2 Choosing Hardware of Cluster System
• 3.3 Choosing Operating System of Cluster System
• 3.4 Choosing Programming Environment of Cluster System
• Chapter 4 The Design Approaches of Parallel Program
• 4.1 Parallel Computation Model
• 4.2 The Primary Modes of Parallel Program Designing
• 4.3 Parallel Programming Designing
• 4.4 Parallel Programming Debugging
• 4.5 The Measurements of Parallel programming performance
• 4.6 MPI Parallel Programming Designing
• 4.6.1 MPI Programming Model
• 4.6.2 Six Basic Functions of MPI
• 4.6.3 The Communicative Way of MPI
• 4.6.4 The Operation of Process
• 4.7 Applications Based on MPI Parallel Algorithm
• 4.8 Summary
• Chapter 5 Linear Model Fitting
• 5.1 The Problem of Data Fitting
• 5.2 Serial Algorithm in Universal Polynomial Fitting
• 5.3 Orthogonal Polynomial Fitting
• 5.3.1 The Standard Definition of the Orthogonal Function
• 5.3.2 Construct Orthogonal Function with Gram-Schmidt Method
• 5.3.3 General Orthogonal Polynomial
• 5.3.4 Fitting Steps of Linear Least-square in Orthogonal Polynomial
• 5.4 The Least-squares Approximation Polynomial of Function
• 5.5 Functional Automatic Generation
• 5.6 Linear Model Fitting Parallel Algorithm
• Chapter 6 Model Fitting of Nonlinear
• 6.1 Description of the Problem
• 6.2 Commonly Used Non-linear and Linear Model of Transformation
• 6.3 Iteration
• 6.3.1 The Direct Fitting Principle of Nonlinear Model
• 6.3.2 Newton Iteration
• 6.4 Genetic Algorithm
• 6.5 Neural Network Method
• 6.5.1 BP Neural Network
• 6.5.2 Wavelet Neural Network （WNN）
• 6.6 Other Methods
• 6.6.1 Maximum Likelihood
• 6.6.2 Simulated Annealing
• 6.6.3 Contraction-Expansion Algorithm