CTD2023: Seed Finding in the Acts Software Package: Algorithms and Optimizations

Seed finding is an important and computationally expensive problem in the reconstruction of charged particle tracks; finding solutions to this problem involves forming triplets (seeds) of discrete points at which particles were detected (space-points) in the detector volume. This combinatorial process scales cubically with the number of space-points, which in turn is expected to increase in future collision experiments as well as in upgrades to current experiments such as the HL-LHC (High-Luminosity Large Hadron Collider). The Acts (A Common Tracking Software) software package provides a broad range of algorithms - including seeding - for the reconstruction of charge particle tracks in a broad range of detectors. In order to provide competitive performance - in terms of computation as well as physics - for future experiments, the Acts software provides highly optimized seed finding algorithms which can be configured for different detector geometries. In this talk, we describe the seeding algorithms in traccc which reduce the combinatorial explosion problem through the use of structured grids and k-dimensional search trees. We compare the performance of these algorithms in CPU- and GPU-based environments. Finally, we discuss seed filtering strategies for reducing the volume of output seeds which impacts the performance of other algorithms such as combinatorial Kalman filtering. In particular, we propose to combine a clustering algorithm - such as DBSCAN - and a neural network with Margin Ranking Loss for an efficient and performant seed selection.