We propose a reproducible variant of the unblocked LU factorization for graphics processor units (GPUs). For this purpose, we build upon Level-1/2 BLAS kernels that deliver correctly-rounded and reproducible results for the dot (inner) product, vector scaling, and the matrix-vector product. In addition, we draw a strategy to enhance the accuracy of the triangular solve via iterative refinement. Following a bottom-up approach, we finally construct a reproducible unblocked implementation of the LU factorization for GPUs, which accommodates partial pivoting for stability and can be eventually integrated in a high performance and stable algorithm for the (blocked) LU factorization.
AhrensPNguyenHDDemmelJ (2016) Efficient reproducible floating point summation and BLAS. Technical Report UCB/EECS-2016-121, EECS Department, University of California, Berkeley.
2.
ArteagaAFuhrerOHoeflerT (2014) Designing bit-reproducible portable high-performance applications. In: Proceedings of the 2014 IEEE 28th international parallel and distributed processing symposium, IPDPS ‘14, Washington, DC, USA, pp. 1235–1244. IEEE Computer Society.
BientinesiPQuintana-OrtíESvan de GeijnRA (2005) Representing linear algebra algorithms in code: the FLAME application programming interfaces. ACM Transactions on Mathematical Software31(1): 27–59.
5.
ChohraCLangloisPParelloD (2016) Efficiency of reproducible Level 1 BLAS. In: LNCS. Scientific Computing, Computer Arithmetic, and Validated Numerics: SCAN 2014, Würzburg, Germany, 21–26 September 2014, Revised Selected Paper. Vol. 9553, pp. 99–108. Springer-Verlag.
6.
CollangeSDefourDGraillatS, et al. (2015) Numerical reproducibility for the parallel reduction on multiband many-core architectures. Parallel Computing49: 83–97.
7.
DemmelJNguyenHD (2013) Fast reproducible floating-point summation. In: Proceedings of the 21st IEEE symposium on computer arithmetic, Austin, Texas, USA, pp. 163–172.
8.
DemmelJNguyenHD (2015) Parallel reproducible summation. IEEE Transactions on Computers64(7): 2060–2070.
9.
DongarraJJDuCrozJHammarlingS, et al. (1990) A set of level 3 basic linear algebra subprograms. ACM Transactions on Mathematical Software16(1): 1–17.
10.
DongarraJHittingerJBellJ, et al. (2014) Applied Mathematics Research for Exascale Computing. Washington, DC: U.S. Department of Energy.
11.
FousseLHanrotGLefèvreV, et al. (2007) MPFR: a multiple-precision binary floating-point library with correct rounding. ACM Transactions on Mathematical Software33(2): 13.
12.
GolubGHLoanCFV (1996) Matrix Computations, 3rd ed. Baltimore: The Johns Hopkins University Press.
13.
HaidarADongTLuszczekP, et al. (2015) Batched matrix computations on hardware accelerators based on GPUs. International Journal of High Performance Computing Applications29(2): 193–208.
14.
HidaYLiXSBaileyDH (2001) Algorithms for quad-double precision floating point arithmetic. In: Proceedings of the 15th IEEE symposium on computer arithmetic, Los Alamitos, CA, USA, pp. 155–162. IEEE Computer Society Press.
15.
HighamNJ (2002) Accuracy and Stability of Numerical Algorithms, 2nd ed. Philadelphia: Society for Industrial and Applied Mathematics (SIAM).
16.
IakymchukRCollangeSDefourD, et al. (2015a) ExBLAS: reproducible and accurate BLAS library. In: Proceedings of the Numerical Reproducibility at Exascale (NRE2015) Workshop held as part of the Supercomputing Conference (SC15), Austin, TX, USA, 15–20 November 2015.
17.
IakymchukRCollangeSDefourD, et al. (2015b) Reproducible triangular solvers for high-performance computing. In: Proceedings of the 12th international conference on information technology: new generations (ITNG 2015), special track on: wavelets and validated numerics, Las Vegas, Nevada, USA, 13–15 April 2015, pp. 353–358. HAL: hal-01116588v2.
18.
IakymchukRCollangeSDefourD, et al. (2016a) ExBLAS (Exact BLAS) library. Available at:https://exblas.lip6.fr/ (accessed 15 February 2018).
19.
IakymchukRDefourDCollangeS, et al. (2016b) Reproducible and accurate matrix multiplication. In: LNCS. Scientific Computing, Computer Arithmetic, and Validated Numerics: SCAN 2014, Würzburg, Germany, 21–26 September 2014, Revised Selected Paper. Vol. 9553. pp. 126–137.
20.
ICL Team (2016) MAGMA project home page. Available at: http://icl.cs.utk.edu/magma/ (accessed 02 February 2017).
21.
IEEE (1985) IEEE standard for binary floating-point arithmetic. ANSI/IEEE Standard, Std 754-1985. New York.
KnuthDE (1997) The Art of Computer Programming (Vol. 2). Seminumerical Algorithms, 3rd ed. Boston: Addison-Wesley.
24.
KulischUSnyderV (2011) The exact dot product as basic tool for long interval arithmetic. Computing91(3): 307–313.
25.
LiXSDemmelJWBaileyDH, et al. (2002) Design, implementation and testing of extended and mixed precision BLAS. ACM Transactions on Mathematical Software28(2): 152–205.
26.
LouvetN (2007) Algorithmes compensés en arithmétique flottante: Précision, validation, performances. PhD Thesis, UPVD. Available at: http://perso.ens-lyon.fr/nicolas.louvet/.
27.
LucasR, et al. (2014) Top Ten Exascale Research Challenges. DOE ASCAC Subcommitee Report.
28.
MullerJMBrisebarreNde DinechinF, et al. (2010) Handbook of Floating-Point Arithmetic. Birkhäuser.
29.
NealRM (2015) Fast exact summation using small and large superaccumulators. Technical Report, University of Toronto.
30.
OgitaTRumpSMOishiS (2005) Accurate sum and dot product. SIAM Journal on Scientific Computing26.
31.
OrtegaJM (1988) The ijk forms of factorization methods I. Vector computers. Parallel Computing7: 135–147.
32.
RumpSM (2009) Ultimately fast accurate summation. SIAM Journal on Scientific Computing31(5): 3466–3502.
33.
SkeelRD (1979) Scaling for numerical stability in Gaussian elimination. Journal of the Association for Computing Machinery26(3): 494–526.
34.
van de GeijnRAQuintana-OrtíES (2008) The science of programming matrix computations. Available at: www.lulu.com.
35.
ZhuYKHayesWB (2010) Algorithm 908: online exact summation of floating-point streams. ACM Transactions on Mathematical Software37(3): 1–37.
