A Reconfigurable Analog Substrate for Highly Efficient Maximum Flow Computation

dc.contributor.author	Liu, Gai
dc.contributor.author	Zhang, Zhiru
dc.date.accessioned	2015-12-25T20:22:55Z
dc.date.available	2015-12-25T20:22:55Z
dc.date.issued	2015-12
dc.description.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.	en_US
dc.identifier.uri	https://hdl.handle.net/1813/41513
dc.language.iso	en_US	en_US
dc.subject	Analog computing	en_US
dc.subject	Optimization	en_US
dc.subject	Computer architecture	en_US
dc.title	A Reconfigurable Analog Substrate for Highly Efficient Maximum Flow Computation	en_US
dc.type	technical report	en_US

Files

Now showing 1 - 1 of 1