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.
- Core Generator guide, 2010 http://www.xilinx.com/itp/xilinx6/books/docs/cgn/cgn.pdf.Google Scholar
- Virtex-6 family overview, 2010 http://www.xilinx.com/support/documentation/data_sheets/ds150.pdf.Google Scholar
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- S. P. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, Cambridge, UK, 2004. Google ScholarDigital Library
- B. Fisher. Polynomial based iteration methods for symmetric linear systems. Wiley, Baltimore, MD, USA, 1996.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- S. L. Koh. Solving interior point method on a FPGA. Master's thesis, Nanyang Technological University, Singapore, 2009.Google Scholar
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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. Google ScholarDigital Library
- J. Maciejowski. Predictive Control with Constraints. Pearson Education, Harlow, UK, 2001.Google Scholar
- S. Mehrotra. On the implementation of a primal-dual interior point method. SIAM Journal on Optimization, 2(4):575--601, Nov 1992.Google ScholarDigital Library
- J. Nocedal and S. J. Wright. Numerical Optimization. Springer, New York, USA, 2006.Google Scholar
- 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.Google ScholarCross Ref
- S. J. Wright. Applying new optimization algorithms to model predictive control. In Proc. Int. Conf. Chemical Process Control, pages 147--155. CACHE Publications, 1997.Google Scholar
- S. J. Wright. Primal-Dual Interior-Point Methods. SIAM, Philadelphia, USA, 1997. Google ScholarDigital Library
Index Terms
- An FPGA implementation of a sparse quadratic programming solver for constrained predictive control
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