Application of Mixed Precision GMRES Method in Lattice Quantum Chromodynamics

doi:10.11871/jfdc.issn.2096-742X.2024.06.004

Abstract

Abstract:

[Application Background] Lattice quantum chromodynamics is an important theory for particle physics research through computer simulation, which is built on a four-dimensional space-time lattice. The main computing hotspot in the simulation process is solving sparse linear systems with hundreds of millions of unknowns. [Methods] The generalized minimal residual method (GMRES) is used in this paper, in which a matrix-free algorithm is used to realize the complex matrix-vector multiplication of Wilson fermions. Firstly, the selection of subspace dimension in the GMRES method is evaluated. Secondly, in order to reduce the amount of data movement and memory occupation, and thus, to improve the computational performance of the GMRES algorithm, we implement four mixed precision GMRES algorithms, evaluate the corresponding performance in lattice quantum chromodynamics, and analyze the acceleration of each kernel. [Results] The experimental results show that the four mixed-precision GMRES algorithms converge consistently with the double-precision GMRES algorithm and obtain different degrees of performance acceleration. [Limitations and Conclusions] The performance bottleneck of the mixed-precision algorithms is analyzed, and the future research directions are forecasted.

Key words: lattice quantum chromodynamics, mixed precision, GMRES, parallel computing

ZHANG Kelong,HE Lianhua,XU Shun,JIN Zhong. Application of Mixed Precision GMRES Method in Lattice Quantum Chromodynamics[J]. Frontiers of Data and Computing, 2024, 6(6): 32-42, https://cstr.cn/32002.14.jfdc.CN10-1649/TP.2024.06.004.

Figures/Tables 13

Alg.1

GMRES(m)"

输入：

x 0

：初始值.
输出：数值解.

1 for i=0,1,

?

do
2 计算

r = b - A x i

3 计算

β = h 1,0 = r 2

4 检查是否收敛，若收敛则退出
5 for k=1,

?

, m do
6

? v k = r / h k, k - 1

r = A v k

8 for j=1,

?

, k do
9

h j, k = (r, v j)

10 r=r-

h j, k v j

11 end
12 计算

h k + 1, k = r 2

13 end
14 定义

V k = v 1, ?, v k, ? H k = h i, j 1 ≤ ? ? i ≤ ? ? k + 1,1 ≤ ? ? j ≤ ? ? k

15 计算

y k = a r g m i n y β e 1 - H k y k 2

? x i + 1 = x i + V k y k

17 end

Alg.1

Alg.2

GMRES-SD"

输入：

x 0

：初始值.
输出：数值解.

1 计算

r 0 = b - A x 0

[single]
2 for i=0,1,

?

do
3 GMRES(m)求解

A e i = r i

[single]
4

x i + 1 = x i + e i

[single]
5

? r i + 1 = b - A x i + 1

[single]
6 若

r i + 1 2 / r 0 2 10 - 7

，令

r 0 = r i + 1

且退出
7 end
8 for i=0,1,

?

do
9 GMRES(m)求解

A e i = r i

[double]
10

x i + 1 = x i + e i

[double]
11

? r i + 1 = b - A x i + 1

[double]
12 若

r i + 1 2 / r 0 2 t o l

，退出
13 end

Alg.2

Alg.3

GMRES-IR"

输入： $x 0$ ：初始值. 输出：数值解.
1 计算 $r 0 = b - A x 0$ [double] 2 for i=0,1, $?$ do 3 GMRES(m)求解 $A e i = r i$ [single] 4 $x i + 1 = x i + e i$ [double] 5 $? r i + 1 = b - A x i + 1$ [double] 6 检查是否收敛，若收敛则退出 7 end

Alg.3

Alg.4

FGMRES-GMRES"

输入：

x 0

：初始值.
输出：数值解.

1 for i=0,1,

?

do
2 计算

r = b - A x i

[double]
3 计算

β = h 1,0 = r 2

[double]
1 检查是否收敛，若收敛则退出
2 for k=1,

?

m o u t

do
3

v k = r / h k, k - 1

[double]
7 用GMRES

(m i n)

求解

A z k = v k

（初始值

z k

=0）[single]
8

? r = A v k

[double]
9 for j=1,

?

,k do
10

h j, k = (r, v j)

[double]
11 r=r-

h j, k v j

[double]
12 end
13 计算

h k + 1, k = r 2

[double]
14 end
15 定义

Z k = z 1, ?, z k, ? H k = h i, j 1 ≤ ? ? i ≤ ? ? k + 1,1 ≤ ? ? j ≤ ? ? k

16 计算

y k = a r g m i n y β e 1 - H k y k 2

[double]
17

x i + 1 = x i + Z k y k

[double]
18 end

Alg.4

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Table 1

References 29

[1]	DAWSON A, DÜBEN P D, MACLEOD D A, et al. Reliable low precision simulations in land surface models[J]. Climate Dynamics, 2018, 51(7): 2657-2666.
[2]	FABIEN-OUELLET G. Seismic modeling and inversion using half-precision floating point numbers[J]. Geophysics, 2020, 85(3): 1MJ-Z13.
[3]	ABDELFATTAH A, ANZT H, BOMAN E G, et al. A survey of numerical linear algebra methods utilizing mixed-precision arithmetic[J]. International Journal of High Performance Computing Applications, 2021, 35(4): 344-369.
[4]	ZOUNON M, HIGHAM N J, LUCAS C, et al. Performance impact of precision reduction in sparse linear systems solvers[J]. PeerJ Computer Science, 2022, 8: e778.
[5]	BUTTARI A, DONGARRA J, KURZAK J, et al. Using mixed precision for sparse matrix computations to enhance the performance while achieving 64-Bit accuracy[J]. ACM Transactions on Mathematical Software, 2008, 24: 1-22.
[6]	ANZT H, DONGARRA J, FLEGAR G, et al. Adaptive precision in block-Jacobi preconditioning for iterative sparse linear system solvers[J]. Concurrency and Computation: Practice and Experience, 2019, 31(6): e4460.
[7]	FLEGAR G, ANZT H, COJEAN T, et al. Adaptive precision block-jacobi for high performance preconditioning in the ginkgo linear algebra software[J]. ACM Transactions on Mathematical Software, 2021, 47(2): 1-28.
[8]	AHMAD K, SUNDAR H, HALL M. Data-driven mixed precision sparse matrix vector multiplication for GPUs[J]. ACM Transactions on Architecture and Code Optimization, 2019, 16(4):1-24.
[9]	TEZCAN E, TORUN T, KOŞAR F, et al. Mixed and Multi-Precision SpMV for GPUs with Row-wise Precision Selection[C]// IEEE 34th International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), Bordeaux, France, November 02-05, 2022. Piscataway: IEEE, 2022: 31-40.
[10]	WILSON K G. Confinement of quarks[J]. Physical Review D, 1974, 10: 2445.
[11]	HABIB S, ROSER R, GERBER R, et al. ASCR/HEP Exascale Requirements Review Report[R/OL]. https://www.osti.gov/biblio/1408335.2016.
[12]	CLARK M A, BABICH R, BARROS K, et al. Solving lattice QCD systems of equations using mixed precision solvers on GPUs[J]. Computer Physics Co-mmunications, 2010, 181(9): 1517-1528.
[13]	SLEIJPEN G L G, VAN DER VORST H A. Reliable updated residuals in hybrid Bi-CG methods[J]. Computing, 1996, 56: 141-163.
[14]	FROMMER A, KAHL K, KRIEG S, et al. Adaptive aggregation-based domain decomposition multigrid for the lattice wilson-dirac operator[J]. SIAMJournal on Scientific Computing, 2014, 36(4): A1581-A1608.
[15]	SAAD Y, SCHULTZ M H. GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems[J]. SIAMJournal on Scientific and Statistical Computing, 1986, 7(3): 856-869.
[16]	MOLER C B. Iterative refinement in floating point[J]. Journal of the ACM, 1967, 14(2): 316-321.
[17]	LANGOU J, LANGOU J, LUSZCZEK P, et al. Exploiting the performance of 32 bit floating point arithmetic in obtaining 64 bit accuracy (revisiting iterative refinement for linear systems) [C]// Proceedings of the 2006 ACM/IEEE Conference on Supercomputing (SC’06), Tampa, USA, November 11-17, 2006. IEEE, 2006: 50.
[18]	CARSON E, HIGHAM N J. A new analysis of iterative refinement and its application to accurate solution of ill-conditioned sparse linear systems[J]. SIAM Journal on Scientific Computing, 2017, 39(6): A2834-A2856.
[19]	CARSON E, HIGHAM N. Accelerating the solution of linear systems by iterative refinement in three precisions[J]. SIAM Journal on Scientific Computing, 2018, 40(2): A817-A847.
[20]	HAIDAR A, BAYRAKTAR H, TOMOV S, et al. Mixed-precision iterative refinement using tensor cores on GPUs to accelerate solution of linear systems[J]. Proceedings of the Royal Society A, 2020, 476: 20200110.
[21]	AMESTOY P, BUTTARI A, HIGHAM N J, et al. Five-precision GMRES-based iterative refinement[J]. MIMS EPrint 2021.5, Manchester Institute for Mathematical Sciences, The University of Manchester, UK.
[22]	TURNER K, Walker H F. Efficient high accuracy solutions with GMRES(m)[J]. SIAMJournal on Scientific and Statistical Computing, 1992, 13(3): 815-825.
[23]	LINDQUIST N, LUSZCZEK P, DONGARRA J. Improving the performance of the GMRES method using mixed-precision techniques[M]. Driving Scientific and Engineering Discoveries Through the Convergence of HPC, Big Data and AI. SMC 2020. Communications in Computer and Information Science, vol 1315. Springer, Cham.
[24]	LINDQUIST N, LUSZCZEK P, DONGARRA J. Accelerating restarted GMRES with mixed precision arithmetic[J]. IEEE Transactions on Parallel and Distributed Systems 33(4) 1027-1037.
[25]	LOE J A, GLUSA C A, YAMAZAKI I, et al. Experimental evaluation of multiprecision strategies for GMRES on GPUs[C]// IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), Portland, OR, USA, 2021.
[26]	SAAD Y. Iterative methods for sparse linear systems 2nd edition[M]. Philadelphia: SIAM, 2003.
[27]	MORGAN R B. A restarted GMRES method augmented with eigenvectors[J]. SIAMJournal on Matrix Analysis and Applications, 1995, 16(4): 1154-1171.
[28]	SAAD Y. A flexible inner-outer preconditioned GMRES algorithm[J]. SIAMJournal on Scientific Computing, 1993, 14(2): 461-469.
[29]	BABOULIN M, BUTTARI A, DONGARRA J, et al. Accelerating scientific computations with mixed precision algorithms[J]. Computer Physics Communications, 2009, 189(12): 2526-2533.

cpu核数	GMRES-SD	GMRES-IR	FGMRES-BiCGStab	FGMRES-GMRES
16	1.09	1.30	1.12	1.20
32	1.11	1.35	1.22	1.20
64	1.07	1.12	1.19	1.15
128	1.10	1.26	1.21	1.15
256	1.10	1.32	1.16	1.20