IEEE Circuits and Systems Magazine - Q1 2018 - 30

equations in an astonishing O (1) time complexity [5]-[8].
The discovery and physical realization of memristors
has inspired the development of efficient approaches to
implement neuromorphic computing systems that can
mimic neuro-biological architectures and perform highperformance computing for deep neural networks and
optimization algorithms [9].
The similarity between the programmable resistance
state of memristors and the variable synaptic strengths
of biological synapses facilitates the circuit realization
of neural network models [10]. Nowadays, artificial neural networks have become an extremely popular machine learning tool with a wide spectrum of applications,
ranging from prediction/classification, computer vision,
natural language processing, image processing, to signal processing [11]. Encouraged by its success, many
researchers have attempted to design memristor-based
computing systems to accelerate neural network training
[12]-[22]. In [12], [13], memristor crossbars were used to
form an on-chip training circuit for an autoencoder, an
artificial neural network with one hidden layer. Training
a multi-layer neural network requires the implementation of a back-propagation algorithm [23] for synaptic
weight update. Such an implementation using memristor
crossbars was discussed in [14]-[18]. In [19], [20], a memristor-based neural network was proposed by using an
off-chip training approach where synaptic weights are
pre-trained in software. This approach avoided the complexity of mapping the back-propagation algorithm onto
memristors but did not fully utilize the computational
advantages of memristors. In [21], [22], research efforts
were made to overcome hardware restrictions, such as
scalability and routing congestion, to design memristorbased large neural networks.
In addition to artificial neural networks, memristorbased computing systems have also been proposed and
analyzed for sparse coding, dictionary learning, and
compressive sensing [24]-[30]. These applications share
a similar sparse learning framework, where a sparse
solution is sought to minimize a certain cost function.
In [24], a sparse coding algorithm was mapped to memristor crossbars. In [25]-[29], memristors were used to
achieve on-chip acceleration of dictionary learning algorithms. However, the algorithms required the memristor
network to be programmed multiple times due to the gradient update step which resulted in computation errors
caused by device variations. In [27], redundant memristors were employed to suppress these device variations.
Besides sparse learning, memristor crossbars have also

been considered for implementing and training a probabilistic graphical model [31] and image learning [32], [33].
Although memristor-inspired artificial intelligence (AI)
applications are different from one another, the common
underlying theme is the design of a mathematical programming solver for an optimization problem specified
by a machine learning or data processing task. Examples
include linear programming for portfolio optimization
[34], nonlinear programming for regression/classification [35], and regularized optimization for sparse learning [36]. Therefore, a general question to be answered
in this context is: how can one design a general memristor-based computation framework to accelerate the optimization procedure?
The interior-point algorithm is one of the most commonly-used optimization approaches implemented in
software. It begins at a point in the interior of the feasible
region, applies a projective transformation so that the
current interior point is the center of projective space,
and then moves in the direction of the steepest descent
[37]. However, inherent hardware limitations prevent
a direct mapping from the interior-point algorithm to
memristor crossbars. First, a memristor crossbar only
allows square matrices with nonnegative entries during
computation, since the memristance is always nonnegative. Second, the memristor crossbar suffers from hardware variations, which degrade the reading/writing accuracy of memristor crossbars. To circumvent the first
difficulty, additional memristors were used to represent
negative elements of a square matrix [8], [38], [39]. In
particular, the work [8] presented a memristor-based
linear solver using the interior-point algorithm, which,
however, requires programming of the resistance state
of memristors at every iteration. Consequently, the linear solver in [8] is prone to suffering from hardware
variations. Therefore, to successfully design memristor-based optimization solvers, it is crucial to co-optimize algorithm, device and architecture so that the
advantages of memristors can be fully utilized and the
design complexity and the non-ideal hardware effects
can be minimized. Our previous work [7], [30] showed
that the alternating direction method of multipliers
(ADMM) algorithm can take advantage of the hardware implementation of memristor crossbars. With the
aid of ADMM, one can decompose a complex problem
into subproblems that require matrix-vector multiplications and solution of systems of linear equations. The
decomposed operations are more easily mapped onto
memristor crossbars. In this paper, we discuss how to

S. Liu is with the Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI, 48019 USA. (e-mail: lsjxjtu@umich
.edu.) Y. Wang, M. Fardad and P. K. Varshney are with the Department of Electrical Engineering and Computer Science, Syracuse University (e-mail:
{makan,ywang393,varshney}@syr.edu.)

ieee circuits and systems magazine

first quarter 2018

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q1 2018