A Reconfigurable Analog Substrate for Highly Efficient Maximum Flow Computation

Abstract

We present the design and analysis of a novel analog reconfigurable substrate that enables fast and efficient computation of maximum flow on directed graphs. The substrate is composed of memristors and standard analog circuit components, where the on/off states of the crossbar switches encode the graph topology. We show that upon convergence, the steady-state voltages in the circuit capture the solution to the maximum flow problem. We also propose techniques to minimize the impacts of variability and non-ideal circuit components on the solution quality, enabling practical implementation of the proposed substrate. Our performance evaluation indicates two to three orders of magnitude improvements in speed and energy efficiency compared to a standard CPU implementation. In the last part of this report, we also discuss the major limitations of the current design, and suggest promising research directions.