research-article

An FPGA implementation of a sparse quadratic programming solver for constrained predictive control

Authors:

Juan Luis Jerez,

George Anthony Constantinides,

Eric C. KerriganAuthors Info & Claims

FPGA '11: Proceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays

Pages 209 - 218

https://doi.org/10.1145/1950413.1950454

Published: 27 February 2011 Publication History

Abstract

Model predictive control (MPC) is an advanced industrial control technique that relies on the solution of a quadratic programming (QP) problem at every sampling instant to determine the input action required to control the current and future behaviour of a physical system. Its ability in handling large multiple input multiple output (MIMO) systems with physical constraints has led to very successful applications in slow processes, where there is sufficient time for solving the optimization problem between sampling instants. The application of MPC to faster systems, which adds the requirement of greater sampling frequencies, relies on new ways of finding faster solutions to QP problems. Field-programmable gate arrays (FPGAs) are specially well suited for this application due to the large amount of computation for a small amount of I/O. In addition, unlike a software implementation, an FPGA can provide the precise timing guarantees required for interfacing the controller to the physical system. We present a high-throughput floating-point FPGA implementation that exploits the parallelism inherent in interior-point optimization methods. It is shown that by considering that the QPs come from a control formulation, it is possible to make heavy use of the sparsity in the problem to save computations and reduce memory requirements by 75%. The implementation yields a 6.5x improvement in latency and a 51x improvement in throughput for large problems over a software implementation running on a general purpose microprocessor.

References

[1]

Core Generator guide, 2010 http://www.xilinx.com/itp/xilinx6/books/docs/cgn/cgn.pdf.

[2]

Virtex-6 family overview, 2010 http://www.xilinx.com/support/documentation/data_sheets/ds150.pdf.

[3]

S. Bayliss, C. S. Bouganis, and G. A. Constantinides. An FPGA implementation of the Simplex algorithm. In Proc. Int. Conf. on Field Programmable Technology, pages 49--55, Bangkok, Thailand, Dec 2006.

[4]

D. Boland and G. A. Constantinides. An FPGA-based implementation of the MINRES algorithm. In Proc. Int. Conf. on Field Programmable Logic and Applications, pages 379--384, Heidelberg, Germany, Sep 2008.

[5]

D. Boland and G. A. Constantinides. Optimising memory bandwidth use for matrix-vector multiplication in iterative methods. In Proc. Int. Symp. on Applied Reconfigurable Computing, pages 169--181, Bangkok, Thailand, Mar 2010.

Digital Library

[6]

S. P. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, UK, 2004.

Digital Library

[7]

B. Fisher. Polynomial based iteration methods for symmetric linear systems. Wiley, Baltimore, MD, USA, 1996.

[8]

T. A. Johansen, W. Jackson, and P. T. Robert Schreiber. Hardware synthesis of explicit model predictive controllers. IEEE Transactions on Control Systems Technolog, 15(1):191--197, Jan 2007.

[9]

T. Keviczky and G. J. Balas. Receding horizon control of an F-16 aircraft: A comparative study. Control Engineering Practice, 14(9):1023--1033, Sep 2006.

[10]

G. Knagge, A. Wills, A. Mills, and B. Ninnes. ASIC and FPGA implementation strategies for model predictive control. In Proc. European Control Conference, Budapest, Hungary, Aug 2009.

[11]

S. L. Koh. Solving interior point method on a FPGA. Master's thesis, Nanyang Technological University, Singapore, 2009.

[12]

M. S. Lau, S. P. Yue, K.-V. Ling, and J. M. Maciejowski. A comparison of interior point and active set methods for FPGA implementation of model predictive control. In Proc. European Control Conference, pages 156--160, Budapest, Hungary, Aug 2009.

[13]

B. Leung, C.-H. Wu, S. O. Memik, and S. Mehrotra. An interior point optimization solver for real time inter-frame collision detection: Exploring resource-accuracy-platform tradeoffs. In Proc. Int. Conf. on Field Programmable Logic and Applications, pages 113--118, Milano, Italy, Sep 2010.

Digital Library

[14]

K.-V. Ling, B. F. Wu, and J. M. Maciejowski. Embedded model predictive control (MPC) using a FPGA. In Proc. 17th IFAC World Congress, pages 15250--15255, Seoul, Korea, Jul 2008.

[15]

K.-V. Ling, S. P. Yue, and J. M. Maciejowski. An FPGA implementation of model predictive control. In Proc. American Control Conference, page 6 pp., Minneapolis, USA, Jun 2006.

[16]

A. R. Lopes and G. A. Constantinides. A high throughput FPGA-based floating-point conjugate gradient implementation for dense matrices. In Proc. 4th Int. Workshop on Applied Reconfigurable Computing, pages 75--86, London, UK, Mar 2008.

Digital Library

[17]

J. Maciejowski. Predictive Control with Constraints. Pearson Education, Harlow, UK, 2001.

[18]

S. Mehrotra. On the implementation of a primal-dual interior point method. SIAM Journal on Optimization, 2(4):575--601, Nov 1992.

Digital Library

[19]

J. Nocedal and S. J. Wright. Numerical Optimization. Springer, New York, USA, 2006.

[20]

P. D. Vouzis, L. G. Bleris, M. G. Arnold, and M. V. Kothare. A system-on-a-chip implementation for embedded real-time model predictive control. IEEE Transactions on Control Systems Technology, 17(5):1006--1017, Sep 2009.

[21]

S. J. Wright. Applying new optimization algorithms to model predictive control. In Proc. Int. Conf. Chemical Process Control, pages 147--155. CACHE Publications, 1997.

[22]

S. J. Wright. Primal-Dual Interior-Point Methods. SIAM, Philadelphia, USA, 1997.

Digital Library

Cited By

Xiang YChung HLin H(2024)Light Implementation Scheme of ANN-Based Explicit Model-Predictive Control for DC–DC Power ConvertersIEEE Transactions on Industrial Informatics10.1109/TII.2023.331965420:3(4065-4078)Online publication date: Mar-2024
https://doi.org/10.1109/TII.2023.3319654
Xiang YChung HLin H(2024)On the Use of DualReLU ANN for Approximating Explicit Model Predictive Control for Buck Converters2024 IEEE Applied Power Electronics Conference and Exposition (APEC)10.1109/APEC48139.2024.10509403(2822-2827)Online publication date: 25-Feb-2024
https://doi.org/10.1109/APEC48139.2024.10509403
Wang MMcInerney IStellato BBoyd SSo HSolihin YHeinrich M(2023)RSQP: Problem-specific Architectural Customization for Accelerated Convex Quadratic OptimizationProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589108(1-12)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589108
Show More Cited By

Index Terms

An FPGA implementation of a sparse quadratic programming solver for constrained predictive control
1. Hardware

Recommendations

Nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations

We propose in this paper a general D.C. decomposition scheme for constructing SDP relaxation formulations for a class of nonconvex quadratic programs with a nonconvex quadratic objective function and convex quadratic constraints. More specifically, we ...
Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons

At the intersection of nonlinear and combinatorial optimization, quadratic programming has attracted significant interest over the past several decades. A variety of relaxations for quadratically constrained quadratic programming (QCQP) can be ...
Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FPGA '11: Proceedings of the 19th ACM/SIGDA international symposium on Field programmable gate arrays

February 2011

300 pages

ISBN:9781450305549

DOI:10.1145/1950413

General Chair:
John Wawrzynek
University of California, Berkeley, USA
,
Program Chair:
Katherine Compton
University of Wisconsin-Madison, USA

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 February 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FPGA '11

Sponsor:

SIGDA

FPGA '11: ACM/SIGDA International Symposium on Field Programmable Gate Arrays

February 27 - March 1, 2011

CA, Monterey, USA

Acceptance Rates

Overall Acceptance Rate 125 of 627 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
569
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)3

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xiang YChung HLin H(2024)Light Implementation Scheme of ANN-Based Explicit Model-Predictive Control for DC–DC Power ConvertersIEEE Transactions on Industrial Informatics10.1109/TII.2023.331965420:3(4065-4078)Online publication date: Mar-2024
https://doi.org/10.1109/TII.2023.3319654
Xiang YChung HLin H(2024)On the Use of DualReLU ANN for Approximating Explicit Model Predictive Control for Buck Converters2024 IEEE Applied Power Electronics Conference and Exposition (APEC)10.1109/APEC48139.2024.10509403(2822-2827)Online publication date: 25-Feb-2024
https://doi.org/10.1109/APEC48139.2024.10509403
Wang MMcInerney IStellato BBoyd SSo HSolihin YHeinrich M(2023)RSQP: Problem-specific Architectural Customization for Accelerated Convex Quadratic OptimizationProceedings of the 50th Annual International Symposium on Computer Architecture10.1145/3579371.3589108(1-12)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3579371.3589108
Zhu ZKlein ALi GPang S(2023)Fixed-point iterative linear inverse solver with extended precisionScientific Reports10.1038/s41598-023-32338-513:1Online publication date: 30-Mar-2023
https://doi.org/10.1038/s41598-023-32338-5
Ozkaptan CEkici EAltintas O(2022)Adaptive Waveform Design for Communication-Enabled Automotive RadarsIEEE Transactions on Wireless Communications10.1109/TWC.2021.312592421:6(3965-3978)Online publication date: Jun-2022
https://doi.org/10.1109/TWC.2021.3125924
Zhang HZheng HLi SZhang YZhao MCai X(2022)Lifetime improvement through adaptive reconfiguration for nonvolatile FPGAsJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2022.102532128:COnline publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1016/j.sysarc.2022.102532
Ozkaptan CEkici EAltintas O(2020)Enabling Communication via Automotive Radars: An Adaptive Joint Waveform Design ApproachIEEE INFOCOM 2020 - IEEE Conference on Computer Communications10.1109/INFOCOM41043.2020.9155527(1409-1418)Online publication date: Jul-2020
https://doi.org/10.1109/INFOCOM41043.2020.9155527
Deng HOhtsuka T(2020)ParNMPC – A parallel optimization toolkit for real-time nonlinear model predictive controlInternational Journal of Control10.1080/00207179.2020.1798019(1-32)Online publication date: 17-Jul-2020
https://doi.org/10.1080/00207179.2020.1798019
Hsiao YWu YLin C(2019)Energy-Efficient Beamforming Design for MU-MISO Mixed RF/VLC Heterogeneous Wireless NetworksIEEE Transactions on Signal Processing10.1109/TSP.2019.292061267:14(3770-3784)Online publication date: 15-Jul-2019
https://doi.org/10.1109/TSP.2019.2920612
de Lima TPeng HTait ANahmias MMiller HShastri BPrucnal P(2019)Machine Learning With Neuromorphic PhotonicsJournal of Lightwave Technology10.1109/JLT.2019.290347437:5(1515-1534)Online publication date: 1-Mar-2019
https://doi.org/10.1109/JLT.2019.2903474
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents