TriPIM — Exact Triangle Counting on UPMEM Processing-in-Memory for Graph Analytics

Efficient triangle counting remains a fundamental challenge in graph analytics, with applications spanning computational biology, social network analysis, and emerging AI workloads such as Graph Neural Networks (GNNs). As these AI models scale to larger graphs, existing CPU- and GPU-based methods face scalability limits due to memory bottlenecks and limited parallelism. The TriCORE methodology introduced significant improvements with its binary search-driven algorithm, enhancing thread parallelism and memory efficiency on GPUs. This optimization allows TriCORE to outperform existing techniques and handle larger graphs. However, its reliance on multiple graph representations and the inherent limitations of GPU memory capacity can hinder its scalability and practical utility for Exascale graph datasets. We present TriPIM, a novel architectural solution that combines TriCORE’s algorithmic strengths with UPMEM Processing-In- Memory (PIM) technology to overcome graph scalability and memory bandwidth limitations. TriPIM leverages PIM to minimize data movement and accelerate triangle counting computations directly within memory. This integration maintains the algorithmic benefits of TriCORE while extending its applicability to significantly larger graph datasets, overcoming the constraints of traditional CPU- and GPU-based implementations. TriPIM scales triangle counting by partitioning Compressed Sparse Row (CSR) data across multiple UPMEM DIMMs and running TriCORE’s binary search engine independently within each memory partition. Our evaluation demonstrates TriPIM’s superior performance over TriCORE (GPU) and GAP (CPU) benchmarks for Exascale graphs.

• Publication year

  2025

• Venue

  International Symposium on Memory Systems

• Publication date

  2025-10-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/3767110.3767137
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Swift: A Multi-FPGA Framework for Scaling Up Accelerated Graph Analytics

  2024cited by this paper
• Architectural Modeling and Benchmarking for Digital DRAM PIM

  2024cited by this paper
• HiTC: High-Performance Triangle Counting on HBM-Equipped FPGAs Using HLS

  2024cited by this paper
• ECG: Expressing Locality and Prefetching for Optimal Caching in Graph Structures

  2024cited by this paper
• Chapter Eight - Fast exact triangle counting in large graphs using SIMD acceleration

  2023cited by this paper
• System Architecture and Software Stack for GDDR6-AiM

  2022cited by this paper
• FPGA-Based Near-Memory Acceleration of Modern Data-Intensive Applications

  2021cited by this paper
• Aquabolt-XL: Samsung HBM2-PIM with in-memory processing for ML accelerators and beyond

  2021cited by this paper
• Accelerating Triangle Counting on GPU

  2021cited by this paper
• Trust: Triangle Counting Reloaded on GPUs

  2021cited by this paper
• Can graph neural networks count substructures?

  2020cited by this paper
• The true Processing In Memory accelerator

  2019cited by this paper
• Triangle Counting and Truss Decomposition using FPGA

  2018cited by this paper
• Enumerating Trillion Subgraphs On Distributed Systems

  2018cited by this paper
• TriCore: Parallel Triangle Counting on GPUs

  2018influential reference
• TRIÈST

  2017cited by this paper
• Ambit: In-Memory Accelerator for Bulk Bitwise Operations Using Commodity DRAM Technology

  2017cited by this paper
• Exploring optimizations on shared-memory platforms for parallel triangle counting algorithms

  2017cited by this paper
• TRIÈST: Counting Local and Global Triangles in Fully-Dynamic Streams with Fixed Memory Size

  2016cited by this paper
• Multicore triangle computations without tuning

  2015cited by this paper
• The GAP Benchmark Suite

  2015influential reference
• Truss Decomposition in Massive Networks

  2012cited by this paper
• Spectral counting of triangles via element-wise sparsification and triangle-based link recommendation

  2011cited by this paper
• Counting triangles and the curse of the last reducer

  2011cited by this paper
• DOULION: counting triangles in massive graphs with a coin

  2009cited by this paper
• Fast Counting of Triangles in Large Real Networks without Counting: Algorithms and Laws

  2008cited by this paper
• Efficient semi-streaming algorithms for local triangle counting in massive graphs

  2008cited by this paper
• Kronecker Graphs: An Approach to Modeling Networks

  2008cited by this paper
• Main-memory triangle computations for very large (sparse (power-law)) graphs

  2008cited by this paper
• Random graphs

  2006cited by this paper
• Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study

  2005cited by this paper
• Structural Holes and Good Ideas1

  2004cited by this paper
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• Social Capital in the Creation of Human Capital

  1988cited by this paper
• Finding a minimum circuit in a graph

  1977cited by this paper
• Evaluating the Structural Awareness of Large Language Models on Graphs: Can They Count Substructures?

  year unknowncited by this paper
• Collectivedynamicsof ‘ small-world ’ networks

  year unknowncited by this paper

• No citing papers are available for this paper.