Nov 10 (Mon) @ 9:00am: "Scalable High-Order Ising Machines with In-Memory Computing: From Algorithms, Architectures to Integrated Circuits," Tinish Bhattacharya, ECE PhD Candidate

Location: Henley Hall, Lecture Hall 1010
Zoom Link: https://ucsb.zoom.us/j/84238408747?pwd=jYnsE9CzE5NbSQ3curjuqj51WT9F7V.1
Research Area: Communications & Signal Processing, Control Systems, Computer Engineering, Electronics & Photonics
Research Keywords: VLSI Design, Circuits & Systems, Computer Architecture, Machine Learning, AI, Neuromorphic Computing, Control, Optimization and Game Theory

Abstract

Many of the toughest problems in science and engineering can be formulated as optimization tasks, that require finding exact or near-optimal ground states of discrete polynomial functions of arbitrary order. Solving these problems is often computationally prohibitive on traditional processors, as they are typically NP-hard/Complete. This has driven the development of Ising machines, that are specialized hardware designed to efficiently search for ground states of mapped optimization problems.

While current Ising machines excel at problems with quadratic objective functions, they struggle with higher-order cases like Boolean Satisfiability (K-SAT), Max-K-SAT. This slowdown arises from the exponentially larger search space created by the order reduction step required to map high-order problems onto second-order Ising machines. Nevertheless, high-order problems are widespread in fields like electronic structure prediction, network routing, model verification, cryptography, and this necessitates the development of high-order Ising Machines. This dissertation attempts to address this need through innovations in algorithms, architecture, and integrated circuit design.

We present a new hardware paradigm that enables massively parallel computation of high-order gradients (a core operation in such solvers) using mixed-signal in-memory computing circuits. It is shown for the first time, that a pair of cross-coupled crossbars with appropriate peripheral circuits can provide fast solutions to high-order optimization problems with hardware complexity that scale linearly with the number of variables and terms in the objective function but independent of the order. This approach is experimentally validated with an optimization chip (tuned to solving K-SAT), taped out in 55 nm CMOS technology. The integrated circuit featuring custom SRAM based mixed-signal in-memory computing, achieves one to two orders of magnitude speedup over prior solvers, despite implementing a legacy SAT-solving algorithm.

We introduce a new probabilistic SAT-solving algorithm that leverages the bipartite clause-variable relationship to improve navigational efficiency and outperforms several prior algorithms. A second chip demonstrating this algorithm and incorporating dynamic comparator-based Probabilistic-bit (p-bit) circuits to eliminate the need for ADCs or analog-domain reduction circuits  (a critical bottleneck in analog in-memory computing) is taped out in 55 nm CMOS technology. It exhibits the fastest-to-date convergence times on small-scale K-SAT problems and outperforms prior ASICs (including those in more advanced 28 nm) by 4-13 times.

Finally, through hardware-aware simulations, we present a multi-tile architecture that enables scaling these solvers to large high-order optimization problems. The architecture consists of mixed-signal in-memory compute cores interconnected by a field programmable gate array-inspired reconfigurable routing fabric. Analog computations are performed locally within each tile, whereas p-bit-based peripheral circuits confine inter-tile communication to the digital domain.

Bio

Tinish Bhattacharya is a Ph.D. candidate in Electrical and Computer Engineering at the University of California, Santa Barbara, advised by Professor Dmitri Strukov. He received the B. Tech degree in Electrical Engineering from Indian Institute of Technology (IIT) Delhi in 2019, and the M.S. degree in Electrical and Computer Engineering from University of California Santa Barbara (UCSB) in 2021. From 2023 to 2024, he was a research associate intern with the Large-Scale Integrated Photonics Lab at Hewlett Packard Labs.

His research interests include leveraging physics and electronic design automation to enhance performance and energy efficiency of unconventional computing paradigms, with contributions spanning mixed-signal circuits, architecture and algorithm design. He has first-authored publications accepted in venues such as Nature Communications, VLSI Symposium, ISSCC, Hot Chips Symposium and IEDM. His work has been featured by TechXplore, Semiconductor Engineering, UCSB Current, selected by the editors of Nature Communications as one of the 50 best recent papers in a research area, and honored with the UCSB ECE Dissertation fellowship and the James V & Beverly R. Zaleski Discovery Award in 2025.

Hosted By: ECE Professor Dmitri Strukov

Submitted By: Tinish Bhattacharya <tinish@ucsb.edu>"