21-25 May 2012
New York City, NY, USA
US/Eastern timezone

Parallel algorithms for track reconstruction in the CBM experiment

24 May 2012, 13:30
4h 45m
Rosenthal Pavilion (10th floor) (Kimmel Center)

Rosenthal Pavilion (10th floor)

Kimmel Center

Poster Event Processing (track 2) Poster Session


Mr Igor Kulakov (Goethe Universitaet Frankfurt)


The CBM experiment is a future fixed-target experiment at FAIR/GSI (Darmstadt, Germany). It is being designed to study heavy-ion collisions at extremely high interaction rates. The main tracking detectors are the Micro-Vertex Detector (MVD) and the Silicon Tracking System (STS). Track reconstruction in these detectors is very complicated task because of several factors. Up to 1000 tracks per central Au+Au collision intersect 5x5 cm2 region of the first MVD detector plane. Double-sided strip detector modules are used in STS, that leads to about 85% additional combinatorial space points. The detectors are placed in the non-homogeneous magnetic field. The full event reconstruction is required for online event selection. Therefore, both the speed of the reconstruction algorithms and their efficiency are crucial. The Cellular Automaton (CA) algorithm is used for the track reconstruction. It is based on a local reconstruction and therefore is robust, fast and easily parallelizable. The algorithm is optimized for the very complicated and realistic simulation of the detectors. Reconstruction of the central collisions shows 95% efficiency for most of signal particles, 5% incorrectly reconstructed tracks and speed of 200 ms per event per core. The algorithm is stable against detector inefficiency. The CA algorithm is suitable for complicated conditions and high interaction rates of the CBM experiment. The Kalman filter (KF) based package is used for precise estimation of track parameters. It includes track fitter, track smoother and deterministic annealing filter (DAF). Initial approximate estimation of the track parameters with the least square method is used in order to increase stability of the KF algorithms. Several approaches of the Kalman filter track fit are implemented: conventional Kalman filter, U-D filtering and two approaches for the square root Kalman filter. The square root approach, which based on the Potter’s measurement-update equations, is robust with respect to computational round-off errors, gives 1.1% momentum resolution and takes less then 2.5 us per track. It appears to be the most suitable for track fitting in CBM. Two procedures for the track propagation in non-homogeneous magnetic field are implemented: a standard fourth-order Runge-Kutta method and a method based on the analytic formula, specially developed for the CBM experiment. The DAF based procedure rejects with 99% efficiency the noise hits placed in 300 um from the true track position. The track finder and track fitter procedures are implemented in single precision, use the SIMD instruction set and multithreading for parallel computations. The algorithms show a strong scalability with respect to number of cores. Results for the newest AMD Opteron CPU with 48 cores and Intel Westmere CPU with 40 hardware (80 logical) cores are presented and discussed. Future plans include investigation of the parallel algorithms for track reconstruction on non-homogeneous many-core CPU/GPU systems.

Primary author

Mr Igor Kulakov (Goethe Universitaet Frankfurt)


Dr Ivan Kisel (GSI Helmholtzzentrum fuer Schwerionenforschung GmbH) Mr Maksym Zyzak (Goethe Universitaet Frankfurt)

Presentation Materials