Ph.D. Public Defense
Extending Ising Machines for solving Machine learning problems and LDPC Codes
Uday Kumar Reddy Vengalam
Supervised by Michael C. Huang
Monday, October 16, 2023
10 a.m.11 a.m.
426 Computer Studies Building
Nature does a lot of computation constantly. Suppose we can harness some of that computation at an appropriate level; in that case, we can potentially perform a certain type of computation (much) faster and more efficiently than we can do with a von Neumann computer. One branch of this effort that has seen recent rapid advances is Ising machines. A physical Ising machine relies on the system’s nature to guide itself to- wards an optimal state. The final state of the machine represents a heuristic solution to a problem that was mapped on the system. Quantum annealers are a prominent example of such efforts. However, existing Ising machines are generally bulky and energy intensive. Such disadvantages may be acceptable if these designs provide some significant intrinsic advantages at a much larger scale in the future, which remains to be seen. For now, integrated electronic designs of Ising machines allow more immediate applications. We propose one such design that uses bistable nodes coupled with programmable and variable strengths. The design is fully CMOS compatible for on-chip applications and demonstrates competitive solution quality and significantly superior execution time and energy.
Indeed, many powerful algorithms are inspired by nature and are thus prime candidates for nature-based computation. These algorithms are used to solve problems like combinatorial optimizations and machine learning. In this proposal, we explore our design for solving three such problems, namely finding Max-Cut for a given graph, training Restricted Boltzmann machines for different applications, and decoding LDPC codes.
For solving Max-cut problems, our design BRIM achieved four orders of magnitude improvements in speedup and energy consumption compared to existing Ising machines. By modifying the BRIM design, we were able to train RBMs 30X faster than a TPU with a 1000x reduction in energy consumption. Decoding LDPC codes is a combinatorial optimization problem with constraints. Mapping this problem on an Ising machine needs conversion into a Quadratic Unconstrained Binary Optimization (QUBO). This conversion leads to an increase in the problem size, which leads to poor solution quality. In this proposal, we introduced a new way of mapping LDPC codes onto Ising machines by slightly modifying the hardware to implement a different style of decoding algorithm than prevailing implementations. The experimental results show that such a design is 4.4× more energy efficient than state of the art in the literature.
By leveraging the potential of nature-based computation and employing innovative designs, our proposal demonstrates significant advancements in solving various computational problems. The improved performance, energy efficiency, and solution quality offered by our CMOS-compatible Ising machine design pave the way for practical ap- plications in domains such as graph analysis, machine learning, and error correction.