Segment Linking: A Highly Parallelizable Track Reconstruction Algorithm for HL-LHC

P. Chang, P. Elmer, 裕二 池谷, V. Krutelyov, G Niendorf, M. Reid, B. V. Sathia Narayanan, M. Tadel, E. Vourliotis, B Wang, P. Wittich, A. YagilJournal of Physics Conference Series 2022 · DOI

TL;DR

The High Luminosity LHC (HL-LHC) will generate an overwhelming number of particle collisions, making traditional track reconstruction computationally infeasible. This paper introduces "Segment Linking," a novel, highly parallelizable algorithm designed for GPUs that efficiently reconstructs particle tracks by progressively linking local "stubs" into longer segments. This GPU-accelerated approach shows comparable physics performance to existing CPU-based methods while offering significant speedups, crucial for the future of high-energy physics data analysis.

What Problem Does This Paper Address?

The upcoming High Luminosity upgrade to the Large Hadron Collider (HL-LHC) will dramatically increase the rate of proton-proton collisions. This "pileup" means that in a single bunch crossing, hundreds of interactions will occur simultaneously. For particle physics experiments like CMS, this creates an unprecedented challenge for reconstructing the paths of charged particles (tracks). The sheer volume of data and the combinatorial explosion of potential track combinations will overwhelm current computational resources, exceeding projected budgets if relying solely on traditional CPUs. This necessitates a fundamental shift towards more efficient and parallelizable algorithms, particularly leveraging the power of heterogeneous computing architectures like GPUs.

Methods

The core of this paper is the "Segment Linking" (or Line Segment Tracking - LST) algorithm. It's a bottom-up approach that starts by identifying "stubs" – localized combinations of hits within closely spaced sensors of the tracker. These stubs are then progressively linked to form longer "segments," then "triplets," and "quintuplets." This process leverages the Single Instruction, Multiple Data (SIMD) paradigm, allowing hundreds of these linking operations to occur in parallel on a GPU. The algorithm incorporates physics-based requirements and geometrical constraints to filter out invalid combinations early on. It also utilizes information from the inner pixel detector to create even higher-purity objects like "pixel triplets" and "pixel quintuplets." A crucial "cross-cleaning" step is employed to remove duplicate track candidates. The implementation on an NVIDIA Tesla V100 GPU is detailed, focusing on efficient memory management (Structure of Arrays), custom cache allocation, and multi-streaming for event-level parallelization.

Datasets

The paper evaluates the algorithm using simulated "tt" (top-antitop quark) events at a high pileup of 200 interactions per bunch crossing. They also mention using a "muon gun" sample for specific efficiency studies. These simulated datasets are representative of the conditions expected at the HL-LHC.

Key Insights and Ideas

  • Leveraging "Stubs" for Combinatorial Reduction: By starting with pre-processed "stubs" instead of individual hits, the algorithm significantly reduces the initial combinatorial complexity, by up to a factor of 7.5.
  • Bottom-Up Parallelism: The progressive linking of local stubs into larger objects is inherently parallelizable, making it an ideal candidate for GPU acceleration.
  • Multi-Streaming for GPU Throughput: Employing multiple GPU streams to process different events concurrently effectively hides GPU latency and maximizes resource utilization, leading to a ~20% speedup.
  • GPU-Optimized Implementation: The use of Structure of Arrays (SoA) and custom memory management techniques are critical for efficient data access and transfer on GPUs, minimizing bottlenecks.
  • Comparable Physics Performance: The algorithm achieves efficiency and fake rate performance on par with existing, highly optimized CPU-based tracking algorithms, demonstrating its viability.

Key Results

  • The Segment Linking algorithm achieves a track finding efficiency of approximately 90% over a wide range of transverse momentum ($p_T$) and pseudorapidity ($\eta$).
  • The fake rate (reconstructing non-existent tracks) is kept below 10% for most events, with specific values around 15% in the barrel and 20% in the endcap.
  • The GPU implementation achieves an average event processing time of 26 ms for the 8-stream case, a significant improvement over the 32 ms for a single stream.
  • The algorithm's performance is comparable to the latest CMS tracking algorithms, even though some components like final track fitting are not yet implemented in this version.

Limitations and Future Work

The authors acknowledge that important components of track reconstruction, such as the final track fitting, have not yet been implemented in their current LST algorithm. This means the comparison with existing CMS algorithms is not entirely apples-to-apples. Future work includes:

  • Physics Performance Improvements: Re-evaluating selection criteria to enhance efficiency, particularly for displaced tracks, and lower the fake rate.
  • Integration with Other GPU Developments: Exploring integration with other GPU-accelerated tracking frameworks like Patatrack.
  • Computational Optimizations: Further mathematical optimizations, exploring half-precision floats, and refining memory coalescing techniques to reduce timing further.
  • Full Integration: The ultimate goal is to integrate the LST algorithm into the central CMS software for both High-Level Trigger (HLT) and offline data analysis during the HL-LHC operation.

Summary updated

Abstract

Abstract The High Luminosity upgrade of the Large Hadron Collider (HL-LHC) will produce particle collisions with up to 200 simultaneous proton-proton interactions. These unprecedented conditions will create a combinatorial complexity for charged-particle track reconstruction that demands a computational cost that is expected to surpass the projected computing budget using conventional CPUs. Motivated by this and taking into account the prevalence of heterogeneous computing in cutting-edge High Performance Computing centers, we propose an efficient, fast and highly parallelizable bottom-up approach to track reconstruction for the HL-LHC, along with an associated implementation on GPUs, in the context of the Phase 2 CMS outer tracker. Our algorithm, called Segment Linking (or Line Segment Tracking), takes advantage of localized track stub creation, combining individual stubs to progressively form higher level objects that are subject to kinematical and geometrical requirements compatible with genuine physics tracks. The local nature of the algorithm makes it ideal for parallelization under the Single Instruction, Multiple Data paradigm, as hundreds of objects can be built simultaneously. The computing and physics performance of the algorithm has been tested on an NVIDIA Tesla V100 GPU, already yielding efficiency and timing measurements that are on par with the latest, multi-CPU versions of existing CMS tracking algorithms.
BibTeX
@article{chang2022segment,
  author = {P. Chang and P. Elmer and 裕二 池谷 and V. Krutelyov and G Niendorf and M. Reid and B. V. Sathia Narayanan and M. Tadel and E. Vourliotis and B Wang and P. Wittich and A. Yagil},
  title = {{Segment Linking: A Highly Parallelizable Track Reconstruction Algorithm for HL-LHC}},
  journal = {Journal of Physics Conference Series},
  year = {2022},
  doi = {10.1088/1742-6596/2375/1/012005},
}
Figure