AI & ML
Tackling Parallelization Challenges of Randomized Preconditioners With Dependency Tracking
arXiv cs.DC0 views
arXiv:2505.02977v4 Announce Type: replace Abstract: Incomplete Cholesky (IC) preconditioners are the standard black-box, memory-efficient first resort for large graph Laplacian systems, but classical IC can break down on irregular graphs. Approximate Cholesky (AC) addresses this with randomized dropping that is provably breakdown-free. Its stochastic fill-in pattern, however, resists static parallelization, creating a "setup bottleneck." We present ParAC, which parallelizes the sequential rchol algorithm on CPUs and GPUs using dynamic dependency tracking and architecture-aware memory management, without altering its numerics. Total time-to-solution speedups over deterministic IC reach $57.3\times$ on CPU and $52.2\times$ on GPU. Algebraic multigrid (AMG) remains preferable on structured PDE discretizations; on irregular graph Laplacians where AMG struggles, ParAC attains up to $7.2\times$ and $6.0\times$. On 200 adversarial SDD systems, ParAC converges on every instance, whereas the AMG solvers fail on 15 and 19, on CPU and GPU, respectively.
Source:https://arxiv.org/abs/2505.02977PreviousDispersedBFT: Bottleneck-Free Primary-Backup Consensus using Dispersed ReplicationNextDemystifying NVSHMEM: A System-Level Analysis on Symmetric Memory and Device-Initiated Operations in GPU Communication
Related posts

How I Built an Offline Voice Dictation App Using Small AI Models
0HackerNoon
FAA's $50 Billion Modernization Push Faces a Problem Money Alone Can't Fix
0HackerNoon
Why AI Agent Security Starts With Permissions, Not Prompts
0HackerNoon

I Let My AI Agent Take Over My Life. Then It Started Making Decisions for Me
0HackerNoon

Does Options Delta Really Predict the Probability of Expiring In the Money?
0HackerNoon
Building Offline AI on Android: 5 LiteRT-LM Pitfalls and Fixes
0HackerNoon