Parallel graph algorithms on a RISCV-based many-core

Abstract

Graph algorithms are essential in domains like social network analysis, web search, and bioinformatics. Their execution on modern hardware is vital due to the growing size and complexity of graphs. Traditional multi-core systems struggle with irregular memory access patterns in graph workloads. Reduced instruction set computer–five (RISC-V)-based many-core processors offer a promising alternative with their customizable open-source architecture suitable for optimization. This work focuses on parallelizing graph algorithms like breadth-first search (BFS) and PageRank (PR) on RISC-V many-core systems. We evaluated performance based on graph structure and processor architecture, and developed an analytical model to predict execution time. The model incorporates the unique characteristics of the RISC-V architecture and the types and numbers of instructions executed by multiple cores, with a maximum prediction error of 11%. Our experiments show a speedup of up to 11.55× for BFS and 7.56× for PR using 16 and 8 cores, respectively, over single-core performance. Comparisons with existing graph processing frameworks demonstrate that RISC-V systems can deliver up to 20× better energy efficiency on real-world graphs from the network repository.