CS Paper Radar

Extreme-Scale Ising Machines with Cluster Mean-Field Theory

Xiuqi Zhang, Shuvro Chowdhury, Shaila Niazi, Christian Z. Pratt, Navid Anjum Aadit, Kerem Y. Camsari

cs.DC cond-mat.dis-nncs.ET ·submitted 2026-09-18 23:46 UTC · v1

Abstract

Scaling analog and digital Ising machines to larger problems requires overcoming finite device capacity and the cost of communication between devices. We present cluster mean-field theory (CMFT), a framework that partitions a large interaction graph into clusters sized to fit available hardware. Each cluster performs local updates independently, while interactions across cluster boundaries enter through periodically updated effective biases computed from boundary-spin averages. To reduce the error introduced by fixed cluster boundaries, we introduce dynamic partitioning, which cycles through multiple partitions so that interactions approximated by mean fields at one stage can act through instantaneous spins at another. On three-dimensional spin glasses and planted Pegasus instances, dynamic CMFT exhibits power-law decay of residual energy over sweep budgets. This shows that solution quality continues to improve with computational effort despite the mean-field approximation. An automated graph partitioner combined with a weighted recovery ratio provides a practical heuristic for selecting partition combinations on graphs without natural cut directions. We demonstrate CMFT on four GPUs with approximately four million p-bits, reaching comparable energy densities up to 15 times faster than a single-GPU implementation of the full graph. By coupling locally evolving clusters through programmable effective biases, CMFT provides a route to extreme-scale Ising machines on both analog and digital hardware.

Comment
15 pages, 10 figures including Supplementary Information

Closest papers

Nearest neighbours by meaning across the whole index.

Accelerating Distributed Digital Ising Machines

cs.AR cs.DCcs.LG ·2026-11-18 ·Tong Wu, Ziyad Alswaidan, Shreya Mukherjee, Ting-Yu Lee, Daniel Xu +9 more
top venue similarity 0.61
Abstract · 16 pages. Accepted at HPCA

Ising machines, dedicated accelerators built around the dynamics of Ising-like spin models, have emerged as a leading platform for combinatorial optimization and probabilistic sampling. The problems that motivate them require millions of spins, far beyond the on-chip capacity of any single device, so a practical Ising machine must distribute its computation across many devices. Prior work reports throughput at a single operating point, leaving the binding resource unidentified and platform crossovers measurable only by experiment; no calibrated cross-platform cost model of distributed Ising machines has been reported, nor have systematic techniques to accelerate their Markov chain Monte Carlo (MCMC) workloads. This work presents a calibrated cost model that decomposes digital Ising sweep time into compute, memory, synchronization, and inter-device communication terms, validated with 4.8% mean error across three GPU generations, FPGA and ASIC up to 1 million spins. Guided by the model, we address each term in turn and propose: (i) a data placement strategy, worth up to 4.2$\times$ speedup; (ii) multi-rate and bounded-staleness schedules that relax the barrier that Gibbs sampling imposes, cutting time-to-solution (TTS) by up to 3.16$\times$ on three benchmarks; and (iii) a phase-offset streaming dataflow that hides boundary exchange behind interior computation whenever a link satisfies a latency-transparency criterion, yielding up to 1.25$\times$/1.74$\times$/2.01$\times$ on an H200 pair, a ZCU106 pair, and a four-board XEM8320 $2{\times}2$ mesh. The streaming dataflow is also implemented on a fabricated four-chip 28 nm ASIC sustaining 28.1 Gflips/s at 4.81 pJ/flip.

0.40

Probabilistic Algorithms for Ising Machines from Optimization to Generative AI

cs.LG cond-mat.dis-nncond-mat.stat-mechcs.ET ·2026-10-02 ·Corentin Delacour, Xiuqi Zhang, Abdelrahman S. Abdelrahman, Saleh Bunaiyan, Kyle Lee +2 more
publishedsurvey similarity 0.60
Abstract

Ising machines have emerged as promising hardware accelerators for intractable optimization and sampling problems, yet their practical impact increasingly hinges on the co-design of algorithms and hardware, where algorithmic demands shape new architectures and new hardware capabilities inspire entirely new algorithms. In this Review, we survey probabilistic algorithms designed for portability across diverse Ising platforms, advocating a top-down perspective that prioritizes principled methods with provable guarantees. We cover foundational methods such as simulated annealing and parallel tempering, including two-dimensional extensions that natively encode hard constraints, and examine approaches that expand the scale of solvable problems from cluster mean-field methods to variational samplers. We highlight the Probabilistic Approximate Optimization Algorithm (PAOA), a classical analog of QAOA that emerged directly from probabilistic hardware development, and explore how generative AI and Ising machines might reinforce each other: learned models propose global moves to accelerate optimization, while probabilistic techniques improve inference in large language models. Much as quantum computing has seen algorithms co-evolve with hardware, probabilistic and Ising computing stand at a similar inflection point. We outline a co-design framework for accelerating the capabilities and adoption of next-generation Ising machines.

0.51

multi-Stochastic Core Architecture for Scaling Probabilistic Ising Machines

cs.ET cs.AR ·2026-09-06 ·Chirag Garg, Pratik Brahma, Saavan Patel, Sayeef Salahuddin
similarity 0.58
Abstract · 19 pages, 6 figures

Ising Machines offer vast potential to solve NP-hard optimization problems efficiently that are intractable to solve using conventional computing architecture. A lot of these optimization problems fall into statistical learnability and involve finding an optimal solution among many possible, near-analogous configurations, by searching in a non-convex energy landscape. In this context, the probabilistic Boltzmann machine architecture especially PASS (Parallel Asynchronous Stochastic Sampler), explores and models the complex probability landscape pertaining to all possible configurations and excels in finding the ground-state energy solution of these intractable problems. Additionally, the noise-based neuron architecture addresses the limitation of conventional annealing methods, which may get stuck around local minima. Here, we demonstrate a stochastic sampling approach based on Block Gibbs Sampling to integrate multiple asynchronous PASS chips (four in this work), enabling improved scalability. Further, we demonstrate the scaling by mapping 784 nodes Max-Cut problem integrating 256 nodes PASS accelerator manufactured in 14 nm CMOS FinFET technology. PASS-enabled system with Block Gibbs Sampling protocol shows approximately 1000 times speedup for Max-Cut optimization compared to state-of-the-art methods implemented on CPUs and GPUs. The general applicability of this approach is further illustrated by solving a quantum spin chain Transverse Ising system and accurately representing complex probability landscapes. Moreover, our results demonstrate the change in the scaling law to constant in the scaled-PASS accelerator as compared to exponential on GPUs enabling at least 4 orders of magnitude improvement in time-to-solution. Hence, the presented methodology enables the pathway for scaling of asynchronous brain-like dynamics systems that do not follow any clock for its operation.

0.26

GEM-KMeans: Memory-Efficient and Accurate Clustering on Massive Scale with GPU Optimization

cs.LG cs.ARcs.PF ·2026-09-28 ·Peng Xu, Nihar Koganti, Volodymyr Kindratenko, Xiaohui Chen
similarity 0.55
Abstract

Memory-efficient scaling on clustering problems without sacrificing statistical accuracy is of central interest for large-scale data analysis and machine learning problems. Nonnegative low-rank (NLR) matrix factorization for $K$-means is a scalable clustering method, which connects to semidefinite relaxations with optimal average-case exact recovery guarantees. However, a direct GPU implementation of NLR requires multiple large factor-sized buffers and substantial data movements that are essentially memory-bound. In this paper, we introduce GEM-KMeans, a spectrally normalized yet mathematically equivalent NLR formulation that fuses the gradient update, nonnegative projection, and sufficient statistics for normalization and iterate movement into a matrix-multiplication epilogue. Instead of retaining three massive factor-sized arrays, our IO-aware GPU implementation materializes only one single factor with small tile-reduction arrays as additional storage in the High Bandwidth Memory (HBM). We derive explicit memory costs and spectrally normalized smoothness bounds for optimizing the clustering objective function. Accurate clustering is demonstrated at massive scales on synthetic and real datasets, where performance gains of GEM-KMeans over existing GPU-accelerated Lloyd's algorithms involve data-dependent runtime tradeoffs.

0.28

Multilevel Graph Partitioning on GPU Supercomputers

cs.DC ·2026-11-18 ·Michael S. Gilbert, Erik G. Boman, Kamesh Madduri
published similarity 0.54
Abstract · To appear in the proceedings of HiPC 2026

Graph partitioning is a key enabler in computational science, with applications to sparse linear algebra, load-balanced parallel computation, and graph computations. In recent years, graphics processing units (GPUs) have become the preferred accelerator on the world's top supercomputers. Despite this, most existing distributed graph partitioners do not utilize GPUs. In this work, we develop a new multi-GPU distributed partitioner based on Jet, a prior single-GPU partitioner. We seek to optimize scalability without sacrificing quality. Our partitioner utilizes CUDA-aware MPI, one-sided communication routines, and an overall bulk-synchronous parallel structure. We demonstrate solution quality comparable to Jet. Our experiments show excellent weak scaling up to 256 GPUs, enabling partitioning of instances significantly larger than a single-GPU partitioner can handle.

0.23

Graph-Based Stochastic Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation

cs.LG ·2026-09-17 ·Tung Tran, Viet Bao Mai, Hoang Ta, Tuan Dam
theory similarity 0.53
Abstract · No

Tree-based Monte-Carlo Tree Search (MCTS) duplicates the same state when it is reached through different trajectories, which can waste simulations in stochastic MDPs. We introduce Graph-Based Stochastic-Power-UCT (GS-Power-UCT), which shares states reached at the same planning depth while keeping separate values for states reached at different depths. This design applies to general stochastic MDPs, including problems with cycles. We prove that for a fixed planning horizon, the root estimate converges to the finite-horizon value at rate $O(n^{-1/2})$, matching tree-based Stochastic-Power-UCT while reusing samples across shared states. We also study two full-state variants: GS-Power-UCT-F, which stores one node per physical state to increase sample sharing but may mix values from different remaining horizons, and GS-Power-UCT-F$^+$, which uses an adaptive horizon to control this bias. The latter converges to $V^{\star}(s_0)$, the optimal infinite-horizon discounted value at the root state $s_0$, when the remaining cross-depth gap vanishes. Experiments on stochastic planning benchmarks show improved sample efficiency over tree-based and graph-based baselines.

0.18

DMuon-2: Scaling Matrix Optimizers in Data Parallelism with Topology-Aware Matrix Ownership and Communication

cs.DC ·2026-11-04 ·Starrick Liu, Ruizhi Chengze, Lufang Chen, Michael Zhao, Ran Yu +8 more
code/datahot direction similarity 0.53
Abstract · 25 pages, including appendices. Code: https://github.com/X-Square-Robot/dmuon

Matrix optimizers such as Muon update whole weight matrices, which conflicts with the element- or row-wise sharding of data-parallel runtimes. Once parameters are sharded as well, matrix optimizers incur extra communication or repeated computation. We present DMuon, a matrix-granular optimizer runtime for PyTorch FSDP (ZeRO-2/3) and HSDP. DMuon assigns each matrix a unique owner, which performs the Newton--Schulz (NS) iteration and optimizer update on the full matrix, and balances the load across owners by computational cost. On HSDP, ownership is global across replicas, so the cluster keeps a single copy of gradients and optimizer state, and updated parameters are published across nodes as soon as they are ready, overlapping subsequent computation. This layout makes every collective sparse and variable in length, so DMuon schedules these collectives as their data becomes ready and routes them along the cluster's two-level network. On up to 256 H100 GPUs, across three dense LLMs and two VLA models, DMuon matches or exceeds the training throughput of PyTorch FSDP2 with AdamW, reaching 1.05$\times$ that of FSDP2 with AdamW at the median on 256 GPUs. The optimized parameter gathering and gradient reduction absorb the extra communication and computation a matrix optimizer requires. Against a gather-then-replicate Muon baseline, DMuon's throughput is 2.1 times as high at the median.

0.42

Graph neural networks and the energetic cavity method for combinatorial optimization

cs.LG cond-mat.dis-nn ·2026-09-07 ·Joe Bacchus George, George T. Cantwell
similarity 0.53
Abstract

We study the use of graph neural networks (GNNs) for finding approximate ground states of Ising models. Efficiently finding these ground states is of broad significance because many combinatorial optimization problems can be formulated as an Ising model with the appropriate choice of couplings and fields. Exactly solving these problems is hard but there are many good heuristic methods. A lineage of these heuristics build from mean-field approximations: one approach uses the leading eigenvector of an appropriately defined matrix, another is the min-sum algorithm, also known as the energetic cavity method. Without modification, GNNs perform worse than both of these methods. We consider small modifications to the GNN to incorporate these heuristics and find that this considerably improves performance. While the modified approach is competitive against other deep-learning approaches, we still find that simulated annealing is reliably at least as good as deep learning methods for the same computational cost.

0.26