  The online event reconstruction for the ALICE experiment at CERN requires
processing capabilities to process central Pb-Pb collisions at a rate of more
than 200 Hz, corresponding to an input data rate of about 25 GB/s. The
reconstruction of particle trajectories in the Time Projection Chamber (TPC) is
the most compute intensive step. The TPC online tracker implementation combines
the principle of the cellular automaton and the Kalman filter. It has been
accelerated by the usage of graphics cards (GPUs). A pipelined processing
allows to perform the tracking on the GPU, the data transfer, and the
preprocessing on the CPU in parallel. In order for CPU pre- and postprocessing
to keep step with the GPU the pipeline uses multiple threads. A splitting of
the tracking in multiple phases searching for short local track segments first
improves data locality and makes the algorithm suited to run on a GPU. Due to
special optimizations this course of action is not second to a global approach.
Because of non-associative floating-point arithmetic a binary comparison of GPU
and CPU tracker is infeasible. A track by track and cluster by cluster
comparison shows a concordance of 99.999%. With current hardware, the GPU
tracker outperforms the CPU version by about a factor of three leaving the
processor still available for other tasks.
