Analog Approach to Constraint Satisfaction Enabled by Spin Orbit Torque Magnetic Tunnel Junctions

Abstract 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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Parami Wijesinghe, Chamika Liyanagedera, Kaushik Roy
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2018
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/c3e6a1b8ed9e493b9d85cbc2bf45a2c6
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:c3e6a1b8ed9e493b9d85cbc2bf45a2c6
record_format	dspace
spelling	oai:doaj.org-article:c3e6a1b8ed9e493b9d85cbc2bf45a2c62021-12-02T15:09:05ZAnalog Approach to Constraint Satisfaction Enabled by Spin Orbit Torque Magnetic Tunnel Junctions10.1038/s41598-018-24877-z2045-2322https://doaj.org/article/c3e6a1b8ed9e493b9d85cbc2bf45a2c62018-05-01T00:00:00Zhttps://doi.org/10.1038/s41598-018-24877-zhttps://doaj.org/toc/2045-2322Abstract 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).Parami WijesingheChamika LiyanagederaKaushik RoyNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 8, Iss 1, Pp 1-12 (2018)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Parami Wijesinghe Chamika Liyanagedera Kaushik Roy Analog Approach to Constraint Satisfaction Enabled by Spin Orbit Torque Magnetic Tunnel Junctions
description	Abstract 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).
format	article
author	Parami Wijesinghe Chamika Liyanagedera Kaushik Roy
author_facet	Parami Wijesinghe Chamika Liyanagedera Kaushik Roy
author_sort	Parami Wijesinghe
title	Analog Approach to Constraint Satisfaction Enabled by Spin Orbit Torque Magnetic Tunnel Junctions
title_short	Analog Approach to Constraint Satisfaction Enabled by Spin Orbit Torque Magnetic Tunnel Junctions
title_full	Analog Approach to Constraint Satisfaction Enabled by Spin Orbit Torque Magnetic Tunnel Junctions
title_fullStr	Analog Approach to Constraint Satisfaction Enabled by Spin Orbit Torque Magnetic Tunnel Junctions
title_full_unstemmed	Analog Approach to Constraint Satisfaction Enabled by Spin Orbit Torque Magnetic Tunnel Junctions
title_sort	analog approach to constraint satisfaction enabled by spin orbit torque magnetic tunnel junctions
publisher	Nature Portfolio
publishDate	2018
url	https://doaj.org/article/c3e6a1b8ed9e493b9d85cbc2bf45a2c6
work_keys_str_mv	AT paramiwijesinghe analogapproachtoconstraintsatisfactionenabledbyspinorbittorquemagnetictunneljunctions AT chamikaliyanagedera analogapproachtoconstraintsatisfactionenabledbyspinorbittorquemagnetictunneljunctions AT kaushikroy analogapproachtoconstraintsatisfactionenabledbyspinorbittorquemagnetictunneljunctions
_version_	1718387964046737408

Analog Approach to Constraint Satisfaction Enabled by Spin Orbit Torque Magnetic Tunnel Junctions

Ejemplares similares