A real-time throughput model based particle filter program generator on GPU : a real-time analysis

State estimation plays an important role in cyber-physical systems. An accurate state of the physical plant is required by the controller to compute optimal control signals that are sent to the actuators to move the physical system towards the target state. However, in most cases, states cannot be obtained from sensors directly. And for complicated physical systems, whose dynamics are high-dimensional non-linear models, particle filters are required for state estimation due to their superior quality compared to linear estimators such as Kalman filters. A major drawback of particle filters is the computational cost they incur since a large number of particles is required to produce accurate estimation results. Fortunately, the computation of particle filters can be parallelized so that it can be accelerated by graphics processing units (GPUs). One of the hindrances of utilizing GPUs as the computing engine in cyber-physical systems is the lack of real-time performance information. Due to concurrency and synchronization between different processors, real-time performance analysis for parallel architectures is challenging. This dissertation focuses on the real-time analysis of state estimators using particle filters implemented on GPUs. The goal is to compute an accurate prediction of the execution time of the state estimator according to static information of the implementation, which includes both the source code of the state estimator and the hardware specifications. To achieve its goal, this dissertation presents an analytical performance model, which takes as input the source code of the state estimator, the number of particles, and the specifications of the hardware. The analytical performance model outputs a prediction of the execution time of the state estimator. The analytical performance model is tested by a synthetic benchmark and three real-world applications. The benchmark contains synthetic GPU programs with different arithmetic intensities and parallelism. The real-world applications, Vacuum Arc Remelting, Early Kick Detection, and Monte Carlo Localization, apply particle filters to perform state estimation. This dissertation demonstrates the application of the analytical performance model in a particle filter program generator system.Computer Science