Mar 13 (Thu) @ 7:30pm: "Design of ASIC Ising Machines for Solving Combinatorial Optimization Problems," Jooyoung Bae, ECE PhD Defense

Location: Ellison Hall Conference Room (EH, Rm 1815)
Research Area: Computer Engineering
Research Keywords: VLSI Design

Abstract

Combinatorial Optimization Problems (COPs) are prevalent in our daily lives, from route searching to optimal placement or optimization of scheduling. Solving these problems effectively can lead to significant improvements in efficiency and performance across industries. However, most COPs are classified as NP–hard, indicating that they can’t be solved in polynomial time using classical algorithms. As an alternative computing method, Ising machines using an Ising model’s property to be naturally converged to expedite computation have been studied recently. Various implementations, such as quantum, optical, and MTJ-based Ising machines, have been investigated.

Non-ASIC Ising computers often face limitations in scalability, reliability and high costs. Digital-based Ising machines have been developed to resolve the issues, demonstrating notable progress in accuracy, scalability, and spin density. However, these digital-based Ising machines typically operate in discrete time, necessitating sequential spin updates to find global solution. The number of operation cycles to process all spins increases exponentially as the connectivity and problem size increase. Additionally, they rely on multiple on-chip or off-chip bulky RNGs to lower the Ising Hamiltonian through probabilistic updates, leading to area and power overheads. 

To overcome these challenges, analog-based Ising machines utilizing ROSCs have been introduced, enabling continuous-time operation. However, there still remains room for improvement in these analog-based systems. In our initial work, we proposed a continuous-time latch-based Ising machine, achieving over 1000× faster time-to-solution compared to baseline digital processing at 1GHz. Subsequently, we developed an enhanced latch-based Ising machine incorporating repica equalization without iteration, resulting in near-ground solutions and outperforming the baseline Ising operation with 40× iterations. However, these designs had limited connectivity with fixed topologies, restricting the range of solvable problems. To address this, we introduced the first-of-its-kind SRAM-based Ising macro with an enhanced Chimera topology. The proposed Ising machine integrated up to approximately 10k spins per mm2, which is the highest spin density reported to date, and offers reconfigurability to lattice or Chimera graphs, enhancing the connectivity.

Bio

Jooyoung Bae received the B.S. degree in electronic engineering from Kwangwoon University, Seoul, South Korea, in 2014, and the M.S. degree in electrical engineering from the Korea Advanced Institute of Science and Technology (KAIST), Daejeon, South Korea, in 2016. She worked as a Memory Circuit Designer with SK Hynix, Icheon, South Korea, until 2021. She is currently pursuing the Ph.D. degree with the Department of Electrical and Computer Engineering (ECE), University of California at Santa Barbara, Santa Barbara, CA, USA. Her research interests include in-memory computing for machine learning (ML)/Ising machines and simulated quantum computing.

Hosted By: ECE Professor Luke Theogarajan

Submitted By: Jooyoung Bae <jooyoung@ucsb.edu>