Accelerating gustavson-based SpMM on embedded FPGAs with element-wise parallelism and access pattern-aware caches
The Gustavson’s algorithm (i.e., the row-wise product algorithm) shows its potential as the backbone algorithm for sparse matrix-matrix multiplication (SpMM) on hardware accelerators. However, it still suffers from irregular memory accesses and thus its performance is bounded by the off-chip memory...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/167477 |
| _version_ | 1811688511398477824 |
|---|---|
| author | Li, Shiqing Liu, Weichen |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Li, Shiqing Liu, Weichen |
| author_sort | Li, Shiqing |
| collection | NTU |
| description | The Gustavson’s algorithm (i.e., the row-wise product algorithm) shows its potential as the backbone algorithm for sparse matrix-matrix multiplication (SpMM) on hardware accelerators. However, it still suffers from irregular memory accesses and thus its performance is bounded by the off-chip memory traffic. Previous works mainly focus on high bandwidth memory-based architectures and are not suitable for embedded FPGAs with traditional DDR. In this work, we propose an efficient Gustavson-based SpMM accelerator on embedded FPGAs with element-wise parallelism and access pattern-aware caches. First of all, we analyze the parallelism of the Gustavson’s algorithm and propose to perform the algorithm with element-wise parallelism, which reduces the idle time of processing elements caused by synchronization. Further, we show a counter-intuitive example that the traditional cache leads to worse performance. Then, we propose a novel access pattern-aware cache scheme called SpCache, which provides quick responses to reduce bank conflicts caused by irregular memory accesses and combines streaming and caching to handle requests that access ordered elements of unpredictable length. Finally, we conduct experiments on the Xilinx Zynq-UltraScale ZCU106 platform with a set of benchmarks from the SuiteSparse matrix collection. The experimental results show that the proposed design achieves an average 1.62x performance speedup compared to the baseline. |
| first_indexed | 2024-10-01T05:33:22Z |
| format | Conference Paper |
| id | ntu-10356/167477 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T05:33:22Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | ntu-10356/1674772023-06-16T15:35:54Z Accelerating gustavson-based SpMM on embedded FPGAs with element-wise parallelism and access pattern-aware caches Li, Shiqing Liu, Weichen School of Computer Science and Engineering 2023 Design, Automation & Test in Europe Conference & Exhibition (DATE) Engineering::Computer science and engineering Engineering::Computer science and engineering::Hardware SpMM FPGA Gustavson Cache The Gustavson’s algorithm (i.e., the row-wise product algorithm) shows its potential as the backbone algorithm for sparse matrix-matrix multiplication (SpMM) on hardware accelerators. However, it still suffers from irregular memory accesses and thus its performance is bounded by the off-chip memory traffic. Previous works mainly focus on high bandwidth memory-based architectures and are not suitable for embedded FPGAs with traditional DDR. In this work, we propose an efficient Gustavson-based SpMM accelerator on embedded FPGAs with element-wise parallelism and access pattern-aware caches. First of all, we analyze the parallelism of the Gustavson’s algorithm and propose to perform the algorithm with element-wise parallelism, which reduces the idle time of processing elements caused by synchronization. Further, we show a counter-intuitive example that the traditional cache leads to worse performance. Then, we propose a novel access pattern-aware cache scheme called SpCache, which provides quick responses to reduce bank conflicts caused by irregular memory accesses and combines streaming and caching to handle requests that access ordered elements of unpredictable length. Finally, we conduct experiments on the Xilinx Zynq-UltraScale ZCU106 platform with a set of benchmarks from the SuiteSparse matrix collection. The experimental results show that the proposed design achieves an average 1.62x performance speedup compared to the baseline. Ministry of Education (MOE) Nanyang Technological University Submitted/Accepted version This work is partially supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 2 (MOE2019-T2-1-071), and Nanyang Technological University, Singapore, under its NAP (M4082282). 2023-06-12T01:15:52Z 2023-06-12T01:15:52Z 2023 Conference Paper Li, S. & Liu, W. (2023). Accelerating gustavson-based SpMM on embedded FPGAs with element-wise parallelism and access pattern-aware caches. 2023 Design, Automation & Test in Europe Conference & Exhibition (DATE). https://dx.doi.org/10.23919/DATE56975.2023.10136958 https://hdl.handle.net/10356/167477 10.23919/DATE56975.2023.10136958 en MOE2019-T2-1-071 NAP (M4082282) 10.21979/N9/OA7NLF © 2023 EDAA. Published by IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: https://doi.org/10.23919/DATE56975.2023.10136958. application/pdf |
| spellingShingle | Engineering::Computer science and engineering Engineering::Computer science and engineering::Hardware SpMM FPGA Gustavson Cache Li, Shiqing Liu, Weichen Accelerating gustavson-based SpMM on embedded FPGAs with element-wise parallelism and access pattern-aware caches |
| title | Accelerating gustavson-based SpMM on embedded FPGAs with element-wise parallelism and access pattern-aware caches |
| title_full | Accelerating gustavson-based SpMM on embedded FPGAs with element-wise parallelism and access pattern-aware caches |
| title_fullStr | Accelerating gustavson-based SpMM on embedded FPGAs with element-wise parallelism and access pattern-aware caches |
| title_full_unstemmed | Accelerating gustavson-based SpMM on embedded FPGAs with element-wise parallelism and access pattern-aware caches |
| title_short | Accelerating gustavson-based SpMM on embedded FPGAs with element-wise parallelism and access pattern-aware caches |
| title_sort | accelerating gustavson based spmm on embedded fpgas with element wise parallelism and access pattern aware caches |
| topic | Engineering::Computer science and engineering Engineering::Computer science and engineering::Hardware SpMM FPGA Gustavson Cache |
| url | https://hdl.handle.net/10356/167477 |
| work_keys_str_mv | AT lishiqing acceleratinggustavsonbasedspmmonembeddedfpgaswithelementwiseparallelismandaccesspatternawarecaches AT liuweichen acceleratinggustavsonbasedspmmonembeddedfpgaswithelementwiseparallelismandaccesspatternawarecaches |