并行linpack分析与优化探讨


并行 linpack 分析与优化探讨 张文力 陈明宇 冯圣中 樊建平 (中国科学院计算技术研究所 北京 100080) (zhangwl@ncic.ac.cn) 摘要:HPL 是大规模集群系统广泛采用的 linpack 测试软件包,本文在深入分析线性代数方程组分块并行求解算法和 HPL 实现技巧的基础上,探讨了 HPL 峰值性能的制约因素。重点讨论了 LU 分解过程中主要参数 P×Q 和 NB 对计算性能的影响。 理论分析与实验结果表明,定义为矩阵运算时间与其运算量之比的效率因子很大程度上相关于矩阵的分块大小,而与矩阵 规模本身关系微乎其微。根据这一规律,本文作者提出通过扫描小规模矩阵运算效率来确定大规模并行测试中分块大小 NB, 改善长期以来只是通过反复实验试探获取 NB 的现状,大大缩短了 NB 的确定过程,为其最终定位提供了相对精确的理论化 依据。目前实际测试结果基本验证了本文作者的想法,这一方法同样适用于其他过程中的矩阵并行运算。 关键词:HPL(high performance linpack), 线性代数方程组,LU 分解,MPI Analysis and Optimization Discussion on Parallel Linpack Zhang Wenli Chen Mingyu Feng Shengzhong Fan Jianping (Institute of Computing Technology, CAS.,Beijing,100080) Abstract: HPL is a linpack benchmark package widely adopted on massive scale cluster system. Based on further analysis of the blocked parallel solution algorithm of linear algebra equations and HPL implementation skills, the restriction factors of the HPL peak performance are probed. The influence of main parameter P * Q and NB on computing performance in LU factorization process is discussed especially. Theory analysis and experiment results indicate that, the efficient factor, which is defined as the quotient of the matrix operation time and the total number of operations, is relevant to the matrix block size to a great extent, yet little correlate to the matrix dimensions. According to this law, the author proposes that to determine the block size NB of massively parallel test through scanning the operation efficiency of small-scale matrix. Thus it has improved the status getting NB through try -and-error experiment test without definite aim, shorten the determination course greatly, and offered a relatively accurate theoretical basis for making a reservation finally. The author’s idea has been verified by the actual test results at present, as well as been applicable to the matrix parallel operations of other procedure. Key words: high performance linpack, linear algebra equations,LU factorization,MPI 1.引言 Linpack 是当前国际上流行的性能测试基准,通过对高性能计算机求解稠密线性代数方程组能力的测 试,评价高性能计算机系统的浮点性能,由 Jack Dongarra 在 1979 年首次提出,多为 Fortran 版本。它 提供多种程序并在其它函数库的支持下解决线性方程问题,包括求解稠密矩阵运算,带状的线性方程, 求解最小平方问题以及其它各种矩阵运算,但它们都是基于高斯消去法的原理。 Linpack 根据问题规模与优化选择的不同分为 100×100,1000×1000,n×n 三种测试[1]。HPL[2] (High performance linpack) 是第一个标准的公开版本并行 Linpack 测试软件包,是 n×n 测试的 MPI 实现,可适 应多体系移植,目前广泛用于 top500 测试[3]。这一测试主要针对分布式存储大规模并行计算系统而设计, 它的要求也是 Linpack 标准中最为宽松的,用户可以对任意大小的问题规模,使用任意个数的 CPU,使 用基于高斯消去法的各种优化方法来执行该测试程序,寻求最佳的测试结果。性能测试实际就是要计算 浮点运算率。由于高斯分解法求解规模为 n 的线性代数方程问题的浮点运算次数(2n3/3 +3n2/2)是一定的, 而这一浮点运算次数的大小只与问题规模有关,也即与系数矩阵的维数有关,这样只要给出问题规模 n, 根据线性方程组求解过程中消元和回代部分的计时 t,就可以定量计算出机器的性能参数—— 浮点运算次 数/秒: (2n3/3 +3n2/2)/t (1) 一般来说,要获得 HPL 实测峰值,需要使用与内存匹配的最大问题规模,也就是大约接近内存总容量的 80%。 本文作者在 HPL 源码详细分析的基础上,权衡重点可调参数,开展相关实验并分析结果,得出一些 有用的结论,希望对后续 Linpack 测试优化具有一定的指导意义。本文第 2 部分简要给出高斯消去法原 理及 LU 算法并行思想,第 3 部分围绕分析及测试过程中相关问题的思考与尝试展开讨论,尤其对确定 NB 依据的探讨上,并给出测试结果及相应分析。最后归纳总结,展望以后的工作。 2.高斯消去法的原理 线性代数方程组的数值解法分为直接法和迭代法两种。对于系数矩阵稠密的线性代数方程组 Ax = b (2) 其中,A=(aij)n×n 且为非奇异矩阵;b=(b1, b2, ┄ , bn)T, x=(x1, x2, ┄ , xn)T, A 与 b 均为已知,而 x 是待求的 n 维向量,其经典的直接解法是 LU 分解法[4, 5, 6, 7]。而高斯消去法是实现 LU 分解的经典算法,按消元过程 和回代过程两步建立具体的求解。 也就是,LU 分解将问题(1)化为两个三角形方程组的求解 LUx = Pb 等价于 Ly = Pb (3) Ux = y (4) 其中,P 表示行交换的初等变换矩阵,式(3)在 HPL 中与 LU 分解过程同时操作,y=(y1, y2, ┄ , yn)T 是增广矩阵经过消元处理后 b 相应的部分,式(4)则表示回代求解过程。 2.1 消元过程演进[10] 0 x x x x . . 标准方法 实施行初等变换 x 0 0 . . . 0 LINPACK 实施列初等变换 图 1. 消元过程演进三阶段示意图 作为解线性方程组的一类重要而有效的方法,高斯列主元消去法的算法是这样的,为增加算法的数 值稳定性,首先寻找增广矩阵(A|b)第一列中绝对值最大的数,即主元,选取该行作为参照行,将其它行 的第一个元素消为零,然后对剩余行依次重复该操作,直到将矩阵 A 分解为下三角阵 L 与上三角阵 U 的 乘积,完成消元过程。之后通过上三角方程回代求得线性方程组(2)的解。 只是传统的高斯消去法对增广矩阵(A|b)施行行初等变换,而 linpack 中出于 Fortran 语言存储、列向 找主元等运算方便的考虑以列为操作单位。随着现代并行计算机的出现,为了提高并行度,HPL 则继承 Lapack[8]采用矩阵分块的思想,利用 BLAS 库[9]对向量、矩阵进行操作,按图 2 示意的过程完成消元。演 进的三阶段示意如图 1。 BLAS(Basic Linear Algebra Subroutines)包是一些关于矩阵的基本操作。 共分三层,第一层(最底 层)实现向量与向量的运算,比如向量内积(DDOT),DAXPY,即 z = ax + y,其中 x, y 为向量,a 为标 量);第二层(中间层)实现向量与矩阵的运算,比如 DGEMV, 即 z = aAx + by,其中 x, y为向量,a 为 标量,A 为矩阵;第三层(最高层)实现矩阵与矩阵的运算,如 DGEMM, 即 D = aAB + bC,其中 a, b 为标量,A, B和 C 为矩阵。上一层是建立在下一层的基础之上的,运行效率也有相当提高。Linpack 软件 包建立在 BLAS 之上,HPL 算法中大量的浮点运算是通过调用 BLAS 实现的,这就为使用特定的计算机 硬件但不修改底层的算法提供了条件,不需牺牲可靠性,就可以实现移植和软件透明。 [1] nb1=i×NB, nb2=nb1+NB [2] for(j=nb1; j=| Li j:N,j | [2.2] Li j,: ←→ Li P[j],: [2.3] lj ← lj/L i j, j [2.4] Lj ← Lj - ljuj [3] 行向广播 LLi, Li 及行交换信息 [4] for (j=nb1; j
还剩8页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

wujiandeyu

贡献于2013-08-03

下载需要 3 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf