An event-based architecture for solving constraint satisfaction problems

Hesham Mostafa (), Lorenz K. Müller and Giacomo Indiveri
Additional contact information
Hesham Mostafa: Institute for Neuroinformatics, University of Zurich and ETH Zurich
Lorenz K. Müller: Institute for Neuroinformatics, University of Zurich and ETH Zurich
Giacomo Indiveri: Institute for Neuroinformatics, University of Zurich and ETH Zurich

Nature Communications, 2015, vol. 6, issue 1, 1-10

Abstract: Abstract Constraint satisfaction problems are ubiquitous in many domains. They are typically solved using conventional digital computing architectures that do not reflect the distributed nature of many of these problems, and are thus ill-suited for solving them. Here we present a parallel analogue/digital hardware architecture specifically designed to solve such problems. We cast constraint satisfaction problems as networks of stereotyped nodes that communicate using digital pulses, or events. Each node contains an oscillator implemented using analogue circuits. The non-repeating phase relations among the oscillators drive the exploration of the solution space. We show that this hardware architecture can yield state-of-the-art performance on random SAT problems under reasonable assumptions on the implementation. We present measurements from a prototype electronic chip to demonstrate that a physical implementation of the proposed architecture is robust to practical non-idealities and to validate the theory proposed.

Date: 2015
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.nature.com/articles/ncomms9941 Abstract (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nat:natcom:v:6:y:2015:i:1:d:10.1038_ncomms9941

Ordering information: This journal article can be ordered from
https://www.nature.com/ncomms/

DOI: 10.1038/ncomms9941

Access Statistics for this article

Nature Communications is currently edited by Nathalie Le Bot, Enda Bergin and Fiona Gillespie

More articles in Nature Communications from Nature
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().