GPU-Accelerated PD-IPM for Real-Time Model Predictive Control in Integrated Missile Guidance and Control Systems

Sanghyeon Lee, Heoncheol Lee, Yun-Young Kim, Jae‐Hyun Kim, Wonseok ChoiSensors 2022 · DOI

TL;DR

This paper tackles the computational bottleneck of real-time Model Predictive Control (MPC) for integrated missile guidance and control (IGC) systems. They propose a novel GPU-accelerated method to speed up the Primal-Dual Interior Point Method (PD-IPM) solver, specifically by parallelizing the computationally intensive KKT condition construction, achieving significant real-time performance improvements on an embedded system.

What Problem Does This Paper Address?

Integrated Guidance and Control (IGC) aims to improve missile performance by unifying guidance and control system design, considering their interactions. Model Predictive Control (MPC) is a powerful technique for IGC due to its ability to handle constraints and optimize performance over a finite horizon. However, a key challenge for real-time MPC, especially in fast-dynamics systems like missiles, is the computational burden of solving the optimization problem at each control step. The Primal-Dual Interior Point Method (PD-IPM), a common choice for convex optimization in MPC, suffers from long computation times, particularly in constructing and solving the Karush-Kuhn-Tucker (KKT) conditions. This paper specifically targets the KKT condition construction part of PD-IPM, which is identified as a significant contributor to the overall computation time, and aims to accelerate it for real-time IGC applications.

Methods

The core of this paper is the development of a GPU-accelerated approach to speed up the PD-IPM solver for MPC in IGC systems. The authors first profile the PD-IPM algorithm to identify computationally expensive parts, pinpointing the "construct modified KKT condition" and "calculate search direction" steps.

Their novel contribution lies in parallelizing the "construct modified KKT condition" part. This involves:

  1. Sparse Matrix Representation: Recognizing that the matrices involved in KKT condition construction are sparse, they convert dense matrices into Compressed Sparse Row (CSR) and Compressed Sparse Column (CSC) formats. This reduces memory usage and speeds up operations.
  2. Parallel Matrix Multiplication: They implement a parallel sparse matrix multiplication algorithm (Algorithm 2) using CSR and CSC formats for the left and right matrices, respectively, to optimize access patterns.
  3. Parallel KKT Matrix Construction: A parallel algorithm (Algorithm 3) is proposed to construct the modified KKT matrix by efficiently adding sparse matrices P and D and their transposes.
  4. GPU Acceleration: These parallelized operations are implemented using CUDA on a GPU.
  5. Linear Equation Solver Improvement: For the "calculate search direction" part, which involves solving a linear equation, they replace the CPU-based Eigen library with the CUDA cusolver library for GPU acceleration.

Datasets

Not discussed in the paper. The evaluation uses a simulated missile terminal homing engagement scenario with specific parameters.

Key Insights and Ideas

  • KKT Construction is a Bottleneck: While solving linear equations is often cited as the bottleneck in PD-IPM, this paper highlights that the KKT condition construction part also demands significant computation, especially for IGC systems with large matrices.
  • Sparse Matrix Techniques are Crucial: For IGC problems, the matrices involved are often sparse. Leveraging CSR and CSC formats, along with optimized parallel sparse matrix operations, is key to achieving substantial speedups.
  • GPU Acceleration for Embedded Systems: The paper demonstrates that GPU acceleration can be effectively applied even on embedded systems like the Nvidia Jetson Xavier NX, offering significant performance gains over CPU-only implementations.
  • CUDA Initialization Delay Consideration: For embedded systems, the overhead of CUDA initialization can be substantial. The proposed method aims to minimize this delay by using efficient libraries and parallelization strategies.

Key Results

The proposed GPU-accelerated PD-IPM method achieved significant real-time performance improvements:

  • Construct Modified KKT Condition: The proposed method was approximately 4 times faster than the CPU-only implementation. Even including CUDA initialization delay, it was about 3 times faster.
  • Entire Application: When considering the entire PD-IPM process, the proposed method was approximately 2.7 times faster than the CPU-only implementation. When the CUDA initialization delay was included, it was about 1.4 times faster.
  • Overall Flight: The total computation time reduction for the entire flight was estimated to be about 62.5% when considering the CUDA initialization delay as a one-time overhead.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that the "construct modified KKT condition" part, while accelerated, is not the most time-consuming part of the entire PD-IPM process. The "solve linear equation" part still takes a significant amount of time.
  • The CUDA initialization delay can be a notable factor on embedded systems, impacting the overall speedup.
  • Future Work:
    • The authors suggest exploring algorithm acceleration using other hardware, such as FPGAs.
  • They also propose extending the method to other algorithms and evaluating the stability of the MPC approach with closed-loop performances.

Summary updated

Abstract

This paper addresses the problem of real-time model predictive control (MPC) in the integrated guidance and control (IGC) of missile systems. When the primal-dual interior point method (PD-IPM), which is a convex optimization method, is used as an optimization solution for the MPC, the real-time performance of PD-IPM degenerates due to the elevated computation time in checking the Karush-Kuhn-Tucker (KKT) conditions in PD-IPM. This paper proposes a graphics processing unit (GPU)-based method to parallelize and accelerate PD-IPM for real-time MPC. The real-time performance of the proposed method was tested and analyzed on a widely-used embedded system. The comparison results with the conventional PD-IPM and other methods showed that the proposed method improved the real-time performance by reducing the computation time significantly.
BibTeX
@inproceedings{lee2022gpu,
  author = {Sanghyeon Lee and Heoncheol Lee and Yun-Young Kim and Jae‐Hyun Kim and Wonseok Choi},
  title = {{GPU-Accelerated PD-IPM for Real-Time Model Predictive Control in Integrated Missile Guidance and Control Systems}},
  booktitle = {Sensors},
  year = {2022},
  doi = {10.3390/s22124512},
}
Figure