TY - GEN
T1 - A low-computation-complexity, energy-efficient, and high-performance linear program solver using memristor crossbars
AU - Cai, Ruizhe
AU - Ren, Ao
AU - Wang, Yanzhi
AU - Soundarajan, Sucheta
AU - Qiu, Qinru
AU - Yuan, Bo
AU - Bogdan, Paul
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/7/2
Y1 - 2016/7/2
N2 - Linear programming is required in a wide variety of application including routing, scheduling, and various optimization problems. The primal-dual interior point (PDIP) method is state-of-the-art algorithm for solving linear programs, and can be decomposed to matrix-vector multiplication and solving systems of linear equations, both of which can be conducted by the emerging memristor crossbar technique in O(1) time complexity in the analog domain. This work is the first to apply memristor crossbar for linear program solving based on the PDIP method, which has been reformulated for memristor crossbars to compute in the analog domain. The proposed linear program solver can overcome limitations of memristor crossbars such as supporting only non-negative coefficients, and has been extended for higher scalability. The proposed solver is iterative and achieves O(N) computation complexity in each iteration. Experimental results demonstrate that reliable performance with high accuracy can be achieved under process variations.
AB - Linear programming is required in a wide variety of application including routing, scheduling, and various optimization problems. The primal-dual interior point (PDIP) method is state-of-the-art algorithm for solving linear programs, and can be decomposed to matrix-vector multiplication and solving systems of linear equations, both of which can be conducted by the emerging memristor crossbar technique in O(1) time complexity in the analog domain. This work is the first to apply memristor crossbar for linear program solving based on the PDIP method, which has been reformulated for memristor crossbars to compute in the analog domain. The proposed linear program solver can overcome limitations of memristor crossbars such as supporting only non-negative coefficients, and has been extended for higher scalability. The proposed solver is iterative and achieves O(N) computation complexity in each iteration. Experimental results demonstrate that reliable performance with high accuracy can be achieved under process variations.
UR - http://www.scopus.com/inward/record.url?scp=85019076915&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85019076915&partnerID=8YFLogxK
U2 - 10.1109/SOCC.2016.7905500
DO - 10.1109/SOCC.2016.7905500
M3 - Conference contribution
AN - SCOPUS:85019076915
T3 - International System on Chip Conference
SP - 317
EP - 322
BT - Proceedings - 29th IEEE International System on Chip Conference, SOCC 2016
A2 - Bhatia, Karan
A2 - Alioto, Massimo
A2 - Zhao, Danella
A2 - Marshall, Andrew
A2 - Sridhar, Ramalingam
PB - IEEE Computer Society
T2 - 29th IEEE International System on Chip Conference, SOCC 2016
Y2 - 6 September 2016 through 9 September 2016
ER -