GPU Semiring Primitives for Sparse Neighborhood Methods

Corey J. Nolet, Divye Gala, Edward Raff, Joe Eaton, Brad Rees +2 more
4/13/2021
cs.LGcs.DCmath.RA

Official code: NVIDIA/cuml (5,306 stars, Apache-2.0, last commit 2026-10-20). 1 more implementation below.

Abstract

High-performance primitives for mathematical operations on sparse vectors must deal with the challenges of skewed degree distributions and limits on memory consumption that are typically not issues in dense operations. We demonstrate that a sparse semiring primitive can be flexible enough to support a wide range of critical distance measures while maintaining performance and memory efficiency on the GPU. We further show that this primitive is a foundational component for enabling many neighborhood-based information retrieval and machine learning algorithms to accept sparse input. To our knowledge, this is the first work aiming to unify the computation of several critical distance measures on the GPU under a single flexible design paradigm and we hope that it provides a good baseline for future research in this area. Our implementation is fully open source and publicly available as part of the RAFT library of GPU-accelerated machine learning primitives (https://github.com/rapidsai/raft).

View on arXivView PDF

Code Implementations(2)

NVIDIA/cumlOfficial100%
Apache-2.0

NVIDIA cuML: GPU-Accelerated Machine Learning

5,306688C++, CudaOct 11, 20184 days agoApache-2.0
cudagpumachine-learningmachine-learning-algorithmsnvidia
NVIDIA/raftOfficial100%
Apache-2.0

RAFT contains fundamental widely-used algorithms and primitives for machine learning and information retrieval. The algorithms are CUDA-accelerated and form building blocks for more easily writing high performance applications.

1,047254C, C++Jun 13, 20194 days agoApache-2.0
annsbuilding-blocksclusteringcudadistance+15 more

Similar Papers

ReLU$^2$ Wins: Discovering Efficient Activation Functions for Sparse LLMs

77% match2024

R-Sparse: Rank-Aware Activation Sparsity for Efficient LLM Inference

77% match1 repo212025

The Sparsity Roofline: Understanding the Hardware Limits of Sparse Neural Networks

77% match2023

Full Attention Strikes Back: Transferring Full Attention into Sparse within Hundred Training Steps

77% match2026

Sparsity-Aware Hardware-Software Co-Design of Spiking Neural Networks: An Overview

77% match2024

SparseByteNN: A Novel Mobile Inference Acceleration Framework Based on Fine-Grained Group Sparsity

77% match2023

Cite this paper

@article{nolet2021semiring,
  title  = {GPU Semiring Primitives for Sparse Neighborhood Methods},
  author = {Corey J. Nolet and Divye Gala and Edward Raff and Joe Eaton and Brad Rees and John Zedlewski and Tim Oates},
  year   = {2021},
  eprint = {2104.06357},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/2104.06357}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2104.06357.svg)](https://codeofpaper.com/paper/2104.06357)

Discussion