Charged particle track reconstruction algorithms for massively parallel systems

In high-energy physics, the collisions of particles at high energies allow us to study the behaviour and properties of fundamental particles in our universe. An important part of this process is the reconstruction of continuous particle trajectories from discrete measurements, a process which is performed by computers in soft real-time and non-real-time environments. Future upgrades to particle accelerators and detectors will lead to a massively increased volume of tracks to be reconstructed. This poses a computational challenge, as current software systems operating on CPU-like hardware architectures may no longer be able to meet the processing demands of the future. In this thesis, we examine opportunities to reconstruct tracks on massively parallel GPGPU architectures, which can provide higher throughput than multi-core CPUs.
Throughout our work, we tackle challenges faced in track reconstruction with more widely applicable methods, allowing us to take the lessons learned from a domain-specific problem and apply them to high-performance computing in general. We examine the effects of cache misses on the performance of GPGPU applications and show that we can systematically explore the design space of data layouts in order to improve performance. We also explore generalised Morton curve layouts using evolutionary algorithms, which we show can lead to improved throughput. Furthermore, we examine the effects of thread imbalance on GPGPU algorithms and provide a novel model for evaluating the impact of these effects on application performance. Finally, we describe the design and implementation of a novel track reconstruction pipeline that runs entirely on massively parallel architectures and show that this will be able to meet the data processing demands of the physics experiments of the future.