- Rating
- 3
- Confidence
- 2
- Informativeness
- 3(+1)
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper presents a memory-aware and workload-aware partitioning method for GNN training on GPUs. The main motivation lies in the imbalance in memory-access workloads. Due to the imbalance of node degrees, some nodes will access memory much more frequently than others, leading to straggler effects. The authors present two levels of optimization. The first is a scheduling-level one, which partitions all nodes into bins and work concurrently on the GPU. In each bin, nodes are ordered according to workloads. The second is a kernel-level one that accelerates kernel memory access, including staging, wide memory access, bank conflict avoidance, etc.
The authors experiment with 16 real-world graphs with different properties to show the improvements of the proposed method on attention kernels, where each individual technique achieves positive improvements where it should, in a well-interpreted manner. The authors also implement the proposed methods as general primitives that support a wide range of GNNs and outperform current open-source implementations like DGL.
Critical strengths
Overall, I find the paper to be technically sound, well-motivated, and well-written.
-
This paper is well-written and easy to follow. As someone who is not very familiar with GPU kernels, I find the presentation to be sufficiently clear for me to follow. Each design point is well-motivated by observed facts (which are easy to follow too).
-
The techiniques are used in a way that is simple and clearly addresses each observed weakness. The main motivation of this paper is that the IO-based workloads are highly imbalanced in GNN training, and the techniques are designed to address that: binning, largest workload first, concurrency, further paralllelizing the heavy bin. Further, the proposed kernel-level optimizations are designed to help in cases where the workloads of each edge/the whole graph become too large. The designs are easy to follow.
-
The experimental results are extensive and, more importantly, coincide well with what the techniques expect. I briefly checked the correlations between the improvements of each technique and how it is supposed to, and they align well. For example, for bucketing, it should work where the tail workload is heaviest, and async mainly works on extremely large graphs (larger than L2). This good alignment enhances the technical soundness of the paper.
Critical weaknesses
-
How the optimized g-SPMM and g-SDDMM dominate training time is unknown/not reported in the paper. The authors motivate the paper based on model training, but only report kernel-level speedups. To remedy this, the authors can report some (not necessarily all) end-to-end training speedups, or show a decomposition of the end-to-end training time (this can show how much time the attention kernels occupy, and deduce the end-to-end speedups).
-
Scope is slightly limited --- but not much. I specifically have two additional scenarios where the authors can discuss. The first is sampling techniques --- e.g. neighbor sampling, subgraph sampling, etc. In this case (which may be the norm for further large graphs), will the improvements of this paper diminish? The second is about distributed GNN training on multiple GPUs or nodes (e.g. where the graph is larger than ogbn-products), where the bottleneck may lie in communication rather than memory access. It is not a big scope limitation but the authors can briefly discuss them.
-
One minor question on the design of bucketing --- I suppose that degree ordering should have something to do with "the imbalance within a bucket". In this case, is it possible to spawn even more buckets, instead of scheduling within an bucket?
Questions for authors
See weaknesses 1-3.
6 comments
Authors' Response Part 2/3
2.1 Scope is slightly limited --- but not much. I specifically have two additional scenarios where the authors can discuss. The first is sampling techniques --- e.g. neighbor sampling, subgraph sampling, etc. In this case (which may be the norm for further large graphs), will the improvements of this paper diminish?
The improvements become smaller but remain substantial. With neighbor sampling, our implementation is still faster than the fastest DGL sampling mode by on H100 and on A100 in the median, and by up to for deeper models, while DGL runs out of memory in the deepest setting on the two largest graphs. We provide full details in General Response [GR1]. When every node takes its full neighborhood, the speedups are larger, up to , and DGL runs out of memory in 18 of 24 settings, as we show in General Response [GR2].
Subgraph sampling methods such as GraphSAINT [1] and Cluster-GCN [2] train on induced subgraphs, which our kernels process exactly like full graphs, so the full-graph results of General Response [GR3] apply to each such subgraph.
We also checked whether degree-aware partitioning remains effective on sampled subgraphs. With a fixed fanout, sampling caps the in-degree of every destination node, so the forward pass of a mini-batch has almost no load imbalance: in a block sampled with fanouts 15-10-5, the highest-degree node has at most 2.6 times more neighbors than the average node, against up to 42K times in the full graphs. The imbalance moves to the backward pass, where a hub node sampled by many destinations becomes one long row of the transposed block, 188 to 400 times longer than the average row on avazu-ctr, twitch-views and the web graphs. Applying the heavy bucket to the backward pass makes the backward kernels - faster in 11 of 12 such settings with fanouts 25 and 50, and has no effect on the low-skew ogbn-products. With full neighborhoods, the batches keep the skew of the graph, and bucketing makes training - faster on the web graphs than the same kernels without it. The improvements of the paper therefore carry over to sampled training as long as the partitioning is applied where the sampled block is skewed. Table 6 in our response to Reviewer jfM5 gives the per-graph numbers.
[1] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. GraphSAINT: Graph Sampling Based Inductive Learning Method.
[2] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks.
*2.2 The second is about distributed GNN training on multiple GPUs or nodes (e.g. where the graph is larger than ogbn-products), where the bottleneck may lie in communication rather than memory access. It is not a big scope limitation but the authors can briefly discuss them.
We did not run multi-GPU experiments, but our kernels apply to distributed training without modification. Distributed full-graph training systems usually split the graph into partitions, and each device runs the same layer kernels on its local partition as on a single GPU. For instance, one can use a vertex cut: every edge belongs to exactly one partition, the vertices on the cut are replicated on every partition that contains their edges, and the partial aggregates of the replicas are combined by communication, which is also how their gradients are accumulated in the backward pass [3]. The aggregation inside each partition is exactly the g-SPMM and g-SDDMM work that our kernels accelerate. Communication is therefore performed outside the kernels and remains orthogonal to the computation we optimize. Moreover, faster local computation leaves more time to overlap it where it becomes the bottleneck.
Our memory savings are also useful in this setting. A smaller per-GPU footprint allows larger partitions per GPU, and therefore fewer GPUs and fewer cut edges, or leaves more memory for communication buffers and feature caches. For example, our fused kernel trains GATv2 on the full ogbn-products graph on a single 80 GB GPU, while DGL fails with a single allocation of 120 GiB, as described in General Response [GR3].
[3] Vasimuddin Md, Sanchit Misra, Guixiang Ma, Ramanarayan Mohanty, Evangelos Georganas, Alexander Heinecke, Dhiraj Kalamkar, Nesreen K. Ahmed, and Sasikanth Avancha. DistGNN: Scalable Distributed Training for Large-Scale Graph Neural Networks.
Authors' Response Part 3/3
3. One minor question on the design of bucketing --- I suppose that degree ordering should have something to do with "the imbalance within a bucket". In this case, is it possible to spawn even more buckets, instead of scheduling within a bucket?
Thank you for suggesting this experiment. Finer buckets reduce the variation of degrees within each bucket, while degree ordering starts the highest-degree nodes first and shortens the tail of the launch. More buckets are harder to implement, however: each degree range needs its own work decomposition and warp allocation, and every extra bucket adds a kernel launch.
To evaluate the idea, we extended the SM-utilization simulator from Section 4.3 to more than two buckets, with costs calibrated on the A100 for the GATv2 forward pass (fp32, one head of width 128), and ran it on all 16 graphs of the paper. We varied three things:
- The total number of buckets , including the heavy ones, is 2, 4 or 8.
- The bucket boundaries follow one of three policies.
quantilekeeps the heavy bucket of the paper (nodes above the 99th percentile of degree) and splits the light nodes into buckets of roughly equal size.logkeeps the same heavy bucket and splits the light degree range into intervals equally spaced in , where is the node degree.tailalso splits the heavy nodes, with finer quantiles towards the highest degrees, e.g. at the 90th, 99th and 99.9th percentiles for . Nodes of equal degree always share a bucket. - Degree ordering is on or off, and the buckets are launched either sequentially on one CUDA stream, as in TurboGNN, or concurrently on separate streams with the heaviest one first, as introduced in Section 3.1.
The per-node work and the resources of each bucket stay fixed, so only the partitioning changes. For each graph, we report in Table 8 the best of the 6 configurations with or and the effect of ordering with .
| graph | concurrent: more buckets | concurrent: ordering | sequential: more buckets | sequential: ordering |
|---|---|---|---|---|
artnet-exp | +7.09 | +7.27 | -1.61 | +10.22 |
avazu-ctr | 0.00 | 0.00 | -0.13 | +0.71 |
citeseer | 0.00 | 0.00 | -0.64 | +0.85 |
city-reviews | 0.00 | 0.00 | -0.04 | +1.51 |
city-roads-L | +0.12 | +0.12 | 0.00 | +0.85 |
city-roads-M | +0.22 | +0.22 | 0.00 | +0.44 |
cora | 0.00 | 0.00 | -0.49 | +0.70 |
hm-categories | -10.15 | 0.00 | -1.72 | +0.63 |
ogbn-arxiv | 0.00 | 0.00 | -0.01 | +0.41 |
ogbn-products | +0.19 | +0.19 | -0.02 | +3.40 |
ogbn-proteins | +1.04 | +1.30 | -0.22 | +4.93 |
pokec-regions | +0.05 | +0.05 | -0.04 | +0.05 |
pubmed | +2.74 | +2.74 | -0.34 | +3.92 |
tolokers-2 | 0.00 | 0.00 | -0.61 | +15.94 |
twitch-views | +4.99 | +4.99 | -0.08 | +3.33 |
web-fraud | 0.00 | 0.00 | 0.00 | 0.00 |
Table 8: Simulated runtime reduction in % relative to without ordering, for the GATv2 forward pass on A100, so a positive value means faster. "More buckets" is the best of the 6 configurations with or without ordering, and "ordering" is the effect of degree ordering with .
Thus, the results answer your question directly. With concurrent launch, more buckets help on some graphs, by up to on artnet-exp and on twitch-views, but every configuration slows down hm-categories, by -. Ordering with only two buckets gives the same or a larger gain on every graph, and once ordering is enabled, additional buckets improve the runtime by less than . With sequential launch, additional buckets never help and the worst configurations more than double the runtime, while ordering alone gains up to on tolokers-2. No tested configuration with more buckets and no ordering is faster than two ordered buckets. Degree ordering therefore already captures the benefit that finer buckets would bring without extra kernel launches.
The table also shows where degree ordering matters. Namely, on the graphs with the strongest hubs, such as web-fraud, ogbn-arxiv and avazu-ctr, neither ordering nor more buckets changes the runtime with concurrent launch, because the heavy bucket already spreads the hub neighborhoods over many parallel workloads, so the thread blocks are close to uniform in size. Degree-aware partitioning thus subsumes ordering on strongly skewed graphs, and ordering pays mainly on graphs with a moderate tail, such as artnet-exp, twitch-views and pubmed.
We acknowledge that the simulations omit the cost of partitioning, sorting and extra kernel launches, which all count against more buckets, and do not retune per-bucket resources. This is also the strength of the simulator: it evaluates a design such as finer bucketing directly from the degree distribution of each graph, without developing a specialized kernel for every degree range. We will add this analysis to the revised paper.
Authors' Response Part 1/3
Thank you for your insightful review and for finding the paper technically sound, well-motivated and well-written. We address your questions and concerns below.
Thank you for this suggestion. We now report both the decomposition and the end-to-end speedups. To decompose the training time, we profiled a full-graph training step of a GATv2 model implemented in three ways: with DGL's primitives, with our g-SDDMM, edge_softmax and g-SPMM primitives, and with our fused GATv2 kernel. We present the breakdown in Table 3 in General Response [GR4]. In DGL's training step on
ogbn-arxiv, which takes 117 ms on H100, g-SPMM takes 26.6 ms in the forward and 32.3 ms in the backward pass, g-SDDMM takes 6.7 and 3.7 ms, and the per-edge elementwise operations between them take 9.6 and 26.9 ms. Together, these operators account for about 90% of the step, so the attention kernels dominate training time, as you expected.This decomposition also explains the end-to-end speedups. Replacing only DGL's primitives with ours makes the step 1.43× faster. Our fused GATv2 kernel replaces all of them with 5.5 ms of forward and 14.3 ms of backward kernel time, which makes the step 4.27× faster than DGL (3.44× on A100) and uses 3.7× less energy. Nsight Compute shows why DGL is slow: its edge_softmax reductions run at 11% achieved occupancy and 0.5% SM throughput, because individual threads wait on high-degree rows. This is the imbalance our degree-aware partitioning removes. End to end, full-graph training is 4.4× faster on H100 and 3.6× faster on A100 on the graph where DGL fits, and DGL runs out of memory on the other 11 graphs, as described in General Response [GR3]. With neighbor sampling, the median speedup is 1.62× on H100 and 2.50× on A100, as described in General Response [GR1]. We will add this decomposition and the end-to-end results to the revised paper.