An event-based architecture for solving constraint satisfaction problems
An event-based architecture for solving constraint satisfaction problems
复制标题
用于解决约束满足问题的基于事件的体系结构
DOI：
--
复制
发表时间：
2015
影响因子：
16.6
通讯作者：
G. Indiveri
中科院分区：
文献类型：
--
作者：
H. Mostafa;Lorenz K. Muller;G. Indiveri
约束满足问题普遍存在于许多领域。它们通常使用传统的数字计算架构来解决，这些架构不反映这些问题中的许多问题的分布式性质，因此不适合解决它们。在这里，我们提出了一个并行的模拟/数字硬件架构，专门设计来解决这些问题。我们将约束满足问题视为使用数字脉冲或事件进行通信的定型节点网络。每个节点包含一个使用模拟电路实现的振荡器。振子之间的非重复相位关系驱动解空间的探索。我们表明，这种硬件架构可以产生国家的最先进的随机SAT问题的性能在合理的假设下的实施。我们目前的测量从一个原型电子芯片，以证明所提出的架构的物理实现是强大的实际非理想，并验证所提出的理论。约束满足问题通常使用传统的冯·诺依曼计算架构来解决，然而这些架构不适合解决它们。在这里，作者提出了一个原型的基于事件的架构，产生最先进的性能随机SAT问题。
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. Constraint satisfaction problems are typically solved using conventional von Neumann computing architectures, which are however ill-suited to solving them. Here, the authors present a prototype for an event-based architecture that yield state of the art performance on random SAT problems.