Computing High-Degree Polynomial Gradients in Memory

arXiv (Cornell University)

Abstract

Specialized function gradient computing hardware could greatly improve the performance of state-of-the-art optimization algorithms, e.g., based on gradient descent or conjugate gradient methods that are at the core of control, machine learning, and operations research applications. Prior work on such hardware, performed in the context of the Ising Machines and related concepts, is limited to quadratic polynomials and not scalable to commonly used higher-order functions. Here, we propose a novel approach for massively parallel gradient calculations of high-degree polynomials, which is conducive to efficient mixed-signal in-memory computing circuit implementations and whose area complexity scales linearly with the number of variables and terms in the function and, most importantly, independent of its degree. Two flavors of such an approach are proposed. The first is limited to binary-variable polynomials typical in combinatorial optimization problems, while the second type is broader at the cost of a more complex periphery. To validate the former approach, we experimentally demonstrated solving a small-scale third-order Boolean satisfiability problem based on integrated metal-oxide memristor crossbar circuits, one of the most prospective in-memory computing device technologies, with a competitive heuristics algorithm. Simulation results for larger-scale, more practical problems show orders of magnitude improvements in the area, and related advantages in speed and energy efficiency compared to the state-of-the-art. We discuss how our work could enable even higher-performance systems after co-designing algorithms to exploit massively parallel gradient computation.

Authors 8

1. George Hutchinson

   University of California, Santa Barbara

   Affiliation as printed

   Department of Electrical and Computer Engineering , University of California at Santa Barbara , Santa Barbara , CA 93106 , USA;

2. Giacomo Pedretti

   Hewlett-Packard (United States)

   Affiliation as printed

   Artificial Intelligence Research Lab , Hewlett Packard Labs , Milpitas , CA , USA;

3. Xia Sheng

   Hewlett-Packard (United States)

   Affiliation as printed

   Artificial Intelligence Research Lab , Hewlett Packard Labs , Milpitas , CA , USA;

4. Jim Ignowski

   Hewlett-Packard (United States)

   Affiliation as printed

   Artificial Intelligence Research Lab , Hewlett Packard Labs , Milpitas , CA , USA;

5. Thomas Van Vaerenbergh

   Hewlett-Packard (United States)

   Affiliation as printed

   Large Scale Integrated Photonics , Hewlett Packard Labs , Milpitas , CA , USA;

6. Raymond G. Beausoleil

   Hewlett-Packard (United States)

   Affiliation as printed

   Large Scale Integrated Photonics , Hewlett Packard Labs , Milpitas , CA , USA;

7. John Paul Strachan Aachen Peter Grünberg Institut (PGI-14) and

   RWTH Aachen University

   Affiliation as printed

   Peter Grünberg Institut (PGI-14) and RWTH Aachen University , Germany

8. Dmitri B. Strukov

   University of California, Santa Barbara

   Affiliation as printed

   Department of Electrical and Computer Engineering , University of California at Santa Barbara , Santa Barbara , CA 93106 , USA;