Computing high-degree polynomial gradients in memory

Area of Science:

• Computer Engineering
• Hardware Acceleration
• Optimization Algorithms

Background:

• Existing hardware for optimization is limited to quadratic polynomials.
• Higher-order polynomial functions are common in complex optimization problems.
• Scalability and efficiency are key challenges in current hardware implementations.

Purpose of the Study:

• To propose a novel hardware approach for massively parallel gradient computation of high-degree polynomials.
• To enable efficient mixed-signal in-memory computing circuit implementations.
• To achieve hardware area scaling independent of polynomial degree.

Main Methods:

• Developed two flavors of parallel gradient computation approaches for high-degree polynomials.
• Implemented a third-order Boolean satisfiability problem solver using metal-oxide memristor crossbar circuits.
• Validated the approach with competitive heuristics algorithms and large-scale simulations.

Main Results:

• Experimental demonstration on a small-scale Boolean satisfiability problem.
• Simulation results show orders of magnitude improvement in area, speed, and energy efficiency.
• Hardware area scales with problem size, independent of polynomial degree.

Conclusions:

• The proposed hardware approach significantly enhances performance for optimization algorithms.
• This work paves the way for higher-performance systems through co-design of algorithms and hardware.
• The approach is particularly suited for combinatorial optimization problems with binary variables.