Optimization of a high-performance tracking algorithm on GPUs for the Inner Tracking System of the ALICE experiment

The subject of this thesis is the design and the optimization of a fast track-ing algorithm that will be used for the innermost detector of the ALICE (A LargeIon Collider Experiment) experiment installed at the CERN Large Hadron Collider(LHC) in Geneva. In 2019, after the end of the Long Shutdown 2 (LS2), the In-ner Tracking System (ITS) of ALICE will be upgraded and equipped with a newsilicon detector. This new detector has been designed to fulll the Run 3 physicsrequirements, which consist rst of all in an incremented collision rate that canreach 50 kHz of frequency for collisions between lead ions. Along with an hardwareupgrade, also the software must be upgraded in order to match the new requiredperformances.The 7 layers, which compose the new detector, will be hit by the particles gener-ated from the collision between proton-proton (p-p), proton-lead (p-Pb) or lead-lead(Pb-Pb). The points where the particles hit the pixel of each detector are calledclusters. The tracking algorithm uses the clusters to reconstruct the trajectory ofa particle and nd the point where the collision happened. This point is calledinteraction vertex.Currently, two dierent versions of the tracking algorithm have been developed:the rst version is a serial implementation that can run on CPUs only and the secondone is a parallel version based on the CUDA framework and it can be executed onlyon NVIDIA GPUs.The purpose of my thesis work is to develop a third version of the trackingalgorithm, based on the OpenCL framework. OpenCL allows to run the program ondierent kind of devices such as CPUs, GPUs, FPGAs and others. To this purposeI designed and implemented three dierent versions of OpenCL porting, the rstone based on the schema developed for the CUDA version, the others two basedon dierent schema in order to better t the algorithm to the features oered byOpenCL and to improve the overall performance.The thesis is organized as follows: the rst chapter is dedicated to the descriptionof the features of both the present ITS and the upgraded detector. The secondchapter is devoted to the description of the current tracking algorithm and of theperformances achieved for the serial (on CPU) and parallel versions (on NVIDIAGPU). The third chapter describes the main features of the OpenCL framework andIntel Interception Layer on the tool adopted for the analysis of the execution ow.The fourth chapter is focused on the OpenCL porting with the descriptions of threedierent versions I developed highlighting advantages, disadvantages and describingin detail the achieved performances to make a comparison between them, the serialand the CUDA parallel versions of the algorithm.