文章基本信息

标题：Analog Approach to Constraint Satisfaction Enabled by Spin Orbit Torque Magnetic Tunnel Junctions
本地全文：下载
作者：Parami Wijesinghe ; Chamika Liyanagedera ; Kaushik Roy 等
期刊名称：Scientific Reports
电子版ISSN：2045-2322
出版年度：2018
卷号：8
期号：1
页码：6940
DOI：10.1038/s41598-018-24877-z
语种：English
出版社：Springer Nature
摘要：Boolean satisfiability (k-SAT) is an NP-complete (k ≥ 3) problem that constitute one of the hardest classes of constraint satisfaction problems. In this work, we provide a proof of concept hardware based analog k-SAT solver, that is built using Magnetic Tunnel Junctions (MTJs). The inherent physics of MTJs, enhanced by device level modifications, is harnessed here to emulate the intricate dynamics of an analog satisfiability (SAT) solver. In the presence of thermal noise, the MTJ based system can successfully solve Boolean satisfiability problems. Most importantly, our results exhibit that, the proposed MTJ based hardware SAT solver is capable of finding a solution to a significant fraction (at least 85%) of hard 3-SAT problems, within a time that has a polynomial relationship with the number of variables(<50).