Source-linked AI summary
Accelerating Scientific Computations with Mixed Precision Algorithms
Marc Baboulin, Alfredo Buttari, Jack Dongarra, Jakub Kurzak, Julie Langou, Julien Langou, Piotr Luszczek, Stanimire Tomov
TL;DR
The paper addresses how to retain 64-bit accuracy when 32-bit arithmetic is faster, presenting mixed precision methods for dense and sparse linear systems. These methods deliver double-precision accuracy near single-precision speed, with speedups up to 1.8 for nonsymmetric and 1.5 for symmetric dense solvers.
Problem
32-bit accuracy may be insufficient for accurate and stable physics computations, while 64-bit operations are often slower than 32-bit operations.
Method
The paper performs bulk linear-system operations in 32-bit arithmetic and refines the solution using 64-bit computations, including direct and inner-outer iterative methods.
Results
Mixed precision iterative refinement achieves the accuracy of full double-precision solvers near the speed of full single-precision solvers, with speedups up to 1.8 for nonsymmetric and 1.5 for symmetric dense systems.
Takeaways & Limitations
The approach extends across dense and sparse linear systems and to Cholesky, least-squares, eigenvalue, and singular-value computations.
Takeaways & Limitations
The direct mixed precision approach uses 50% more memory than the standard double-precision algorithm because it retains the original matrix and single-precision factors.
Abstract
from arXiv · showhide
On modern architectures, the performance of 32-bit operations is often at least twice as fast as the performance of 64-bit operations. By using a combination of 32-bit and 64-bit floating point arithmetic, the performance of many dense and sparse linear algebra algorithms can be significantly enhanced while maintaining the 64-bit accuracy of the resulting solution. The approach presented here can apply not only to conventional processors but also to other technologies such as Field Programmable Gate Arrays (FPGA), Graphical Processing Units (GPU), and the STI Cell BE processor. Results on modern processor architectures and the STI Cell BE are presented.
1 Introduction
Modern architectures often execute 32-bit operations at least twice as fast as 64-bit operations, while many applications still require 64-bit accuracy. The paper therefore proposes performing bulk computation in 32-bit arithmetic and refining the result in 64-bit arithmetic.
- 32-bit operations are often at least twice as fast as 64-bit operations on modern architectures.The advantage reflects both faster single-precision arithmetic and halving the bytes moved through memory.
- Several physics applications require 64-bit accuracy because it provides accurate answers and improves the stability of modern computational methods.
- The proposed methodology performs bulk operations in 32-bit arithmetic, then refines the solution to 64-bit accuracy.It is presented for sparse or dense linear systems, including symmetric positive definite and nonsymmetric systems solved by direct or iterative methods.
2 The Idea Behind Mixed Precision Algorithms
Mixed-precision algorithms perform computationally intensive work in single precision and use double precision selectively to recover accurate solutions. Their effectiveness depends on cheap refinement or inner solves, convergence, and memory or sparsity characteristics.
- Core idea: Single-precision computation handles the bulk of operations, while double precision refines the solution to double-precision accuracy.Newton refinement and iterative refinement provide examples of this strategy.
- Core idea: Double-precision accuracy can be achieved nearly at single-precision speed when refinement costs less than the initial solution computation.The paper applies this concept to direct and iterative linear-system solvers.
- Direct methods: Mixed-precision direct solvers factor and triangular-solve in single precision, but compute residuals and solution updates in double precision using the original coefficients.The O(n^3) operation is single precision, whereas double-precision operations are at most O(n^2).
- Direct methods: 50% more memory is required because single-precision factors are stored alongside the original double-precision coefficient matrix.This is a drawback relative to the standard double-precision algorithm.
- Iterative methods: Iterative refinement requires rapid convergence and iterations that are inexpensive relative to system factorization.Sparse-system costs vary substantially with nonzero counts and sparsity structure, while dense-case results are more predictable.
- Iterative methods: Mixed-precision iterative methods use single-precision inner solves or approximations within a double-precision outer Krylov method, exemplified by FGMRES(mout)-GMRESSP(min).The inner solver uses a single-precision matrix-vector product as a fast approximation of the double-precision operator.
3 Performance Results
Performance experiments evaluate mixed-precision iterative refinement for dense and sparse direct systems and iterative solvers across several architectures and test matrices. The method can approach single-precision speed while matching double-precision accuracy, with especially large gains on the STI Cell BE and selected iterative cases.
- Experimental setup: Experiments use systems from Table 1 and sparse test matrices from Table 2; STI Cell BE results cover dense systems because sparse-computation libraries were unavailable.Dense and sparse solver experiments use BLAS/LAPACK-based implementations and the listed hardware and matrices.
- Accuracy criterion: The mixed-precision solver stops when its solution is as accurate as a full double-precision solution, using the latter as the experimental reference.The stopping criterion follows comparison with a separately computed full double-precision solution.
- Dense matrices: Up to 1.8 speedup for nonsymmetric and 1.5 for symmetric dense solvers is reported on AMD Opteron, Intel Woodcrest, and IBM PowerPC systems.These gains apply for sufficiently large problem sizes; small problems can lose efficiency because refinement costs outweigh factorization savings.
- Dense matrices: The STI Cell BE implementation runs up to 7 times faster than the double-precision peak for nonsymmetric systems and 11 times faster for symmetric positive definite systems.The large gains reflect the Cell processor’s substantial single-versus-double precision performance difference.
- Sparse matrices: Sparse direct experiments with MUMPS compare full single-precision and mixed-precision solvers against full double precision across six real-world matrices, while recording refinement iterations.MUMPS uses analysis, factorization, and solution phases; the mixed-precision mapping aligns these with Algorithm 1.
- Iterative methods: For matrix #2, mixed-precision FGMRES-GMRESSP reaches up to 6 speedup over double-precision GMRES; on IBM PowerPC, 3.5 of the 5.5-fold gain comes from improved convergence and 1.57 from arithmetic.The comparison also includes full double-precision inner-outer FGMRES-GMRESDP, differing only in inner incomplete-solver precision.
4 Numerical Remarks
Mixed precision iterative refinement converges to higher-than-double-solve accuracy under conditioning constraints, with iteration counts evaluated against matrix condition number. When κεs exceeds 1, the convergence formula fails and the method may not converge.
- Convergence conditions: Mixed precision iterative refinement works when the coefficient-matrix condition number is smaller than the inverse of the lower precision used.For larger condition numbers, the standard double precision solver is needed for practical reasons.
- Experimental setup: Figure 4 reports mean iterations over 200 random 200-by-200 matrices for each prescribed condition number.The maximum allowed was 30 iterations, where 30 denotes failure to converge rather than convergence in 30 iterations.
- Experimental setup: The iteration count is measured until the mixed precision method reaches accuracy better than the associated double precision solve.The experiment concerns direct dense nonsymmetric solves.
- Convergence conditions: When κεs is above 1, the iteration formula is invalid and practice is characterized by an infinite number of iterations, meaning lack of convergence.This threshold marks the boundary of the formula's validity.
5 Extension to Quadruple Precision
The paper extends iterative refinement experiments to quadruple precision on an Intel Xeon 3.2GHz. The setup uses condition-number estimates for random-entry matrices and reference BLAS compiled with Intel ifort because no optimized quadruple-precision BLAS was available.
- Experimental setup: The quadruple-precision extension evaluates iterative refinement on an Intel Xeon 3.2GHz.The section presents this as an extension to the earlier study.
- Experimental setup: Input matrices have random entries drawn from a uniform distribution, and the code computes a condition-number estimate for each matrix.The condition-number estimate is part of the quadruple-precision experiment.
- Implementation: Quadruple-precision arithmetic uses the reference BLAS compiled with Intel Fortran ifort using the -O3 optimization flag.The reference BLAS is used because an optimized quadruple-precision BLAS was unavailable.
6 Extension to Other Algorithms
Mixed precision algorithms can provide substantial speedups with little code effort by exploiting existing hardware properties. The paper extends the approach across linear-system, least-squares, eigenvalue, and singular-value algorithms and encourages applications beyond linear algebra.
- General implications: Mixed precision algorithms can provide substantial speedup for little code effort by mainly exploiting existing hardware properties.This is presented as a broad practical benefit of the approach.
- Extensions within linear algebra: Mixed precision iterative refinement applies to symmetric positive definite systems using Cholesky factorization.The paper also identifies applications beyond the general linear-system setting.
- Extensions within linear algebra: For overdetermined least squares, iterative refinement can be applied to augmented systems, QR factorization, semi-normal equations, or normal equations.The augmented-system approach refines both the solution and residual.
- Extensions within linear algebra: Iterative refinement can also be applied to eigenvalue and singular-value computation.These are additional algorithmic extensions listed by the paper.
- Beyond linear algebra: The manuscript encourages scientists to extend mixed precision beyond applications originating in linear algebra.The statement is framed as an invitation for future application development.