Speed up approaches in the Cellular Automaton track finder

Jul 7, 2017, 1:30 PM
15m
LIT Conference Hall

LIT Conference Hall

Speaker

Mr Grigory Kozlov (LIT JINR Dubna, FIAS Frankfurt)

Description

Tracking procedure is an important part of event reconstruction in high energy physics experiments. One of the fastest and efficient track finding algorithm is a cellular automaton (CA). It is used in various experiments including CBM at FAIR and STAR at RHIC. CBM and STAR CA track finders have similar implementations. But standard track finding procedure may be not fast enough for online calculations, especially in case of high particle multiplicity. In this work we consider several methods to speed up CA track finders in STAR and CBM. Different approaches were implemented and investigated. For instance, grid structure allows us to seriously reduce the number of calculations when hits are combined into segments. Using of multimap for merging of neighbouring segments help us quickly exclude impossible combinations. In addition, CA track finder was vectorized taking into account scalability for CPUs with SSE and AVX instructions (128 and 256 bit registers). Appropriate data structures provides to reduce combinatorial calculations and optimise memory usage, which leads to nice speed up for vectorized calculations. Most of used approaches are common and can be easily applied to different versions of CA tracking algorithms.

Primary author

Mr Grigory Kozlov (LIT JINR Dubna, FIAS Frankfurt)

Co-author

Prof. Ivan Kisel (Goethe University Frankfurt, Frankfurt am Main, Hesse, Germany, Frankfurt Institute for Advanced Studies, Frankfurt am Main, Hesse, Germany GSI Helmholtz Centre for Heavy Ion Research, Darmstadt, Germany)

Presentation materials