Solving Vertex Cover via Ising Model on a Neuromorphic Processor
Solving Vertex Cover via Ising Model on a Neuromorphic Processor
复制标题
DOI：
10.1109/iscas.2018.8351248
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
Kevin Corder;John V. Monaco;Manuel M. Vindiola
中科院分区：
文献类型：
--
作者：
Kevin Corder;John V. Monaco;Manuel M. Vindiola
神经形态架构的特征在于异步计算单元的网络，其类似于大脑中神经元的行为。随着大量的兴趣致力于这些架构如何可以利用在学习和智能系统，我们注意到，神经形态架构的大规模并行性也可以被利用来解决一些NP问题比冯诺依曼架构更有效。在这项工作中，我们演示了如何神经形态处理器可以用来解决经典的顶点覆盖问题，通过伊辛自旋模型。将伊辛模型映射到神经架构本身需要在初始化时解决两个NP难题，我们使用近似解。最大扇入和扇出约束，常见的许多神经形态处理器，需要一个图形分区，并解决时间依赖性的约束，在更新的图形相当于一个图形着色问题。结果，空间和时间效率仅以恒定因子降低，而不会降低解的质量。
Neuromorphic architectures are characterized by a network of asynchronous computation units that resemble the behavior of neurons in the brain. With much interest devoted to how these architectures can be utilized in learning and intelligent systems, we note that the massive parallelism of neuromorphic architectures can also be leveraged to solve some NP problems more efficiently than on a von Neumann architecture. In this work, we demonstrate how a neuromorphic processor can be used to solve the classic vertex cover problem via an Ising spin model. Mapping the Ising model to a neural architecture itself requires solving two NP-hard problems at initialization, for which we use approximate solutions. The maximum fan-in and fan-out constraint, common on many neuromorphic processors, requires a graph partitioning, and solving the time-dependency constraints in updating the graph amounts to a graph coloring problem. As a result, space and time efficiency is decreased only by a constant factor without degrading solution quality.