LAPACK是由美国国家科学基金等资助开发的著名公开软件。LAPACK包含了求解科学与工程计算中最常见的数值线性代数问题,如求解
线性方程组、线性最小二乘问题、
特征值问题和
奇异值问题等。
背景引言
串行程序的自动
并行化是当今高性能计算领域的一个重要研究热点,也是自有高性能并行计算机以来人们 梦寐以求的一个目标.在并行计算机硬件技术蓬勃高速发展的今天,国外已有万亿次, 四万亿次超大规模并行计算机问世,这就为一批急需解决的大型 科学工程计算问题提供了有利 的物资基础.但是,与上述蓬勃发展的态势相比,并行算法, 并行软件技术, 并行
开发环境和 支持工 具的严重滞后,大大影 响了并行计算机的应用效率与市场推广.目前国内外各大并行机公司与应用部 都在加大 力度投入大量人力、 物力、 财力加速并行软件的开发, 其中包括把现有大量成熟的串行软件移植到并行机上, 这对实际的生产及应用有着重要意义.人工并行化虽然能达到较高 的性能, 但要求对并行计算方法及并行机结构都有较深的了解,而且工作量大, 效率低, 易出错, 这对于大多数应用人员是不现实的, 因此人们 迫切需要有效的 自动并行化工具.现在国际上 已有不少商业化和 非商业化的通用 自动并行化工具, 但是普遍存在实用与效率问题。LAPACK线性代数软件包是一个可以实用高效地解决上述问题的自动并行化工 具
简介
LAPACK,其名为Linear Algebra PACKage的缩写,是一以Fortran编程语言写就,用于
数值计算的函式集。 LAPACK提供了丰富的工具函式,可用于诸如解多元线性方程式、线性系统方程组的最小平方解、计算特征向量、用于计算矩阵QR分解的Householder转换、以及奇异值分解等问题。 在NetLib亦提供了API经简化的Fortran 95版本的LAPACK95。LAPACK以BSD授权的方法释出。
命名规则
LAPACK里的每个函数名已经说明了该函数的使用规则。所有函数都是以XYYZZZ的形式命名,对于某些函数,没有第六个字符,只是XYYZZ的形式。
第一个字母X代表以下的数据类型:SREAL,单精度实数;DDOUBLEPRECISION,双精度实数;CCOMPLEX,单精度复数;ZCOMPLEX*16或DOUBLECOMPLEX。[注:在新版LAPACK中含有使用重复迭代法的函数DSGESV和ZCDESV。]
头2个字母表示使用的精度:DS输入数据是double双精度,算法使用单精度;ZC输入数据是complex*16,算法使用complex
单精度复数。
接下面两个字母YY代表数组的类型。BDbidiagonal,双对角矩阵DIdiagonal,对角矩阵;GBgeneralband,一般带状矩阵;GEgeneral(i.e.,unsymmetric,insomecasesrectangular),一般情形(即非对称,在有些情形下为矩形);GGgeneralmatrices,generalizedproblem(i.e.,apairofgeneralmatrices),一般矩阵,广义问题(即一对一般矩阵);GTgeneraltridiagonal,一般三对角矩阵;HB(complex)Hermitianband,(复数)厄尔米特带状阵HE(complex)Hermitian,(复数)厄尔米特矩阵;HGupperHessenbergmatrix,generalizedproblem(i.eaHessenbergandatriangularmatrix),上海森伯格矩阵,广义问题(即一个海森伯格矩阵和一个三角矩阵);HP(complex)Hermitian,packedstorage,(复数)压缩储存的厄尔米特矩阵;HSupperHessenberg,上海森博格矩阵;OP(real)orthogonal,packedstorage,(实数)压缩储存的正交阵;OR(real)orthogonal,(实数)正交阵;PBsymmetricorHermitianpositivedefiniteband,对称或厄尔米特正定带状矩阵;POsymmetricorHermitianpositivedefinite,对称或厄尔米特正定矩阵;PPsymmetricorHermitianpositivedefinite,packedstorage,压缩储存的对称或厄尔米特正定矩阵;PTsymmetricorHermitianpositivedefinitetridiagonal,对称或厄尔米特正定三对角阵;SB(real)symmetricband,(实数)对称带状阵;SPsymmetric,packedstorage,压缩储存的对称阵;ST(real)symmetrictridiagonal,(实数)对称三对角阵;SYsymmetric,对称阵;TBtriangularband,三角形带状矩阵;TGtriangularmatrices,generalizedproblem(i.e.,apairoftriangularmatrices),三角形矩阵,广义问题(即一对三角形阵);TPtriangular,packedstorage,压缩储存的三角形阵;TRtriangular(orinsomecasesquasi-triangular),三角形阵(在某些情形下为类三角形阵);TZtrapezoidal,梯形阵;UN(complex)unitary,(复数)酉矩阵;UP(complex)unitary,packedstorage,(复数)压缩储存的酉矩阵。
最后三个字母ZZZ代表计算方法。比如,SGEBRD是一个单精度函数,用于把一个实数一般阵压缩为双对角阵(abidiagonalreduction,即BRD)。
函数举例
dgesv_()函数用来求解对称矩阵问题。从名字的意义上可以看出是用来解决双精度一般型的线性方程(组)的问题。DGESV是用来求解实数的线性方程组AX=B的。A是N×N型矩阵,X和B是N×NRHS型矩阵。与之对应的单精度方式为:sgesv_()方程,只是把双精度的化为单精度就可以,另外一个就是zgesv_()方程,它解的是复数形式。
dgeev_()对于非对称矩阵特征向量密集复杂的问题应用此函数,此函数的工能是求特征值。d表示double。ge表示general,说明是普通矩阵,按照列主序存储。ev表示eigenvector(猜测),表达的是函数的功能。
intsgetrf_()通过行交换的方式将M×N的矩阵A进行LU分解。矩阵变换有如下形式:A=P*L*U,P矩阵为置换矩阵,L时下三角形式,U是上三角形式。
参数介绍: M(input)INTEGER矩阵A的行数,M>=0。N (input)INTEGER矩阵A的列数,N>=0。A (input/output)REALarray,A(LDA×N):输入时,是M×N的将被分解的矩阵。输出时,A=P*L*U中的L,U;该单位对角元素的L不存储。LDA(input)INTEGER矩阵A的主尺寸。LDA>=max(1,M)。IPIV(output)INTEGERarray,dimension(min(M,N))指点指数,for1<=i<=min(M,N),矩阵的第i行与IPIV(i)行被交换。
integer*IPIV=(integer*)malloc(sizeof(integer)*min(M,N));这样不会被报错。INFO(output)INTEGER=0:成功退出。
LAPACK 源代码分析
LAPACK 包含 了求解一些实际应用 中常见数值线性代数问题的 FORTRAN77 子程序, 如求解线性方程组,线性最小二乘问题, 特征值问题和奇异值 问题等.LAPACK 还可 以实现如矩阵分解和 条件数估计等相 关的计算.由于在许多高性能计算机上 提供 了高效的 BLAS(基本线性代数子程序库), 为达到可移植性和 效率的统一,LAPACK尽 可能调用BLAS 来进行计算.LAPACK 是一个庞大 的软件包, 目前约有 735000 行 FORTRAN 代码, 完全靠手工 优化的工作量是相 当大 的.为 了使 LAPACK在并行机上 获得高性能, 有很多针对算法级别优化 的研究, 但我们 要考虑的是在程序级别 上 的优化,也就是指直 接从程序文 本中提取并行性.算法级别的优化虽然可 以达到更高的加速 比, 但工作量要远远大于 程序级别 的优化, 而且我们将看到, 程序级别的优化也能获得较高的加速 比.我们利用
UNIX系统下 的 profile工具来分析LAPCK 的运行开销, 得到一个过程级别 的运行开销比例 图(如右图)。
结论与展望
随着现代科技的高速发展, 在许多重要应用领域,如
石油勘探, 气象, 地震数据处理,
核技术等方面出现了一批重大挑战问题,迫切 需要更高性能的计算机.如何有效的使用并行计算机, 利用并行资源是需要解决 的关键问题.自动并行化是解决这一 问题的关键技术之一。在共享主 存并行机上针对LAPACK的并行化研究.LAPACK的庞大 的数值代数软件包 可以通 过对程序的分析生成并行代码,完成自动数据分布,通讯代码生成和优化。