Architectures to scale out Ising machines and improve its problem solving capabilities

Anshujit Sharma

Supervised by Michael Huang

523 Computer Studies Building

Nature has inspired a lot of problem-solving techniques over the decades. More recently, researchers have increasingly turned to harnessing nature to solve problems directly. Ising machines are a good example and there are numerous research prototypes as well as many design concepts. They can map a family of NP-complete problems and derive competitive solutions at speeds much greater than conventional algorithms and in some cases, at a fraction of the energy cost of a von Neumann computer. However, Ising machines do have some shortcomings which become bottlenecks in realizing its true potential. In this work, I show that with proper architectural support, some of these shortcomings can be overcome.

In the first part of this thesis, I focus on the issue of solving problems bigger than the capacity of an Ising machine. Being fixed in its capacity, without any support, an Ising machine cannot solve a bigger problem. With a simple partitioning strategy, it turns out, the advantage of using an Ising machine quickly diminishes. It is therefore, desirable to design Ising machines from the ground up such that multiple instances can collaborate to solve a bigger problem. I discuss the design issues of a macrochip architecture which lead to a multiprocessor Ising machine architecture. Experimental analyses show that my proposed architecture does allow an Ising machine to scale out to multiple processors while maintaining a significant performance advantage. When communication bandwidth is limited, my proposed optimizations in supporting batch mode operation can cut down communication demand without a significant impact on solution quality.

 In the second part, I do a detailed analysis of Ising machines in solving Boolean Satisfiability (SAT). Ising machines have shown great potential in solving binary optimization problems. However, in the case of 3-SAT problems, a basic architecture fails to produce meaningful acceleration, largely due to the relentless progress made in conventional SAT solvers. Nevertheless, careful analysis attributes part of the failure to the lack of two important components: cubic interactions and efficient randomization heuristics. To overcome these limitations, we add proper architectural support for cubic interaction on a state-of-the-art Ising machine. More importantly, we propose a novel semantic-aware annealing schedule that makes the search-space navigation much more efficient than existing annealing heuristics. Using numerical simulations, we show that such an “Augmented” Ising Machine for SAT (AIMS) is projected to outperform state- of-the-art software-based, GPU-based and conventional hardware SAT solvers by orders of magnitude.