Skip to main content

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

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal para Desarrollar, Atraer y Retener Talento
Subprogram Subprograma Estatal de Formación
Call Contratos Predoctorales
Call year 2022
State Plan 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre 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
Publication 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)