Many computations on trees have the same shape: fold information up from the leaves, pass it through internal nodes, and read off an answer at the root. Examples include exact inference in tree-shaped probabilistic models, dynamic programs such as maximum weighted independent set, and evaluating large expression trees. On one CPU this is a simple depth-first pass. On GPUs and GPU clusters it is surprisingly awkward. A tree stored as a sparse matrix is scattered almost at random through memory. The natural parallel schedule, one tree level per step, needs as many global synchronizations as the tree is deep. Theory from massively parallel computation has shown how to cut the number of synchronized communication rounds on trees to logarithmic or even constant. Systems work has separately shown how to make scattered sparse matrices run fast on dense matrix hardware. The two lines have never been combined.
This proposal makes one claim. A single object, a partition of the tree into connected clusters of about $B$ vertices with at most two boundary vertices each, does two jobs at once when $B$ is set to what one GPU thread block can hold in on-chip memory. It is the "round compression" device of parallel algorithms theory: many contraction steps happen locally, and only the tiny cluster summaries take part in global rounds. It is also a free, linear-time reordering that turns the tree's scattered sparsity into dense tiles. With this partition, computing a tree dynamic program becomes about $\log_B n$ global rounds of batched small dense matrix products in the appropriate algebra. The alternatives are about $\log n$ pointer-jumping rounds, or depth-many rounds of sparse matrix–matrix multiplication (SpMM).
Background and what is missing
On the theory side, Massively Parallel Dynamic Programming on Trees splits a tree into components with a constant number of boundary edges. It solves dynamic programs whose per-vertex state is small (the paper calls them poly-log-expressible) in $O(\log n)$ rounds of the MPC model (massively parallel computation: machines with sublinear memory exchanging messages in synchronized rounds). Adaptive Massively Parallel Constant-round Tree Contraction goes further. It contracts trees in $O(1/\varepsilon^3)$ rounds by letting machines make adaptive lookups into a shared distributed hash table within a round, which is the AMPC model. Both papers supply the method we reuse, the bounded-boundary decomposition and rake/compress contraction. Both also treat a round as an abstract unit and a lookup as uniformly cheap. The file itself flags this as unresolved: whether AMPC's constant-round advantage survives once remote lookups cost real network latency.
On the systems side, Sputnik and SMaT show that unstructured sparse matrix products can beat dense cuBLAS. Sputnik breaks even at 71% sparsity with tiling and aligned vector loads. SMaT breaks even at 78% by using Jaccard-similarity row reordering to pack nonzeros into 16×8 blocks for Tensor Cores. These papers motivate the proposal and also constrain it. SMaT's reordering is an expensive preprocessing step that is only worth paying for static matrices. A tree being contracted changes shape every phase, and a tree adjacency matrix has sparsity $1 - O(1/n)$, far outside the moderate regime these kernels target. Sparsity-Aware Communication for Distributed GNN Training supplies the distributed-systems lesson. On irregular graphs it pays to send only the entries the neighbors need and to balance the maximum per-process communication volume. It optimizes volume per epoch, not the number of rounds, and it does not exploit tree structure.
No existing work treats the tree's own decomposition as the sparse reordering. None measures whether the round savings promised by MPC and AMPC appear as wall-clock gains on real accelerators.
Core Claim
Consider a tree dynamic program whose per-vertex state has $K$ entries. Compressing a path of degree-2 vertices then amounts to multiplying $K\times K$ transfer matrices in a semiring. A semiring here means an algebra where "addition" and "multiplication" can be swapped for, say, max and plus in optimization problems, or sum and product in probabilistic inference. Raking leaves amounts to a segmented reduction of $K$-vectors. First binarize the tree. Then partition it into $O(n/B)$ clusters of about $B$ vertices, each touching the rest of the tree through at most two boundary vertices. Each cluster can then be reduced to a single $K\times K$ summary by one thread block using only block-local barriers, which cost nanoseconds rather than the microseconds of a kernel launch or the tens of microseconds of a network exchange. The summaries form a tree of size about $n/B$, so the process repeats, and the number of global rounds is
$$R(B) \approx \lceil \log_B n \rceil,$$
because each level shrinks the tree by a factor of roughly $B$. A simple cost model separates the regimes:
$$T \approx R(B)\,\tau_{\text{sync}} + \frac{V(B)}{\beta} + \frac{n K^3}{\pi(K, B)}.$$
Here $\tau_{\text{sync}}$ is the latency of one global synchronization, $V(B)$ the bytes moved between clusters, $\beta$ the bandwidth, and $\pi$ the achieved throughput of the batched small products.
Larger $B$ means fewer rounds and less traffic, but it must fit in shared memory, which limits $B$ for a given $K$. Tensor Cores only help $\pi$ once $K$ reaches roughly 16. The claim is falsifiable. It predicts large gains on deep, path-like trees and in multi-GPU runs where $\tau_{\text{sync}}$ is large. It predicts little gain on shallow trees on a single GPU.
Research Program
We will build three pieces.
The first is a linear-time GPU cluster partitioner. It binarizes the tree, forms bounded-boundary clusters by merging along an Euler-tour order, and lays each cluster's vertices out contiguously. We will measure its cost against SMaT-style reordering, because it replaces that step.
The second is a contraction engine. It runs one thread block per cluster and performs intra-cluster rake and compress entirely in shared memory. Summaries are $K\times K$ semiring matrices. It uses batched Tensor Core products when the semiring is ordinary sum-product and $K\ge 16$, and plain arithmetic kernels otherwise.
The third is a distributed version for trees that do not fit on one node. Clusters become the unit of partitioning, and the only data exchanged is boundary summaries, sent in the sparsity-aware, max-volume-balanced style of the GNN communication work. We will implement this in two ways. The standard MPC variant uses synchronized exchanges. The AMPC variant uses one-sided remote reads to emulate the adaptive hash table of the constant-round contraction paper, which lets us measure directly whether constant-round theory beats logarithmic-round theory once lookups have real latency.
On the analysis side, we will prove the round and volume bounds for the $B$-sized decomposition in the MPC model with $B$ as a parameter, recovering the Bateni et al. $O(\log n)$ bound at $B=O(1)$. We will fit the cost model to measurements so that $\tau_{\text{sync}}$, $\beta$ and $\pi$ are estimated rather than assumed.
Baselines
The do-nothing reference is a sequential depth-first dynamic program on one CPU core with the tree in compact arrays. For trees that fit in one node's memory it is a serious competitor, because it does linear work with no synchronization at all. A parallel method that cannot beat it has no practical case. It runs on the same trees and is timed end to end, including loading from host memory in the layout each method prefers.
The level-synchronous GPU dynamic program processes one depth level per kernel launch. It is the natural first attempt and is strong on shallow, bushy trees, so it protects against overclaiming on those shapes.
The strongest existing GPU approach is contraction by pointer jumping over an Euler tour, which performs rake and compress with about $\log n$ global kernel rounds. It is the direct GPU realization of classic tree contraction and the $B=1$ end of our own design. It shares our code base, differing only in $B$, so implementation quality cancels out.
For the sparse-linear-algebra view, we run depth-many rounds of semiring SpMM with cuSPARSE, Sputnik and SMaT. SMaT is tested both on the natural vertex order and after its own Jaccard reordering, with preprocessing time reported separately and amortized. We have no reported numbers for these kernels on tree matrices, and no reported result on Lacuna for any GPU tree-contraction runtime. The theory papers report only round bounds: $O(\log n)$ for Bateni et al. and $O(1/\varepsilon^3)$ for Hajiaghayi et al. The most relevant reported kernel figures are SMaT's average 2.6× advantage over DASP and up to 125× over cuSPARSE on SuiteSparse, and Sputnik's 3.58× geometric-mean speedup over cuSPARSE. These describe general matrices, not trees, which is exactly why we must rerun the kernels on our workloads.
In the distributed setting the strongest competitor is Bateni et al.'s MPC dynamic program with METIS-style partitioning. We run it once with naive communication and once with sparsity-aware, max-volume-balanced communication, the configuration that the GNN communication paper reports as up to 14× faster than sparsity-oblivious exchange on Protein with 256 GPUs.
Two ablations isolate the key ingredient. The first sweeps $B$ from 1 to the shared-memory limit with everything else fixed. The second keeps our kernel but swaps the cluster layout for SMaT's Jaccard layout, which separates the benefit of the decomposition-as-reordering from the benefit of fewer rounds.
All methods get the same hardware and the same trees. Every method with tunable parameters (tile sizes, block counts, $B$) gets the same budget of 50 autotuning configurations. Beating the strongest baseline means at least 2× lower end-to-end time than the better of pointer jumping and the best SpMM variant on path-like and real spanning trees, with no more than a 10% loss on shallow trees. In the distributed case it means lower wall-clock than the balanced Bateni implementation at 64 GPUs and above.
Why not just…?
Why not just run a sequential depth-first pass on the CPU? For trees of up to a few hundred million vertices, a well-laid-out sequential pass is memory-bound and finishes in seconds, and this is a real threat. Our answer is empirical and limited in scope. We report the crossover size and the state dimension $K$ at which the GPU engine wins, because the $K^3$ work per vertex grows quickly. Beyond one node's memory the CPU option does not exist, and the comparison becomes a distributed one. If the GPU engine does not beat the CPU at $K\le 4$ on single-node trees, we will say so and restrict the claim to large $K$ or large $n$.
Why not just use pointer-jumping contraction on the GPU, whose $\log n$ rounds are only about 30 kernel launches? On one GPU the launch overhead of 30 rounds may well be negligible, and the real advantage of clustering may come from memory locality rather than round count. The $B$ sweep separates the two effects. If pointer jumping comes within 20% of our method on a single GPU, we will conclude that round compression does not matter on-device and that its value lies only across devices, where $\tau_{\text{sync}}$ is orders of magnitude larger.
Why not just treat the tree as a sparse matrix and use SMaT or Sputnik? Two facts from those papers argue against it. Both were tuned for the 70–95% sparsity of deep learning weights, while a tree adjacency matrix is almost entirely zeros, so most 16×8 blocks would be nearly empty. SMaT's reordering is also a preprocessing cost justified only for static matrices, whereas contraction changes the matrix every phase. Message passing by SpMM additionally needs a number of rounds equal to the depth. We still run these kernels, with and without reordering, because on bushy trees their mature engineering could win.
Why not just prune into 2:4 structured sparsity to get hardware speedups? The 2:4 method of Zhou et al. keeps accuracy for learned weights because those weights can be retrained to fit the pattern. A tree's edges are data, not parameters: dropping or adding edges to fit a pattern changes the problem. Our dense tiles come from regrouping computation, not altering structure, so this alternative does not apply.
Proposed Experiments
The workloads are synthetic trees chosen to stress depth and degree: paths, caterpillars, complete binary trees, random recursive trees, preferential-attachment trees and stars, from $10^6$ to $10^9$ vertices. Real trees come from breadth-first and minimum spanning trees of the Reddit, Amazon, Protein and Papers graphs used by Mukhopadhyay et al., and of the SuiteSparse matrices evaluated by SMaT. The tasks are weighted independent set and weighted matching, where the semiring is max-plus; expression evaluation; and sum-product marginals on tree-structured probabilistic models with $K\in\{2,8,16,64\}$ states. The largest $K$ is where Tensor Cores should matter, and it connects to tree-restricted Bayesian network updates of the kind studied by Cheuk et al..
We record end-to-end time, the number of global synchronizations, bytes moved across devices, the fraction of peak throughput achieved, and preprocessing time. For the distributed runs we scale from 8 to 256 GPUs.
Three results decide the question. First, the measured round count should track $\lceil\log_B n\rceil$, and wall-clock time should improve with $B$ on path-like trees while staying flat on shallow ones. If time does not improve on path-like trees, the core claim fails. Second, with our kernel held fixed, the cluster layout should beat the Jaccard layout once preprocessing is included; otherwise the "decomposition is the reordering" half of the claim fails. Third, across devices, the AMPC variant's constant rounds either beat the MPC variant's $\log_B n$ rounds at realistic remote-read latency or they do not. Either outcome answers the realizability question that the AMPC tree-contraction work leaves open, and the fitted cost model says at what latency the answer flips.
References
- Massively Parallel Dynamic Programming on Trees.
- Adaptive Massively Parallel Constant-Round Tree Contraction
- Sparse GPU Kernels for Deep Learning
- High Performance Unstructured SpMM Computation Using Tensor Cores
- Sparsity-Aware Communication for Distributed Graph Neural Network Training
- Learning N: M Fine-grained Structured Sparse Neural Networks From Scratch
- Structured Arc Reversal and Simulation of Dynamic Probabilistic Networks