Header

UZH-Logo

Maintenance Infos

An event-based architecture for solving constraint satisfaction problems


Mostafa, Hesham; Müller, Lorenz K; Indiveri, Giacomo (2015). An event-based architecture for solving constraint satisfaction problems. Nature Communications, 6:8941.

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.

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.

Statistics

Citations

4 citations in Web of Science®
6 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

12 downloads since deposited on 22 Feb 2016
8 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Neuroinformatics
Dewey Decimal Classification:570 Life sciences; biology
Language:English
Date:2015
Deposited On:22 Feb 2016 13:23
Last Modified:11 Aug 2017 16:44
Publisher:Nature Publishing Group
Series Name:Nature communications
ISSN:2041-1723
Free access at:PubMed ID. An embargo period may apply.
Publisher DOI:https://doi.org/10.1038/ncomms9941
PubMed ID:26642827

Download

Download PDF  'An event-based architecture for solving constraint satisfaction problems'.
Preview
Content: Published Version
Filetype: PDF
Size: 691kB
View at publisher
Licence: Creative Commons: Attribution 4.0 International (CC BY 4.0)