| Efficient Solution of Constraint Satisfaction Problems on Loihi
Gabriel Fonseca-Guerra
Intel Labs, Neuromorphic Computing Lab Abstract:
In this talk we will show how Loihi yields orders of magnitude better energy-delay-product than certain state-of-the-art classical solvers for the task of solving constraint satisfaction problems (CSPs). We have rigorously benchmarked the performance of Loihi which, with a single chip, is able to handle the largest CSPs implemented on neuromorphic hardware to date (with up to 400 variables each taking on up to 20 possible values). These gains in performance come from harnessing the asymmetric dynamics between the active and inactive states of spiking neurons, as well as from the ability to encode probability distributions in stochastic spiking neural networks, as previously demonstrated by Prof. Maass’ group at TU Graz. Furthermore, we will show the first performance results on applying our solver to the real-world problem of assigning resources in the context of train scheduling from our current collaboration with DB. With these encouraging results of solving CSPs on Loihi, we begin our journey into the two sessions on Neuromorphic Solutions for Optimization Problems, wherein we seek to understand the properties that make the neuromorphic hardware paradigm competitive for such tasks. |
Loihi Spiking Processor for Execution Quasi-Complete Constraint Satisfaction
Chris Yakopcic
University of Dayton Abstract:
In many cases, low power autonomous systems need to make decisions extremely efficiently. However, as a problem space becomes more complex, finding a solution quickly becomes nearly impossible using traditional computing methods. Thus, in this work we show that constraint satisfaction problems (CSPs) can be solved quickly and efficiently using spiking neural networks. Constraint satisfaction is a general problem solving technique that can be applied to a large number of different applications. To demonstrate the validity of this algorithm, we show successful execution of the Boolean satisfiability problem (SAT) on the Intel Loihi spiking neuromorphic research processor. In many cases, constraint satisfaction problems have solution sets as opposed to single solutions. Therefore, the manycore architecture of the Loihi chip is used to parallelize the solution finding process, leading to a quasi-complete solution set generated at extreme efficiency. Power consumption in this spiking processor is due primarily to the propagation of spikes, which are the key drivers of data movement and processing. Thus, the proposed SAT algorithm was customized for spiking neural networks to achieve the greatest efficiency gains. In general, we show that embedded spiking neuromorphic hardware is capable of parallelizing the constraint satisfaction problem solving process to yield extreme gains in terms of time, power, and energy. |