AAQAL: A Machine Learning-Based Tool for Performance Optimization of Parallel SPMV Computations Using Block CSR
The sparse matrix–vector product (SpMV), considered one of the seven dwarfs (numerical methods of significance), is essential in high-performance real-world scientific and analytical applications requiring solution of large sparse linear equation systems, where SpMV is a key computing operation. As...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-07-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/12/14/7073 |
| _version_ | 1827598112611368960 |
|---|---|
| author | Muhammad Ahmed Sardar Usman Nehad Ali Shah M. Usman Ashraf Ahmed Mohammed Alghamdi Adel A. Bahadded Khalid Ali Almarhabi |
| author_facet | Muhammad Ahmed Sardar Usman Nehad Ali Shah M. Usman Ashraf Ahmed Mohammed Alghamdi Adel A. Bahadded Khalid Ali Almarhabi |
| author_sort | Muhammad Ahmed |
| collection | DOAJ |
| description | The sparse matrix–vector product (SpMV), considered one of the seven dwarfs (numerical methods of significance), is essential in high-performance real-world scientific and analytical applications requiring solution of large sparse linear equation systems, where SpMV is a key computing operation. As the sparsity patterns of sparse matrices are unknown before runtime, we used machine learning-based performance optimization of the SpMV kernel by exploiting the structure of the sparse matrices using the Block Compressed Sparse Row (BCSR) storage format. As the structure of sparse matrices varies across application domains, optimizing the block size is important for reducing the overall execution time. Manual allocation of block sizes is error prone and time consuming. Thus, we propose AAQAL, a data-driven, machine learning-based tool that automates the process of data distribution and selection of near-optimal block sizes based on the structure of the matrix. We trained and tested the tool using different machine learning methods—decision tree, random forest, gradient boosting, ridge regressor, and AdaBoost—and nearly 700 real-world matrices from 43 application domains, including computer vision, robotics, and computational fluid dynamics. AAQAL achieved 93.47% of the maximum attainable performance with a substantial difference compared to in practice manual or random selection of block sizes. This is the first attempt at exploiting matrix structure using BCSR, to select optimal block sizes for the SpMV computations using machine learning techniques. |
| first_indexed | 2024-03-09T03:44:52Z |
| format | Article |
| id | doaj.art-e1bb31f7660f42b28bf38b91953274e7 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-09T03:44:52Z |
| publishDate | 2022-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-e1bb31f7660f42b28bf38b91953274e72023-12-03T14:36:12ZengMDPI AGApplied Sciences2076-34172022-07-011214707310.3390/app12147073AAQAL: A Machine Learning-Based Tool for Performance Optimization of Parallel SPMV Computations Using Block CSRMuhammad Ahmed0Sardar Usman1Nehad Ali Shah2M. Usman Ashraf3Ahmed Mohammed Alghamdi4Adel A. Bahadded5Khalid Ali Almarhabi6Department of Software Engineering, Islamia University Bahawalpur, Bahawalpur 63100, PakistanDepartment of Computer Science and Software Engineering, Gran Asian University Sialkot, Sialkot 53310, PakistanDepartment of Mechanical Engineering, Sejong University, Seoul 05006, KoreaDepartment of Computer Science, Government College Women University, Sialkot 53310, PakistanDepartment of Software Engineering, College of Computer Science and Engineering, University of Jeddah, Jeddah 21493, Saudi ArabiaDepartment of Information System, Faculty of Computing and Information Technology, King Abdulaziz University, Jeddah 21589, Saudi ArabiaDepartment of Computer Science, College of Computing in Al-Qunfudah, Umm Al-Qura University, Makkah 24381, Saudi ArabiaThe sparse matrix–vector product (SpMV), considered one of the seven dwarfs (numerical methods of significance), is essential in high-performance real-world scientific and analytical applications requiring solution of large sparse linear equation systems, where SpMV is a key computing operation. As the sparsity patterns of sparse matrices are unknown before runtime, we used machine learning-based performance optimization of the SpMV kernel by exploiting the structure of the sparse matrices using the Block Compressed Sparse Row (BCSR) storage format. As the structure of sparse matrices varies across application domains, optimizing the block size is important for reducing the overall execution time. Manual allocation of block sizes is error prone and time consuming. Thus, we propose AAQAL, a data-driven, machine learning-based tool that automates the process of data distribution and selection of near-optimal block sizes based on the structure of the matrix. We trained and tested the tool using different machine learning methods—decision tree, random forest, gradient boosting, ridge regressor, and AdaBoost—and nearly 700 real-world matrices from 43 application domains, including computer vision, robotics, and computational fluid dynamics. AAQAL achieved 93.47% of the maximum attainable performance with a substantial difference compared to in practice manual or random selection of block sizes. This is the first attempt at exploiting matrix structure using BCSR, to select optimal block sizes for the SpMV computations using machine learning techniques.https://www.mdpi.com/2076-3417/12/14/7073sparse matricesartificial intelligencemachine learningcompressed sparse row (CSR)block CSRdecision trees |
| spellingShingle | Muhammad Ahmed Sardar Usman Nehad Ali Shah M. Usman Ashraf Ahmed Mohammed Alghamdi Adel A. Bahadded Khalid Ali Almarhabi AAQAL: A Machine Learning-Based Tool for Performance Optimization of Parallel SPMV Computations Using Block CSR Applied Sciences sparse matrices artificial intelligence machine learning compressed sparse row (CSR) block CSR decision trees |
| title | AAQAL: A Machine Learning-Based Tool for Performance Optimization of Parallel SPMV Computations Using Block CSR |
| title_full | AAQAL: A Machine Learning-Based Tool for Performance Optimization of Parallel SPMV Computations Using Block CSR |
| title_fullStr | AAQAL: A Machine Learning-Based Tool for Performance Optimization of Parallel SPMV Computations Using Block CSR |
| title_full_unstemmed | AAQAL: A Machine Learning-Based Tool for Performance Optimization of Parallel SPMV Computations Using Block CSR |
| title_short | AAQAL: A Machine Learning-Based Tool for Performance Optimization of Parallel SPMV Computations Using Block CSR |
| title_sort | aaqal a machine learning based tool for performance optimization of parallel spmv computations using block csr |
| topic | sparse matrices artificial intelligence machine learning compressed sparse row (CSR) block CSR decision trees |
| url | https://www.mdpi.com/2076-3417/12/14/7073 |
| work_keys_str_mv | AT muhammadahmed aaqalamachinelearningbasedtoolforperformanceoptimizationofparallelspmvcomputationsusingblockcsr AT sardarusman aaqalamachinelearningbasedtoolforperformanceoptimizationofparallelspmvcomputationsusingblockcsr AT nehadalishah aaqalamachinelearningbasedtoolforperformanceoptimizationofparallelspmvcomputationsusingblockcsr AT musmanashraf aaqalamachinelearningbasedtoolforperformanceoptimizationofparallelspmvcomputationsusingblockcsr AT ahmedmohammedalghamdi aaqalamachinelearningbasedtoolforperformanceoptimizationofparallelspmvcomputationsusingblockcsr AT adelabahadded aaqalamachinelearningbasedtoolforperformanceoptimizationofparallelspmvcomputationsusingblockcsr AT khalidalialmarhabi aaqalamachinelearningbasedtoolforperformanceoptimizationofparallelspmvcomputationsusingblockcsr |