Паралельний SVD алгоритм для тридіагональної матриці на відеокарті з використанням архітектури Nvidia CUDA
Loading...
Date
2021-12-10
Authors
Семилітко, Микола
Малашонок, Геннадiй
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Ця робота пропонує реалізацію паралельного алгоритму SVD для тридіагональної матриці на відеокарті з використанням архітектури Nvidia CUDA для роботи з великими матрицями. Для цього було досліджено роботу послідовного алгоритму, розроблено модель паралельного алгоритму на Java, який враховує особливості роботи відеокарти, і реалізовано та протестовано алгоритми для відеокарти з використанням різних типів пам’яті відеокарти, які можна використовувати у програмах на Java та С/C++.
SVD (Singular Value Decomposition) algorithm is used in recommendation systems, machine learning, image processing, and in various algorithms for working with matrices which can be very large and Big Data, so, given the peculiarities of this algorithm, it can be performed on a large number of computing threads that have only video cards. CUDA is a parallel computing platform and application programming interface model created by Nvidia. It allows software developers and software engineers to use a CUDA-enabled graphics processing unit for general purpose processing – an approach termed GPGPU (general-purpose computing on graphics processing units). The GPU provides much higher instruction throughput and memory bandwidth than the CPU within a similar price and power envelope. Many applications leverage these higher capabilities to run faster on the GPU than on the CPU. Other computing devices, like FPGAs, are also very energy efficient, but they offer much less programming flexibility than GPUs. The developed modification uses the CUDA architecture, which is intended for a large number of simultaneous calculations, which allows to quickly process matrices of very large sizes. The algorithm of parallel SVD for a three-diagonal matrix based on the Givents rotation provides a high accuracy of calculations. Also the algorithm has a number of optimizations to work with memory and multiplication algorithms that can significantly reduce the computation time discarding empty iterations. This article proposes an approach that will reduce the computation time and, consequently, resources and costs. The developed algorithm can be used with the help of a simple and convenient API in C ++ and Java, as well as will be improved by using dynamic parallelism or parallelization of multiplication operations. Also the obtained results can be used by other developers for comparison, as all conditions of the research are described in detail, and the code is in free access.
SVD (Singular Value Decomposition) algorithm is used in recommendation systems, machine learning, image processing, and in various algorithms for working with matrices which can be very large and Big Data, so, given the peculiarities of this algorithm, it can be performed on a large number of computing threads that have only video cards. CUDA is a parallel computing platform and application programming interface model created by Nvidia. It allows software developers and software engineers to use a CUDA-enabled graphics processing unit for general purpose processing – an approach termed GPGPU (general-purpose computing on graphics processing units). The GPU provides much higher instruction throughput and memory bandwidth than the CPU within a similar price and power envelope. Many applications leverage these higher capabilities to run faster on the GPU than on the CPU. Other computing devices, like FPGAs, are also very energy efficient, but they offer much less programming flexibility than GPUs. The developed modification uses the CUDA architecture, which is intended for a large number of simultaneous calculations, which allows to quickly process matrices of very large sizes. The algorithm of parallel SVD for a three-diagonal matrix based on the Givents rotation provides a high accuracy of calculations. Also the algorithm has a number of optimizations to work with memory and multiplication algorithms that can significantly reduce the computation time discarding empty iterations. This article proposes an approach that will reduce the computation time and, consequently, resources and costs. The developed algorithm can be used with the help of a simple and convenient API in C ++ and Java, as well as will be improved by using dynamic parallelism or parallelization of multiplication operations. Also the obtained results can be used by other developers for comparison, as all conditions of the research are described in detail, and the code is in free access.
Description
Keywords
сингулярний розклад матриці, SVD, Nvidia CUDA, Java, С, стаття, Singular value decomposition, SVD, Nvidia CUDA, Java, С, article
Citation
Семилітко М.Ю. Паралельний SVD алгоритм для тридіагональної матриці на відеокарті з використанням архітектури Nvidia CUDA / Семилітко М. Ю., Малашонок Г. І. // Наукові записки НаУКМА. Комп'ютерні науки. - 2021. - Т. 4. - С. 16-22. - https://doi.org/10.18523/2617-3808.2021.4.16-22