Alinea: An Advanced Linear Algebra Library for Massively Parallel Computations on Graphics Processing Units

Abstract

Direct and iterative methods are often used to solve linear systems in engineering. The matrices involved can be large, which leads to heavy computations on the central processing unit. A graphics processing unit can be used to accelerate these computations. In this paper, we propose a new library, named Alinea, for advanced linear algebra. This library is implemented in C++, CUDA and OpenCL. It includes several linear algebra operations and numerous algorithms for solving linear systems. For both central processing unit and graphic processing unit devices, there are different matrix storage formats, and real and complex arithmetics in single- and double-precision. The CUDA version includes a self-tuning of the grid, i.e. threading distribution, depending upon the hardware configuration and the size of the problems. Numerical experiments and comparison with existing libraries illustrates the efficiency, accuracy and robustness of the proposed library.

Keywords

Alinea linear algebra direct solvers iterative solvers parallel computing CPU GPU CUDA OpenCL auto-tuning energy efficiency

Get full access to this article

View all access options for this article.

References

Aliaga

Bollhofer

Martien

Quintana-Orti

(2010) Parallelization of multilevel ILU preconditioners on distributed-memory multiprocessors. In: PARA (1) (Lecture Notes in Computer Science, vol. 7133). New York: Springer, pp. 162–172.

Bell

Garland

(2012) Cusp: Generic Parallel Algorithms for Sparse Matrix and Graph Computations. Nvidia Corporation. Available on line at: http://cusplibrary.github.io/.

Berry

Hendrickson

Raghavan

(1996) Sparse matrix reordering schemes for browsing hypertext. In: Renegar

. (eds) The mathematics of numerical analysis. 1995 AMS–SIAM summer seminar in applied mathematics, 17 July–11 August 1995, Park City, UT, USA (Lectures in Applied Mathematics, vol. 32). Providence, RI: American Mathematical Society, pp. 99–123.

Blackford

Demmel

Dongarra

. (2002) An updated set of basic linear algebra subprograms (BLAS). ACM Transactions on Mathematical Software 28(2): 135–151.

Boisvert

Pozo

Remington

Barrett

Dongarra

(1997) Matrix market: a web resource for test matrix collections. In: Proceedings of the IFIP TC2/WG2.5 working conference on quality of numerical software: assessment and enhancement. London, UK: Chapman and Hall, pp. 125–137.

Bosma

Cannon

Playoust

(1997) The magma algebra system. I. The user language. Computational algebra and number theory (London, 1993). Journal of Symbolic Computation 24(3–4): 235–265.

Buluç

Fineman

Frigo

Gilbert

Leiserson

(2009) Parallel sparse matrix–vector and matrix–transpose-vector multiplication using compressed sparse blocks. In: auf der Heide

Bender

(eds.) SPAA. New York: ACM Press, pp. 233–244.

Chan

George

(2002) A linear time implementation of the reverse Cuthill–McKee algorithm. BIT 20(1): 8–14.

Cheik Ahamed

Magoulès

(2012a) Fast sparse matrix–vector multiplication on graphics processing unit for finite element analysis. In: 14th IEEE international conference on high performance computing and communications (HPCC 2012), Liverpool, UK, 25–27 June 2012. Los Alamitos, CA: IEEE Computer Society, pp. 1307–1314.

10.

Cheik Ahamed

Magoulès

(2012b) Iterative methods for sparse linear systems on graphics processing unit. In: 14th IEEE international conference on high performance computing and communications (HPCC 2012), Liverpool, UK, 25–27 June 2012. Los Alamitos, CA: IEEE Computer Society, pp. 836–842.

11.

Cheik Ahamed

Magoulès

(2013) Schwarz method with two-sided transmission conditions for the gravity equations on graphics processing unit. In: 12th international symposium on distributed computing and applications to business, engineering and science (DCABES), Kingston, London, UK, 2–4 September 2013. Los Alamitos, CA: IEEE Computer Society, pp. 105–109.

12.

Cheik Ahamed

Magoulès

(2014a) Energy consumption analysis on graphics processing units. In: 13th international symposium on distributed computing and applications to business, engineering and science (DCABES 2014), Xianning, China, 24–27 November 2014. Los Alamitos, CA: IEEE Computer Society, pp. 46–50.

13.

Cheik Ahamed

Magoulès

(2014b) Iterative Krylov methods for acoustic problems on graphics processing unit. In: 13th international symposium on distributed computing and applications to business, engineering and science (DCABES 2014), Xianning, China, 24–27 November 2014. Los Alamitos, CA: IEEE Computer Society, pp. 19–23.

14.

Cheik Ahamed

Magoulès

(2014c) A stochastic-based optimized Schwarz method for the gravimetry equations on GPU clusters. In: Domain decomposition methods in science and engineering XXI (DDXXI), Rennes, France, 25–29 June 2012 (Lecture Notes in Computational Science and Engineering, vol. 98). Berlin: Springer-Verlag, pp. 1307–1314.

15.

Chi

Shen

Jun

Zhang

(2002) Robust parallel ILU preconditioning techniques for solving large sparse matrices. In: International proceedings on parallel and distributed processing symposium (IPDPS 2002), Ft. Lauderdale, FL, USA, 15–19 April 2001. Los Alamitos, CA: IEEE Computer Society, p. 231. DOI:10.1109/IPDPS.2002.1016646.

16.

Creel

Zubair

(2012) High performance implementation of an econometrics and financial application on GPUs. In: High performance computing, networking, storage and analysis (SCC), 2012 SC Companion, pp. 1147–1153.

17.

Davis

(2011) The university of florida sparse matrix collection. ACM Transactions on Mathematical Software 38(1): 1–25.

18.

Després

(1993) Domain decomposition method and the helmholtz problem.II. In: Second international conference on mathematical and numerical aspects of wave propagation, Newark, DE, 1993. Philadelphia, PA: SIAM, pp. 197–206.

19.

Djinevski

Arsenovski

Ristov

Gusev

(2013) Optimal configuration of GPU cache memory to maximize the performance. In: ICT innovations 2013 web proceedings.

20.

Dongarra

Luszczek

Petitet

(2003) The LINPACK benchmark: Past, present, and future. Concurrency and Computation: Practice and Experience 15(9): 803 820.

21.

Gaikwad

Toke

(2010) Parallel iterative linear solvers on GPU: a financial engineering case. In: 2010 18th Euromicro international conference on parallel, distributed and network-based processing (PDP), pp. 607–614.

22.

Goto

van de Geijn

(2008) High-performance implementation of the level-3 BLAS. ACM Transactions on Mathematical Software 35(1): 4:1–4:14.

23.

Griebel

Zaspel

(2010) A multi-GPU accelerated solver for the three-dimensional two-phase incompressible Navier-Stokes equations. Computer Science—Research and Development 25(1-2): 65–73. DOI:10.1007/s00450-010- 0111-7.

24.

Guo

Wang

(2010) Auto-tuning CUDA parameters for sparse matrix–vector multiplication on GPUs. In: 2010 international conference on computational and information sciences (ICCIS), pp. 1154–1157.

25.

Hong

Kim

(2009) An analytical model for a GPU architecture with memory-level and thread-level parallelism awareness. In: Proceedings of the 36th Annual International Symposium on Computer Architecture (ISCA’09). New York, NY: ACM Press, pp. 152–163.

26.

Janna

Ferronato

Gambolati

(2010) A block FSAI-ILU parallel preconditioner for symmetric positive definite linear systems. SIAM Journal of Scientific Computing 32(5): 2468–2484.

27.

Jones

Plassmann

(1995) An improved incomplete Cholesky factorization. ACM Transactions on Mathematical Software 21(1): 5–17.

28.

Kahhaleh

(1993) Analysis of memory latency factors and their impact on KSR1 MPP performance. Technical Report CSE-TR 159-93, University of Michigan.

29.

Khronos (2010) OpenCL. Available at: http://www.khronos.org/opencl/.

30.

Kim

Lee

Chung

. (2012) Hybrid DRAM/PRAM-based main memory for single-chip CPU/GPU. In: Proceedings of the 49th annual design automation conference (DAC’12). New York, NY: ACM Press, pp. 888–896.

31.

Kim

Shrivastava

(2013) Memory performance estimation of CUDA programs. ACM Transactions on Embedded Computer Systems 13(2): 21:1–21:22.

32.

Lezar

Davidson

(2010) GPU-based LU decomposition for large method of moments problems. Electronics Letters 46(17): 1194–1196.

33.

Suchomel

Osei-Kuffuor

Saad

(2010) ITSOL. Available at: http://www-users.cs.umn.edu/saad/software/ITSOL/index.html.

34.

Lin

Moré

(1999) Incomplete Cholesky factorizations with limited memory. SIAM Journal of Scientific Computing 21(1): 24–45.

35.

Lions

(1988) On the Schwarz alternating method. I. In: Proceedings of the first international symposium on domain decomposition methods for partial differential equations, pp. 1–42.

36.

Luo

Yang

Zhao

Cai

(2011) A scalable hybrid algorithm based on domain decomposition and algebraic multigrid for solving partial differential equations on a cluster of CPU/GPUs. In: 2nd international workshop on GPUs and scientific applications (GPUScA 2011), p. 45.

37.

Luo

Zhao

Cai

(2012) A hybrid implementation of two-level domain decomposition algorithm for solving elliptic equation on CPU/GPUs. In: 13th international conference on parallel and distributed computing, applications and technologies (PDCAT 2012). IEEE, pp. 474–477. DOI:10.1109/PDCAT.2012.18.

38.

Agrawal

Chamberlain

(2014) A memory access model for highly-threaded many-core architectures. Future Generation Computer Systems 30: 202–215.

39.

Maday

Magoulès

(2006a) Absorbing interface conditions for domain decomposition methods: a general presentation. Computer Methods in Applied Mechanics and Engineering 195(29–32): 3880–3900.

40.

Maday

Magoulès

(2006b) Improved ad hoc interface conditions for Schwarz solution procedure tuned to highly heterogeneous media. Applied Mathematical Modelling 30(8): 731–743.

41.

Maday

Magoulès

(2007) Optimized Schwarz methods without overlap for highly heterogeneous media. Computer Methods in Applied Mechanics and Engineering 196(8): 1541–1553.

42.

Magoulès

Cheik Ahamed

Putanowicz

(2015a) Auto-tuned Krylov methods on cluster of graphics processing unit. International Journal of Computer Mathematics 92(6): 1222–1250.

43.

Magoulès

Cheik Ahamed

Putanowicz

(2015b) Optimized Schwarz method without overlap for the gravitational potential equation on cluster of graphics processing unit. International Journal of Computer Mathematics, pp. 1–26.

44.

Magoulès

Roux

(2006) Lagrangian formulation of domain decomposition methods: a unified theory. Applied Mathematical Modelling 30(7): 593–615.

45.

NVidia Corporation (2011a) CUDA Programming Guide. 4.0 edition. Available at: http://developer.nvidia.com/cuda-toolkit-40.

46.

NVidia Corporation (2011b) CUDA Toolkit 4.0, CUBLAS Library. Available at: http://developer.nvidia.com/cuda-toolkit-40.

47.

Corporation (2011c) CUDA Toolkit 4.0, CUSPARSE Library. Available at: http://developer.nvidia.com/cuda-toolkit-40.

48.

Pakzad

Lloyd

Phillips

(1997) Independent columns: A new parallel ILU preconditioner for the PCG method. Parallel Computing 23(6): 637–647.

49.

Papadrakakis

Stavroulakis

Karatarakis

(2011) A new era in scientific computing: Domain decomposition methods in hybrid CPU–GPU architectures. Computer Methods in Applied Mechanics and Engineering 200(13–16): 1490–1508. DOI:10.1016/j.cma.2011.01.013.

50.

Prakash

VVS

Mittra

(2001) Multi-frontal preconditioners for iterative solvers. In: IEEE antennas and propagation society international symposium, 2001, vol. 3, pp. 12–15.

51.

Quarteroni

Valli

(1999) Domain Decomposition Methods for Partial Differential Equations. Oxford: Oxford University Press.

52.

Saad

(2003) Iterative methods for sparse linear systems, 2nd edn. Philadelphia, PA: SIAM.

53.

Taniguchi

Shiraishi

(1980) New renumbering algorithm for minimizing the bandwidth of sparse matrices. Advances in Engineering Software (1978) 2(4): 173–179.

54.

Volkov

Demmel

(2008) LU, QR and Cholesky factorizations using vector capabilities of GPUs. Technical Report No. UCB/EECS-2008-49, EECS Department University of California, Berkeley. Available at: http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-49.pdf.

55.

Wang

Yao

Han

Zhang

(2009) Implementation of Jacobi iterative method on graphics processor unit. In: IEEE international conference on intelligent computing and intelligent systems, 2009 (ICIS 2009), vol. 3, pp. 324–327.

56.

Zhang

Speight

Rajamony

Xie

(2009) Hybrid cache architecture with disparate memory technologies. In: Proceedings of the 36th annual international symposium on computer architecture (ISCA’09). New York, NY: ACM Press, pp. 34–45.

57.

Lin

Xue

(2010) Sparse matrix–vector multiplication optimizations based on matrix bandwidth reduction using NVIDIA CUDA. In: 2010 ninth international symposium on distributed computing and applications to business engineering and science (DCABES), pp. 609–614.

58.

Zein

AHE

Rendell

(2012) Generating optimal CUDA sparse matrix–vector product implementations for evolving GPU hardware. Concurrency and Computation: Practice and Experience 24(1): 3–13.

59.

Zhang

Miao

Wang

(2009) CUDA-based Jacobi’s iterative method. In: International forum on computer science-technology and applications, 2009 (IFCSTA’09), vol. 1, pp. 259–262.

60.

Zou

Dou

(2012) Implementation of parallel sparse Cholesky factorization on GPU. In: 2012 2nd international conference on computer science and network technology (ICCSNT), pp. 2228–2232.