CoSPARSE: A Software and Hardware Reconfigurable SpMV Framework for Graph Analytics

Siying Feng, Jiawen Sun, Subhankar Pal, Xin He, Kuba Kaszyk, Dong-hyeon Park, Magnus Morton, Trevor Mudge, Murray Cole, Michael O'Boyle, Chaitali Chakrabarti, Ronald Dreslinski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Sparse matrix-vector multiplication (SpMV) is a critical building block for iterative graph analytics algorithms. Typically, such algorithms have a varying active vertex set across iterations. This variablity has been used to improve performance by either dynamically switching algorithms between iterations (software) or designing custom accelerators (hardware) for graph analytics algorithms. In this work, we propose a novel framework, CoSPARSE, that employs hardware and softwarere configuration as a synergistic solution to accelerate SpMV-based graph analytics algorithms. Building on previously proposed general-purpose reconfigurable hardware, we implement CoSPARSE as a software layer, abstracting the hardware as a specialized SpMV accelerator. CoSPARSE dynamically selects software and hardware configurations for each iteration and achieves a maximum speedup of 2.0× compared to the naïve implementation with no reconfiguration. Across a suite of graph algorithms, CoSPARSE outperforms a state-of-the-art shared memory framework, Ligra, on a Xeon CPU with up to 3.51× better performance and 877× better energy efficiency.
Original languageEnglish
Title of host publication2021 58th ACM/IEEE Design Automation Conference (DAC)
PublisherInstitute of Electrical and Electronics Engineers
Pages949-955
Number of pages6
ISBN (Electronic)978-1-6654-3274-0
ISBN (Print)978-1-6654-3275-7
DOIs
Publication statusPublished - 13 Nov 2021
Event58th Design Automation Conference - San Francisco, United States
Duration: 5 Dec 20219 Dec 2021
https://www.dac.com/

Publication series

Name
ISSN (Print)0738-100X

Conference

Conference58th Design Automation Conference
Abbreviated titleDAC 2021
Country/TerritoryUnited States
CitySan Francisco
Period5/12/219/12/21
Internet address

Fingerprint

Dive into the research topics of 'CoSPARSE: A Software and Hardware Reconfigurable SpMV Framework for Graph Analytics'. Together they form a unique fingerprint.

Cite this