The goal of this research is to develop a methodology to solve in real-time linear and quadratic programming (LP and QP) problems with an analog circuit. Simple and straight forward computation tasks can be done quickly with digital hardware, but as the complexity builds up, certain tasks demand long computing time (particularly optimization problems). Some of these tasks can be solved significantly faster using analog computer. Indeed, we have shown that a quadratic optimization task can be solved with an analog circuit many orders of magnitude faster than with a CPU. Using analog technology, a solution to real-time optimization problems can be obtained in a few microseconds and ongoing work aims to reduce it to a few nanoseconds, which is lower than any current method known to us. Digital computers are based on a sequential computation paradigm, which assumes that every computation is a sequence of operations. The sequential computation paradigm leads to iterative algorithms, which are major contributors to high latency. Analog computers do not necessarily follow the sequential computation paradigm. For example, the optimization circuit reaches an equilibrium using a simultaneous multi-way interaction between all parts of the problem and the solution is obtained in a single “iteration”, unlike digital computers that require multiple iterations. The proposed method expresses an optimization problem as an equivalent electric circuit whose steady state voltages are solution of the optimization problem. Everything that requires repeated low-latency solution of similar problems is a potential application for analog optimization technology. Possible applications of the new technology are fast and power-efficient analog signal processing (e.g. Kalman filter), image processing (e.g. optical flow, mathematical morphology), advanced control (e.g. model predictive control), error correcting decoders (LDPC) and more.
Radically low latency can be achieved when the circuit is made in a nanoscale, using standard VLSI technologies. This project, done in cooperation with prof. Elad Alon and Kristel Deems from the EECS department, is to build a chip that solves a QP problem with speed typical for analog VLSI - hundreds of MHz up to a few GHz. |

Research >