Tracking haute fréquence pour architectures SIMD : optimisation de la reconstruction LHCb

During this thesis, we studied linear algebra systems with small matrices (typically from 2x2 to 5x5) used within the LHCb experiment (and also in other domains like computer vision). Linear algebra libraries like Eigen, Magma or the MKL are not optimized for such small matrices. We used and combined many well-known transforms helping SIMD and some unusual transforms like the fast reciprocal square root computation. We wrote a code generator in order to simplify the use of such transforms and to have a portable code. We tested these optimizations and analyzed their impact on the speed of simple algorithm. Batch processing in SoA is crucial to process fast these small matrices. We also analyzed how the accuracy of the results depends on the precision of the data. We implemented these transforms in order to speed-up the Cholesky factorization of small matrices (up to 12x12). The processing speed is capped if the fast reciprocal square root computation is not used. We got a speed up between x10 and x33 using F32. Our version is then from x3 to x10 faster than MKL. Finally, we studied and sped up the Kalman filter in its general form. Our 4x4 F32 implementation is x90 faster. The Kalman filter used within LHCb has been sped up by x2.2 compared to the current SIMD version and by at least x2.3 compared to filters used other high energy physics experiments.Tout au long de cette thèse, nous avons étudié des problèmes d'algèbre linéaire de petite dimension (typiquement de 2x2 à 5x5) utilisés au sein de l'expérience LHCb (mais aussi dans d'autres domaines tels que la vision par ordinateur). Les bibliothèques d’algèbre linéaire telles que Eigen, Magma ou la MKL ne sont pas optimisées pour de petites matrices. Nous avons utilisé et combiné plusieurs transformations connues facilitant le SIMD ainsi que des transformations moins usuelles comme la racine carré inverse rapide. Pour faciliter l’écriture de ces transformations, mais également dans le but d’avoir un code portable, nous avons écrit un générateur de code. Nous avons testé ces transformations et analysé leur impact sur la vitesse de traitement d’algorithmes simples. Le traitement par lot (batch) en SoA est crucial pour maximiser la vitesse de traitements de ces problèmes à faible dimension. Une analyse de la précision des résultats en fonction de la précision de calcul a également été faite sur ces exemples. Nous avons alors implémenté ces transformations dans le but d’accélérer la factorisation de Cholesky de petites matrices (jusqu'à 12x12). La vitesse de traitement plafonne sans l’utilisation du calcul rapide de la racine carrée inverse. Nous avons obtenu une accélération entre x10 et x33 en F32. Notre code est ainsi de x3 à x10 plus rapide que la MKL. Enfin, nous avons étudié et accéléré le filtre de Kalman généraliste. Nous avons ainsi obtenu une accélération de x90 sur l'implémentation 4x4 F32. Le filtre de Kalman utilisé au sein de LHCb a été accéléré d'un facteur x2,2 par rapport à la version actuelle SIMD et supérieur à x2,3 par rapport aux filtres d'autres expériences de physique des particules