A low-computation-complexity, energy-efficient, and high-performance linear program solver using memristor crossbars

Ruizhe Cai, Ao Ren, Yanzhi Wang, Sucheta Soundarajan, Qinru Qiu, Bo Yuan, Paul Bogdan

Research output: ResearchConference contribution

Abstract

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.

LanguageEnglish (US)
Title of host publicationProceedings - 29th IEEE International System on Chip Conference, SOCC 2016
PublisherIEEE Computer Society
Pages317-322
Number of pages6
ISBN (Electronic)9781509013661
DOIs
StatePublished - Apr 19 2017
Event29th IEEE International System on Chip Conference, SOCC 2016 - Seattle, United States
Duration: Sep 6 2016Sep 9 2016

Other

Other29th IEEE International System on Chip Conference, SOCC 2016
CountryUnited States
CitySeattle
Period9/6/169/9/16

Fingerprint

Memristors
Linear equations
Linear programming
Scalability
Scheduling

ASJC Scopus subject areas

  • Hardware and Architecture
  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Cite this

Cai, R., Ren, A., Wang, Y., Soundarajan, S., Qiu, Q., Yuan, B., & Bogdan, P. (2017). A low-computation-complexity, energy-efficient, and high-performance linear program solver using memristor crossbars. In Proceedings - 29th IEEE International System on Chip Conference, SOCC 2016 (pp. 317-322). [7905500] IEEE Computer Society. DOI: 10.1109/SOCC.2016.7905500

A low-computation-complexity, energy-efficient, and high-performance linear program solver using memristor crossbars. / Cai, Ruizhe; Ren, Ao; Wang, Yanzhi; Soundarajan, Sucheta; Qiu, Qinru; Yuan, Bo; Bogdan, Paul.

Proceedings - 29th IEEE International System on Chip Conference, SOCC 2016. IEEE Computer Society, 2017. p. 317-322 7905500.

Research output: ResearchConference contribution

Cai, R, Ren, A, Wang, Y, Soundarajan, S, Qiu, Q, Yuan, B & Bogdan, P 2017, A low-computation-complexity, energy-efficient, and high-performance linear program solver using memristor crossbars. in Proceedings - 29th IEEE International System on Chip Conference, SOCC 2016., 7905500, IEEE Computer Society, pp. 317-322, 29th IEEE International System on Chip Conference, SOCC 2016, Seattle, United States, 9/6/16. DOI: 10.1109/SOCC.2016.7905500
Cai R, Ren A, Wang Y, Soundarajan S, Qiu Q, Yuan B et al. A low-computation-complexity, energy-efficient, and high-performance linear program solver using memristor crossbars. In Proceedings - 29th IEEE International System on Chip Conference, SOCC 2016. IEEE Computer Society. 2017. p. 317-322. 7905500. Available from, DOI: 10.1109/SOCC.2016.7905500
Cai, Ruizhe ; Ren, Ao ; Wang, Yanzhi ; Soundarajan, Sucheta ; Qiu, Qinru ; Yuan, Bo ; Bogdan, Paul. / A low-computation-complexity, energy-efficient, and high-performance linear program solver using memristor crossbars. Proceedings - 29th IEEE International System on Chip Conference, SOCC 2016. IEEE Computer Society, 2017. pp. 317-322
@inbook{27d73528b3da4e8a96afff7b4ea30049,
title = "A low-computation-complexity, energy-efficient, and high-performance linear program solver using memristor crossbars",
abstract = "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.",
author = "Ruizhe Cai and Ao Ren and Yanzhi Wang and Sucheta Soundarajan and Qinru Qiu and Bo Yuan and Paul Bogdan",
year = "2017",
month = "4",
doi = "10.1109/SOCC.2016.7905500",
pages = "317--322",
booktitle = "Proceedings - 29th IEEE International System on Chip Conference, SOCC 2016",
publisher = "IEEE Computer Society",

}

TY - CHAP

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

PY - 2017/4/19

Y1 - 2017/4/19

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

SP - 317

EP - 322

BT - Proceedings - 29th IEEE International System on Chip Conference, SOCC 2016

PB - IEEE Computer Society

ER -