Publications
17 results found
Wang M, McInerney I, Stellato B, et al., 2023, RSQP: problem-specific architectural customization for accelerated convex quadratic optimization, ISCA '23: The 50th Annual International Symposium on Computer Architecture, Publisher: Association for Computing Machinery, Pages: 1-12
Convex optimization is at the heart of many performance-critical applications across a wide range of domains. Although many high-performance hardware accelerators have been developed for specific optimization problems in the past, designing such accelerator is a challenging task and the resulting computing architecture is often so specific to the targeted application that they can hardly be reused even in a related application within the same domain. To accelerate general-purpose optimization solvers that must operate on diverse user input during run time, an ideal hardware solver should be able to adapt to the provided optimization problem dynamically while achieving high performance and power-efficiency. In this work, a hardware-accelerated general-purpose quadratic program solver, called RSQP, with reconfigurable functional units and data path that facilitate problem-specific customization is presented. RSQP uses a string-based encoding to describe the problem structure with fine granularity. Based on this encoding, functional units and datapath customized to the sparsity pattern of the problem are created by solving a dictionary-based lossless string compression problem and a mixed integer linear program respectively. RSQP has been integrated to accelerate the general-purpose quadratic programming solver OSQP and has been tested using an extensive benchmark with 120 optimization problems from 6 application domains. Through architectural customization, RSQP achieves up to 7× performance improvement over its baseline generic design. Furthermore, when compared with a CPU and a GPU-accelerated implementation, RSQP achieves up to 31.2× and 6.9× end-to-end speedup on these benchmark programs, respectively. Finally, the FPGA accelerator operates at up to 6.6× lower dynamic power consumption and up to 22.7× higher power efficiency over the GPU implementation, making it an attractive solution for power-conscious datacenter applications.
McInerney I, Kerrigan E, Constantinides G, 2023, Horizon-independent preconditioner design for linear predictive control, IEEE Transactions on Automatic Control, Vol: 68, Pages: 580-587, ISSN: 0018-9286
First-order optimization solvers, such as the Fast Gradient Method, are increasingly being used to solve Model Predictive Control problems in resource-constrained environments. Unfortunately, the convergence rate of these solvers is significantly affected by the conditioning of the problem data, with ill-conditioned problems requiring a large number of iterations. To reduce the number of iterations required, we present a simple method for computing a horizon-independent preconditioning matrix for the Hessian of the condensed problem. The preconditioner is based on the block Toeplitz structure of the Hessian. Horizon-independence allows one to use only the predicted system and cost matrices to compute the preconditioner, instead of the full Hessian. The proposed preconditioner has equivalent performance to an optimal preconditioner in numerical examples, producing speedups between 2x and 9x for the Fast Gradient Method. Additionally, we derive horizon-independent spectral bounds for the Hessian in terms of the transfer function of the predicted system, and show how these can be used to compute a novel horizon-independent bound on the condition number for the preconditioned Hessian.
McInerney I, Kerrigan EC, 2022, Teaching predictive control using specification-based summative assessments, 13th Symposium on Advances in Control Education, Publisher: Elsevier, Pages: 236-241, ISSN: 2405-8963
Including Model Predictive Control (MPC) in the undergraduate/graduate control curriculum is becoming vitally important due to the growing adoption of MPC in many industrial areas. In this paper, we present an overview of the predictive control course taught by the authors at Imperial College London between 2018 and 2021. We discuss how the course evolved from focusing solely on the linear MPC formulation to covering nonlinear MPC and some of its extensions. We also present a novel specification-based summative assessment framework, written in MATLAB, that was developed to assess the knowledge and understanding of the students in the course by tasking them with designing a controller for a real-world problem. The MATLAB assessment framework was designed to provide the students with the freedom to design and implement any MPC controller they wanted. The submitted controllers were then assessed against over 30 variations of the real-world problem to gauge student understanding of design robustness and the MPC topics from the course.
Nita L, Vila EMG, Zagorowska M, et al., 2022, Fast and accurate method for computing non-smooth solutions to constrained control problems, 2022 European Control Conference (ECC), Publisher: IEEE, Pages: 1049-1054
Introducing flexibility in the time-discretisation mesh can improve convergence and computational time when solving differential equations numerically, particularly when the solutions are discontinuous, as commonly found in control problems with constraints. State-of-the-art methods use fixed mesh schemes, which cannot achieve superlinear convergence in the presence of non-smooth solutions. In this paper, we propose using a flexible mesh in an integrated residual method. The locations of the mesh nodes are introduced as decision variables, and constraints are added to set upper and lower bounds on the size of the mesh intervals. We compare our approach to a uniform fixed mesh on a real-world satellite reorientation example. This example demonstrates that the flexible mesh enables the solver to automatically locate the discontinuities in the solution, has superlinear convergence and faster solve times, while achieving the same accuracy as a fixed mesh.
McInerney I, 2022, Conditions for Digit Stability in Iterative Methods Using the Redundant Number Representation
Iterative methods play an important role in science and engineeringapplications, with uses ranging from linear system solvers in finite elementmethods to optimization solvers in model predictive control. Recently, a newcomputational strategy for iterative methods called ARCHITECT was proposed byLi et al. in [1] that uses the redundant number representation to create"stable digits" in the Most-significant Digits (MSDs) of an iterate, allowingthe future iterations to assume the stable MSDs have not changed their value,eliminating the need to recompute them. In this work, we present a theoreticalanalysis of how these "stable digits" arise in iterative methods by showingthat a Fejer monotone sequence in the redundant number representation candevelop stable MSDs in the elements of the sequence as the sequence grows inlength. This property of Fejer monotone sequences allows us to expand the classof iterative methods known to have MSD stability when using the redundantnumber representation to include any fixed-point iteration of a contractiveLipschitz continuous function. We then show that this allows for thetheoretical guarantee of digit stability not just in the Jacobi method that waspreviously analyzed by Li et al. in [2], but also in other commonly usedmethods such as Newton's method.
McInerney I, 2022, Numerical methods for model predictive control
There has been an increased interest in controlling complex systems using Model Predictive Control (MPC). However, the use of resource-constrained computing platforms in these systems has slowed the adoption of MPC. This thesis focuses on increasing the efficiency of numerical methods for MPC in terms of resource usage and solution time, while also simplifying the design process. We first show how block Toeplitz operators can be used to link the linear MPC matrices to the transfer function of the predicted system, resulting in horizon-independent bounds on the condition number of the condensed Hessian and the upper iteration bound for the Fast Gradient Method (FGM). We derive a horizon-independent preconditioner that produces up to a 9x speedup for the FGM while reducing the preconditioner computation time by up to 50,000x compared to an existing preconditioner. We propose a new method for computing the minimum number of fractional bits needed to ensure the FGM with fixed-point arithmetic is stable, with an example showing decreases of up to 77% in resource usage and 50% in the computational energy when using this method on a Field Programmable Gate Array. Finally, we present a framework using the derivative-free Mesh Adaptive Direct Search method to solve nonlinear MPC problems with non-differentiable features or quantized variables without the need for complex or costly reformulations. We augment the system dynamics with additional states to compute the Lagrange cost term and the violation of the path constraints along the state trajectory, and then perform a structured search of the input space using a single-shooting simulation of the system dynamics. We demonstrate this framework on a robust Goddard rocket problem with a non-differentiable cost and a quantized thrust input, where we achieve an altitude within 40m of the target, while other methods are unable to get closer than 180m.
Biggs B, McInerney I, Kerrigan EC, et al., 2022, High-level synthesis using the Julia language, 2nd Workshop on Languages, Tools, and Techniques for Accelerator Design (LATTE’22)
The growing proliferation of FPGAs and High-level Synthesis (HLS) tools hasled to a large interest in designing hardware accelerators for complexoperations and algorithms. However, existing HLS toolflows typically require asignificant amount of user knowledge or training to be effective in bothindustrial and research applications. In this paper, we propose using the Julialanguage as the basis for an HLS tool. The Julia HLS tool aims to decrease thebarrier to entry for hardware acceleration by taking advantage of thereadability of the Julia language and by allowing the use of the existing largelibrary of standard mathematical functions written in Julia. We present aprototype Julia HLS tool, written in Julia, that transforms Julia code to VHDL.We highlight how features of Julia and its compiler simplified the creation ofthis tool, and we discuss potential directions for future work.
McInerney I, Nita L, Nie Y, et al., 2021, Towards a framework for nonlinear predictive control using derivative-free optimization, 7th IFAC Conference on Nonlinear Model Predictive Control, Publisher: Elsevier, Pages: 284-289, ISSN: 2405-8963
The use of derivative-based solvers to compute solutions to optimal control problems with non-differentiable cost or dynamics often requires reformulations or relaxations that complicate the implementation or increase computational complexity. We present an initial framework for using the derivative-free Mesh Adaptive Direct Search (MADS) algorithm to solve Nonlinear Model Predictive Control problems with non-differentiable features without the need for reformulation. The MADS algorithm performs a structured search of the input space by simulating selected system trajectories and computing the subsequent cost value. We propose handling the path constraints and the Lagrange cost term by augmenting the system dynamics with additional states to compute the violation and cost value alongside the state trajectories, eliminating the need for reconstructing the state trajectories in a separate phase. We demonstrate the practicality of this framework by solving a robust rocket control problem, where the objective is to reach a target altitude as close as possible, given a system with uncertain parameters. This example uses a non-differentiable cost function and simulates two different system trajectories simultaneously, with each system having its own free final time.
Li H, McInerney I, Davis J, et al., 2021, Digit Stability Inference for Iterative Methods Using Redundant Number Representation, IEEE Transactions on Computers, Vol: 70, Pages: 1074-1080, ISSN: 0018-9340
In our recent work on iterative computation in hardware, we showed that arbitrary-precision solvers can perform more favorably than their traditional arithmetic equivalents when the latter's precisions are either under- or over-budgeted for the solution of the problem at hand. Significant proportions of these performance improvements stem from the ability to infer the existence of identical most-significant digits between iterations. This technique uses properties of algorithms operating on redundantly represented numbers to allow the generation of those digits to be skipped, increasing efficiency. It is unable, however, to guarantee that digits will stabilize, i.e., never change in any future iteration. In this article, we address this shortcoming, using interval and forward error analyses to prove that digits of high significance will become stable when computing the approximants of systems of linear equations using stationary iterative methods. We formalize the relationship between matrix conditioning and the rate of growth in most-significant digit stability, using this information to converge to our desired results more quickly. Versus our previous work, an exemplary hardware realization of this new technique achieves an up-to 2.2x speedup in the solution of a set of variously conditioned systems using the Jacobi method.
Rodriguez Bernuz JM, McInerney I, Junyent Ferre A, et al., 2021, Design of a linear time-varying Model Predictive Control energy regulator for grid-tied VSCs, IEEE Transactions on Energy Conversion, Vol: 36, Pages: 1425-1434, ISSN: 0885-8969
This paper presents an energy regulator based on a Model Predictive Control (MPC) algorithm for a Voltage Source Converter (VSC). The MPC is formulated to optimise the converter performance according to the weights defined in an objective function that trades off additional features, such as current harmonic distortion, reactive power tracking and DC bus voltage oscillation. Differently from most approaches found in the research literature, the MPC proposed here considers the coupling dynamics between the AC and DC sides of the VSC. This study is focused on the example case of a single-phase VSC, which presents a nonlinear relationship between its AC and DC sides and a sustained double-line frequency power disturbance in its DC bus. To reduce the burden of the MPC, the controller is formulated to benefit from the slow energy dynamics of the system. Thus, the cascaded structure typically used in the control of VSCs is kept and the MPC is set as an energy regulator at a reduced sampling frequency while the current control relies on a fast inner controller. The computational burden of the algorithm is further reduced by using a linear time-varying approximation. The controller is presented in detail and experimental validation showing the performance of the algorithm is provided.
McInerney I, Kerrigan E, Constantinides G, 2020, Modeling round-off error in the fast gradient method for predictive control, 2019 IEEE 58th Conference on Decision and Control (CDC), Publisher: IEEE, Pages: 1-6
We present a method for determining the smallest precision required to have algorithmic stability of an implementation of the Fast Gradient Method (FGM) when solving a linear Model Predictive Control (MPC) problem in fixed-point arithmetic. We derive two models for the round-off error present in fixed-point arithmetic. The first is a generic model with no assumptions on the predicted system or weight matrices. The second is a parametric model that exploits the Toeplitz structure of the MPC problem for a Schur-stable system. We also propose a metric for measuring the amount of round-off error the FGM iteration can tolerate before becoming unstable. This metric is combined with the round-off error models to compute the minimum number of fractional bits needed for the fixed-point data type. Using these models, we show that exploiting the MPC problem structure nearly halves the number of fractional bits needed to implement an example problem. We show that this results in significant decreases in resource usage, computational energy and execution time for an implementation on a Field Programmable Gate Array.
McInerney I, Kerrigan E, Constantinides G, 2020, Closed-form preconditioner design for linear predictive control, 21st IFAC World Congress, Publisher: IFAC Secretariat, Pages: 1-4, ISSN: 2405-8963
Model Predictive Control (MPC) with linear models and constraints is extensivelybeing utilized in many applications, many of which have low power requirements and limitedcomputational resources. In these resource-constrained environments, many designers chooseto utilize simple iterative first-order optimization solvers, such as the Fast Gradient Method.Unfortunately, the convergence rate of these solvers is affected by the conditioning of the problemdata, with ill-conditioned problems requiring a large number of iterations to solve. In order toreduce the number of solver iterations required, we present a simple closed-form method forcomputing an optimal preconditioning matrix for the Hessian of the condensed primal problem.To accomplish this, we also derive spectral bounds for the Hessian in terms of the transferfunction of the predicted system. This preconditioner is based on the Toeplitz structure of theHessian and has equivalent performance to a state-of-the-art optimal preconditioner, withouthaving to solve a semidefinite program during the design phase.
McInerney I, Kerrigan EC, Constantinides GA, 2019, Bounding computational complexity under cost function scaling in predictive control, Publisher: arXiv
We present a framework for upper bounding the number of iterations requiredby first-order optimization algorithms implementing constrained LQRcontrollers. We derive new bounds for the condition number and extremaleigenvalues of the primal and dual Hessian matrices when the cost function isscaled. These bounds are horizon-independent, allowing for their use withreceding, variable and decreasing horizon controllers. We considerably relaxprior assumptions on the structure of the weight matrices and assume only thatthe system is Schur-stable and the primal Hessian of the quadratic program (QP)is positive-definite. Our analysis uses the Toeplitz structure of the QPmatrices to relate their spectrum to the transfer function of the system,allowing for the use of system-theoretic techniques to compute the bounds.Using these bounds, we can compute the effect on the computational complexityof trading off the input energy used against the state deviation. An examplesystem shows a three-times increase in algorithm iterations between the twoextremes, with the state 2-norm decreased by only 5% despite a greatlyincreased state deviation penalty.
McInerney I, Kerrigan EC, 2018, Automated project-based assessment in a predictive control course, UKACC 12th International Conference on Control (CONTROL), Publisher: IEEE, Pages: 443-443
Written assessments, such as book problems and exams, have customarily been used in control courses to measure student progress, but usually only gauge their knowledge of the theoretical concepts. More complicated control methods, such as predictive control, benefit from gauging student progress through implementation projects. We present a set of automatically marked project-based assessments that test student knowledge on concepts ranging from the derivation of physics models to the creation of a closed-loop predictive controller. We present a simulation framework that allows for the students to utilize any predictive control concepts that they decide to use in their implementation. The framework then automatically tests the student solutions against multiple constraint sets and conditions to provide quantitative data for marking the assessment.
McInerney I, Constantinides G, Kerrigan EC, 2018, A Survey of the implementation of linear model predictive control on FPGAs, 6th IFAC Conference on Nonlinear Model Predictive Control, Publisher: IFAC Secretariat, Pages: 381-387, ISSN: 2405-8963
Over the past 20 years, great strides have been made in the real-time implementationof linear MPC on FPGA devices. Starting from initial work, which demonstrated the benefits ofembedding linear MPC onto FPGAs, recent work has shown sampling rates of more than 1 MHzare possible with FPGA-based implementations. This work surveys FPGA implementationsof linear MPC, with a focus on the computational architecture. This includes the choice ofnumber representation, the parallelizations exploited and the memory architecture. We discussthe transferability of those design choices to the FPGA implementation of nonlinear MPC, andprovide some future research directions related to the implementation of MPC on FPGAs.
McInerney I, Ma X, Elia N, 2018, Cooperative Localization from Imprecise Range-Only Measurements: A Non-Convex Distributed Approach, 56th IEEE Annual Conference on Decision and Control (CDC), Publisher: IEEE, ISSN: 0743-1546
Mcinerney IS, 2017, Development of a multi-agent quadrotor research platform with distributed computational capabilities
Research on multi-agent systems of UAVs is of growing interest in the research community, with specific interest in the testing of novel algorithms on actual systems. Many existing testbeds already exist, but the majority of them utilize expensive quadrotors for their agents. With the recent surge in interest from consumers, companies have started to market lower cost quadrotor options. One such option is the Crazyflie 2.0 from Bitcraze. This quadrotor measures just 10cm from rotor to rotor, uses open-source firmware, and has developed a strong community backing. This work develops a multi-agent testbed using the Crazyflie 2.0.This work presents a parameterization of the Crazyflie quadrotor so it can be modeled and have more advanced controllers designed for it. Additionally, this work discusses the default control loop of the Crazyflie 2.0. Then nested-loop PID controllers are designed and compared against the simulated physics model.A software system that is capable of controlling multiple flying Crazyflie’s is also presented. This system is also capable of modifying the controller at runtime, and implementing distributed computation on the Crazyflie.Finally, a novel algorithm for localization of a target object using distance-only measurements is presented. This algorithm uses optimization dynamics to solve a non-convex QCQP formulation of the problem in a distributed manner. The algorithm is presented and then implemented using the distributed computation framework presented in this work.
This data is extracted from the Web of Science and reproduced under a licence from Thomson Reuters. You may not copy or re-distribute this data in whole or in part without the written consent of the Science business of Thomson Reuters.