Реализация и оценка сходимости итерационных CG и PCG решателей многократной точности для графических процессоров
Автор: Исупов Константин Сергеевич, Князьков Владимир Сергеевич, Коржавина Анастасия Сергеевна
Журнал: Проблемы информатики @problem-info
Рубрика: Теоретическая и системная информатика
Статья в выпуске: 1 (54), 2022 года.
Бесплатный доступ
Для решения систем линейных алгебраических уравнений с разреженными матрицами коэффициентов широко применяются итерационные методы подпространства Крылова. Однако сходимость этих методов может ухудшаться из-за ошибок округления, возникающих при выполнении вычислений в арифметике фиксированной разрядности. Снизить влияние ошибок округления позволяет использование арифметики многократной точности, обеспечивающей выполнение операций с числами повышенной разрядности. В статье представлены реализации итерационных решателей многократной точности на базе метода сопряженных градиентов без предобуславливания и с диагональным предобуславливанием для графических процессоров видеокарт. Для поддержки вычислений с числами повышенной разрядности используется система остаточных классов. Матрично-векторное произведение реализовано в виде гибридного ядра, в котором матрица двойной точности, представленная в формате CSR, умножается на вектор многократной точности. Параллельное скалярное произведение вычисляется с использованием двухэтапного алгоритма. Результаты экспериментов с разреженными матрицами различных размеров показывают, что повышенная точность арифметики позволяет ускорить сходимость итерационных методов.
Разреженная линейная алгебра, метод сопряженных градиентов, арифметика многократной точности, система остаточных классов, cuda
Короткий адрес: https://sciup.org/143179062
IDR: 143179062 | УДК: 001.222 | DOI: 10.24412/2073-0667-2022-1-17-27
Implementation and convergence evaluation of multiple-precision iterative CG and PCG solvers for GPUS
To solve systems of linear equations with sparse coefficient matrices, iterative Krylov subspace methods such as conjugate gradients (CG) and preconditioned conjugate gradients (PCG) are widely used. The convergence rate and numerical reliability of these methods may suffer from rounding errors. One way to reduce the impact of rounding errors is to use arithmetic over numbers with increased word length, which is called multiple-precision arithmetic. In the paper, we consider multiple-precision iterative CG and PCG solvers for graphics processing units (GPUs) and evaluate their convergence rate. The preconditioned implementation uses a diagonal preconditioner, which is well suited for parallel computing. The residue number system is employed to support multiple-precision floating-point arithmetic. The matrix-vector product is implemented as a hybrid kernel, in which a double-precision matrix, represented in the CSR storage format, is multiplied by a dense multiple-precision vector. A two-stage algorithm is used to compute the parallel multiple-precision dot product. Experimental results with sparse matrices of different sizes show that higher arithmetic precision improves the convergence rate of iterative methods.
Список литературы Реализация и оценка сходимости итерационных CG и PCG решателей многократной точности для графических процессоров
- Saad Y. Iterative Methods for Sparse Linear Systems, 2nd ed. Philadelphia: SIAM, 2003. 547 p.
- Barrett R. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods (2nd Edition) / R. Barrett et al. Philadelphia: SIAM, 1994. 107 p.
- Saito Т., Ishiwata E., Hasegawa H. Analysis of the GCR method with mixed precision arithmetic using QuPAT // Journal of Computational Science. 2012. Vol. 3, N 3. P. 87-91. DOI: 10.1016/j.joes.2011.05.001.
- Cools S., Yetkin E.F., Agullo E., Giraud L., Vanroose W. Analyzing the Effect of Local Rounding Error Propagation on the Maximal Attainable Accuracy of the Pipelined Conjugate Gradient Method // SIAM Journal on Matrix Analysis and Applications. 2018. Vol. 39, N 1. P. 426-450. DOI: 10.1137/17M1117872.
- Kouva T. A highly efficient implementation of multiple precision sparse matrix-vector multiplication and its application to product-type Krvlov subspace methods // International Journal of Numerical Methods and Applications. 2012. Vol. 7, N 2. P. 107-119.
- Hishinuma Т., Hasegawa H., Tanaka T. SIMD Parallel Sparse Matrix-Vector and Transposed-Matrix-Vector Multiplication in DD Precision // Lecture Notes in Computer Science. 2017. Vol. 10150. P. 21-34.
- Hasegawa H. Utilizing the quadruple-precision floating-point arithmetic operation for the Krvlov subspace methods. 2003. [Electron. Res.]: http://www.slis.tsukuba.ac.jp/~hasegawa.hidehiko. ga/GYOSEKI/hhasegaw.pdf (accessed 17 January 2022).
- Masui K. Ogino M. Research on the Convergence of Iterative Method Using Mixed Precision Calculation Solving Complex Symmetric Linear Equation // IEEE Transactions on Magnetics. 2020. Vol. 56, N 1. Article no. 7503604. DOI: 10.1109/TMAG.2019.2951280.
- Mukunoki D., Takahashi D. Using Quadruple Precision Arithmetic to Accelerate Krvlov Subspace Methods on GPUs // Lecture Notes in Computer Science. 2014. Vol. 8384. P. 632-642. DOI: 10.1007/978-3-642-55224-3^59.
- Isupov K., Knvazkov V. Multiple-Precision BLAS Library for Graphics Processing Units // Communications in Computer and Information Science. 2020. Vol. 1331. P. 37-49. DOI: 10.1007/978-3-030-64616-5^4.
- Omondi A., Premkumar B. Residue Number Systems: Theory and Implementation. Imperial College Press, 2007. 402 p.
