Parallel Algorithm of Conjugate Gradient Solver using OpenGL Compute Shader
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
OpenGL compute shader is a shader stage that operate differently from other shader stage and it can be used for the calculating purpose of any data in parallel. This paper proposes a GPU-based parallel algorithm for computing sparse linear systems through conjugate gradient using an iterative method, which perform calculation on OpenGL compute shader. Basically, this sparse linear solver is used to solve large linear systems such as symmetric positive definite matrix. Four well-known matrix formats (Dense, COO, ELL and CSR) have been used for matrix storage. The performance comparison from our experimental tests using eight sparse matrices shows that GPU-based linear solving system much faster than CPU-based linear solving system with the best average computing time 0.64ms in GPU-based and 15.37ms in CPU-based.
Abstract
OpenGL compute shader is a shader stage that operate differently from other shader stage and it can be used for the calculating purpose of any data in parallel. This paper proposes a GPU-based parallel algorithm for computing sparse linear systems through conjugate gradient using an iterative method, which perform calculation on OpenGL compute shader. Basically, this sparse linear solver is used to solve large linear systems such as symmetric positive definite matrix. Four well-known matrix formats (Dense, COO, ELL and CSR) have been used for matrix storage. The performance comparison from our experimental tests using eight sparse matrices shows that GPU-based linear solving system much faster than CPU-based linear solving system with the best average computing time 0.64ms in GPU-based and 15.37ms in CPU-based.
참고문헌 (23)
- S. Abbasbandy, "Conjugate gradient method for fuzzy symmetric positive definite system of linear equations", Applied Mathematics and Computation, 171(2), pp.1184~1191 (2005), Elsevier BV[DOI]
- Mykola Kryshchuk, "Iterative Method for Solving a System of Linear Equations", Procedia Computer Science, 104, pp.133~137 (2017), Elsevier BV[DOI]
- Angelika Bunse-Gerstner, "On a conjugate gradient-type method for solving complex symmetric linear systems", Linear Algebra and its Applications, 287(1-3), pp.105~123 (1999), Elsevier BV[DOI]
- Alberto Cano, "A survey on graphic processing unit computing for large-scale data mining", Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 8(1), pp.e1232~ (2018), Wiley[DOI]
- J. Sim, "A Performance Analysis Framework for Identifying Potential Benefits in GPGPU Applications", Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 47(8), pp.11~22 (2012)[DOI]
- Daniel Gerzhoy, "Nested MIMD-SIMD Parallelization for Heterogeneous Microprocessors", ACM Transactions on Architecture and Code Optimization, 16(4), pp.1~27 (2019), Association for Computing Machinery (ACM)[DOI]
- Woosuk Shin, "Large-Scale Data Computing Performance Comparisons on SYCL Heterogeneous Parallel Processing Layer Implementations", Applied Sciences, 10(5), pp.1656~ (2020), MDPI AG[DOI]
- J. S. Kirtzic, "A parallel algorithm design model for the gpu architecture", Ph.D., pp.2012
- M. Ament, "A Parallel Preconditioned Conjugate Gradient Solver for the Poisson Problem on a Multi-GPU Platform", 201018th Euromicro Conference on Parallel, Distributed and Network-based Processing, Pisa, pp.583~592 (2010)
- Rudi Helfenstein, "Parallel preconditioned conjugate gradient algorithm on GPU", Journal of Computational and Applied Mathematics, 236(15), pp.3584~3590 (2012), Elsevier BV[DOI]
- Abal-Kassim Cheik Ahamed, "Conjugate gradient method with graphics processing unit acceleration: CUDA vs OpenCL", Advances in Engineering Software, 111, pp.32~42 (2017), Elsevier BV[DOI]
- M. M. Baskaran, "Optimizing Sparse Matrix-Vector Multiplications on GPUs", Computer Science, 8, pp.812~847 (2009)
- A. Benatia, "Sparse Matrix Format Selection with Multiclass SVM for SpMV on GPU", 2016 45th International Conference on Parallel Processing (ICPP), pp.496~505 (2016)
- N. Bell, "Implementing sparse matrix-vector multiplication on throughput-oriented processors", Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, pp.1~11 (2009)
- D. Shreiner, "OpenGL programming guide: The Official guide to learning OpenGL version 4.3" (2013), Addison-Wesley
- 성낙준, "질량스프링 시뮬레이션을 위한 병렬 구조 설계 방법", 한국컴퓨터그래픽스학회논문지, 25(3), pp.55~63 (2019), (사)한국컴퓨터그래픽스학회[DOI]
- Efficient Sparse Matrix-Vector Multiplication on CUDA, "N. Bell", NVIDIA, ~, pp.NVIDIA Technical Report NVR-2008-004 (2008)
- W. Cao, "Implementing Sparse Matrix-Vector multiplication using CUDA based on a hybrid sparse matrix format", 2010 International Conference on Computer Application and System Modeling, pp. V11-161-V11-165, pp.V11-161~V11-165 (2010)
- Segmented Operations for Sparse Matrix Computation on Vector Multiprocessors, "G. E. Blelloch", Carnegie Mellon University, ~ (1993)
- M.R. Hestenes, "Methods of conjugate gradients for solving linear systems", Journal of Research of the National Bureau of Standards, 49(6), pp.409~ (1952), National Institute of Standards and Technology (NIST)[DOI]
- "SuiteSparse Matrix Collection"[URL]
- D. Mukunoki, "Conjugate Gradient Solvers with High Accuracy and Bit-wise Reproducibility between CPU and GPU using Ozaki scheme", The International Conference on High Performance Computing in Asia-Pacific Region, pp.100~109 (2021)
- Nileshchandra K Pikle, "GPGPU-based parallel computing applied in the FEM using the conjugate gradient algorithm: a review", Sādhanā, 43(7) (2018), Springer Science and Business Media LLC[DOI]