.png){kind=icon}
返回
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}
分享.png){kind=icon}
收藏
摘要
En 中文
广度优先搜索（BFS）是科学计算、数据库和分析应用中的基础算法。在代数BFS范式中，每次BFS迭代被表示为稀疏矩阵-向量乘法，这使得BFS可以通过成熟的线性代数原语进行加速和分析。尽管已投入大量工作优化代数BFS在CPU等并行平台以及分布式内存系统上的性能，但利用单指令多数据（SIMD）并行性的向量架构，特别是其针对稀疏工作负载的高性能表现，在BFS领域仍相对未被充分探索。在本文中，我们提出了代数绕过BFS算法（ALBBA），一种针对长向量架构的新型高效代数BFS实现。ALBBA采用定制化的SELL-C-6数据结构变体，以充分利用SIMD能力。通过集成一种友好的向量化方法与两级绕过策略，我们提升了稀疏矩阵-稀疏向量乘法（SpMSpV）和稀疏矩阵-稠密向量乘法（SpMV）算法的性能，这些对于代数BFS操作至关重要。我们进一步引入合并原语，并为每次迭代采用高效的选取方法。我们在NEC VE20B处理器上的实验表明，ALBBA相较于在NVIDIA H100上运行的Enterprise、GraphBLAST和Gunrock，分别实现了3.91倍、2.88倍和1.46倍的平均加速比。
Keyword:
Breadth first search
Sparse matrix-sparse vector multiplication
Sparse matrix-dense vector multiplication
Vector architecture
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
P
IF:
2.1
论文数:
19
被引数:
0
机构
引用论文
Improving Parallelism of Breadth First Search (BFS) Algorithm for Accelerated Performance on GPUs
.png){kind=icon}
PREAI
分享收藏分享收藏Performance Evaluation of a Next-Generation SX-Aurora TSUBASA Vector Supercomputer下一代SX-Aurora TSUBASA向量超级计算机的性能评估
PREAI
分享收藏Scalable Irregular Parallelism with GPUs: Getting CPUs Out of the Way基于GPU的可扩展不规则并行计算：让CPU退出核心处理
OAAI
OAAI分享收藏
查看更多内容