Algorithm-hardware Co-optimization of the memristor-based framework for solving SOCP and homogeneous QCQP problems

Ao Ren, Sijia Liu, Ruizhe Cai, Wujie Wen, Pramod K. Varshney, Yanzhi Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A memristor crossbar, which is constructed with memristor devices, has the unique ability to change and memorize the state of each of its memristor elements. It also has other highly desirable features such as high density, low power operation and excellent scalability. Hence the memristor crossbar technology can potentially be utilized for developing low-complexity and high-scalability solution frameworks for solving a large class of convex optimization problems, which involve extensive matrix operations and have critical applications in multiple disciplines. This paper, as the first attempt towards this direction, proposes a novel memristor crossbar-based framework for solving two important convex optimization problems, i.e., second-order cone programming (SOCP) and homogeneous quadratically constrained quadratic programming (QCQP) problems. In this paper, the alternating direction method of multipliers (ADMM) is adopted. It splits the SOCP and homogeneous QCQP problems into sub-problems that involve the solution of linear systems, which could be effectively solved using the memristor crossbar in O(1) time complexity. The proposed algorithm is an iterative procedure that iterates a constant number of times. Therefore, algorithms to solve SOCP and homogeneous QCQP problems have pseudo-O(N) complexity, which is a significant reduction compared to the state-of-the-art software solvers (O(N3.5) - O(N4)).

Original languageEnglish (US)
Title of host publication2017 22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages788-793
Number of pages6
ISBN (Electronic)9781509015580
DOIs
StatePublished - Feb 16 2017
Event22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017 - Chiba, Japan

Other

Other22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017
CountryJapan
CityChiba
Period1/16/171/19/17

Fingerprint

Memristors
Quadratic programming
Cones
Convex optimization
Scalability
Linear systems
Hardware

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Cite this

Ren, A., Liu, S., Cai, R., Wen, W., Varshney, P. K., & Wang, Y. (2017). Algorithm-hardware Co-optimization of the memristor-based framework for solving SOCP and homogeneous QCQP problems. In 2017 22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017 (pp. 788-793). [7858420] Institute of Electrical and Electronics Engineers Inc.. DOI: 10.1109/ASPDAC.2017.7858420

Algorithm-hardware Co-optimization of the memristor-based framework for solving SOCP and homogeneous QCQP problems. / Ren, Ao; Liu, Sijia; Cai, Ruizhe; Wen, Wujie; Varshney, Pramod K.; Wang, Yanzhi.

2017 22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 788-793 7858420.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Ren, A, Liu, S, Cai, R, Wen, W, Varshney, PK & Wang, Y 2017, Algorithm-hardware Co-optimization of the memristor-based framework for solving SOCP and homogeneous QCQP problems. in 2017 22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017., 7858420, Institute of Electrical and Electronics Engineers Inc., pp. 788-793, 22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017, Chiba, Japan, 16-19 January. DOI: 10.1109/ASPDAC.2017.7858420
Ren A, Liu S, Cai R, Wen W, Varshney PK, Wang Y. Algorithm-hardware Co-optimization of the memristor-based framework for solving SOCP and homogeneous QCQP problems. In 2017 22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017. Institute of Electrical and Electronics Engineers Inc.2017. p. 788-793. 7858420. Available from, DOI: 10.1109/ASPDAC.2017.7858420

Ren, Ao; Liu, Sijia; Cai, Ruizhe; Wen, Wujie; Varshney, Pramod K.; Wang, Yanzhi / Algorithm-hardware Co-optimization of the memristor-based framework for solving SOCP and homogeneous QCQP problems.

2017 22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017. Institute of Electrical and Electronics Engineers Inc., 2017. p. 788-793 7858420.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

@inbook{4f115eebdfca4a9db6d64e33fc20285d,
title = "Algorithm-hardware Co-optimization of the memristor-based framework for solving SOCP and homogeneous QCQP problems",
abstract = "A memristor crossbar, which is constructed with memristor devices, has the unique ability to change and memorize the state of each of its memristor elements. It also has other highly desirable features such as high density, low power operation and excellent scalability. Hence the memristor crossbar technology can potentially be utilized for developing low-complexity and high-scalability solution frameworks for solving a large class of convex optimization problems, which involve extensive matrix operations and have critical applications in multiple disciplines. This paper, as the first attempt towards this direction, proposes a novel memristor crossbar-based framework for solving two important convex optimization problems, i.e., second-order cone programming (SOCP) and homogeneous quadratically constrained quadratic programming (QCQP) problems. In this paper, the alternating direction method of multipliers (ADMM) is adopted. It splits the SOCP and homogeneous QCQP problems into sub-problems that involve the solution of linear systems, which could be effectively solved using the memristor crossbar in O(1) time complexity. The proposed algorithm is an iterative procedure that iterates a constant number of times. Therefore, algorithms to solve SOCP and homogeneous QCQP problems have pseudo-O(N) complexity, which is a significant reduction compared to the state-of-the-art software solvers (O(N3.5) - O(N4)).",
author = "Ao Ren and Sijia Liu and Ruizhe Cai and Wujie Wen and Varshney, {Pramod K.} and Yanzhi Wang",
year = "2017",
month = "2",
doi = "10.1109/ASPDAC.2017.7858420",
pages = "788--793",
booktitle = "2017 22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - CHAP

T1 - Algorithm-hardware Co-optimization of the memristor-based framework for solving SOCP and homogeneous QCQP problems

AU - Ren,Ao

AU - Liu,Sijia

AU - Cai,Ruizhe

AU - Wen,Wujie

AU - Varshney,Pramod K.

AU - Wang,Yanzhi

PY - 2017/2/16

Y1 - 2017/2/16

N2 - A memristor crossbar, which is constructed with memristor devices, has the unique ability to change and memorize the state of each of its memristor elements. It also has other highly desirable features such as high density, low power operation and excellent scalability. Hence the memristor crossbar technology can potentially be utilized for developing low-complexity and high-scalability solution frameworks for solving a large class of convex optimization problems, which involve extensive matrix operations and have critical applications in multiple disciplines. This paper, as the first attempt towards this direction, proposes a novel memristor crossbar-based framework for solving two important convex optimization problems, i.e., second-order cone programming (SOCP) and homogeneous quadratically constrained quadratic programming (QCQP) problems. In this paper, the alternating direction method of multipliers (ADMM) is adopted. It splits the SOCP and homogeneous QCQP problems into sub-problems that involve the solution of linear systems, which could be effectively solved using the memristor crossbar in O(1) time complexity. The proposed algorithm is an iterative procedure that iterates a constant number of times. Therefore, algorithms to solve SOCP and homogeneous QCQP problems have pseudo-O(N) complexity, which is a significant reduction compared to the state-of-the-art software solvers (O(N3.5) - O(N4)).

AB - A memristor crossbar, which is constructed with memristor devices, has the unique ability to change and memorize the state of each of its memristor elements. It also has other highly desirable features such as high density, low power operation and excellent scalability. Hence the memristor crossbar technology can potentially be utilized for developing low-complexity and high-scalability solution frameworks for solving a large class of convex optimization problems, which involve extensive matrix operations and have critical applications in multiple disciplines. This paper, as the first attempt towards this direction, proposes a novel memristor crossbar-based framework for solving two important convex optimization problems, i.e., second-order cone programming (SOCP) and homogeneous quadratically constrained quadratic programming (QCQP) problems. In this paper, the alternating direction method of multipliers (ADMM) is adopted. It splits the SOCP and homogeneous QCQP problems into sub-problems that involve the solution of linear systems, which could be effectively solved using the memristor crossbar in O(1) time complexity. The proposed algorithm is an iterative procedure that iterates a constant number of times. Therefore, algorithms to solve SOCP and homogeneous QCQP problems have pseudo-O(N) complexity, which is a significant reduction compared to the state-of-the-art software solvers (O(N3.5) - O(N4)).

UR - http://www.scopus.com/inward/record.url?scp=85015347881&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85015347881&partnerID=8YFLogxK

U2 - 10.1109/ASPDAC.2017.7858420

DO - 10.1109/ASPDAC.2017.7858420

M3 - Conference contribution

SP - 788

EP - 793

BT - 2017 22nd Asia and South Pacific Design Automation Conference, ASP-DAC 2017

PB - Institute of Electrical and Electronics Engineers Inc.

ER -