OptNet: Optimization with p-bit Networks
Abstract
Optimization problems are of great importance in many real-world contexts, and the common feature underlying them all is the searchfor a configuration # that will minimize a cost or energy function E(#). For many such problems, the number of possible configurations grows exponentially with the number of optimization variables, making it exponentially difficult to find the exact solution, andmuch effort has been devoted to finding solutions that are acceptably close. The aim of this proposal is to develop a framework forefficient real world optimization by integrating the insights from three separate lines of thought from three separate communities.First are the heuristic approaches that have been developed to perform efficient searches tailored to specific cost functions that scale gently with problem size. Second are the Ising computers whose architecture accelerates the solution of quadratic unconstrained binary optimization (QUBO) problems through massively parallel updates. Third are the quantum annealers that operate clocklessly. We adopt an Ising-like architecture but generalize it to include Markov Chain Monte Carlo (MCMC) methods so that the scope can be broadened beyond QUBO to exploit powerful heuristic approaches. Furthermore we replace the clocked updates characteristic of digital computing with random updates that can function without a globally synchronized clock. This leads us to the concept of a parallel asynchronous architecture that can provide enhancements of six orders of magnitude, partly from the parallelism and partly from the asynchrony. To create the knowledge base for this new computing paradigm we propose two tasks. Task 1 designs novel nanodevices and uses them to build parallel asynchronous circuits, while Task 2 develops new algorithms for two common optimization problems and maps them onto parallel asynchronous circuits.Task 1 is centered around a key component of our parallel asynchronous architecture which isa unit that generates random numbers with n bits where the 2n possible outputs are generated according to a specified probability distribution function. Standard semiconductor technology requires thousands of transistors per bit to implement this function, but our past work has experimentally established two innovative alternatives using a Zener diode (Zdiode) and a stochastic magnetic tunneljunction (sMTJ) respectively, which in conjunction with a few transistors constitutes what we call a p-bit. A number of p-bits can be used to construct a p-bit network (pBN) that provides our desired functionality in a compact and energy-efficient way. We will also perform proof-of-concept experiments on a third alternative using low barrier magnets (LBM s) communicating through spin currentson a conducting substrate with a long spin diffusion length. Simulations using experimentally benchmarked spin circuit models suggest that this third alternative, LBM, could provide orders of magnitude improvement in the efficiency over the other alternatives. Each of these novel nanodevices can be used to construct pBN s that generate proposals at unprecedented rates, but in the MCMC method the relative cost #E of specific proposals has to be performed at ultrafast rates so as not to cause a bottleneck in the processing of proposals. Task 1 will not only develop new nanodevices but also combine them with FPGA s or integrate them into ASIC s to demonstrate and benchmark the operation of parallel asynchronous circuits. Initially Task 1 will use QUBO cost functions with simple nearest neighbor connectivity to demonstrate the principles and then expand the scope to address two real world optimization problems, multi-target tracking (MTT) and graph coloring (GC) with applications to planning and scheduling, incorporating the insights developedin Task 2 into the mapping of MTT and GC onto parallel asynchronous architectures.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jul 24, 2023
- Source ID
- N000142312708
Entities
People
- Supriyo Datta
Organizations
- Office of Naval Research
- Purdue University
- United States Navy