Keynote II: Digital Annealer: A Stochastic Search for Global Optimum
Ali Sheikholeslami · 2020
Summary form only given, as follows. The complete presentation was not made available for publication as part of the conference proceedings. As Moore's law nears the end of its time, the search for continued improvement in performance has focused on the architecture-level and system-level innovations. At the system level, we resort to stochastic moves to solve hard optimization problems, where the goal is to minimize (or maximize) a function of many variables (in the order of 1000's) in a fraction of a second. These optimization problems are predominant in engineering, health, finance, and environment. In engineering, for example, we often wish to allocate resources to tasks, or schedule tasks given limited resources, to minimize waste. In health, we wish to maximize radiation to a tumor in a patient's body while sparing the healthy organs surrounding the tumor. This indeed requires optimization of the density of an X-ray beam as it rotates 360 degrees around the patient. In this keynote speech, we will walk you through a stochastic journey of a Markov Chain Monte Carlo (MCMC) process where we try to find the global minimum of a quadratic function of 1024 binary variables. We will demonstrate how employing several techniques in hardware parallelism including parallel tempering (deploying several parallel hardware blocks exploring the solution space at various "temperatures" and occasionally exchanging their states), parallel trial, and parallel update, can provide significant speedup, allowing CMOS to live far beyond the end of CMOS scaling.