.png){kind=icon}
.png){kind=icon}
Return
ALBBA: An efficient ALgebraic Bypass BFS Algorithm on long vector architectures
.png){kind=icon}
OA
AI
DOI：10.1016/j.parco.2025.103147.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Breadth First Search (BFS) is a fundamental algorithm in scientific computing, databases, and analysis applications. In the algebraic BFS paradigm, each BFS iteration is expressed as a sparse matrix-vector multiplication, allowing BFS to be accelerated and analyzed through well-established linear algebra primitives. Although much effort has been made to optimize algebraic BFS on parallel platforms such as CPUs, and distributed memory systems, vector architectures that exploit Single Instruction Multiple Data parallelism, particularly with their high performance on sparse workloads, remain relatively underexplored for BFS. In this paper, we propose the ALgebraic Bypass BFS Algorithm (ALBBA), a novel and efficient algebraic BFS implementation optimized for long vector architectures. ALBBA utilizes a customized variant SELL-C-6 data structure to fully exploit the SIMD capabilities. By integrating a vectorization-friendly method alongside a two-level bypass strategy, we enhance both sparse matrix-sparse vector multiplication (SpMSpV) and sparse matrix-dense vector multiplication (SpMV) algorithms, which are crucial for algebraic BFS operations. We further incorporate merge primitives and adopt an efficient selection method for each iteration. Our experiments on an NEC VE20B processor demonstrate that ALBBA achieves average speedups of 3.91x , 2.88x , and 1.46x over Enterprise, GraphBLAST, and Gunrock running on an NVIDIA H100 respectively.
Keywords:
Breadth first search
Sparse matrix-sparse vector multiplication
Sparse matrix-dense vector multiplication
Vector architecture
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
P
IF:
2.1
Papers:
19
Citations:
0