From GPUs to RRAMs: Distributed In-Memory Primal–Dual Hybrid Gradient Method for Solving Large-Scale Linear Optimization Problems

Huynh Q. N. Vo, M. T. R. Chowdhury, Paritosh Ramanan, Gözde Tutuncuoglu, Junchi Yang, Feng Qiu, Murat Yildirim · 2025

Read From GPUs to RRAMs: Distributed In-Memory Primal–Dual Hybrid Gradient Method for Solving Large-Scale Linear Optimization Problems by Huynh Q. N. Vo, M. T. R. Chowdhury, Paritosh Ramanan, Gözde Tutuncuoglu, Junchi Yang, Feng Qiu, Murat Yildirim (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-21137.txt.

Introduction

Solving vast linear optimization problems on conventional chips is running into physical limits, so computing inside memory itself is gaining ground. Huynh Vo and six co-authors adapt an optimization algorithm for resistive memory arrays in a 2025 paper for the SIAM PP26 conference. Their method is a distributed in-memory primal-dual hybrid gradient algorithm.

Resistive RAM can compute with analog physics, saving latency and energy, but reprogramming the arrays is costly. Algorithms from conventional architectures translate poorly, especially for constrained problems. The authors co-design the method with the hardware: it minimizes write cycles and tolerates device imperfections. Work is distributed across arrays of devices. The paper charts a path from GPU-bound optimization toward in-memory solvers for logistics-scale problems.

Catalog record

CREATORHuynh Q. N. Vo, M. T. R. Chowdhury, Paritosh Ramanan, Gözde Tutuncuoglu, Junchi Yang, Feng Qiu, Murat Yildirim
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE82 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-21137

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

From GPUs to RRAMs: Distributed In-Memory Primal–Dual Hybrid Gradient Method for Solving Large-Scale Linear Optimization Problems Huynh Q. N. Vo, M. T. R. Chowdhury, Paritosh Ramanan, Gözde Tutuncuoglu, Junchi Yang, Feng Qiu, Murat Yildirim Abstract The exponential growth of computational workloads is surpassing the capabilities of conventional architectures, which are constrained by fundamental limits. In-memory computing (IMC) with RRAM provides a promising alternative by providing analog computations with significant gains in latency and energy use. However, existing algorithms developed for conventional architectures do not translate to IMC, particularly for constrained optimization problems where frequent matrix reprogramming remains cost prohibitive for IMC applications. Here we present a distributed in-memory primal–dual hybrid gradient (PDHG) method, specifically co-designed for arrays of RRAM devices. Our approach minimizes costly write cycles, incorporates robustness against device non-idealities, and leverages a symmetric block-matrix formulation to unify operations across distributed crossbars. We integrate a physics-based simulation framework called MELISO+ to evaluate performance under realistic device conditions. Benchmarking against GPU-accelerated solvers on large-scale linear programs demonstrates that our RRAM-based solver achieves comparable accuracy with up to three orders-of-magnitude reductions in energy consumption and latency. These results demonstrate the first PDHG-based LP solver implemented on RRAMs, showcasing the transformative potential of algorithm–hardware co-design for solving large-scale optimization through distributed in-memory computing. Keywords: In-Memory Computing, Distributed Constrained Optimization, Primal-Dual Hybrid Gradient Method 1 Introduction The exponential growth in computational workloads is imposing significant challenges for sustainable computing [ 1 ] , while conventional computing architectures are struggling to keep pace due to diminishing returns from Moore’s law [ 2 , 3 ] . A central obstacle for conventional computing architectures is the von Neumann bottleneck—the physical separation of memory and processing—which imposes substantial energy and latency costs through continual data movement during sequential computational tasks [ 4 , 5 ] . Emerging in-memory computing (IMC) architectures, such as resistive random-access memory (RRAM) device arrays, resolve this obstacle in two key aspects: (i) by co-locating memory and computation, RRAM eliminates costly data transfers, and (ii) RRAMs enable a single analog step for performing matrix vector multiplication (MVM) operations when configured in a crossbar array architecture. Collectively, these aspects offer not only significant gains in latency and energy use for a range of computing tasks but also introduce a new set of challenges stemming from device non-idealities and intrinsic differences in RRAM operations. Hence, computing methods developed for conventional computing do not translate well to IMC applications, which require the development of new algorithms to ensure both computational accuracy and scalability for fundamental computing tasks. This is particularly true for constrained optimization problems, where frequent write operations—trivial in conventional computing systems—become cost prohibitive for IMC applications. Among the various IMC technologies, RRAM devices stand out as an ideal candidate for computing applications like constrained optimization due to their scalability potential, back-end-of-the-line (BEOL) compatibility with existing CMOS technology, and nonvolatile characteristics [ 6 ] . RRAM devices operate through reversible resistance switching [ 7 ] in metal-oxide-metal structures [ 8 , 9 ] , where the conductance state can be precisely controlled by analog input and retained without power, enabling both data storage and analog computation within the same physical device. By satisfying key development criteria—including high density, rapid read/write capabilities, fast access speeds, and low power consumption—RRAM positions itself as a promising candidate to potentially replace traditional storage devices and achieve significant computing power enhancements [ 10 ] . RRAM device arrays inherently enable efficient MVMs by leveraging Ohm’s and Kirchhoff’s law [ 11 , 12 ] . More specifically, RRAMs perform MVM by applying an input voltage to the rows of the crossbar that triggers an analog multiplication with the conductance states that are located at the intersection points of the array, which are then summed over the arrays. In the context of an MVM operation, the conductance states of the array are analogous to matrix entries, the vector entries are given by the input voltage, and the output current gives the resulting vector. This way of conducting MVM computation is in sheer contrast to conventional architectures that rely on sequential multiply–accumulate operations between memory and processing units. These factors collectively provide significant improvements for RRAMs in scientific computing compared to their digital equivalents, reported to reduce energy use 160 times and 128 times [ 13 ] . Since MVMs are the fundamental operations for the majority of linear operations and optimization algorithms [ 14 , 15 ] , enabling energy-efficient low-latency computing architectures offers a transformative path toward sustainable computing for optimization tasks [ 16 ] . Capitalizing on this promise, this paper develops a novel framework specifically designed for RRAM devices to solve distributed constrained optimization problems. 1.1 Related Work In this section, we revise two streams of research that, until now, have largely been developed with limited interaction. The first stream focuses on emerging optimization methods in conventional computing that motivate some of our method development. The second stream focuses on computing in RRAM-based devices that showcase opportunities and challenges unique to in-memory architectures. Together, these research streams form the foundation for our proposed method. First-order methods for linear programs: Large-scale constrained linear programs (LP) push the limits of classical solvers based on simplex and interior-point methods due to heavy sparse matrix factorizations that are performed at each iteration [ 17 ] . These factorizations become a bottleneck: they can consume significant memory—since sparse constraint matrices often yield dense LU/Cholesky factors—and are difficult to parallelize. In fact, for very large instances, memory blow-up from factorization often causes out-of-memory errors even when the raw matrix data fits in memory [ 17 ] . First-order methods such as primal–dual hybrid gradient (PDHG), initially designed for image processing applications [ 18 , 19 , 20 , 21 ] , avoid this pitfall by using only matrix–vector multiplications instead of matrix inversions. Each PDHG iteration has a low per-iteration cost and is matrix-free, meaning the algorithm only needs to access the constraint matrix via multiply operations. This leads to multiple advantages in large-scale settings: the solver’s memory footprint is essentially just the problem data, and the simple, regular operations can exploit modern parallel hardware much more effectively than the sequential steps of simplex or interior-point solvers. These advantages also enable an efficient use of GPU for solving LP models, which is not practical for more conventional solution methods such as simplex and interior point methods. Recent research has demonstrated that with proper enhancements, first-order methods can attain high solution accuracy on LPs and even outperform classical solvers on certain problems. For example, PDLP [ 17 ] applies PDHG to LPs with additional techniques like diagonal preconditioning, adaptive step sizing, and restarting, enabling it to solve many benchmark LPs faster than the ADMM-based splitting conic solver (SCS) [ 22 ] and to beat commercial solvers—e.g., Gurobi [ 23 ] —on a very large PageRank LP instance [ 24 ] . Interestingly, the developers of commercial LP solvers have also begun integrating PDHG: Gurobi reports that an experimental PDHG algorithm can be competitive with its highly optimized simplex and interior-point methods on certain large-scale LPs. These studies underscore that a matrix–vector-centric iterative solver can scale to problem sizes beyond the reach of factorization-based solvers, especially

Read the complete text