Tackling Parallelization Challenges of Randomized Preconditioners With Dependency Tracking
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Tackling Parallelization Challenges of Randomized Preconditioners With Dependency Tracking".
Paper summary: Tom: So Jane, this paper tackles Incomplete Cholesky and Approximate Cholesky methods for large graph Laplacian systems. The main issue they point out is that while Incomplete Cholesky is memory efficient, it breaks down when the graph has irregular sparsity patterns.
Jane: Right, and they introduce Approximate Cholesky with randomized dropping which they claim makes it provably breakdown-free. But the problem isn't the numerical stability of AC; it’s how to run it fast on modern hardware.
Lu: Exactly. The authors say that AC has this stochastic fill-in pattern because the fill-in positions are determined online, which means you can't use a static schedule for parallel computing because the dependencies change during the process, creating this setup bottleneck.
Meng: I’m worried about that bottleneck on actual production hardware. If the factorization part stays serial or poorly parallelized, all those speedups from the subsequent solve phase just vanish. What's their main claim here?
Tom: The authors are proposing a framework to overcome that by using dynamic dependency tracking and architecture-aware memory management. They are essentially trying to maintain the randomized elimination kernel used by rchol while still getting high performance on GPUs and CPUs.
Jane: So they aren't just fixing the numerical issue, they're building a parallel execution model that respects how the dependencies actually form during the factorization process. But how do you track those dependencies dynamically without killing performance?
Lu: They use dynamic dependency tracking to identify direct dependencies for each vertex at runtime. This means instead of guessing where things go beforehand, the system figures out what needs to happen right when it happens.
Meng: That sounds complex for a GPU. I’m picturing all that runtime tracking causing massive overhead or memory allocation issues inside the CUDA kernels themselves.
Tom: They addressed that by using lock-free dependency updates and pre-allocated memory structures on both multicore CPUs and massively parallel GPUs to avoid those penalties from dynamic allocation inside the kernels. It's about keeping things stable under high parallelism.
Jane: That’s interesting because it tries to keep the randomized elimination kernel, which is already used by rchol, but adapts it for this stochastic fill-in pattern without a static schedule constraint. So they’re leveraging existing good math but building a better parallel engine around it.
Paper summary: Lu: And they show that this approach preserves the output distribution of the randomized Cholesky factorization, meaning the results are still correct and breakdown-free on connected graph Laplacians, which is a big deal for trust in the method itself.
Meng: It's good they proved it’s breakdown-free, but I need to know how much faster this setup phase actually gets compared to what we have now. We can't just accept a framework if it doesn't deliver a real speedup.
Tom: The results are pretty substantial. They show total time-to-solution speedups over deterministic Incomplete Cholesky reaching fifty-seven point three times faster on CPUs and fifty-two point two times faster on GPUs for the irregular graph Laplacians they tested. That’s a lot of gain right there.
Jane: And when you compare it to Algebraic Multigrid, they found that this method is up to seven point two times faster on CPUs and six point zero times faster on GPUs for those irregular graph problems. So it’s not just about being better than the old standard; it’s competitive against AMG.
Lu: It's important to remember that AMG is generally preferred for structured problems, but this paper shows that for irregular graph Laplacians and SDDM systems, ParAC offers a memory-efficient alternative without needing to sacrifice numerical tolerance.
Meng: That makes sense for deployment because if the memory hierarchy can’t hold a full multilevel hierarchy, or if Incomplete Cholesky just won't converge on the irregular sparsity pattern, this method is a practical choice. It’s lightweight and works where other things fail.
Tom: So they showed that for these irregular systems, ParAC converges on all two hundred systems in both platform studies, which shows it’s more robust than some of the AMG baselines they tested. That convergence across all twenty systems is a strong indicator of its reliability.
Jane: It sounds like the authors are really pushing the idea that we can get high-performance results from methods that traditionally struggled with static parallelization just by using dynamic tracking to expose the real parallelism. What’s their final word on where this leads?
Lu: They acknowledge that there’s still a trade-off between how much fill reduction you get versus how much structural parallelism you unlock, which is something they want to look into next. They also suggest looking at maximal independent set algorithms to choose the elimination order dynamically when the fill pattern changes.
Paper summary: Meng: If we can dynamically choose the order based on how the fill changes, that’s more practical for real-world scenarios than fixing a permutation in advance, especially if we are dealing with mixed sign matrices.
Tom: And they also mentioned another direction: using ParAC as a parallel smoother within an algebraic multigrid framework instead of just a standalone preconditioner. That would integrate it more deeply into existing solvers.
Jane: It’s clear this work isn't just about one factorization; it’s about finding a way to make randomized preconditioning usable on modern, irregular graph structures without needing perfect prior knowledge of the structure.
Lu: That seems to be the core idea: using dynamic dependency tracking to bridge the gap between a numerically robust method like Approximate Cholesky and high-performance parallel execution architectures. The paper tackles parallelization challenges with dependency tracking, which is how you expose parallelism despite those stochastic fill-ins mentioned on page two of this work.
Meng: If we look at deployment costs, this framework seems promising because it avoids the severe penalties of dynamic allocation inside kernels by using pre-allocated memory structures. That’s a huge win for production environments where performance and predictable memory usage are everything.
Tom: So to wrap up what they did in "Tackling Parallelization Challenges of Randomized Preconditioners With Dependency Tracking," they showed how dynamic dependency tracking allows parallel execution of the randomized Cholesky kernel, which is the mechanism used by rchol, achieving significant speedups on both CPUs and GPUs over deterministic Incomplete Cholesky.
Jane: It’s a practical framework for when classical methods break down due to irregular sparsity patterns, offering strong performance gains over alternatives like AMG on those specific graph Laplacians.
Lu: The paper points toward future work focusing on dynamically choosing elimination orders based on fill changes, or integrating this concept into parallel smoothers within algebraic multigrid solvers.
Meng: For anyone running large SDDM systems where memory is tight and the structure is irregular, this paper shows a way to get a much faster preconditioner than what we currently use.
Tom: It’s about taking randomized preconditioning and making it actually run fast on the hardware we have today by using that dynamic dependency tracking mechanism.
Jane: So that’s what this paper is all about, showing how to harness the power of randomized factorization even when the structure changes unpredictably during runtime.
Conclusion: Tom: So, we’re wrapping up this piece on "Tackling Parallelization Challenges of Randomized Preconditioners With Dependency Tracking" by ParAC, which is about how they made a randomized method actually run fast on modern hardware.
Jane: Right, so the main thing here is that they took Incomplete Cholesky methods and figured out a way to make them parallel without having to guess the fill-in pattern in advance.
Lu: They introduced this dynamic dependency tracking model, which basically lets the system figure out exactly what needs to happen at runtime instead of relying on a fixed schedule.
Meng: I still need to know how much overhead that tracking adds when you’re actually running on a GPU, because dynamic allocation inside those kernels can kill performance quickly.
Tom: They handled that by using lock-free updates and pre-allocated memory structures, which keeps things stable even when the dependencies are moving around.
Jane: And the results they showed are pretty compelling. They got speedups over deterministic Incomplete Cholesky of fifty-seven point three times on CPUs and over fifty-two times on GPUs for these irregular graph systems.
Meng: Fifty-seven times? That’s a big number, but I need to know if that speedup holds up when you try to run it on real, messy traffic instead of a clean test case.
Lu: They proved that the output distribution is the same as if you ran the standard randomized Cholesky serially, which means their results are trustworthy and breakdown-free on connected graph Laplacians.
Tom: So basically, they took a method that breaks down on irregular graphs and built a framework around it so it can actually perform well in production environments like SDDM systems.
Jane: It shows that for problems where the structure is messy, you don't have to just settle for slow methods like classical Incomplete Cholesky or even Algebraic Multigrid.
Lu: The authors are looking at future work on how to dynamically choose the elimination order based on how the fill-in pattern actually changes during the factorization.
Tom: And they also looked at integrating this into algebraic multigrid smoother, which is a way to use this method inside larger solvers rather than just as a standalone preconditioning step.
Jane: This whole paper suggests that we can harness randomized preconditioning even when the graph structure is unpredictable, provided you have the right dynamic execution framework.
University of California, Berkeley · North Carolina State University · Lawrence Berkeley National Lab · Rice University
cs.DC, cs.DS, cs.NA, math.NA
Submitted: 2025-05-05
Updated: 2026-11-18
Code: https://github.com/Tianyu-Liang/Parallel-Randomized-Cholesky
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 97/100
The gist: Incomplete Cholesky (IC) is a common memory-efficient preconditioner for large graph Laplacian systems, but classical IC can break down on irregular graphs Its stochastic fill-in pattern…
Key concepts
- Incomplete Cholesky (IC)
- IC is a memory-saving method used as a preconditioner for large graph Laplacian systems. While efficient, its random fill-in pattern makes it hard to parallelize statically because the dependencies are determined during the factorization process, leading to performance bottlenecks.
- Dynamic Dependency Tracking
- This is ParAC's core mechanism. Instead of knowing all dependencies beforehand, the framework tracks which vertices directly depend on others as edges are processed at runtime. A vertex is considered ready only when its dependency counter reaches zero, allowing for dynamic scheduling that exposes parallelism.
- Architecture-Aware Design
- ParAC implements its dynamic tracking model specifically for CPUs and GPUs. It uses lock-free updates and pre-allocated memory structures to avoid the performance penalties associated with allocating memory dynamically inside parallel kernels on both architectures.
Terminology
Summary
Incomplete Cholesky (IC) is a common memory-efficient preconditioner for large graph Laplacian systems, but classical IC can break down on irregular graphs Its stochastic fill-in pattern, however, resists static parallelization, creating a “setup bottleneck”
The Problem with Existing Parallel Methods
Despite the numerical superiority of Approximate Cholesky (AC), it faces a significant hurdle on modern high-performance architectures, particularly GPUs The stochastic nature of AC makes parallelization difficult because its fill-in pattern is determined “online,” so a static schedule cannot represent the realized dependencies exactly Existing parallel methods for fixed-pattern or level-scheduled incomplete Cholesky rely on dependencies known before numerical factorization Domain decomposition strategies, like rchol, introduce a nontrivial preprocessing cost because partitioning carries a nontrivial preprocessing cost
The ParAC Framework
ParAC introduces a practical high-performance execution framework built on dynamic dependency tracking and architecture-aware memory management This framework preserves rchol’s randomized elimination kernel and output distribution, inheriting its breakdown-free guarantee Its key features include:
-
The ParAC Framework: It introduces a dynamic dependency-tracking execution model that identifies the direct dependencies of each vertex at runtime
-
Architecture-Aware Design: It realizes this model on both multicore CPUs and massively parallel GPUs, using lock-free dependency updates and pre-allocated memory structures to avoid the severe penalties of dynamic allocation inside parallel CUDA kernels
Performance Gains and Comparison
ParAC achieves total time-to-solution speedups over deterministic IC reaching 57.3× on CPU and 52. p. 0 p. 02× on GPU On the irregular graph Laplacians tested, ParAC is up to 7. p. 1 p. 12× faster than AMG on CPUs and 6. p. 0 p. 00× faster on GPUs While Algebraic Multigrid (AMG) generally remains preferable for structured PDE discretizations, ParAC offers a lightweight, memory-efficient alternative for graph Laplacians and SDDM systems without a numerical drop tolerance
Architectural Implementation Details
The implementation differs between CPUs and GPUs based on their respective architectures
CPU Design:
-
Memory Layout: It uses a contiguous workspace O for the final factor and temporary update data, with threads reserving column chunks by applying atomic fetch add to a shared global offset
-
Work Scheduling: It employs a
left-searching
mechanism where vertices traverse a linked list of fill-ins to aggregate updates
GPU Design:
-
Memory Layout: It uses a hashmap array W for right-searching, where Schur-complement updates are written near a target-specific hash location rather than stored in a linked list
-
Work Scheduling: It adopts a persistent kernel model where all blocks remain active and continuously poll the queue at their assigned locations, fetching and performing a job whenever one is available
Robustness and Conclusion
ParAC demonstrates greater robustness for heterogeneous SDD systems than AMG baselines tested ParAC converges on all 200 systems in both platform studies, whereas AmgX fails on 19 full, no-boundary Laplacians The results show that ParAC is preferable on irregular graph Laplacians and SDDM systems when device memory cannot hold a multilevel hierarchy or when classical IC fails to converge on an irregular sparsity pattern Several questions remain open regarding the trade-off between fill reduction and structural parallelism The mechanism may extend to other randomized sparse primitives whose structure is revealed only at runtime
REFERENCE
ParAC preserves rchol’s randomized elimination kernel while output distribution Dynamic dependency tracking is the key mechanism to expose parallelism despite AC’s stochastic fill-ins The saving is that ParAC needs only the scalar counter dt(i), updated locally as edges are inserted and deleted, rather than any transitive reachability information A vertex becomes ready exactly when this counter reaches zero, at which point it is inserted into the ready queue Because SampleClique draws using only the weights on the pivot’s own star, each ready pivot therefore has the same conditional sampling distribution whether it is eliminated first, last, or concurrently The output distribution of ParAC matches that of a serial execution of the rchol kernel, which is provably breakdown-free on connected graph Laplacians Incomplete Cholesky (IC) is a common memory-efficient preconditioner for large graph Laplacian systems, but classical IC can break down on irregular graphs Its stochastic fill-in pattern, however, resists static parallelization, creating a “setup bottleneck” The total time-to-solution speedups over deterministic IC reach 57.3× on CPU and 52.2× on GPU On the irregular graph Laplacians tested, ParAC is up to 7.2× faster than AMG on CPUs and 6.0× faster on GPUs The ParAC Framework: We introduce a dynamic dependency-tracking execution model that identifies the direct dependencies of each vertex at runtime Architecture-Aware Design: We realize this model on both multicore CPUs and massively parallel GPUs, using lock-free dependency updates and pre-allocated memory structures to avoid the severe penalties of dynamic allocation inside parallel CUDA kernels The ParAC Framework: We introduce a dynamic dependency-tracking execution model that identifies the direct dependencies of each vertex at runtime Architecture-Aware Design: We realize this model on both multicore CPUs and massively parallel GPUs, using lock-free dependency updates and pre-allocated memory structures to avoid the severe penalties of dynamic allocation inside parallel CUDA kernels Performance vs. p. 1 ichol: Both ParAC and ichol are incomplete factorization methods, so the two are direct competitors ParAC is faster than ichol on 14 of the 15 test cases On the network problems where ParAC does use fewer iterations, the count for ichol is up to 50× higher Performance vs. p. 8 BoomerAMG (hypre): The advantage of ParAC over AMG therefore lies in robustness and construction cost, not in total time across the board ParAC converges on all 200 systems in both platform studies These results show greater robustness for ParAC than for both AMG baselines tested Several questions remain open. p. 9 A mathematical characterization of the trade-off between fill reduction and structural parallelism would put the ordering guidance of Section V-B on firmer ground One promising direction draws on maximal independent set (MIS) algorithms: choose the elimination order dynamically as sampled fill changes, rather than fixing the permutation in advance Supporting mixed-sign SDD matrices directly, rather than through the standard constantfactor reduction to a Laplacian [6], is another natural next step A further direction is to use ParAC as a parallel smoother within algebraic multigrid rather than as a standalone preconditioner The mechanism is not specific to Cholesky factorization either, and may extend to other randomized sparse primitives whose structure is revealed only at runtime
REFERENCE
The ParAC Framework: We introduce a dynamic dependency-tracking execution model that identifies the direct dependencies of each vertex at runtime Architecture-Aware Design: We realize this model on both multicore CPUs and massively parallel GPUs, using lock-free dependency updates and pre-allocated memory structures to avoid the severe penalties of dynamic allocation inside parallel CUDA kernels CPU Algorithm: The CPU implementation is based on the “left-searching” mechanism: at each step, the Schur-complement updates are stored locally and chained together by a linked list GPU Algorithm: We use “rightsearching,” in which Schur-complement updates are written near a target-specific hash location GPU Algorithm: We use “rightsearching,” in which Schur-complement updates are written near a target-specific hash location
REFERENCE
Table I: Properties of the test matrices. The role of matrix density is clearest on com-LiveJournal, the densest matrix in our test suite (average degree ≈ 17, see Table I) AMD Ordering: AMD generally has the lowest lowthread factorization cost, although NNZ-sorted or random can overtake it at 32 threads Performance vs. p. 8 ichol: ParAC is faster than ichol on 14 of the 15 test cases Performance vs. p. 8 BoomerAMG (hypre): The advantage of ParAC over AMG therefore lies in robustness and construction cost, not in total time across the board GPU Results: Ordering affects both fill and dependency structure [37], [50] AMD is a fill-reducing heuristic [38]; in our additional structural measurements, it produced deeper post-factorization elimination trees for the sampled ParAC factors and longer triangular-solve critical paths than NNZ-sorted or random ordering
REFERENCE
Table III: GPU performance: ParAC vs. cuSPARSE IC(0) (zero fill-in) and AmgX. p. 9
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Dynamic dependency tracking allows ParAC to
expose finergrained parallelism than rchol’s nested-dissection scheme,
enabling it toschedule elimination tasks with low overhead, avoiding the conservative bottlenecks of static elimination trees.
This allows the system to exploit parallelism thatcannot be scheduled statically in advance.
-
Architecture aware design enables GPU implementations using a persistent kernel and rightsearching, which avoids
severe penalties of dynamic allocation inside parallel CUDA kernels
and reduces kernel launch overhead by computing the factorization within a single launch. -
The system can achieve total time-to-solution speedups up to 57.3 times on CPU and 52.2 times on GPU compared to deterministic IC, significantly accelerating the preconditioned iterative phase for irregular graph Laplacians where AMG solvers often fail or exhaust memory.
-
The improved AI system can converge successfully on challenging heterogeneous SDDM systems, as ParAC
converges on every instance
across 200 systems where classical IC and AMG solvers failed on 15 and 19 instances, respectively.
Sources
Related papers
- Programmable Probabilistic Computer with 1,000,000 p-bits
- BatchGen: An Architecture for Scalable and Efficient Batch Inference
- Seamless Reconfiguration for DAG-BFT (Technical Report)
- ELDR: Expert-Locality-Aware Decode Routing for PD-Disaggregated MoE Serving
- iScheduler: Reinforcement Learning-Driven Continual Optimization for Large-Scale Resource Investment Problems
- TIRx: A Unified Tile Primitive ML Compiler Across Heterogeneous Backends