毕业设计论文-高斯消去法求解线性方程组.doc
《毕业设计论文-高斯消去法求解线性方程组.doc》由会员分享，可在线阅读，更多相关《毕业设计论文-高斯消去法求解线性方程组.doc（42页珍藏版）》请在冰点文库上搜索。
摘要
高斯消去法是求解线性方程组的最基本的方法之一。
为了充分利用GPU（GraphicsProcessingUnit，图形处理器）的并行处理能力，本文改进了高斯列主元消去法的实现过程，从而提高了求解线性方程组的速度。
并研究了在不同方程组阶数下，GPU对这此算法的加速效果。
NVIDIA新近推出的GPU计算平台采用矩阵型的计算架构，对处理大型矩阵具有极大的优势，且相对CPU有着更高的算法可并行性和计算效率。
本文力图基于GPU的CUDA开发环境，利用GP-GPU的计算特性实现求解线性方程组，以提高算法的运行效率。
最后，本文用C语言实现了高斯列主元消去算法求解线性方程组的基本过程，并分别在NVIDIAGPU并行计算平台和IntelCPU计算平台上加以运行，同时进行了两种计算平台上算法实现的性能比较。
关键词：
求解线性方程组；高斯消去法；GPU；CUDA；并行计算
Abstract
Gaussianeliminationmethodisoneofthemostbasicmethodsforsolvinglinearequations.InordertotakefulladvantageofGPU（GraphicsProcessingUnit,GPU）oftheparallelprocessingcapability,thispaperimprovedGaussianPCAoutoftherealizationoftheprocessofelimination,resultinginimprovedsystemoflinearequationstosolvethespeed.Andstudiedthedifferentequationsinafewbands,GPUacceleratedtheeffectofthisalgorithm.NVIDIArecentlyintroducedtheuseofGPUcomputingplatformforthecalculationofmatrix-typestructure,todealwithlarge-scalematrixhasgreatadvantages,andtherelativeCPUalgorithmhashighercomputationalefficiencyandparallelism.ThisarticleseekstoCUDAforGPU-baseddevelopmentenvironment,theuseofGP-GPUcomputingfeaturestoachievethesolutionoflinearequationsinordertoimprovetheefficiencyofalgorithm.Finally,usingClanguagerealizationoftheGaussianeliminationalgorithmPCAoutoflinearequationstosolvethebasicprocessandNVIDIAGPUinparallelcomputingplatformandIntelCPUcomputingplatformtoberun,atthesametimeontwotypesofcomputingplatformsalgorithmPerformanceComparisonoftheachievement.
Key words:
Solving linear equations; Gaussian elimination method;GPU;CUDA;Parallel Computing
目录
第一章绪论 1
1.1引言 1
1.2论文研究背景 1
1.3论文研究的目的和意义 2
1.4论文结构安排 3
第二章求解线性方程组的基本理论 4
2.1高斯－约当消去法 4
2.2矩阵三角分解法 5
直接三角分解法 5
追赶法 5
2.3平方根法 6
2.4迭代法 6
2.5高斯消去法 7
2.6高斯列主元素消去法 10
第三章NVIDIACUDA并行计算平台 12
3.1GPU技术简介 12
3.2CUDA介绍 14
3.3CUDA编程模型 18
3.4应用程序接口 21
编程语言扩展 21
第四章功能实现和相关函数介绍 23
4.1程序在CPU上的实现 23
高斯列主元消去算法实现过程 23
各文件中的主要功能函数介绍 25
4.2程序在GPU上的实现 27
文件中C语言的扩展 27
文件编写过程 30
并行性实现 32
4.3性能比较与结果分析 33
第五章总结与展望 37
致谢 38
参考文献 39
毕业设计说明书（论文）
第一章绪论
1.1引言
当今很多科学与工程计算问题大都可以化为线性代数方程组的形式，所以有效的求解线性方程组在科学和工程计算中是非常重要的。
虽然线性代数方程的求解方法和数值计算软件包均很成熟，但随着并行计算机的发展，问题的求解速度和解题规模都大大提高，因而使数值计算方法和响应的数学软件包都产生了变化，相应地线性方程组的有效并行求解也引起了人们的普遍关注。
本文讨论使用并行算法解线性方程组，介绍了并行计算理论，求解线性方程组的串行算法的实现以及并行化。
本文算法用C语言描述，用VS2005环境进行编译，用高斯消去法求线性方程组的解并成功运行程序求解方程。
1.2论文研究背景
在工程领域里，在进行系统分析和设计时，首先要建立系统的数学模型。
求解线性方程组一直是解决许多数值计算问题的核心,因此对大规模线性方程组的求解在科学计算中显得非常重要。
线性方程组求解是有限元结构分析的基础，求解线性方程组的方法有直接法和迭代法两种，直接法的优点是可以预先估计计算的工作量并且根据消去法的基本原理，可以得到有关矩阵运算的一些方法，它求解稳定，精度有保证，是有限元方程求解的主要方法。
迭代法是是用某种极限过程去逐步逼近线性方程组精确解的方法。
对于那些要求快速计算的应用问题，单处理机由于器件受物理速度的限制而无法满足要求，所以使用多台处理机联合求解就势在必行了；其次，对于那些大型复杂的科学工程计算问题，为了提高计算精度，往往需要加密计算网格，而细网格的计算也意味着大计算量，它通常需要在并行机上实现；最后，对于那些实时性要求很高的应用问题，传统的串行处理往往难以满足实时性的需要而必须在并行机上用并行算法求解。
在实现算法方面主要有串行和并行两种。
串行算法在执行的过程中，对于数据的处理是串行的，也就是一次只能处理一个数据，显然效率比较低下，而并行算法则不存在这样的问题。
所谓并行算法就是用多台处理机联合求解问题的方法和步骤，其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问题，然后使用多台计算机同时求解它，从而最终求得原问题的解。
利用GPU强大的计算性能显著提高方程组的求解速度，弥补CPU的不足，把CPU从复杂计算中解放出来，毫无疑问GPU今后会继续往两个方面发展，一方面是具备更强大的性能和更高的运算能力；另一方面就是可编程性和通用性更强。
不论是游戏视频还是各种应用程序，将会更多地借助到GPU的计算能力。
1.3论文研究的目的和意义
对计算机系统超过当前可能提供的计算速度的需求总是不断增长。
需要高计算速度的领域包括科学和工程问题的数值建模和模拟，这样的问题常需要对大量的数据进行很多次重复计算以得到有效的结果。
计算必须在“合理”的时间内完成。
在设计环境中，如果进行一次模拟需要两个星期才能得到结果，这通常是不可接受的。
因为只有模拟完成时间足够短时，设计者方可高效的工作。
当系统变得更复杂时，就需要增加更多时间对系统进行模拟。
有一些应用问题的计算对时间有特定的期限（最著名的要数气象预报），花两天的时间来获取当地第二天精确的天气预报将使得这种预报毫无意义。
某些研究领域，如对大型DNA结构建模以及进行全球天气预报均具有巨大挑战性问题。
所谓巨大挑战性的问题是指无法用当今计算机在结合里的时间内完成求解的那些问题。
解决这些问题都要依靠多处理器的并行计算机，其处理器通常达到几百台。
它的优势主要体现在以下几个方面：
1.它可以加快速度，即在更短的时间内解决相同的问题或在相同的时间内解决更多更复杂的问题，特别是对一些新出现的巨大挑战问题，不使用并行计算，有时根本无法解决的；2.节省投入，并行计算可以以较低的投入完成串行计算的任务；3.物理极限的约束，光速是不可逾越的速度极限，设备和材料也不可能做得无限小，只有通过并行才能够不断提高
第38页
速度。
本文的主要工作是从并行算法的实现出发，结合并行程序的设计特点，并行算法和并行应用程序进行了一些基本的研究与探索。
1.4论文结构安排
论文将按照下面的描述进行内容的安排。
第一章介绍本论文的研究背景及现实意义，以及论文的组织；第二章介绍了求解线性方程组的基本理论：
第三章主要针对NVIDIACUDA并行计算平台进行分析并介绍了图形处理单元GPU的特点和工作模式，及相较于CPU的优点，并简单介绍了用CUDA环境实现在GPU上的并行处理的编程模型，描述了其使用的C扩展语言；第四章首先介绍了各个功能的实现和相关的主要函数，然后阐述了对于基于并行计算平台的功能的实现及与CPU平台的比较。
结束语主要对论文进行总结，并对今后的研究设想做了展望。
第二章求解线性方程组的基本理论
在自然科学和工程技术中很多问题的解决常常归结为解线性代数方程组，例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元方法解常微分方程、偏微分方程边值问题等都导致求解线性方程组，而这些方程组的系数矩阵大致分为两种，一种是低阶稠密矩阵（例如，阶数不超过150），另一种是大型稀疏矩阵（即矩阵阶数高且零元素较多）。
关于线性方程组的数值解法一般有两类：
直接法：
就是经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差）．但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解．下面将阐述这类算法中最基本的高斯消去法及其某些变形．这类方法是解低阶稠密矩阵方程组及其某些大型稀疏方程组（例如，大型带状方程组）的有效方法。
迭代法：
就是用某种极限过程去逐步逼近线性方程组精确解的方法．迭代法具有需要计算机的存贮单元较少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点，但存在收敛性用收敛速度问题．迭代法是解大型稀疏矩阵方程组的重要方法。
2.1高斯－约当消去法
高斯消去法始终是消去对角线下方的元素，现考虑高斯消去法的一种修正，即消去对角线下方和上方的元素，这种方法称为高斯－约当（Gauss-Jordan）消去法。
用高斯－约当方法将矩阵约化为单位矩阵，计算解就在常数项位置得到，因此用不着回代求解，用高斯约当方法解方程组其计算量大约需要次乘除法，要经高斯消去法大，但用高斯约当方法求一个矩阵的逆矩阵还是比较合适的。
2.2矩阵三角分解法
高斯消去法有很多变形，有的是高斯消去法的改进、改写，有的是用于某一类特殊性质矩阵的高斯消去法的简化。
2.2.1直接三角分解法
将高斯消去法改写为紧凑形式，可以直接从矩阵的元素得到计算，元素的递推公式，而不需任何中间步骤，这就是所谓直接三角分解法．一旦实现了矩阵A的LU分解，那么求解的问题就等价于求解两个三角形方程组
（1）Ly=b,求y：
（2）Ux=y,求x。
2.2.2追赶法
在一些实际总是中，例如解常微分方程边值问题，解热传导方程以及船体数学放样中建立三次样条函数等，都会要求解系数矩阵为对角占优的三对角线性方程组，而解三对角方程组的最简单方法是用追赶法，它公式简单，计算量小，所占用的存储单元少，所以在小机器上也能求解。
追赶法是用来求解三对角方程组的专用方法，对于三对角方程组，追赶法比Gauss消去法的计算量要小的多。
应用追赶法求解三对角线性方程组。
追赶法仍然保持LU分解特性,它是一种特殊的LU分解。
充分利用了系数矩阵的特点，而且使之分解更简单,得到对三对角线性方程组的快速解法。
设矩阵A非奇异，A有Crout分解A=LU，其中L为下三角矩阵，U为单位上三角矩阵，可先依次求出L，U中的元素后，令Ux=y，先求解下三角方程组Ly=f得出y，再求解上三角方程组Ux=y。
事实上，求解三对角方程组的2追赶法将矩阵三角分解的计算与求解两个三角方程组的计算放在一起，使算法吏为紧凑。
追赶发公式实际上就是把高斯消去法用到求解三对角线方程组上的结果。
这时由于A特别简单，因此使得求解的计算公式非常简单，而且计算量仅为5n-4次乘除法，而另外增加解一个方程组Ax=f2仅增加3n-2次乘除运算，易见追赶法的计算量是比较小的。
2.3平方根法
应用有限元法解结构力学问题时，最后归结为求解线性方程组，系数矩阵大多具有对称正定性质．系数矩阵为对称正定矩阵的方程组称为对称正定方程组，对称正定方程组可用高斯消去法、LU分解法求解，但可导出计算量更小的平方根法。
利用对称正定矩阵的三角分解（乔累斯基分解）求解对称正定方程组的方法称为平方根法，这种方法已成为目前计算机上广泛应用的有效方法。
2.4迭代法
迭代法的基本思想是构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规则。
由不同的计算规则得到不同的迭代法，本章介绍单步定常线性迭代法。
直接法比较适用于中小型方程组。
对高阶方程组，既使系数矩阵是稀疏的，但在运算中很难保持稀疏性，因而有存储量大，程序复杂等不足。
迭代法则能保持矩阵的稀疏性，具有计算简单，编制程序容易的优点，并在许多情况下收敛较快。
故能有效地解一些高阶方程组。
迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。
迭代法的两种主要方法分别是雅可比迭代法和高斯——塞德尔迭代法。
雅可比迭代法的特点是公式简单,每迭代一次只需计算一次矩阵和向量的乘法.高斯—塞德尔迭代法相比与雅可比迭代法收敛快（达到同样的精度所需迭代次数少）。
下面重点介绍本课题所选用的高斯消去法和高斯列主元素消去法的基本原理。
2.5高斯消去法
设有线性方程组
（2.1.1）
或写为矩阵形式
简记为Ax=b。
用消去法解方程组的基本思想是用逐次消去未知数的方法把原方程组化为与其其的三角方程组．而求解三角方程组可用回代的方法求解．换句话说，上述过程就是用行的初等变换将原方程组系数矩阵化为简单形式（上三角矩阵），从而将求解原方程组（2.1.1）的问题转化为求解简单方程组的问题．或者说，对系数矩阵Ａ施行一些左变换（用一些简单矩阵）将其约化为上三角矩阵。
将（2.1.1）记为
其中
（1）第１步（k=1）.
设，首先计算乘数
用－乘（2.1.1）的第一个方程，加到第i个（）方程上，消去（2.1.1）的从第二个方程到第m个方程中的未知数，得到与（2.1.1）等价的方程组
（）
简记为，
其中的元素计算公式为
（2）第k次消元（）
设上述第1步,…，第k-1步消元过程计算已经完成，即已计算好（2.1）等价的方程组
（2.2）
简记为。
设，计算乘数
用乘（2.2）的第k个方程加到第i个方程，消去从第k+1个方程到第m个方程中的未知数，得到与（２.１）等价的方程组
其中元素的计算公式为
（2.3）
显然中从第1行到第k行相同．
（3）继续上述过程，且设，直到完成第s步消元计算．最后得到与原方程组等价的简单方程组，其中为上梯形．
特别当m=n时，与原方程组等价的方程组为，即
（2.4）
由（2.1）约化为（2.4）的过程称为消元过程。
如果是非奇异矩阵，且，求解三角形方程组（2.1），得到求解公式
（2.5）
（2.4）的求解过程（2.5）称为回代过程。
注意：
设，其中为非奇异矩阵，如果，由于为非奇异矩阵，所以的第一列一定有非零元素（不妨设），于是可交换两行元素（即），将调到（1,1）位置，然后进行消元计算，这时右下角矩阵为n-1阶非奇异矩阵，继续这过程，高斯消去法照样可进行计算。
总结上述讨论即有
设，其中．那么
（1）如果，则可通过高斯消去法将Ax=b约化为等价的三角方程组（2.4），且计算公式为：
（a）消元计算（k=1,2,…,n-1）
（b）回代计算
（2）如果为非奇异矩阵，则可通过高斯消去法（及交换两行的初等变换）将方程组约化为（2.4）。
2.6高斯列主元素消去法
由高斯消去法知道，在消元过程中可能出现＝0的情况，这时消去法将无法进行；即使主元素但很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可靠。
设方程组（2.1）的增广矩阵为
首先在的第一列中选取绝对值最大的元素作为主元素．例如，
然后交换的第１行和第行，经第1次消元计算得
．
重复上述过程，设已完成k-1步的选主元素，交换两行及消元计算，约化为
，
其中的元素仍记为，的元素仍记为。
第步选主元素（在右下角方阵的第１列内选），即确定，使
交换的第k行和第行的元素，再进行消元计算，最后将原方程组化为
回代求解得
第三章NVIDIACUDA并行计算平台
3.1GPU技术简介
GPU英文全称GraphicProcessingUnit，中文翻译为“图形处理器”。
GPU是相对于CPU的一个概念，由于在现代的计算机中图形的处理变得越来越重要，需要一个专门的图形的核心处理器。
NVIDIA公司在1999年发布GeForce256图形处理芯片时首先提出GPU的概念。
GPU使显卡减少了对CPU的依赖，并进行部分原本CPU的工作，尤其是在3D图形处理时。
GPU所采用的核心技术有硬体T&L、立方环境材质贴图和顶点混合、纹理压缩和凹凸映射贴图、双重纹理四像素256位渲染引擎等，而硬体T&L技术可以说是GPU的标志。
下图为GPU的图像处理机制。
近年来，GPU正在以大大超过摩尔定律的速度高速发展，极大的提高了计算机图形处理的速度和质量，不但促进了图像处理、虚拟现实、计算机仿真等相关应用领域的快速发展，同时也为人们利用GPU进行图形处理以外的通用计算提供了良好的运行平台。
目前GPU的浮点运算能力已经达到了接近370GFLOPS，而CPU却只有32GFLOPS，二者对比差别很大，另外，GPU有更大的内存带宽，目前已经达到了86.4GB/s，相当于CPU的10倍。
如果能够充分利用这种计算能力和存取能力，那么GPU将能够更好地体现其价值。
图形处理器技术的迅速发展带来的并不只是速度的提高，还产生了很多全新的图形硬件技术，使GPU具有流处理、高密集并行运算、可编程流水线等特性，从而极大的拓展了GPU的处理能力和应用范围。
正是由于GPU具有高效的并行性和灵活的可编程性等特点，越来越多的研究人员和商业组织开始利用GPU完成一些非图形绘制方面的计算，并开创了一个新的研究领域：
基于GPU的通用计算（GPGPU，General-PurposecomputationonGPU），其主要研究内容是如何利用GPU在图形处理之外的其他领域进行更为广泛的科学计算。
目前已成功应用于运动规划、代数运算、优化计算、偏微分方程、数值求解、流体模拟、数据库应用、频谱分析等非图形应用领域，甚至包括智能信息处理系统和数据挖掘工具等商业化应用。
同时，也产生了一些针对GPU开发的通用计算工具包，能够基于GPU平台对FFT、BLAS、排序及线性方程组求解等科学计算进行优化实现。
基于GPU的通用计算已成为近几年人们关注的一个研究热点。
将GPU用于通用计算的主要目的是为了加速计算，加速的动力来自GPU在高性能计算方面所具有的优势：
（1）高效的并行性。
这一功能主要是通过GPU多条绘制流水线的并行计算来体现的。
在目前主流的GPU中，配置多达16个片段处理流水线，6个顶点处理流水线。
多条流水线可以在单一控制部件的集中控制下运行，也可以独立运行。
GPU的顶点处理流水线使用MIMD方式控制，片段处理流水线使用SIMD结构。
相对于并行机而言，GPU提供的并行性在十分廉价的基础上，为很多适合于在GPU上进行处理的应用提供了一个很好的并行方案。
（2）高密集的运算。
GPU通常具有128位或256位的内存位宽，因此GPU在计算密集型应用方面具有很好的性能。
（3）超长图形流水线。
GPU超长图形流水线的设计以吞吐量的最大化为目标（如NVIDIAGeForce3流水线有800个阶段），因此GPU作为数据流并行处理机，在对大规模的数据流并行处理方面具有明显的优势。
CPU中的大部分晶体管主要用于构建控制电路（如分支预测等）和Cache，只有少部分的晶体管来完成实际的运算工作。
GPU与CPU的设计目标不同，其控制电路相对简单，而且对Cache的需求较小，所以大部分晶体管可以组成各类专用电路和多条流水线，使GPU的计算速度有了突破性的飞跃，拥有惊人的处理浮点运算的能力。
正是由于GPU在并行处理和计算密集型问题求解等方面所具有的诸多优势，GPU已成为目前普通PC机所拥有的强大、高效的计算资源。
从系统架构上看，GPU是针对向量计算进行了优化的高度并行的数据流处理机。
这种以数据流作为处理单元的处理机，在对数据流的处理上可以获得很高的效率。
根据NVIDIA公司开发的GPU工具包CUDA（ComputeUnifiedDeviceArchitecture）的测试结果显示，利用GPU实现FFT、BLAS、排序及线性方程组求解等科学计算，与单纯依靠CPU实现的算法相比，平均性能提高了近20倍。
由此可见，GPU的发展速度（包括集成度、计算密集型问题的处理能力等）已远远超过通用处理器，特别是随着可编程能力、并行处理能力和应用范围方面得到不断提升和扩展，使得GPU已成为当前计算机系统中具备高性能处理能力的部件。
因此，充分利用现有计算资源，发挥GPU的高性能计算能力，在GPU与CPU的协作模式、GPU通用计算的计算模式以及性能优化等方面进行深入研究，将对进一步拓展目前高性能计算体系结构，为科学计算和工程应用提供新型的计算资源具有重要意义。
3.2CUDA介绍
由于GPU浮点计算性能强劲，灵活性高，以GPU为计算平台的应用也越来越多，而不仅仅局限于计算机图形学。
如[Kruger2003]将纹理作为矩阵的表示数据结构，在GPU中实现了一些线性代数的数值算法。
而
[Bolz2003]则利用GPU来进行稀疏矩阵的共轭梯度计算等。
[Govidaraju2004]甚至利用GPU来进行数据库的海量操作计算。
这方面最优秀的成果之一，是通用GPU语言的研究。
典型的代表是Stanford大学的Brook项目和加拿大Waterl
升级会员 