Реализация и оценка производительности разреженного матрично-векторного умножения многократной точности на CUDA с использованием системы остаточных классов
Автор: Исупов Константин Сергеевич, Князьков Владимир Сергеевич, Бабешко Иван Павлович, Крутиков Александр Константинович
Журнал: Проблемы информатики @problem-info
Рубрика: Параллельное системное программирование и вычислительные технологии
Статья в выпуске: 1 (50), 2021 года.
Бесплатный доступ
Умножение разреженной матрицы на плотный вектор (SpMV) является основным и наиболее затратным элементом в итерационных методах решения разреженных линейных систем и задач на собственные значения. Эффективная реализация SpMV имеет решающее значение для многих научных и инженерных вычислений, причем важно обеспечить не только высокое быстродействие, но и достаточную точность SpMV, поскольку итерационные методы известны своей чувствительностью к ошибкам округления. В статье мы рассматриваем параллельные реализации SpMV для CUDA-совместимых графических процессоров видеокарт (GPU) с использованием арифметики многократной точности на основе системы остаточных классов (СОК). Основным преимуществом СОК перед позиционными системами счисления является отсутствие переносов между цифрами числа, что позволяет заменить многоразрядные операции группами покомпонентных операций с цифрами небольшой разрядности, которые выполняются без накладных расходов, связанных с обработкой информации о переносах между цифрами. Мы рассматриваем реализации SpMV, основанные на двух широко распространенных форматах хранения разреженной матрицы - CSR и ELLPACK. Экспериментальная оценка с матрицами из реальных приложений показывает, что во многих случаях представленные реализации выполняются быстрее, чем реализации на основе существующих библиотек многократной точности для GPU.
Разреженные матрицы, spmv, арифметика многократной точности, система остаточных классов, программирование для графических процессоров
Короткий адрес: https://sciup.org/143178105
IDR: 143178105 | DOI: 10.24411/2073-0667-2021-10005
Список литературы Реализация и оценка производительности разреженного матрично-векторного умножения многократной точности на CUDA с использованием системы остаточных классов
- Filippone S., Cardellini V., Barbieri D., Fanfarillo A. Sparse Matrix-Vector Multiplication on GPGPUs // ACM Transactions on Mathematical Software. 2017. Vol. 43, N 4. Article No. 30. DOI: 10.1145/3017994.
- Bell N., Garland M. Efficient Sparse Matrix-Vector Multiplication on CUDA. Technical Report NVR-2008-004. NVIDIA Corporation. 2008. [Electron. Res.]: https://www.nvidia.com/docs/IO/66889/nvr-2008-004.pdf (date of access: 10.01.2021).
- Greathouse J. L., Daga M. Efficient sparse matrix-vector multiplication on GPUs using the CSR storage format // Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC14, November 16-21, 2014, New Orleans, LA, USA. IEEE, 2014. P. 769-780. DOI: 10.1109/SC.2014.68.
- Liu Y., Schmidt B. LightSpMV: Faster CSR-based sparse matrix-vector multiplication on CUDA-enabled GPUs // Proceedings of the 2015 IEEE 26th International Conference on Application-specific Systems, Architectures and Processors (ASAP), July 27-29, 2015, Toronto, ON, Canada. IEEE, 2015. P. 82-89. DOI: 10.1109/ASAP.2015.7245713.
- Sedaghati N., Mu Т., Pouchet L.-N., Parthasarathv S., Sadavappan P. Automatic selection of sparse matrix representation on GPUs // Proceedings of the 29th ACM on International Conference on Supercomputing, ICS'15, June 8-11, 2015 at Newport Beach, CA, USA. ACM, 2015. P. 99-108. DOI: 10.1145/2751205.2751244.
- 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.
- 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.
- Shewchuk J. R. Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates // Discrete and Computational Geometry. 1997. Vol. 18, N 3. P. 305-363. DOI: 10.1007/PL00009321.
- 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.
- 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. DOI: 10.1007/978-3-319-61982-8^4.
- 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.
- Hirokawa Y., It oh T., Tadano H., Ikuno S. Speedup and numerical evaluation of multiple-precision Krylov subspace method using GPU cluster for large-sparse linear system // Proceedings of the international conference for high performance computing, networking, storage and analysis, SC13, November 17-22, Denver, Colorado, USA. Colorado Convention Center, 2013.
- Mohan Ananda P. A. Residue Number Systems. Theory and Applications. Cham: Birkhauser. 2016.
- Omondi A., Premkumar B. Residue Number Systems: Theory and Implementation. Imperial College Press, 2007.
- Isupov K. Using Floating-Point Intervals for Non-Modular Computations in Residue Number System // IEEE Access. 2020. Vol. 8. P. 58603-58619. DOI: 10.1109/ACCESS.2020.2982365.
- Isupov K., Knyazkov V., Kuvaev A. Design and Implementation of Multiple-Precision BLAS Level 1 Functions for Graphics Processing Units // Journal of Parallel and Distributed Computing. 2020. Vol. 140. P. 25-36. DOI: 10.1016/j.jpdc.2020.02.006.
- Joldes M., Muller J. M., Popescu V. Implementation and Performance Evaluation of an Extended Precision Floating-Point Arithmetic Library for High-Accuracy Semidefinite Programming // Proceedings of the 24th IEEE Symposium on Computer Arithmetic, ARITH, July 24-26, 2017, London, UK. IEEE, 2017. P. 27-34. DOI: 10.1109/ARITH.2017.18.
- Nakayama T., Takahashi D. Implementation of Multiple-Precision Floating-Point Arithmetic Library for GPL* Computing // Proceedings of the 23rd IASTED International Conference on Parallel and Distributed Computing and Systems, PDCS 2011, December 14-16, 2011, Dallas, L'SA. ACTA Press, 2011. P. 343-349.
