Parallel Boolean Matrix Multiplication In Linear Time Using Rectifying Memristors

Abstract

Boolean matrix multiplication (BMM) is a fundamental problem with applications in graph theory, group testing, data compression, and digital signal processing (DSP). The search for efficient BMM algorithms has produced several fast, albeit impractical, algorithms with sub-cubic time complexity. In this paper, we propose a memristor-crossbar framework for computing BMM at the hardware level in linear time. Our design leverages the diode-like characteristics of recently studied rectifying memristors to resolve the pervasive sneak paths constraint that is ubiquitous in crossbar computing.

Publication Date

7-29-2016

Publication Title

Proceedings - IEEE International Symposium on Circuits and Systems

Volume

2016-July

Number of Pages

1874-1877

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/ISCAS.2016.7538937

Socpus ID

84983390336 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84983390336

This document is currently not available here.

Share

COinS