Charged Particle Track Reconstruction Algorithms for Massively Parallel Systems

In this thesis, we investigate the feasibility of implementing algorithms for track reconstruction – the process of computing the continuous trajectories of charged particles in high-energy physics experiments according to the discrete measurements of those particles – on massively parallel architectures. Track reconstruction software commonly employs a task graph consisting of a variety of algorithms, including but not limited to algorithms inspired by computer vision, combinatorial algorithms, and numerical methods. Besides consisting of vastly different algorithms, track reconstruction software is also run in very different environments; on the one hand, so-called offline environments – in which the reconstruction of tracks takes place after they have been recorded to disk – require very high throughput. On the other hand, online environments – in which a decision is made whether to store or discard data immediately after it is gathered – present soft real-time constraints with latency requirements. The thesis includes a brief outline of high-energy physics in order to motivate our work in Chapter 2.