Pasar al contenido principal

COMPUTER SCIENCES: RESEARCH ON NOVEL ARCHITECTURES AND THEIR IMPLEMENTATION, PROGRAMMING MODELS AND PERFORMANCE UNDERSTANDING AND OTHER COMPONENTS IN THE SOFTWARE STACK, INCLUDING COMPILERS AND RESOURCE MANAGEMENT FOR PERFORMANCE AND ENERGY EFFICIENCY II

PRE2022-104335

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
Programa Programa Estatal para Desarrollar, Atraer y Retener Talento
Subprograma Subprograma Estatal de Formación
Convocatoria Contratos Predoctorales
Año convocatoria 2022
Plan Estatal 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario BARCELONA SUPERCOMPUTING CENTER CENTRO NACIONAL DE SUPERCOMPUTACION

Resultados relacionados

Resultados totales (Incluyendo duplicados): 1
Encontrada(s) 1 página(s)

Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

BerryBees: Breadth first search by bit-tensor-cores

  • Niu, Yuyao
  • Casas, Marc
Breadth First Search (BFS) plays a key role in computational science, networking, and artificial intelligence applications. Although the BFS approach has been extensively studied, particularly in its direction-optimized form, existing implementations still present three main issues: (1) high memory footprint; (2) the under-realized lightweight representations using bitmaps; and (3) the underuse of modern hardware such as Tensor Cores Units (TCUs). In this paper, we propose BerryBees, an efficient algebraic BFS algorithm that leverages the Matrix Multiply-Accumulate (MMA) instructions of TCUs. The novelty of BerryBees lies in (1) the Binarized Row Slice (BRS) format, which encodes the adjacency matrix by using bitmaps to represent non-empty row segments; and (2) a warp-level algorithm that leverages TCUs for accelerating both SpMV and SpMSpV operations for enhanced BFS performance. The experimental results on three latest NVIDIA GPUs show that BerryBees outperforms five state-of-the-art BFS methods: GAP, Gunrock, Enterprise, GSWITCH, and GraphBLAST, and delivers average speedups of 1.42 ×, 1.97×, 5.05×, 1.24×, and 3.74× (up to 9.99×, 13.66×, 114.07×, 13.97×, and 24.74×), respectively., This work has been partially supported by the European HiPEAC Network of Excellence, the Spanish Ministry of Science and Innovation MCIN/AEI/10.13039/501100011033 (contracts PID2019-107255GB-C21 and PID2019-105660RBC22), and the Generalitat de Catalunya (contract 2021-SGR00864). Yuyao Niu is supported by Grant PRE2022-104335, funded by MICIU/AEI/10.13039/501100011033, and by the "ESF+" Grant CEX2021-001148-S-20-2, funded by MICIU/AEI/10.13039/501100011033., Peer Reviewed, Postprint (author's final draft)