Particle Track Reconstruction for the Large Hadron Collider: Progress in Many-Core Parallel Computing.
Steve Lantz (CAC, Cornell)

Track finding and fitting is one of the most computationally intensive aspects of event reconstruction in particle physics. At the High-Luminosity Large Hadron Collider (HL-LHC), where tens or hundreds of events may overlap in time, "tracking" is expected to grow to become by far the dominant problem. To attain the necessary computational capacity, while staying within power and budgetary limits, it is clear that tracking methods must rely increasingly on parallelism rather than raw speed. This is because the growth trend in today's commodity processors is evidently toward many-core configurations emphasizing fine-grained, SIMD-style parallelism. At the LHC and elsewhere, the most commonly used techniques for tracking are based on the Kalman Filter: they have proven to be robust and provide high physics performance. Previously we showed how to apply Kalman filtering in parallel to large numbers of particle tracks through a particular arrangement of the data that is amenable to both vectorization and multithreading. In our ongoing work, we identify several keys to achieving large speedups on many-core parallel architectures such as the Intel Xeon Phi. For track fitting, we find it is essential to shrink and otherwise optimize the basic data structures and their movement in order to get good vector (SIMD) utilization. For track finding (the harder problem), we find we must also enhance data locality through binning, and improve load balancing by allowing threads to steal work from one another. The goal of the project is to produce an algorithm to do end-to-end track reconstruction exploiting these vectorization and parallelization techniques, first in a simplified experimental environment, and ultimately with realistic geometry and materials.