Page 27 - 《软件学报》2021年第8期

黎雷生 等:复杂异构计算系统 HPL 的优化 2309

行偏主元 LU 分解 N×(N+1)系数矩阵[A,b]:
[, ] [[b =
PA L U⋅ ],]; , ,y P L U ∈ R NN× ; y∈ R N .
r
r
其中,P r 表示行主元交换矩阵,分解过程中下三角矩阵因子 L 已经作用于 b,解 x 通过求解上三角矩阵系统得到:
Ux=y
2 3 1 2 2
HPL 中 LU 分解浮点运算次数 N − N ,回代浮点运算次数 2N .
3 2
HPL 采用分块 LU 算法,每个分块是一个 NB 列的细长矩阵,称为 panel.LU 分解主循环采用 right-looking 算
法,单步循环计算 panel 的 LU 分解和更新剩余矩阵.基本算法如图 1 所示,其中 A 1,1 和 A 2,1 表示 panel 数据.需要
特别说明的是,图示矩阵是行主顺序,HPL 代码中矩阵是列主存储的.

Fig.1 Block LU algorithm
图 1 分块 LU 算法
计算公式如下:
⎡ L 1,1 ⎤ ⎛ A 1,1 ⎞
⎢ ,U 1,1 = LU ⎜ , ⎟
⎥
⎣ L 2,1 ⎦ ⎝ A 2,1 ⎠
−
1
U 1,2 = L A ,
1,1 1,2
A update = A − 2,2 L U 1,2 .
2,1
2,2
第 1 个公式表示 panel 的 LU 分解,第 2 个公式表示求解 U,一般使用 DTRSM 函数,第 3 个公式表示矩阵更
新,一般使用 DGEMM 函数.
对于分布式内存计算系统,HPL 并行计算模式基于 MPI,每个进程是基本计算单元.进程组织成二维网格.
矩阵 A 被划分为 NB×NB 的逻辑块,以 Block-Cycle 方式分配到二维进程网格,数据布局示例如图 2 所示.

Fig.2 Block-Cycle algorithm
图 2 Block-Cycle 算法

对于具有多列的进程网格,单步循环只有一列进程执行 panel 分解计算,panel 分解过程中每一列执行一次