Acceleration of Approximate Matrix Multiplications on GPUs
Matrix multiplication is important in various information-processing applications, including the computation of eigenvalues and eigenvectors, and in combinatorial optimization algorithms. Therefore, reducing the computation time of matrix products is essential to speed up scientific and practical ca...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-07-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/25/8/1130 |
| _version_ | 1827729876689354752 |
|---|---|
| author | Takuya Okuyama André Röhm Takatomo Mihana Makoto Naruse |
| author_facet | Takuya Okuyama André Röhm Takatomo Mihana Makoto Naruse |
| author_sort | Takuya Okuyama |
| collection | DOAJ |
| description | Matrix multiplication is important in various information-processing applications, including the computation of eigenvalues and eigenvectors, and in combinatorial optimization algorithms. Therefore, reducing the computation time of matrix products is essential to speed up scientific and practical calculations. Several approaches have been proposed to speed up this process, including GPUs, fast matrix multiplication libraries, custom hardware, and efficient approximate matrix multiplication (AMM) algorithms. However, research to date has yet to focus on accelerating AMMs for general matrices on GPUs, despite the potential of GPUs to perform fast and accurate matrix product calculations. In this paper, we propose a method for improving Monte Carlo AMMs. We also give an analytical solution for the optimal values of the hyperparameters in the proposed method. The proposed method improves the approximation of the matrix product without increasing the computation time compared to the conventional AMMs. It is also designed to work well with parallel operations on GPUs and can be incorporated into various algorithms. Finally, the proposed method is applied to a power method used for eigenvalue computation. We demonstrate that, on an NVIDIA A100 GPU, the computation time can be halved compared to the conventional power method using cuBLAS. |
| first_indexed | 2024-03-10T23:58:20Z |
| format | Article |
| id | doaj.art-739291fcb120495fbe70d9044c5184ae |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-10T23:58:20Z |
| publishDate | 2023-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-739291fcb120495fbe70d9044c5184ae2023-11-19T00:58:59ZengMDPI AGEntropy1099-43002023-07-01258113010.3390/e25081130Acceleration of Approximate Matrix Multiplications on GPUsTakuya Okuyama0André Röhm1Takatomo Mihana2Makoto Naruse3Department of Information Physics and Computing, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8656, JapanDepartment of Information Physics and Computing, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8656, JapanDepartment of Information Physics and Computing, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8656, JapanDepartment of Information Physics and Computing, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113-8656, JapanMatrix multiplication is important in various information-processing applications, including the computation of eigenvalues and eigenvectors, and in combinatorial optimization algorithms. Therefore, reducing the computation time of matrix products is essential to speed up scientific and practical calculations. Several approaches have been proposed to speed up this process, including GPUs, fast matrix multiplication libraries, custom hardware, and efficient approximate matrix multiplication (AMM) algorithms. However, research to date has yet to focus on accelerating AMMs for general matrices on GPUs, despite the potential of GPUs to perform fast and accurate matrix product calculations. In this paper, we propose a method for improving Monte Carlo AMMs. We also give an analytical solution for the optimal values of the hyperparameters in the proposed method. The proposed method improves the approximation of the matrix product without increasing the computation time compared to the conventional AMMs. It is also designed to work well with parallel operations on GPUs and can be incorporated into various algorithms. Finally, the proposed method is applied to a power method used for eigenvalue computation. We demonstrate that, on an NVIDIA A100 GPU, the computation time can be halved compared to the conventional power method using cuBLAS.https://www.mdpi.com/1099-4300/25/8/1130approximate calculationapproximate matrix multiplicationGPU computing |
| spellingShingle | Takuya Okuyama André Röhm Takatomo Mihana Makoto Naruse Acceleration of Approximate Matrix Multiplications on GPUs Entropy approximate calculation approximate matrix multiplication GPU computing |
| title | Acceleration of Approximate Matrix Multiplications on GPUs |
| title_full | Acceleration of Approximate Matrix Multiplications on GPUs |
| title_fullStr | Acceleration of Approximate Matrix Multiplications on GPUs |
| title_full_unstemmed | Acceleration of Approximate Matrix Multiplications on GPUs |
| title_short | Acceleration of Approximate Matrix Multiplications on GPUs |
| title_sort | acceleration of approximate matrix multiplications on gpus |
| topic | approximate calculation approximate matrix multiplication GPU computing |
| url | https://www.mdpi.com/1099-4300/25/8/1130 |
| work_keys_str_mv | AT takuyaokuyama accelerationofapproximatematrixmultiplicationsongpus AT andrerohm accelerationofapproximatematrixmultiplicationsongpus AT takatomomihana accelerationofapproximatematrixmultiplicationsongpus AT makotonaruse accelerationofapproximatematrixmultiplicationsongpus |