PaperlayerView exact revision on arXiv

Source-linked AI summary

Enumeration-based Triangle Counting on GPUs

Sayan Ghosh

arXiv:2610.29988v1cs.DC

TL;DR

Irregular distance-2 work and GPU thread-block imbalance complicate triangle counting at scale. The paper presents an exact distributed-memory GPU approach using wedge enumeration and single-counting rules. It reports 2–100× improvement over vendor-optimized cuGraph for varied graphs.

  • Problem

    Partitioned-graph triangle counting must manage irregular distance-2 workloads that challenge uniform GPU thread-block execution.

    Source: §I · p. 1

  • Method

    The approach fuses filtering and enumeration over edge-list batches, applies precedence rules for single counting, and adapts the work to distributed GPU systems.

    Source: §I · p. 2, §II · p. 2

  • Results

    2–100× improvement over state-of-the-art vendor-optimized cuGraph is reported for a variety of graphs.

    Source: §IV · p. 10

  • Takeaways & Limitations

    The proposed approach is reported as performant across scaling domains and diverse inputs without changing the core graph data structure or partitioning.

    Source: §I · p. 2

Abstract

from arXiv · show

Subgraph enumeration in partitioned graphs across distributed-memory systems is beset with challenges in balancing data movement with the local computation. Especially, counting the number of triangles induced by the closed wedges (i.e., length-3 cycles) is a measure of connectedness in a graph, but often limited by the significant search space caused by open wedges or length-2 paths (usually greater than the number of edges in a graph), which must be inspected to assess whether a particular wedge is closed. To mitigate triangle counting on massive graphs, distributed-memory partitioned-graph approaches are viable (i.e., assessing closed wedges independently within a partition), but load imbalance due to arbitrary communication can overshadow any gains from enhanced concurrency, owing to the inherent lack of structure in regular graphs. In this paper, we discuss a distributed-memory exact graph triangle counting implementation, and assess its performance over billion-edge real-world graphs on contemporary scale-out and scale-up based NVIDIA GPU platforms (considering NVIDIA ``Ampere'' and ``Hopper'' architectures), depicting a scalability spectrum of multiple orders of magnitude. Comparisons with existing state-of-the-art approaches demonstrates up to 10$\times$ improvements relative to distributed-memory CPU baseline, 2-100$\times$ over single-GPU vendor-optimized NVIDIA RAPIDS cuGraph and 10-60\% over multi-GPU $G^2$Miner, in terms of end-to-end execution times.

I. INTRODUCTION

Exact triangle counting must balance local computation against long-latency data movement and irregular distance-2 work. The paper adapts wedge-based enumeration for distributed GPU systems and evaluates the approach across scaling domains and diverse inputs.

I. INTRODUCTION

  • Distance-2 computations and irregular workloads make triangle counting difficult to balance against data movement, unlike BFS’s distance-1 work and fixed-size frontiers.GPU concurrency can widen the gap between processing and data access, while general graphs challenge uniform thread-block execution.Source: §I · p. 1
  • Triangle counting filters candidate wedges and then checks whether they close, using methods such as set intersections of neighbor lists or matrix operations.For candidate edge {u, v}, the number of triangles can be found from N(u) ∩ N(v).Source: §I · pp. 1–2, Figure 1 · p. 1
  • The approach fuses filtering and enumeration over batches of edge lists, assigning wedge searches across GPU threads to reduce enumerations per thread relative to CPUs.It derives from TriC’s search-per-wedge approach,.Source: §I · p. 2
  • The work adopts selected exact-counting strategies without changing the core graph data structure or partitioning, then evaluates GPU implementations across scaling domains and diverse inputs.The stated assessments include Perlmutter, Polaris, and DGX systems with A100 and H100 GPUs.Source: §I · p. 2

II. DISTRIBUTED-MEMORY METHODOLOGY

The methodology partitions undirected graphs across processing elements, then uses ordering rules to count each triangle once. An iterative buffered MPI process handles local and remote edge lookups.

II. DISTRIBUTED-MEMORY METHODOLOGY

  • Vertex-based partitioning balances edge counts across processing elements, while an ordering rule assigns each triangle to one valid path for single counting.A parent-to-child path is valid when |parent| < |child|; the graph’s local CSR partitions are copied to GPUs before counting.Source: §II · p. 2

A. Distributed-memory implementation

2) Process incoming messages and test completion:

Incoming edge pairs are checked against locally owned neighborhoods, and a nonblocking barrier tests for global completion. The implementation divides work between host-side communication preparation and GPU-side lookup processing, with GPU kernels shaped to reduce nested-loop overhead.

2) Process incoming messages and test completion:

  • Received prospective edge pairs are searched in locally owned neighborhoods; a nonblocking barrier tests completion after outstanding message processing ends.The algorithm preposts receives and reuses buffers and MPI request handles as operations complete.Source: 2) Process incoming messages and test… · p. 3

3) CPU vs. GPU version:

  • The GPU version prepares outgoing messages on the host and processes received edge lookups on the GPU; the CPU version uses OpenMP for both local counting and incoming-data processing.Because messages are sent from the host and processed on the device, the implementation cannot use GPU-aware MPI.Source: 3) CPU vs. GPU version · pp. 3–4
  • GPU communication buffers compress common-parent edge pairs, but the GPU version tolerates redundancy to keep local processing parallelizable.The CPU version also tests lossless buffer compression, reaching over 90% space efficiency.Source: 3) CPU vs. GPU version · p. 4

B. GPU methods for triangle counting

  • The GPU design flattens loops and masks edges to reduce tile-level divergence and improve memory coalescing, though leftover thread blocks can create partial waves and lower throughput.The masked-edge kernel maps work across thread tiles, with threads scanning distance-2 neighborhoods.Source: B. GPU methods for triangle counting · p. 4

1) Masked-edge based local/independent counting:

Masked-edge counting maps local neighborhood scans to GPU thread tiles. The design uses shared and register storage and warp collectives, while acknowledging a trade-off between load balance and kernel overhead.

1) Masked-edge based local/independent counting:

  • The masked-edge kernel counts local triangles by scanning each owned vertex neighborhood, using shared memory, registers, and warp-level collectives to reduce global accesses and coordinate work.Irregular neighborhood sizes can leave thread tiles idle and reduce throughput.Source: 1) Masked-edge based local/independent… · p. 4
  • Splitting distance-1 and distance-2 neighborhoods into separate kernels may improve load balance but can increase execution time and launch overhead.Source: 1) Masked-edge based local/independent… · p. 5
  • Figure 4 depicts grid-, block-, and tile-level operations for masked-edge and split-edge triangle counting.Source: Figure 4 · p. 5

2) Split-edge based receiver-side counting:

The split-edge receiver kernel processes incoming edges concurrently over CUDA streams, while GPU IPC enables processes on the same node to access shared GPU memory without explicit intra-node data movement.

2) Split-edge based receiver-side counting:

  • The split-edge receiver kernel assigns incoming masked edges across GPU grid-blocks and distance-2 neighborhood work across thread tiles, processing incoming edges concurrently over CUDA streams.It roughly corresponds to the local masked-edge kernel’s loop nest, but processes incoming edges.Source: 2) Split-edge based receiver-side… · p. 5

3) GPU Inter-Process Communication:

  • GPU IPC shares GPU memory pointers between processes on a node, enabling peer-to-peer access without explicit intra-node data movement.The implementation performs a one-time all-gather to share IPC handles within the node.Source: 3) GPU Inter-Process Communication · p. 5
  • IPC variants separate edges into local and remote vertex neighborhoods; MPI+IPC also uses split-edge kernels for incoming edges, with work grids shaped by the respective vertex-set volumes.Differences in graph structure, partitions, and working sets can produce disparities in concurrent thread-block counts.Source: 3) GPU Inter-Process Communication · p. 5

1) Datasets:

The evaluation uses real-world citation, social, and web graphs on three GPU platforms. It also describes how performance is measured and compares communication-avoiding and hybrid implementation variants.

1) Datasets:

  • The evaluated real-world graphs span citation networks, social networks, and large-scale web graphs from SuiteSparse and GraphChallenge.Table I lists the graphs used in single- and multi-node GPU evaluations.Source: 1) Datasets · p. 5, Table I · p. 5

2) Platforms:

  • The study evaluates on Perlmutter, Polaris, and single-node DGX A100/H100 platforms, with A100 GPU nodes on the two supercomputers and 8-GPU DGX systems.The platforms differ in memory, interconnect, and system configuration; DGX H100 uses fourth-generation NVLink.Source: 2) Platforms · pp. 5–6

3) Results interpretation:

  • Reported total time includes local counting, communication-buffer preparation and initiation, incoming communication processing, and local scans over received vertices, but excludes graph loading and CSR construction.Graph loading and CSR construction account for about 1–5% of total time.Source: 3) Results interpretation · p. 6

4) Variants:

  • The variants use lossless compression for CPU communication and IPC for GPU communication, while a hybrid variant runs CPUs and GPUs together.GPU-only distributed implementations can have non-trivial load imbalance despite better overall performance; hybrid execution can reduce local counting costs but increase communication overhead.Source: 4) Variants · p. 6

B. Scale-Out CPU evaluations

The evaluation compares CPU and GPU distributed-memory implementations and examines compression, IPC, and hybrid variants. GPU variants outperform CPU variants across diverse inputs, while the benefits of communication strategies vary with graph and configuration.

B. Scale-Out CPU evaluations

  • An order of magnitude improvement in end-to-end times and at least 50% less load imbalance: the distributed-memory CPU implementation outperforms TriC on friendster and orkut at 16–128 Perlmutter nodes.TriC’s triple-counting and limited wedge filtering increase load imbalance and communication volumes.Source: Figure 5 · p. 6, B. Scale-Out CPU evaluations · p. 6
  • 20–50% higher execution times: LZ4 compression saves more than 90% of communication-buffer space but does not amortize its costs under irregular communication.The compression factors are 8:1–55:1; compression memory overhead also requires smaller buffers than in the CPU-baseline evaluations.Source: Figure 6 · p. 6

C. Scale-Out/Up GPU evaluations

  • 3–20× faster execution: GPU variants outperform CPU variants across diverse inputs on Perlmutter.The comparison keeps compute-node counts consistent while using different communication-buffer sizes and processes per node.Source: Figure 8 · p. 7, C. Scale-Out/Up GPU evaluations · p. 7
  • GPU variants have local counting costs on par with CPU variants but surpass them in receiver-side processing over concurrent CUDA streams.Lower GPU processes-per-node counts allow larger per-process buffers and fewer kernel invocations, while load imbalance remains non-trivial.Source: C. Scale-Out/Up GPU evaluations · p. 7, Figure 9 · p. 7
  • 10–80% better performance: MPI+IPC improves over the MPI-only GPU baseline on Perlmutter and Polaris, though some cases show 1–10% slowdown on Perlmutter and 10–60% lower performance on Polaris.Node-local enumeration is typically about 0.1–10% of total vertices, but can raise local computation costs in exceptions; Fig. 10 and Fig. 11 show node-local access volumes.Source: Figure 10 · p. 7, Figure 11 · p. 7, C. Scale-Out/Up GPU evaluations · pp. 7–8
  • 3–35% better performance: the hybrid CPU/GPU variant on Polaris outperforms the baseline MPI-GPU variant, with 24–35% gains on scale-free graphs.The hybrid uses PPN=16 (4 GPUs plus 12 CPUs) and 2× smaller communication buffers; scale-free gains are 10–20% over MPI+IPC.Source: Figure 12 · p. 8, C. Scale-Out/Up GPU evaluations · p. 8

D. Single-node evaluations

The single-node evaluations compare MPI and IPC on DGX A100/H100 systems, including large real-world graphs. Pure IPC is reported to outperform MPI substantially, with performance also varying by GPU architecture.

D. Single-node evaluations

  • Multiple orders of magnitude faster: the IPC variant outperforms MPI on irregular scale-free graphs, and H100 platforms deliver 2× better performance than A100 platforms.Fig. 13 covers Graph500 Kronecker graphs at scales 20–25 on a single node.Source: Figure 13 · p. 8, D. Single-node evaluations · p. 8
  • 20–30% better performance overall: DGX H100’s faster fourth-generation NVLink improves results relative to the other evaluated DGX platforms.For massive real-world graphs, many MPI variants have major startup issues associated with requiring more nodes and high intermediate-data communication.Source: Figure 14 · p. 8, D. Single-node evaluations · p. 8
  • Pure IPC dominates performance by bypassing host-initiated buffering and network communication, while local counting benefits from increasing the number of GPUs.Table II compares execution times for MPI-IPC with local/remote breakup on Polaris and pure IPC on DGX A100-40GB.Source: Table II · p. 8, D. Single-node evaluations · p. 8

E. Workload Characteristics

Triangle counting is compute-bound despite zero floating-point operations, but irregular memory access and uneven warp durations limit instruction throughput. On scale20, partial thread-block waves consume 20–35% of execution time, illustrating the workload’s tail effect.

E. Workload Characteristics

  • Distributed-memory communication is the apparent bottleneck, while zero-copy IPC shifts attention to irregular-workload stalls and device-generation differences.The analysis deliberately uses scale20, whose edge-distribution standard deviation across 8 GPUs exceeds 1000.Source: E. Workload Characteristics · p. 8

1) Tail effect:

  • Despite zero FLOPs, average IPC exceeds 2 and ALU utilization exceeds 75%, making triangle counting compute-bound.Irregular memory accesses and data dependencies limit warp readiness; only 2–5 warps materialize per cycle despite allocating 12 of 16 possible warps.Source: 1) Tail effect · pp. 8–9, Figure 15 · p. 9
  • 20–35% of scale20 execution time is spent in partial waves of 3–635 thread blocks, leaving achieved occupancy at about 60% versus 75% theoretical occupancy.The irregular remote-edge counts produce grids with 1–3 full waves and a partial wave; register allocation can help in specific smaller-input cases but is difficult to balance against spillage across arbitrary graphs.Source: 1) Tail effect · p. 9

2) A100 vs. H100:

H100 outperforms A100 despite lower IPC, with greater per-SM shared-memory capacity enabling better thread-block compaction and fewer partial blocks. H100 clusters further improve execution for some graphs, but gains vary with graph structure and cluster count.

2) A100 vs. H100:

  • 2× better performance on H100 than A100 accompanies 2–4× fewer partial blocks and about 20% better compaction, despite A100’s up to 10% higher IPC.H100’s per-SM shared-memory capacity is about 40% larger, allowing more thread-block compaction; Fig. 16 compares waves and partial blocks across the GPUs.Source: 2) A100 vs. H100 · p. 9, Figure 16 · p. 9
  • Up to 30% better shared-memory throughput appears on H100 for kernels with the fewest partial blocks.On GPU #7, a 769-block launch leaves 122 partial blocks on A100 and none on H100; Fig. 17 reports shared-memory load/store wavefronts per instruction.Source: 2) A100 vs. H100 · p. 9, Figure 17 · p. 9

3) Further optimizations on H100:

  • 2-cluster execution improves times by up to 40% for graphs with relatively high node-local enumerations and around 12% for scale-free graphs in scale 18–25.Fig. 20 compares default and cluster performance ranges; increasing cluster count beyond two can increase partial waves, while DSMEM volume is 2× between two and four or eight clusters.Source: Figure 20 · p. 10, 3) Further optimizations on H100 · p. 10
  • Clusters reduce SM-crossbar-routed memory requests by about 2–5× by localizing inter-block traffic within a cluster.Fig. 19b compares average requests routed to the regional L2 cache/memory subsystem for default and cluster configurations.Source: 3) Further optimizations on H100 · p. 10, Figure 19 · p. 10

IV. COMPARISONS WITH GPU GRAPH FRAMEWORKS

The implementation is compared with cuGraph, TRUST, and GraphMiner across single- and multi-GPU settings. It reports a 2–100× advantage over cuGraph and better H100 performance than GraphMiner, while comparison conditions and scheduling costs qualify the results.

Single GPU evaluations

  • TRUST’s reported end-to-end times exclude relevant allocation and copy times, and its 32-bit CSR representation reduces memory-transfer overhead relative to the 64-bit representation used by this implementation and cuGraph.Fig. 23 compares host-device and device-device transfers; cuGraph has nontrivial device-device transfers from intermediate copies, while this implementation and TRUST have none.Source: §IV · pp. 10–11, Figure 23 · p. 11
  • 2–100× improvement over vendor-optimized cuGraph is reported across varied graphs, while the implementation’s kernel times are competitive with TRUST on most degree-balanced graphs.Fig. 21 compares single-GPU execution times; Fig. 22 compares kernel times.Source: §IV · p. 10, Figure 21 · p. 11, Figure 22 · p. 11

Multi-GPU evaluations

  • On DGX A100, GraphMiner is 20–40% faster on two of three graphs, while this implementation is 10–60% faster on H100 in all scenarios.Fig. 24 compares GraphMiner with the baseline IPC implementation.Source: Figure 24 · p. 11, §IV · p. 11
  • DAG creation takes about 10–80% of total execution time, with the remainder divided among edge-list generation, device copy, and kernel execution.The paper notes potential improvement of greater than 2× between GPU architectures with enhanced memory bandwidths.Source: §IV · p. 11

V. CONCLUDING REMARKS

The conclusion frames GPU triangle counting around edge-enumeration tasks and the tradeoff between faster local processing and data movement. IPC outperforms MPI-GPU variants, while distributed-memory variants can adapt to larger, sparser inputs when graph-induced load imbalance is alleviated.

V. CONCLUDING REMARKS

  • The paper examines hybrid CPU/GPU and zero-copy options by decomposing triangle counting into parallel edge-enumeration tasks.These options address data-movement costs that are accentuated on GPUs for irregular graph workloads.Source: §V · p. 11
  • IPC outperforms MPI-GPU variants because it has zero intermediate data.The conclusion identifies limiting host operations and intermediate copies as a path toward sustainable performance across GPU generations.Source: §V · p. 11
  • Distributed-memory variants can adapt to larger, sparser inputs when graph-structure-induced load imbalance is alleviated.Source: §V · p. 11
  • Limiting host operations and intermediate copies is presented as a path toward sustainable performance across GPU generations.Source: §V · p. 11
Loading 2610.29988v1…