  One of the most computationally challenging problems expected for the
High-Luminosity Large Hadron Collider (HL-LHC) is determining the trajectory of
charged particles during event reconstruction. Algorithms used at the LHC today
rely on Kalman filtering, which builds physical trajectories incrementally
while incorporating material effects and error estimation. Recognizing the need
for faster computational throughput, we have adapted Kalman-filter-based
methods for highly parallel, many-core SIMD architectures that are now
prevalent in high-performance hardware. In this paper, we discuss the design
and performance of the improved tracking algorithm, referred to as mkFit. A key
piece of the algorithm is the Matriplex library, containing dedicated code to
optimally vectorize operations on small matrices. The physics performance of
the mkFit algorithm is comparable to the nominal CMS tracking algorithm when
reconstructing tracks from simulated proton-proton collisions within the CMS
detector. We study the scaling of the algorithm as a function of the parallel
resources utilized and find large speedups both from vectorization and
multi-threading. mkFit achieves a speedup of a factor of 6 compared to the
nominal algorithm when run in a single-threaded application within the CMS
software framework.
