Dr Juan L. Jerez



Circuits & Systems Research Group
Electrical and Electronic Engineering Department
Supervisors: George A. Constantinides and Eric C. Kerrigan

Address:     EEE 905b

                    Imperial College London

                    South Kensington Campus

                    SW7 2BZ London, United Kingdom

Email:         jlj05@imperial.ac.uk

Phone:       +44 7403126034


Research Interests

My main research interest is in computational architectures for numerical linear algebra and optimization algorithms. Most of my research to date comprises an investigation into the interactions between digital circuit implementations and algorithm design. In particular, the design and use of custom computer architectures for efficiently implementing numerical optimization algorithms, and the design of custom optimization algorithms for reliable reduced precision implementations in embedded resource-constrained systems. The applications for real-time numerical optimization range from advanced control systems and signal processing to communications, finance or supply chain management.

Ph.D Thesis

Custom Optimization Algorithms for Efficient Hardware Implementation pdf

Publications

Please note that many of the items listed here are copyright IEEE, ACM, IET, Elsevier, IFAC or SIAM.

Journal papers

  • J. L. Jerez, P. J. Goulart, S. Richter, G. A. Constantinides, E. C. Kerrigan and M. Morari. Embedded Online Optimization for Model Predictive Control at Megahertz Rates. Submitted to IEEE Transactions on Automatic Control. arXiv
    Abstract
    » Faster, cheaper, and more power efficient optimization solvers than those currently offered by general-purpose solutions are required for extending the use of model predictive control (MPC) to resource-constrained embedded platforms. We propose several custom computational architectures for different first-order optimization methods that can handle linear-quadratic MPC problems with input, input-rate, and soft state constraints. We provide analysis ensuring the reliable operation of the resulting controller under reduced precision fixed-point arithmetic. Implementation of the proposed architectures in FPGAs shows that satisfactory control performance at a sample rate beyond 1 MHz is achievable even on low-end devices, opening up new possibilities for the application of MPC on embedded systems.

  • J. L. Jerez, G. A. Constantinides and E. C. Kerrigan. A Low Complexity Scaling Method for the Lanczos Kernel in Fixed-Point Arithmetic. IEEE Transactions on Computers.
    Abstract
    » We consider the problem of enabling fixed-point implementation of linear algebra kernels to enable implementation on low cost embedded systems and to motivate more efficient computational architectures for scientific applications. Fixed-point arithmetic presents additional design challenges compared to floating-point arithmetic, such as having to bound peak values of variables and control their dynamic ranges. Algorithms for solving linear equations or finding eigenvalues are typically nonlinear and iterative making solving these design challenges a non-trivial task. For these types of algorithms the bounding problem cannot be automated by current tools. We focus on the Lanczos iteration, the heart of well known methods such as conjugate gradient and minimum residual, and we show how we can modify the algorithm with a low complexity scaling procedure to allow us to apply standard linear algebra to prove tight analytical bounds on all variables of the process, regardless of the properties of the original matrix. It is shown that the numerical behaviour of fixed-point implementations of the modified problem can be chosen to be at least as good as a double precision floating point implementation, if necessary. The approach is evaluated on field- programmable gate array (FPGA) platforms, highlighting orders of magnitude potential performance and efficiency improvements by moving form floating-point to fixed-point computation.

  • E. Hartley, J. L. Jerez, A. Suardi, J. M. Maciejowski, E. C. Kerrigan and G. A. Constantinides. Predictive Control using an FPGA with Application to Aircraft Control. IEEE Transactions on Control Systems Technology. pdf Video demo
    Abstract
    » Different and more efficient computational methods could enable the use of MPC to be extended. This paper presents a system-on-a-chip MPC system, implemented on a field programmable gate array (FPGA), consisting of a structure-exploiting primal dual interior point (PDIP) QP solver for MPC reference tracking and a fast gradient QP solver for steady-state target calculation. A parallel reduced precision iterative solver is used to accelerate the solution of the set of linear equations forming the computational bottleneck of the PDIP algorithm. A numerical study highlights the feasibility of the approach. The system is demonstrated with a FPGA-in-the-loop testbench controlling a nonlinear simulation of a large airliner and the effect of reducing the number of MINRES iterations is investigated. This study considers a much larger plant than any prior FPGA-based MPC implementation to date, yet the implementation comfortably fits into a mid-range FPGA, and the controller compares favourably in terms of solution quality and latency to that of state-of-the-art QP solvers running on a conventional PC.

  • J. L. Jerez, K.-V. Ling, G. A. Constantinides and E. C. Kerrigan. Model Predictive Control for Deeply Pipelined Field-programmable Gate Array Implementation: Algorithms and Circuitry. IET Control Theory and Applications, 6(8), pages 1029-1041, Jul 2012. pdf
    Abstract
    » Model predictive control (MPC) is an optimisation-based scheme that imposes a real-time constraint on computing the solution of a quadratic programming (QP) problem. The implementation of MPC in fast embedded systems presents new technological challenges. In this paper we present a parameterised field-programmable gate array implementation of a customised QP solver for optimal control of linear processes with constraints, which can achieve substantial acceleration over a general purpose microprocessor, especially as the size of the optimisation problem grows. The focus is on exploiting the structure and accelerating the computational bottleneck in a primal-dual interior-point method. We then introduce a new MPC formulation that can take advantage of the novel computational opportunities, in the form of parallel computational channels, offered by the proposed pipelined architecture to improve performance even further. This highlights the importance of the interaction between the control theory and digital system design communities for the success of MPC in fast embedded systems.

  • J. L. Jerez, E. C. Kerrigan and G. A. Constantinides. A Sparse and Condensed QP Formulation for Predictive Control of LTI Systems. Automatica, 48(5), pages 999-1002, May 2012. pdf
    Abstract
    » The computational burden that model predictive control (MPC) imposes depends to a large extent on the way the optimal control problem is formulated as an optimization problem. We present a formulation where the input is expressed as an affine function of the state such that the closed-loop dynamics matrix becomes nilpotent. Using this approach and removing the equality constraints leads to a compact and sparse optimization problem to be solved at each sampling instant. The problem can be solved with a cost per interior-point iteration that is linear with respect to the horizon length, when this is bigger than the controllability index of the plant. The computational complexity of existing condensed approaches grow cubically with the horizon length, whereas existing non-condensed and sparse approaches also grow linearly, but with a greater proportionality constant than with the method presented here.

  • Conference papers

  • J. L. Jerez, P. J. Goulart, S. Richter, G. A. Constantinides, E. C. Kerrigan and M. Morari. Embedded Predictive Control on an FPGA using the Fast Gradient Method. Submitted to the 12th European Control Conference, Zurich, Switzerland, Jul 2013. pdf
    Abstract
    » The implementation of model predictive control (MPC) in resource-constrained embedded platforms requires faster, cheaper and more power-efficient solvers for convex programs than what is currently offered by software-based solutions. In this paper we present the first field programmable gate array (FPGA) implementation of a fast gradient solver for linear-quadratic predictive control with input constraints. We make use of fixed-point arithmetic to exploit the characteristics of the computing platform and provide analysis to guarantee that no overflow errors occur during operation. In addition, we prove that the arithmetic errors due to round-off can only lead to a loss of accuracy but do not cause instability of the fast gradient method. The results are demonstrated on a model of an industrial atomic force microscope where we show that, on a mid-range modern FPGA, satisfactory control performance at a sample rate beyond 1 MHz is achievable, opening up new possibilities for the application of predictive control. The findings of this paper can also be used for implementing fast gradient solvers on other low cost and low power platforms such as fixed-point digital signal processors (DSPs) and embedded microcontrollers.

  • J. L. Jerez, G. A. Constantinides and E. C. Kerrigan. Towards a Fixed-point QP Solver for Predictive Control. In Proc. 51st IEEE Conf. on Decision and Control, pages 675-680, Maui, HI, USA, Dec 2012. pdf
    Abstract
    » There is a need for high speed, low cost and low energy solutions for convex quadratic programming to enable model predictive control (MPC) to be implemented in a wider set of applications than is currently possible. For most quadratic programming (QP) solvers the computational bottleneck is the solution of systems of linear equations, which we propose to solve using a fixed-point implementation of an iterative linear solver to allow for fast and efficient computation in parallel hardware. However, fixed point arithmetic presents additional challenges, such as having to bound peak values of variables and constrain their dynamic ranges. For these types of algorithms the problems cannot be automated by current tools. We employ a preconditioner in a novel manner to allow us to establish tight analytical bounds on all the variables of the Lanczos process, the heart of modern iterative linear solving algorithms. The proposed approach is evaluated through the implementation of a mixed precision interior-point controller for a Boeing 747 aircraft. The numerical results show that there does not have to be a loss of control quality by moving from floating-point to fixed-point.

  • E. Hartley, J. L. Jerez, A. Suardi, J. M. Maciejowski, E. C. Kerrigan and G. A. Constantinides. Predictive Control of a Boeing 747 Aircraft using an FPGA. In Proc. IFAC Nonlinear Model Predictive Control Conference, pages 80-85, Noordwijkerhout, Netherlands, Aug 2012. pdf Video demo
    Abstract
    » New embedded predictive control applications call for more ecient ways of solving quadratic programs (QPs) in order to meet demanding real-time, power and cost requirements. A single precision QP-on-a-chip controller is proposed, implemented in a eld-programmable gate array (FPGA) with an iterative linear solver at its core. A novel oine scaling procedure is introduced to aid the convergence of the reduced precision solver. The feasibility of the proposed approach is demonstrated with a real-time hardware-in-the-loop (HIL) experimental setup where an ML605 FPGA board controls a nonlinear model of a Boeing 747 aircraft running on a desktop PC through an Ethernet link. Simulations show that the quality of the closed-loop control and accuracy of individual solutions is competitive with a conventional double precision controller solving linear systems using a Riccati recursion.

  • E. C. Kerrigan, J. L. Jerez, S. Longo and G. A. Constantinides. Number Representation in Predictive Control. In Proc. IFAC Nonlinear Model Predictive Control Conference, pages 60-67, Noordwijkerhout, Netherlands, Aug 2012. pdf
    Abstract
    » In predictive control a nonlinear optimization problem has to be solved at each sample instant. Solving this optimization problem in a computationally efficient and numerically reliable fashion on an embedded system is a challenging task. This paper presents results to reduce the computational requirements for solving fundamental problems that arise when implementing predictive controllers in finite precision arithmetic. By employing novel formulations and tailor-made optimization algorithms, this paper shows that computational resources can be reduced using very low precision arithmetic. We also present new mathematical results that enable computational savings to be made in the most numerically critical part of an optimization solver, namely the linear algebra kernel, using fixed-point arithmetic. Our theoretical results are supported by numerical results from implementations on a Field Programmable Gate Array (FPGA).

  • J. L. Jerez, G. A. Constantinides and E. C. Kerrigan. Fixed-Point Lanczos: Sustaining TFLOP-equivalent Performance in FPGAs for Scientific Computing. In Proc. 20th IEEE Symposium on Field-Programmable Custom Computing Machines, pages 53-60, Toronto, Canada, Apr 2012 - Acceptance Rate 22/121 = 18.2% pdf
    Abstract
    » We consider the problem of enabling fixedpoint implementations of linear algebra kernels to match the strengths of the field-programmable gate array (FPGA). Algorithms for solving linear equations, finding eigenvalues or finding singular values are typically nonlinear and recursive making the problem of establishing analytical bounds on variable dynamic range non-trivial. Current approaches fail to provide tight bounds for this type of algorithms. We use as a case study one of the most important kernels in scientific computing, the Lanczos iteration, which lies at the heart of well known methods such as conjugate gradient and minimum residual, and we show how we can modify the algorithm to allow us to apply standard linear algebra analysis to prove tight analytical bounds on all variables of the process, regardless of the properties of the original matrix. It is shown that the numerical behaviour of fixed-point implementations of the modified problem can be chosen to be at least as good as a double precision floating point implementation. Using this approach it is possible to get sustained FPGA performance very close to the peak general-purpose graphics processing unit (GPGPU) performance in FPGAs of comparable size when solving a single problem. If there are several independent problems to solve simultaneously it is possible to exceed the peak floating-point performance of a GPGPU, obtaining approximately 1, 2 or 4 TFLOPs for error tolerances of 10−7, 10−5 and 10−3, respectively, in a large Virtex 7 FPGA.

  • J. L. Jerez, E. C. Kerrigan and G. A. Constantinides. A Condensed and Sparse QP Formulation for Predictive Control. In Proc. 50th IEEE Conf. on Decision and Control, pages 5217-5222, Orlando, FL, USA, Dec 2011. pdf
    Abstract
    » The computational burden that model predictive control (MPC) imposes depends to a large extent on the way the optimal control problem is formulated as an optimization problem. In this paper, we present a new formulation that results in a compact and sparse optimization problem to be solved at each sampling interval. The approach is based on a change of variables that leads to a block banded Hessian when the horizon length is bigger than the controllability index of the plant. In this case the problem can be solved with an interiorpoint method in time linear in the horizon length. Existing dense approaches grow cubically with the horizon length, whereas existing sparse approaches grow at a significantly greater rate than with the method presented here.

  • J. L. Jerez, G. A. Constantinides, E. C. Kerrigan and K.-V. Ling. Parallel MPC for Real-time FPGA-based Implementation. In Proc. IFAC World Congress, pages 1338-1343, Milano, Italy, Sep 2011. pdf
    Abstract
    » The succesful application of model predictive control (MPC) in fast embedded systems relies on faster and more energy efficient ways of solving complex optimization problems. A custom quadratic programming (QP) solver implementation on a field-programmable gate array (FPGA) can provide substantial acceleration by exploiting the parallelism inherent in some optimization algorithms, apart from providing novel computational opportunities arising from deep pipelining. This paper presents a new MPC algorithm based on multiplexed MPC that can take advantage of the full potential of an existing FPGA design by utilizing the provided ‘free’ parallel computational channels arising from such pipelining. The result is greater acceleration over a conventional MPC implementation and reduced silicon usage. The FPGA implementation is shown to be approximately 200x more energy efficient than a high performance general purpose processor (GPP) for large control problems.

  • J. L. Jerez, G. A. Constantinides and E. C. Kerrigan. An FPGA Implementation of a Sparse Quadratic Programming Solver for Constrained Predictive Control. In Proc. ACM Symposium on Field Programmable Gate Arrays, pages 209-218, Monterey, CA, USA, Mar 2011 - Acceptance Rate 21/82 = 25.6% pdf
    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.

  • J. L. Jerez, G. A. Constantinides and E. C. Kerrigan. FPGA Implementation of an Interior-Point Solver for Linear Model Predictive Control. In Proc. Int. Conf. on Field Programmable Technology, pages 316-319, Beijing, China, Dec 2010. pdf
    Abstract
    » Automatic control, the process of measuring, computing, and applying an input to control the behaviour of a physical system, is ubiquitous in engineering and industry. Model predictive control (MPC) is an advanced control technology that has been very successful in the chemical process industries due to its ability to handle large multiple input multiple output (MIMO) systems with physical constraints. It has recently been proposed to be applied to higher bandwidth systems, which add the requirement of greater sampling frequencies. The main hurdle is the need to solve a computationally intensive quadratic programming (QP) problem in real-time. In this paper we address the need for acceleration by proposing a highly efficient floating-point field-programmable gate array (FPGA) implementation that exploits the parallelism opportunities offered by interior-point optimization methods. The approach yields a 5x improvement in latency and a 40x improvement in throughput for large problems over a software implementation. This work builds on a previous FPGA implementation of an iterative linear solver, an operation at the heart of the interior-point method.

  • Other conference talks

  • J. L. Jerez. Embedded Optimization in Fixed-Point Arithmetic. In Int. Conf. on Continuous Optimization, Lisbon, Portugal, Jul 2013. pdf
    Abstract
    » Implementation of complex optimization-based real-time decision making is often not possible due to the limited computational capabilities of embedded computing platforms. Compared to widespread floating-point arithmetic, fundamentally more efficient fixed-point arithmetic can enable implementation in low cost devices and can result in significant performance improvements for meeting tight real-time deadlines. However, fixed-point arithmetic presents additional challenges, such as having to bound the peak value of each variable to prevent overflow errors. First, we show how the linearized KKT system, the solution of which forms the computational bottleneck in interior-point and active-set methods, can be altered to allow for reliable overflow-free fixed-point implementation. We then focus on first-order methods and present an analysis that enables one to predict a priori the numerical error introduced by a given word-length fixed-point implementation. For instance, this approach can allow for the implementation of online optimization-based controllers at megahertz sampling rates on a low cost device.

  • J. L. Jerez, G. A. Constantinides and E. C. Kerrigan. Fixed-Point Lanczos with Analytical Variable Bounds. In SIAM Conference on Applied Linear Algebra, Valencia, Spain, Jun 2012. pdf
    Abstract
    » We consider the problem of establishing analytical bounds on all variables calculated during the symmetric Lanczos process with the objective of enabling fixed-point im- plementations with no overflow. Current techniques fail to provide practical bounds for nonlinear recursive algorithms. We employ a diagonal preconditioner to control the range of all variables, regardless of the condition number of the original matrix. Linear algebra techniques are used to prove the proposed bounds. It is shown that the result- ing fixed-point implementations can lead to similar numerical behaviour as with double precision floating-point while providing very significant performance improvements in custom hardware implementations.

  • J. L. Jerez, G. A. Constantinides and E. C. Kerrigan. FPGA Implementation of a Predictive Controller. In SIAM Conference on Optimization, Darmstadt, Germany, May 2011. pdf
    Abstract
    » Predictive control is an advanced control technique that relies on the solution of a convex QP at every sample instant. In order to apply predictive control at faster sampling rates, there is a need for faster methods for solving the optimization problems. We present an FPGA implementation of an interior-point solver, which provides substantial acceleration over a sequential CPU implementation. In addition, the proposed architecture possesses special features that increase the potential performance benefit by an extra order of magnitude.