* [8] M. Davier, A. Hoecker, B. Malaescu and Z. Zhang, _Reevaluation of the hadronic vacuum polarisation contributions to the Standard Model predictions of the muon $g-2$ and ${\alpha(m_{Z}^{2})}$ using newest hadronic cross-section data_, _Eur. Phys. J._ C77 (2017) 827 [1706.09436].
  * [9] A. Keshavarzi, D. Nomura and T. Teubner, _Muon $g-2$ and $\alpha(M_{Z}^{2})$: a new data-based analysis_, _Phys. Rev._ D97 (2018) 114025 [1802.02995].
  * [10] G. Colangelo, M. Hoferichter and P. Stoffer, _Two-pion contribution to hadronic vacuum polarization_ , _JHEP_ 02 (2019) 006 [1810.00007].
  * [11] M. Hoferichter, B.-L. Hoid and B. Kubis, _Three-pion contribution to hadronic vacuum polarization_ , _JHEP_ 08 (2019) 137 [1907.01556].
  * [12] M. Davier, A. Hoecker, B. Malaescu and Z. Zhang, _A new evaluation of the hadronic vacuum polarisation contributions to the muon anomalous magnetic moment and to $\mathbf{\bm{\alpha}(m_{Z}^{2})}$_, _Eur. Phys. J._ C80 (2020) 241 [1908.00921].
  * [13] A. Keshavarzi, D. Nomura and T. Teubner, _The $g-2$ of charged leptons, $\alpha(M_{Z}^{2})$ and the hyperfine splitting of muonium_, _Phys. Rev._ D101 (2020) 014029 [1911.00367].
  * [14] A. Kurz, T. Liu, P. Marquard and M. Steinhauser, _Hadronic contribution to the muon anomalous magnetic moment to next-to-next-to-leading order_ , _Phys. Lett._ B734 (2014) 144 [1403.6400].
  * [15] K. Melnikov and A. Vainshtein, _Hadronic light-by-light scattering contribution to the muon anomalous magnetic moment revisited_ , _Phys. Rev._ D70 (2004) 113006 [hep-ph/0312226].
  * [16] P. Masjuan and P. Sánchez-Puertas, _Pseudoscalar-pole contribution to the $(g_{\mu}-2)$: a rational approach_, _Phys. Rev._ D95 (2017) 054026 [1701.05829].
  * [17] G. Colangelo, M. Hoferichter, M. Procura and P. Stoffer, _Dispersion relation for hadronic light-by-light scattering: two-pion contributions_ , _JHEP_ 04 (2017) 161 [1702.07347].
  * [18] M. Hoferichter, B.-L. Hoid, B. Kubis, S. Leupold and S. P. Schneider, _Dispersion relation for hadronic light-by-light scattering: pion pole_ , _JHEP_ 10 (2018) 141 [1808.04823].
  * [19] A. Gérardin, H. B. Meyer and A. Nyffeler, _Lattice calculation of the pion transition form factor with $N_{f}=2+1$ Wilson quarks_, _Phys. Rev._ D100 (2019) 034520 [1903.09471].
  * [20] J. Bijnens, N. Hermansson-Truedsson and A. Rodríguez-Sánchez, _Short-distance constraints for the HLbL contribution to the muon anomalous magnetic moment_ , _Phys. Lett._ B798 (2019) 134994 [1908.03331].
  * [21] G. Colangelo, F. Hagelstein, M. Hoferichter, L. Laub and P. Stoffer, _Longitudinal short-distance constraints for the hadronic light-by-light contribution to $(g-2)_{\mu}$ with large-$N_{c}$ Regge models_, _JHEP_ 03 (2020) 101 [1910.13432].
  * [22] T. Blum, N. Christ, M. Hayakawa, T. Izubuchi, L. Jin, C. Jung et al., _The hadronic light-by-light scattering contribution to the muon anomalous magnetic moment from lattice QCD_ , _Phys. Rev. Lett._ 124 (2020) 132002 [1911.08123].
  * [23] G. Colangelo, M. Hoferichter, A. Nyffeler, M. Passera and P. Stoffer, _Remarks on higher-order hadronic corrections to the muon $g-2$_, _Phys. Lett._ B735 (2014) 90 [1403.7512].
  * [24] P. Athron, C. Balázs, D. H. Jacob, W. Kotlarski, D. Stöckinger and H. Stöckinger-Kim, _New physics explanations of $a_{\mu}$ in light of the FNAL muon $g-2$ measurement_, 2104.03691.
  * [25] P. Fayet and S. Ferrara, _Supersymmetry_ , _Phys. Rept._ 32 (1977) 249.
  * [26] H. E. Haber and G. L. Kane, _The Search for Supersymmetry: Probing Physics Beyond the Standard Model_ , _Phys. Rept._ 117 (1985) 75.
  * [27] S. P. Martin, _A Supersymmetry primer_ , hep-ph/9709356.
  * [28] G. Jungman, M. Kamionkowski and K. Griest, _Supersymmetric dark matter_ , _Phys. Rept._ 267 (1996) 195 [hep-ph/9506380].
  * [29] S. P. Martin and J. D. Wells, _Muon Anomalous Magnetic Dipole Moment in Supersymmetric Theories_ , _Phys. Rev. D_ 64 (2001) 035003 [hep-ph/0103067].
  * [30] F. Domingo and U. Ellwanger, _Constraints from the Muon g-2 on the Parameter Space of the NMSSM_ , _JHEP_ 07 (2008) 079 [0806.0733].
  * [31] T. Moroi, _The Muon anomalous magnetic dipole moment in the minimal supersymmetric standard model_ , _Phys. Rev. D_ 53 (1996) 6565 [hep-ph/9512396].
  * [32] W. Hollik, J. I. Illana, S. Rigolin and D. Stockinger, _One loop MSSM contribution to the weak magnetic dipole moments of heavy fermions_ , _Phys. Lett. B_ 416 (1998) 345 [hep-ph/9707437].
  * [33] P. Athron, M. Bach, H. G. Fargnoli, C. Gnendiger, R. Greifenhagen, J.-h. Park et al., _GM2Calc: Precise MSSM prediction for $(g-2)$ of the muon_, _Eur. Phys. J. C_ 76 (2016) 62 [1510.08071].
  * [34] M. Endo, K. Hamaguchi, S. Iwamoto and T. Kitahara, _Supersymmetric interpretation of the muon g – 2 anomaly_ , _JHEP_ 07 (2021) 075 [2104.03217].
  * [35] D. Stockinger, _The Muon Magnetic Moment and Supersymmetry_ , _J. Phys. G_ 34 (2007) R45 [hep-ph/0609168].
  * [36] A. Czarnecki and W. J. Marciano, _The Muon anomalous magnetic moment: A Harbinger for ’new physics’_ , _Phys. Rev. D_ 64 (2001) 013014 [hep-ph/0102122].
  * [37] J. Cao, Z. Heng, D. Li and J. M. Yang, _Current experimental constraints on the lightest Higgs boson mass in the constrained MSSM_ , _Phys. Lett. B_ 710 (2012) 665 [1112.4391].
  * [38] Z. Kang, _$H_{u,d}$ -messenger Couplings Address the $\mu/B_{\mu}$ \& $A_{t}/m_{H_{u}}^{2}$ Problem and $(g-2)_{\mu}$ Puzzle_, 1610.06024.
  * [39] B. Zhu, R. Ding and T. Li, _Higgs mass and muon anomalous magnetic moment in the MSSM with gauge-gravity hybrid mediation_ , _Phys. Rev. D_ 96 (2017) 035029 [1610.09840].
  * [40] T. T. Yanagida and N. Yokozaki, _Muon g $-$ 2 in MSSM gauge mediation revisited_, _Phys. Lett. B_ 772 (2017) 409 [1704.00711].
  * [41] K. Hagiwara, K. Ma and S. Mukhopadhyay, _Closing in on the chargino contribution to the muon g-2 in the MSSM: current LHC constraints_ , _Phys. Rev. D_ 97 (2018) 055035 [1706.09313].
  * [42] P. Cox, C. Han and T. T. Yanagida, _Muon $g-2$ and dark matter in the minimal supersymmetric standard model_, _Phys. Rev. D_ 98 (2018) 055015 [1805.02802].
  * [43] H. M. Tran and H. T. Nguyen, _GUT-inspired MSSM in light of muon $g-2$ and LHC results at $\sqrt{s}=13$ TeV_, _Phys. Rev. D_ 99 (2019) 035040 [1812.11757].
  * [44] B. P. Padley, K. Sinha and K. Wang, _Natural Supersymmetry, Muon $g-2$, and the Last Crevices for the Top Squark_, _Phys. Rev. D_ 92 (2015) 055025 [1505.05877].
  * [45] A. Choudhury, L. Darmé, L. Roszkowski, E. M. Sessolo and S. Trojanowski, _Muon g $-$ 2 and related phenomenology in constrained vector-like extensions of the MSSM_, _JHEP_ 05 (2017) 072 [1701.08778].
  * [46] N. Okada and H. M. Tran, _125 GeV Higgs boson mass and muon $g-2$ in 5D MSSM_, _Phys. Rev. D_ 94 (2016) 075016 [1606.05329].
  * [47] X. Du and F. Wang, _NMSSM From Alternative Deflection in Generalized Deflected Anomaly Mediated SUSY Breaking_ , _Eur. Phys. J. C_ 78 (2018) 431 [1710.06105].
  * [48] X. Ning and F. Wang, _Solving the muon g-2 anomaly within the NMSSM from generalized deflected AMSB_ , _JHEP_ 08 (2017) 089 [1704.05079].
  * [49] K. Wang, F. Wang, J. Zhu and Q. Jie, _The semi-constrained NMSSM in light of muon g-2, LHC, and dark matter constraints_ , _Chin. Phys. C_ 42 (2018) 103109 [1811.04435].
  * [50] J.-L. Yang, T.-F. Feng, Y.-L. Yan, W. Li, S.-M. Zhao and H.-B. Zhang, _Lepton-flavor violation and two loop electroweak corrections to $(g-2)_{\mu}$ in the B-L symmetric SSM_, _Phys. Rev. D_ 99 (2019) 015002 [1812.03860].
  * [51] C.-X. Liu, H.-B. Zhang, J.-L. Yang, S.-M. Zhao, Y.-B. Liu and T.-F. Feng, _Higgs boson decay $h\rightarrow Z\gamma$ and muon magnetic dipole moment in the $\mu\nu$SSM_, _JHEP_ 04 (2020) 002 [2002.04370].
  * [52] J. Cao, J. Lian, L. Meng, Y. Yue and P. Zhu, _Anomalous muon magnetic moment in the inverse seesaw extended next-to-minimal supersymmetric standard model_ , _Phys. Rev. D_ 101 (2020) 095009 [1912.10225].
  * [53] J. Cao, Y. He, J. Lian, D. Zhang and P. Zhu, _Electron and muon anomalous magnetic moments in the inverse seesaw extended NMSSM_ , _Phys. Rev. D_ 104 (2021) 055009 [2102.11355].
  * [54] W. Ke and P. Slavich, _Higgs-mass constraints on a supersymmetric solution of the muon g-2 anomaly_ , 2109.15277.
  * [55] J. L. Lamborn, T. Li, J. A. Maxin and D. V. Nanopoulos, _Resolving the $(g-2)_{\mu}$ Discrepancy with $\mathcal{F}$-$SU$(5) Intersecting D-branes_, 2108.08084.
  * [56] S. Li, Y. Xiao and J. M. Yang, _Constraining CP-phases in SUSY: an interplay of muon/electron $g-2$ and electron EDM_, 2108.00359.
  * [57] Y. Nakai, M. Reece and M. Suzuki, _Supersymmetric alignment models for (g $-$ 2)μ_, _JHEP_ 10 (2021) 068 [2107.10268].
  * [58] S. Li, Y. Xiao and J. M. Yang, _Can electron and muon $g-2$ anomalies be jointly explained in SUSY?_, 2107.04962.
  * [59] J. S. Kim, D. E. Lopez-Fogliani, A. D. Perez and R. R. de Austri, _The new $(g-2)_{\mu}$ and Right-Handed Sneutrino Dark Matter_, 2107.02285.
  * [60] Z. Li, G.-L. Liu, F. Wang, J. M. Yang and Y. Zhang, _Gluino-SUGRA scenarios in light of FNAL muon g-2 anomaly_ , 2106.04466.
  * [61] W. Altmannshofer, S. A. Gadam, S. Gori and N. Hamer, _Explaining $(g-2)_{\mu}$ with Multi-TeV Sleptons_, 2104.08293.
  * [62] H. Baer, V. Barger and H. Serce, _Anomalous muon magnetic moment, supersymmetry, naturalness, LHC search limits and the landscape_ , _Phys. Lett. B_ 820 (2021) 136480 [2104.07597].
  * [63] M. Chakraborti, L. Roszkowski and S. Trojanowski, _GUT-constrained supersymmetry and dark matter in light of the new $(g-2)_{\mu}$ determination_, _JHEP_ 05 (2021) 252 [2104.04458].
  * [64] A. Aboubrahim, M. Klasen and P. Nath, _What the Fermilab muon $g-$2 experiment tells us about discovering supersymmetry at high luminosity and high energy upgrades to the LHC_, _Phys. Rev. D_ 104 (2021) 035039 [2104.03839].
  * [65] S. Iwamoto, T. T. Yanagida and N. Yokozaki, _Wino-Higgsino dark matter in MSSM from the g-2 anomaly_ , _Phys. Lett. B_ 823 (2021) 136768 [2104.03223].
  * [66] M. Chakraborti, S. Heinemeyer and I. Saha, _The new ”MUON G-2” Result and Supersymmetry_ , 2104.03287.
  * [67] J. Cao, J. Lian, Y. Pan, D. Zhang and P. Zhu, _Improved $(g-2)_{\mu}$ measurement and singlino dark matter in $\mu$-term extended $\mathbb{Z}_{3}$-NMSSM_, _JHEP_ 09 (2021) 175 [2104.03284].
  * [68] W. Yin, _Muon g $-$ 2 anomaly in anomaly mediation_, _JHEP_ 06 (2021) 029 [2104.03259].
  * [69] H.-B. Zhang, C.-X. Liu, J.-L. Yang and T.-F. Feng, _Muon anomalous magnetic dipole moment in the $\mu\nu$SSM_, 2104.03489.
  * [70] M. Ibe, S. Kobayashi, Y. Nakayama and S. Shirai, _Muon $g-2$ in Gauge Mediation without SUSY CP Problem_, 2104.03289.
  * [71] C. Han, _Muon g-2 and CP violation in MSSM_ , 2104.03292.
  * [72] F. Wang, L. Wu, Y. Xiao, J. M. Yang and Y. Zhang, _GUT-scale constrained SUSY in light of new muon g-2 measurement_ , _Nucl. Phys. B_ 970 (2021) 115486 [2104.03262].
  * [73] M.-D. Zheng and H.-H. Zhang, _Studying the $b\to s\ell+\ell$\- anomalies and (g-2)$\mu$ in R-parity violating MSSM framework with the inverse seesaw mechanism_, _Phys. Rev. D_ 104 (2021) 115023.
  * [74] M. Chakraborti, S. Heinemeyer, I. Saha and C. Schappacher, _$(g-2)_{\mu}$ and SUSY Dark Matter: Direct Detection and Collider Search Complementarity_, 2112.01389.
  * [75] A. Aboubrahim, M. Klasen, P. Nath and R. M. Syed, _Tests of gluino-driven radiative breaking of the electroweak symmetry at the LHC_ , in _10th International Conference on New Frontiers in Physics_ , 12, 2021, 2112.04986.
  * [76] M. I. Ali, M. Chakraborti, U. Chattopadhyay and S. Mukherjee, _Muon and Electron $(g-2)$ Anomalies with Non-Holomorphic Interactions in MSSM_, 2112.09867.
  * [77] K. Wang and J. Zhu, _A smuon in the NMSSM confronted with the muon g-2 and SUSY searches_ , 2112.14576.
  * [78] M. Chakraborti, S. Heinemeyer and I. Saha, _Improved $(g-2)_{\mu}$ Measurements and Supersymmetry_, _Eur. Phys. J. C_ 80 (2020) 984 [2006.15157].
  * [79] S. Baum, M. Carena, N. R. Shah and C. E. M. Wagner, _The tiny (g-2) muon wobble from small- $\mu$ supersymmetry_, _JHEP_ 01 (2022) 025 [2104.03302].
  * [80] XENON collaboration, E. Aprile et al., _Dark Matter Search Results from a One Ton-Year Exposure of XENON1T_ , _Phys. Rev. Lett._ 121 (2018) 111302 [1805.12562].
  * [81] XENON collaboration, E. Aprile et al., _Constraining the spin-dependent WIMP-nucleon cross sections with XENON1T_ , _Phys. Rev. Lett._ 122 (2019) 141301 [1902.03234].
  * [82] PandaX-II collaboration, C. Cheng et al., _Search for Light Dark Matter-Electron Scatterings in the PandaX-II Experiment_ , _Phys. Rev. Lett._ 126 (2021) 211803 [2101.07479].
  * [83] PandaX-4T collaboration, Y. Meng et al., _Dark Matter Search Results from the PandaX-4T Commissioning Run_ , 2107.13438.
  * [84] ATLAS collaboration, G. Aad et al., _Search for chargino-neutralino production with mass splittings near the electroweak scale in three-lepton final states in $\sqrt{s}$=13 TeV $pp$ collisions with the ATLAS detector_, _Phys. Rev. D_ 101 (2020) 072001 [1912.08479].
  * [85] ATLAS collaboration, G. Aad et al., _Search for electroweak production of charginos and sleptons decaying into final states with two leptons and missing transverse momentum in $\sqrt{s}=13$ TeV $pp$ collisions using the ATLAS detector_, _Eur. Phys. J. C_ 80 (2020) 123 [1908.08215].
  * [86] ATLAS collaboration, G. Aad et al., _Search for direct production of electroweakinos in final states with one lepton, missing transverse momentum and a Higgs boson decaying into two $b$-jets in $pp$ collisions at $\sqrt{s}=13$ TeV with the ATLAS detector_, _Eur. Phys. J. C_ 80 (2020) 691 [1909.09226].
  * [87] CMS collaboration, A. M. Sirunyan et al., _Search for supersymmetric partners of electrons and muons in proton-proton collisions at $\sqrt{s}=$ 13 TeV_, _Phys. Lett. B_ 790 (2019) 140 [1806.05264].
  * [88] CMS collaboration, A. M. Sirunyan et al., _Combined search for electroweak production of charginos and neutralinos in proton-proton collisions at $\sqrt{s}=$ 13 TeV_, _JHEP_ 03 (2018) 160 [1801.03957].
  * [89] ATLAS collaboration, G. Aad et al., _Searches for electroweak production of supersymmetric particles with compressed mass spectra in $\sqrt{s}=$ 13 TeV $pp$ collisions with the ATLAS detector_, _Phys. Rev. D_ 101 (2020) 052005 [1911.12606].
  * [90] ATLAS collaboration, G. Aad et al., _Search for chargino–neutralino pair production in final states with three leptons and missing transverse momentum in $\sqrt{s}=13$ TeV $pp$ collisions with the ATLAS detector_, 2106.01676.
  * [91] CMS collaboration, A. M. Sirunyan et al., _Search for supersymmetry in final states with two oppositely charged same-flavor leptons and missing transverse momentum in proton-proton collisions at $\sqrt{s}=$ 13 TeV_, _JHEP_ 04 (2021) 123 [2012.08600].
  * [92] G. R. Farrar and P. Fayet, _Phenomenology of the Production, Decay, and Detection of New Hadronic States Associated with Supersymmetry_ , _Phys. Lett. B_ 76 (1978) 575.
  * [93] J. F. Gunion and H. E. Haber, _Higgs Bosons in Supersymmetric Models. 1._ , _Nucl. Phys. B_ 272 (1986) 1.
  * [94] A. Djouadi, _The Anatomy of electro-weak symmetry breaking. II. The Higgs bosons in the minimal supersymmetric model_ , _Phys. Rept._ 459 (2008) 1 [hep-ph/0503173].
  * [95] Planck collaboration, N. Aghanim et al., _Planck 2018 results. VI. Cosmological parameters_ , _Astron. Astrophys._ 641 (2020) A6 [1807.06209].
  * [96] E. Bagnaschi et al., _Likelihood Analysis of the pMSSM11 in Light of LHC 13-TeV Data_ , _Eur. Phys. J. C_ 78 (2018) 256 [1710.11091].
  * [97] H. Baer, V. Barger, P. Huang and X. Tata, _Natural Supersymmetry: LHC, dark matter and ILC searches_ , _JHEP_ 05 (2012) 109 [1203.5539].
  * [98] CMS collaboration, A. M. Sirunyan et al., _Searches for physics beyond the standard model with the $M_{\mathrm{T2}}$ variable in hadronic final states with and without disappearing tracks in proton-proton collisions at $\sqrt{s}=$ 13 TeV_, _Eur. Phys. J. C_ 80 (2020) 3 [1909.03460].
  * [99] J. Cao, Y. He, L. Shang, Y. Zhang and P. Zhu, _Current status of a natural NMSSM in light of LHC 13 TeV data and XENON-1T results_ , _Phys. Rev._ D99 (2019) 075020 [1810.09143].
  * [100] ATLAS collaboration, G. Aad et al., _Search for charged Higgs bosons decaying into a top quark and a bottom quark at $\sqrt{\mathrm{s}}$ = 13 TeV with the ATLAS detector_, _JHEP_ 06 (2021) 145 [2102.10076].
  * [101] U. Ellwanger, C. Hugonie and A. M. Teixeira, _The Next-to-Minimal Supersymmetric Standard Model_ , _Phys. Rept._ 496 (2010) 1 [0910.1785].
  * [102] M. Maniatis, _The Next-to-Minimal Supersymmetric extension of the Standard Model reviewed_ , _Int. J. Mod. Phys. A_ 25 (2010) 3505 [0906.0777].
  * [103] J. Cao, Y. He, L. Shang, W. Su and Y. Zhang, _Natural NMSSM after LHC Run I and the Higgsino dominated dark matter scenario_ , _JHEP_ 08 (2016) 037 [1606.04416].
  * [104] U. Ellwanger, _Present Status and Future Tests of the Higgsino-Singlino Sector in the NMSSM_ , _JHEP_ 02 (2017) 051 [1612.06574].
  * [105] Q.-F. Xiang, X.-J. Bi, P.-F. Yin and Z.-H. Yu, _Searching for Singlino-Higgsino Dark Matter in the NMSSM_ , _Phys. Rev. D_ 94 (2016) 055031 [1606.02149].
  * [106] S. Baum, M. Carena, N. R. Shah and C. E. Wagner, _Higgs portals for thermal Dark Matter. EFT perspectives and the NMSSM_ , _JHEP_ 04 (2018) 069 [1712.09873].
  * [107] U. Ellwanger and C. Hugonie, _The higgsino–singlino sector of the NMSSM: combined constraints from dark matter and the LHC_ , _Eur. Phys. J. C_ 78 (2018) 735 [1806.09478].
  * [108] F. Domingo, J. S. Kim, V. M. Lozano, P. Martin-Ramiro and R. Ruiz de Austri, _Confronting the neutralino and chargino sector of the NMSSM with the multilepton searches at the LHC_ , _Phys. Rev. D_ 101 (2020) 075010 [1812.05186].
  * [109] S. Baum, N. R. Shah and K. Freese, _The NMSSM is within Reach of the LHC: Mass Correlations \ & Decay Signatures_, _JHEP_ 04 (2019) 011 [1901.02332].
  * [110] M. van Beekveld, S. Caron and R. Ruiz de Austri, _The current status of fine-tuning in supersymmetry_ , _JHEP_ 01 (2020) 147 [1906.10706].
  * [111] W. Abdallah, A. Chatterjee and A. Datta, _Revisiting singlino dark matter of the natural $Z_{3}$-symmetric NMSSM in the light of LHC_, _JHEP_ 09 (2019) 095 [1907.06270].
  * [112] J. Cao, L. Meng, Y. Yue, H. Zhou and P. Zhu, _Suppressing the scattering of wimp dark matter and nucleons in supersymmetric theories_ , _Phys. Rev. D_ 101 (2020) 075003.
  * [113] M. Guchait and A. Roy, _Light Singlino Dark Matter at the LHC_ , _Phys. Rev. D_ 102 (2020) 075023 [2005.05190].
  * [114] W. Abdallah, A. Datta and S. Roy, _A relatively light, highly bino-like dark matter in the Z 3-symmetric NMSSM and recent LHC searches_, _JHEP_ 04 (2021) 122 [2012.04026].
  * [115] H. Zhou, J. Cao, J. Lian and D. Zhang, _Singlino-dominated dark matter in Z3-symmetric NMSSM_ , _Phys. Rev. D_ 104 (2021) 015017 [2102.05309].
  * [116] J. Cao, D. Li, J. Lian, Y. Yue and H. Zhou, _Singlino-dominated dark matter in general NMSSM_ , _JHEP_ 06 (2021) 176 [2102.05317].
  * [117] U. Ellwanger, _Nonrenormalizable interactions from supergravity, quantum corrections and effecive low-energy theories_ , _Phys. Lett. B_ 133 (1983) 187.
  * [118] S. A. Abel, _Destabilizing divergences in the NMSSM_ , _Nucl. Phys. B_ 480 (1996) 55 [hep-ph/9609323].
  * [119] C. F. Kolda, S. Pokorski and N. Polonsky, _Stabilized singlets in supergravity as a source of the mu - parameter_ , _Phys. Rev. Lett._ 80 (1998) 5263 [hep-ph/9803310].
  * [120] C. Panagiotakopoulos and K. Tamvakis, _Stabilized NMSSM without domain walls_ , _Phys. Lett. B_ 446 (1999) 224 [hep-ph/9809475].
  * [121] G. G. Ross and K. Schmidt-Hoberg, _The Fine-Tuning of the Generalised NMSSM_ , _Nucl. Phys. B_ 862 (2012) 710 [1108.1284].
  * [122] H. M. Lee, S. Raby, M. Ratz, G. G. Ross, R. Schieren, K. Schmidt-Hoberg et al., _A unique $\mathbb{Z}_{4}^{R}$ symmetry for the MSSM_, _Phys. Lett. B_ 694 (2011) 491 [1009.0905].
  * [123] H. M. Lee, S. Raby, M. Ratz, G. G. Ross, R. Schieren, K. Schmidt-Hoberg et al., _Discrete R symmetries for the MSSM and its singlet extensions_ , _Nucl. Phys. B_ 850 (2011) 1 [1102.3595].
  * [124] G. G. Ross, K. Schmidt-Hoberg and F. Staub, _The Generalised NMSSM at One Loop: Fine Tuning and Phenomenology_ , _JHEP_ 08 (2012) 074 [1205.1509].
  * [125] J.-J. Cao, Z.-X. Heng, J. M. Yang, Y.-M. Zhang and J.-Y. Zhu, _A SM-like Higgs near 125 GeV in low energy SUSY: a comparative study for MSSM and NMSSM_ , _JHEP_ 03 (2012) 086 [1202.5821].
  * [126] S. Ferrara, R. Kallosh, A. Linde, A. Marrani and A. Van Proeyen, _Jordan Frame Supergravity and Inflation in NMSSM_ , _Phys. Rev. D_ 82 (2010) 045003 [1004.0712].
  * [127] S. Ferrara, R. Kallosh, A. Linde, A. Marrani and A. Van Proeyen, _Superconformal Symmetry, NMSSM, and Inflation_ , _Phys. Rev. D_ 83 (2011) 025008 [1008.2942].
  * [128] M. B. Einhorn and D. R. T. Jones, _Inflation with Non-minimal Gravitational Couplings in Supergravity_ , _JHEP_ 03 (2010) 026 [0912.2718].
  * [129] W. G. Hollik, S. Liebler, G. Moortgat-Pick, S. Paßehr and G. Weiglein, _Phenomenology of the inflation-inspired NMSSM at the electroweak scale_ , _Eur. Phys. J. C_ 79 (2019) 75 [1809.07371].
  * [130] W. G. Hollik, C. Li, G. Moortgat-Pick and S. Paasch, _Phenomenology of a Supersymmetric Model Inspired by Inflation_ , _Eur. Phys. J. C_ 81 (2021) 141 [2004.14852].
  * [131] C. Cheung, M. Papucci, D. Sanford, N. R. Shah and K. M. Zurek, _NMSSM Interpretation of the Galactic Center Excess_ , _Phys. Rev. D_ 90 (2014) 075011 [1406.6372].
  * [132] M. Badziak, M. Olechowski and P. Szczerbiak, _Blind spots for neutralino dark matter in the NMSSM_ , _JHEP_ 03 (2016) 179 [1512.02472].
  * [133] M. Badziak, M. Olechowski and P. Szczerbiak, _Spin-dependent constraints on blind spots for thermal singlino-higgsino dark matter with(out) light singlets_ , _Journal of High Energy Physics_ 2017 (2017) .
  * [134] M. Pospelov, A. Ritz and M. B. Voloshin, _Secluded WIMP Dark Matter_ , _Phys. Lett. B_ 662 (2008) 53 [0711.4866].
  * [135] F. Feroz, M. P. Hobson and M. Bridges, _MultiNest: an efficient and robust Bayesian inference tool for cosmology and particle physics_ , _Mon. Not. Roy. Astron. Soc._ 398 (2009) 1601 [0809.3437].
  * [136] F. Staub, _SARAH_ , 0806.0538.
  * [137] F. Staub, _SARAH 3.2: Dirac Gauginos, UFO output, and more_ , _Comput. Phys. Commun._ 184 (2013) 1792 [1207.0906].
  * [138] F. Staub, _SARAH 4 : A tool for (not only SUSY) model builders_ , _Comput. Phys. Commun._ 185 (2014) 1773 [1309.7223].
  * [139] F. Staub, _Exploring new models in all detail with SARAH_ , _Adv. High Energy Phys._ 2015 (2015) 840780 [1503.04200].
  * [140] W. Porod, _SPheno, a program for calculating supersymmetric spectra, SUSY particle decays and SUSY particle production at e+ e- colliders_ , _Comput. Phys. Commun._ 153 (2003) 275 [hep-ph/0301101].
  * [141] W. Porod and F. Staub, _SPheno 3.1: Extensions including flavour, CP-phases and models beyond the MSSM_ , _Comput. Phys. Commun._ 183 (2012) 2458 [1104.1573].
  * [142] W. Porod, F. Staub and A. Vicente, _A Flavor Kit for BSM models_ , _Eur. Phys. J. C_ 74 (2014) 2992 [1405.1434].
  * [143] G. Belanger, F. Boudjema, A. Pukhov and A. Semenov, _MicrOMEGAs: A Program for calculating the relic density in the MSSM_ , _Comput. Phys. Commun._ 149 (2002) 103 [hep-ph/0112278].
  * [144] G. Belanger, F. Boudjema, C. Hugonie, A. Pukhov and A. Semenov, _Relic density of dark matter in the NMSSM_ , _JCAP_ 09 (2005) 001 [hep-ph/0505142].
  * [145] G. Belanger, F. Boudjema, A. Pukhov and A. Semenov, _MicrOMEGAs 2.0: A Program to calculate the relic density of dark matter in a generic model_ , _Comput. Phys. Commun._ 176 (2007) 367 [hep-ph/0607059].
  * [146] G. Belanger, F. Boudjema, A. Pukhov and A. Semenov, _micrOMEGAs: A Tool for dark matter studies_ , _Nuovo Cim. C_ 033N2 (2010) 111 [1005.4133].
  * [147] G. Belanger, F. Boudjema, A. Pukhov and A. Semenov, _micrOMEGAs $\\_$3: A program for calculating dark matter observables_, _Comput. Phys. Commun._ 185 (2014) 960 [1305.0237].
  * [148] D. Barducci, G. Belanger, J. Bernon, F. Boudjema, J. Da Silva, S. Kraml et al., _Collider limits on new physics within micrOMEGAs $\\_$4.3_, _Comput. Phys. Commun._ 222 (2018) 327 [1606.03834].
  * [149] Planck collaboration, N. Aghanim et al., _Planck 2018 results. VI. Cosmological parameters_ , _Astron. Astrophys._ 641 (2020) A6 [1807.06209].
  * [150] XENON collaboration, E. Aprile et al., _Dark Matter Search Results from a One Ton-Year Exposure of XENON1T_ , _Phys. Rev. Lett._ 121 (2018) 111302 [1805.12562].
  * [151] XENON collaboration, E. Aprile et al., _Constraining the spin-dependent WIMP-nucleon cross sections with XENON1T_ , _Phys. Rev. Lett._ 122 (2019) 141301 [1902.03234].
  * [152] Fermi-LAT collaboration, M. Ackermann et al., _Searching for Dark Matter Annihilation from Milky Way Dwarf Spheroidal Galaxies with Six Years of Fermi Large Area Telescope Data_ , _Phys. Rev. Lett._ 115 (2015) 231301 [1503.02641].
  * [153] L. M. Carpenter, R. Colburn, J. Goodman and T. Linden, _Indirect Detection Constraints on s and t Channel Simplified Models of Dark Matter_ , _Phys. Rev. D_ 94 (2016) 055027 [1606.04138].
  * [154] P. Bechtle, S. Heinemeyer, O. Stål, T. Stefaniak and G. Weiglein, _Probing the Standard Model with Higgs signal rates from the Tevatron, the LHC and a future ILC_ , _JHEP_ 11 (2014) 039 [1403.1582].
  * [155] P. Bechtle, S. Heinemeyer, O. Stal, T. Stefaniak and G. Weiglein, _Applying Exclusion Likelihoods from LHC Searches to Extended Higgs Sectors_ , _Eur. Phys. J. C_ 75 (2015) 421 [1507.06706].
  * [156] Particle Data Group collaboration, M. Tanabashi, K. Hagiwara, Hikasa et al., _Review of particle physics_ , _Phys. Rev. D_ 98 (2018) 030001.
  * [157] C. K. Khosa, S. Kraml, A. Lessa, P. Neuhuber and W. Waltenberger, _SModelS database update v1.2.3_ , 2005.00555.
  * [158] M. Drees, H. Dreiner, D. Schmeier, J. Tattersall and J. S. Kim, _CheckMATE: Confronting your Favourite New Physics Model with LHC Data_ , _Comput. Phys. Commun._ 187 (2015) 227 [1312.2591].
  * [159] D. Dercks, N. Desai, J. S. Kim, K. Rolbiecki, J. Tattersall and T. Weber, _CheckMATE 2: From the model to the limit_ , _Comput. Phys. Commun._ 221 (2017) 383 [1611.09856].
  * [160] J. S. Kim, D. Schmeier, J. Tattersall and K. Rolbiecki, _A framework to create customised LHC analyses within CheckMATE_ , _Comput. Phys. Commun._ 196 (2015) 535 [1503.01123].
  * [161] J. E. Camargo-Molina, B. O’Leary, W. Porod and F. Staub, _$\mathbf{Vevacious}$ : A Tool For Finding The Global Minima Of One-Loop Effective Potentials With Many Scalars_, _Eur. Phys. J. C_ 73 (2013) 2588 [1307.1477].
  * [162] J. E. Camargo-Molina, B. Garbrecht, B. O’Leary, W. Porod and F. Staub, _Constraining the Natural MSSM through tunneling to color-breaking vacua at zero and non-zero temperature_ , _Phys. Lett. B_ 737 (2014) 156 [1405.7376].
  * [163] A. Fowlie and M. H. Bardsley, _Superplot: a graphical interface for plotting and analysing MultiNest output_ , _Eur. Phys. J. Plus_ 131 (2016) 391 [1603.00555].
  * [164] J. Cao, J. Li, Y. Pan, L. Shang, Y. Yue and D. Zhang, _Bayesian analysis of sneutrino dark matter in the NMSSM with a type-I seesaw mechanism_ , _Phys. Rev. D_ 99 (2019) 115033 [1807.03762].
  * [165] J. L. Hintze and R. D. Nelson, _Violin plots: a box plot-density trace synergism_ , _The American Statistician_ 52 (1998) 181.
  * [166] W. Beenakker, R. Hopker and M. Spira, _PROSPINO: A Program for the production of supersymmetric particles in next-to-leading order QCD_ , hep-ph/9611232.
  * [167] J. Alwall, M. Herquet, F. Maltoni, O. Mattelaer and T. Stelzer, _MadGraph 5 : Going Beyond_ , _JHEP_ 06 (2011) 128 [1106.0522].
  * [168] E. Conte, B. Fuks and G. Serret, _MadAnalysis 5, A User-Friendly Framework for Collider Phenomenology_ , _Comput. Phys. Commun._ 184 (2013) 222 [1206.1599].
  * [169] T. Sjöstrand, S. Ask, J. R. Christiansen, R. Corke, N. Desai, P. Ilten et al., _An introduction to PYTHIA 8.2_ , _Comput. Phys. Commun._ 191 (2015) 159 [1410.3012].
  * [170] DELPHES 3 collaboration, J. de Favereau, C. Delaere, P. Demin, A. Giammanco, V. Lemaître, A. Mertens et al., _DELPHES 3, A modular framework for fast simulation of a generic collider experiment_ , _JHEP_ 02 (2014) 057 [1307.6346].
  * [171] ATLAS collaboration, M. Aaboud et al., _Search for electroweak production of supersymmetric particles in final states with two or three leptons at $\sqrt{s}=13\,$TeV with the ATLAS detector_, _Eur. Phys. J. C_ 78 (2018) 995 [1803.02762].
  * [172] ATLAS collaboration, M. Aaboud et al., _Search for photonic signatures of gauge-mediated supersymmetry in 13 TeV $pp$ collisions with the ATLAS detector_, _Phys. Rev. D_ 97 (2018) 092006 [1802.03158].
  * [173] ATLAS collaboration, M. Aaboud et al., _Search for electroweak production of supersymmetric states in scenarios with compressed mass spectra at $\sqrt{s}=13$ TeV with the ATLAS detector_, _Phys. Rev. D_ 97 (2018) 052010 [1712.08119].
  * [174] CMS collaboration, A. M. Sirunyan et al., _Search for electroweak production of charginos and neutralinos in multilepton final states in proton-proton collisions at $\sqrt{s}=$ 13 TeV_, _JHEP_ 03 (2018) 166 [1709.05406].
  * [175] CMS collaboration, A. M. Sirunyan et al., _Search for new physics in events with two soft oppositely charged leptons and missing transverse momentum in proton-proton collisions at $\sqrt{s}=$ 13 TeV_, _Phys. Lett. B_ 782 (2018) 440 [1801.01846].
  * [176] CMS collaboration, _Search for new physics in the compressed mass spectra scenario using events with two soft opposite-sign leptons and missing momentum energy at 13 TeV_ , CMS-PAS-SUS-16-025.
  * [177] ATLAS collaboration, _Search for supersymmetry with two and three leptons and missing transverse momentum in the final state at \sqrts=13 TeV with the ATLAS detector_ , ATLAS-CONF-2016-096.
  * [178] ATLAS collaboration, M. Aaboud et al., _Search for the direct production of charginos and neutralinos in final states with tau leptons in $\sqrt{s}=$ 13 TeV $pp$ collisions with the ATLAS detector_, _Eur. Phys. J. C_ 78 (2018) 154 [1708.07875].
  * [179] ATLAS collaboration, G. Aad et al., _Search for direct stau production in events with two hadronic $\tau$-leptons in $\sqrt{s}=13$ TeV $pp$ collisions with the ATLAS detector_, _Phys. Rev. D_ 101 (2020) 032009 [1911.06660].
  * [180] A. Pierce, N. R. Shah and K. Freese, _Neutralino Dark Matter with Light Staus_ , 1309.7351.


# A fast and efficient SIMD track reconstruction algorithm for the LHCb
Upgrade 1 VELO-PIX detector

A. Hennequin  B. Couturier  V. V. Gligorov  S. Ponce  R. Quagliani  L.
Lacassagne

###### Abstract

The upgraded CERN LHCb detector, due to start data taking in 2021, will have
to reconstruct 4 TB/s of raw detector data in real time using commodity
processors. This is one of the biggest real-time data processing challenges in
any scientific domain. We present an intrinsically parallel reconstruction
algorithm for the vertex detector of the LHCb experiment designed to optimally
exploit multi-core general purpose architectures. We compare it to previous
state-of-the-art scalar pattern recognition algorithms and show significantly
faster processing and in some cases increased physics performance over all
current alternatives. We evaluate the algorithm on two high-end architectures
from two different vendors and discuss in detail the impact of different SIMD
Instruction Set Architecture extensions on the performance.

##  1 Introduction

The LHCb detector [1] is a general purpose spectrometer in the forward
direction, optimized for the study of heavy flavour (primarily beauty and
charm) hadrons at the Large Hadron Collider111The large hadron collider is an
experimental facility located at CERN, which collides beams of protons with an
energy of 7 TeV per beam and studies the products of those collisions. LHCb is
one of the four main experiments located at the LHC. (LHC). It also has a rich
program of beyond Standard Model searches as well as hadronic, heavy ion, and
electroweak physics. A key limitation of the current LHCb detector is that the
full detector can only be read out at 1 MHz, while LHC collisions occur at 30
MHz. For this reason LHCb employs a hardware trigger system based on FPGAs,
which has access to a limited subset of detector information at 30 MHz, to
decide whether to read out a particular collision. The limited information
available to this hardware trigger, and in particular the lack of information
on charged particle trajectories (tracking) limits the efficiency for hadronic
signals to roughly between 10% and 30%.

For this reason, during the LHC second long shutdown (LS2), the LHCb detector
will undergo its first upgrade, as shown in Figure 1. The maximal physics
reach of collider experiments like LHCb is directly proportional to the number
of proton collisions which the detector can record per second. The primary
goal of this upgrade is to allow LHCb to increase the number of collisions per
second by a factor five. In addition LHCb is switching to a full detector
readout capable of operating at 30 MHz. The full 4 TB/s data rate will be sent
for real-time processing in an off-the-shelf data center, where a two-stage
software trigger222High Level Trigger, or HLT, in High Energy Physics jargon
will process the data in real time and select interesting signals for further
offline physics analysis. The first High Level Trigger stage (HLT1) performs a
fast reconstruction and selects approximately the 1 MHz of most interesting
LHC collisions for further analysis. The second stage (HLT2), operating on the
output of HLT1, performs a full reconstruction and real-time analysis of the
data. Removing the previous hardware trigger, which was reducing the data
volume by a factor 20, implies that the overall data volume processed will
increase by a factor of around 100. On the other hand if this data can be
processed, the additional information available for early decision making will
increase [2] processing efficiency for key physics benchmarks by a factor
between 2 and 10.

Figure 1: LHC timeline and VELO detectors lifespan.

In order to fully exploit this additional information, it is necessary to
improve LHCb’s reconstruction algorithms so that they are able to process the
LHCb upgrade data volume within the available computing resources. Concretely,
the data rate seen by the upgraded LHCb HLT is around 100 times larger than
for the current detector, with a flat budget for computing resources. In this
paper, we present an efficient and highly parallel CPU implementation of one
of the key LHCb reconstruction algorithms, we show that it fits within the
available resources for the LHCb upgrade, and we discuss the scaling of its
performance with some Single Instruction Multiple Data (SIMD) Instruction Set
Architecture (ISA) extensions on Intel’s Skylake and AMD’s Zen2 architectures.

###  1.1 The LHCb Upgrade 1 VELO-PIX detector

In addition to the triggerless readout, one of the major changes in the
upgraded LHCb detector is the total replacement of the VELO (Vertex Locator).
The purpose of this detector, located around the beamline over the interaction
region, is to precisely reconstruct the locations of the proton-proton
collisions (primary vertices, PVs, in physics jargon) and separate tracks
produced directly in PVs from tracks produced by particles which decay inside
the VELO but away from the PV. In order to improve the resolution of the PV
positions while increasing the luminosity, the detector technology changed
from silicon strips to silicon pixels. The geometry of the new VELO-PIX
detector is shown on Figure 2.

Figure 2: VELO-PIX (Silicon pixel detector) Geometry. The (x, y, z) cartesian
coordinate system is aligned with the beamline, with the z axis pointing
downstream. $\phi$ is the angle around the beamline. In the right hand
diagram, each square is a 14 $\times$ 14 mm silicon sensor of 256 $\times$ 256
pixels, positioned perpendicular to the beam.

###  1.2 Pattern recognition and fit

Pattern recognition for tracks consists in finding hits consistent with a
single particle traversing a detector. For the VELO detector, we search for
almost straight lines coming from the beamline. To evaluate the quality of the
tracking algorithm, we compare the reconstructed tracks to the set of
reconstructible tracks from the ground truth given by the Monte-Carlo
simulation [3, 4, 5, 6]. For the VELO, a particle is reconstructible if it
leaves at least 3 hits in the detector. A correctly reconstructed track is one
that has more than 70% of its hits created by a single true particle. If more
than one track candidate is matched to the same true particle, it is
interpreted as a clone. A track candidate that could not be matched to any
particle is a fake. We define the efficiency, the clone rate and the fake rate
as follow:

$\text{efficiency}=\frac{\lvert\\{reconstructed\\}\rvert}{\lvert\\{reconstructible\\}\rvert}$
$\text{clone
rate}=\frac{\lvert\\{clones\\}\rvert}{\lvert\\{clones\\}\cup\\{reconstructed\\}\rvert}$
$\text{fake
rate}=\frac{\lvert\\{fakes\\}\rvert}{\lvert\\{fakes\\}\cup\\{reconstructed\\}\rvert}$

A good tracking algorithm should have the highest efficiency and the lowest
clone and fake rates possible. As the efficiency only accounts for the track
being found but not the quality of the reconstructed tracks, we define the hit
efficiency as the fraction of hits from a true particle included in the
reconstructed track. This metric should be as high as possible and is a good
indicator of the quality of the reconstructed tracks.333Not all track hits are
equally important from a physics point of view. In particular, missing the
first hit on the track worsens the resolution on the track’s physics
parameters far more than missing a hit in the middle of the track. Similarly,
missing the last hit on the track worsens the resolution for extrapolating the
track to the rest of the LHCb detector.

Once the track candidates are found, a Kalman fit is performed on the hits in
order to define the state closest to the beamline and the state at the end of
the VELO (z = 770mm). A state consists in the slope of the track ($t_{x}$,
$t_{y}$) and the coordinates at ($x_{0}$, $y_{0}$, $z=0$). Due to multiple
scattering, it is expected that the two produced states are slightly
different. We define the $\chi^{2}$ of the track as:

$\chi^{2}=\sum_{h=(x,y,z)}^{\\{hits\\}}(x_{0}+h_{z}t_{x}-h_{x})^{2}+(y_{0}+h_{z}t_{y}-h_{y})^{2}$

The $\chi^{2}$ can later be used to remove fake tracks or be included in the
vertex $\chi^{2}$ computation.

###  1.3 History of VELO Tracking algorithms

The VELO Tracking algorithm used during the first LHC data taking period (Run
1) was developed in 2002 [7]. At that time, the VELO detector geometry was
using strips along $\phi$ and R, as shown in Figure 3. Consequently, the
tracking was done in two steps. First, a 2D tracking was performed in the R-z
projection where it was easy to find interesting tracks based on the slope and
alignments, then a space tracking step matched these R-z track stubs to
clusters on the $\phi$ strips.

Figure 3: VELO (Silicon strip detector) Geometry. Figures from [8], the “beam
axis” is what we refer to as beamline in the rest of the paper. The right hand
diagram has an example of a $\phi$ sensor on the left and an R sensor on the
right. The radius of the detectors is 45 mm.

The 2D tracking began by finding a triplet of aligned clusters in three
consecutive R sensors, then extended it as much as possible by predicting the
radius in the next sensors and finding the closest cluster. To avoid finding
the same track again, used clusters were marked and not considered in later
searches. To avoid missing tracks due to sensor inefficiencies, the algorithm
was allowed to skip one sensor in this search. The algorithm processed the R
sensors in a single step going toward the interaction region. Due to the
criteria applied on the slope and the single pass, no backward tracks were
reconstructed. Subsequently, the space tracking was performed for every R-z
track candidate. A second R-z tracking was then performed in the reverse
direction to find the backward tracks, useful for finding primary vertices.
After matching the R-z track stubs to clusters on the $\phi$ strips, the best
track candidate was selected. The candidate with the highest total number of
clusters was selected, or the candidate with the best track fit $\chi^{2}$ in
case of equality.

In 2004, the algorithm was updated [9] to fulfill the speed and efficiency
requirements of the real-time reconstruction for the different LHCb trigger
stages. The changes mainly concerned the tuning of tolerances and search
windows. It was noted that large search windows were needed in the track
extension step to allow the recovery of tracks not pointing to the beam-line,
for which the R-z projection is not exactly a straight line, and low momentum
tracks with large multiple scattering. In 2007, further tuning and analysis of
the algorithm were performed [10].

In 2011, a new implementation of the algorithm was introduced [11], motivated
by LHCb’s choice to run at twice the design’s instantaneous luminosity. The
consequently higher number of proton-proton collisions per bunch crossing and
detector occupancy, required the reconstruction to be reoptimized in order to
fit into the constraints of LHCb’s real-time data processing. In addition,
during the 2010 run it was found that the VELO could not come as close to the
LHC beamline as expected. Because of this, the search for R-z track stubs
introduced a further inefficiency for tracks produced away from the beamline.
The 2011 algorithm modified the R-z tracking to first search for quadruplets
of clusters, then triplets of clusters among the remaining unused clusters.
This approach allowed to reduce the fake track rate and sped the algorithm up.
The rest of the algorithm remained very similar to the previous
implementations. In 2015, a measurement of the reconstruction efficiency of
the VELO tracking was published [12].

A new VELO-PIX (VP) detector has been developed for the LHCb upgrade [13].
This is a silicon detector based on planes of square pixels, with a broadly
similar geometric coverage to the old R-z Velo. In 2009, the simulation
framework started supporting the new detector and in 2012 the first version of
the pixel VELO tracking algorithm was implemented [14]. In the pixel version,
the input of the tracking algorithm are the 3D Cartesian coordinates of the
reconstructed clusters on each pixel plane. Similar to the previous VELO
Tracking algorithm, the tracks are seeded by looking for pairs of unused
clusters whose estimated track slope would be compatible with the geometric
acceptance of the other LHCb detector components. Subsequently, the track
candidates are extended upstream (smaller z-position) by extrapolating and
looking for the closest cluster within a search window. A cut on the maximal
scattering angle is added and the search is abandoned if no clusters are found
on three consecutive stations. Three-clusters tracks are kept only if all
their clusters are unused and their $\chi^{2}$ is below a parametrizable
threshold. A detailed description of the algorithm and its performance was
given in the VELO Upgrade 1 TDR [15].

A study was conducted to use vertical vectorization with 128-bit SSE SIMD
extension to accelerate part of the algorithm [16] but resulted in a slowdown
due, according to the authors, to the need for data preparation to take
advantage of SIMD loads and stores. At that time, alternative global methods
based on the Hough Transform [17] and suitable for parallel architectures were
also evaluated [16][18, 19]. In 2014, a new local search algorithm based on
triplet seeding on GPU was presented [20]. The main difference with the
previous sequential work was that tracks were seeded and extended upstream
independently, in parallel. A post-processing step cleaned ghosts. This
preliminary work was further improved in [21].

In 2018, the CPU pixel tracking algorithm was made faster in order to improve
the throughput of the first stage of LHCb’s real-time reconstruction [22]. The
clusters were ordered by $\phi$ and the cluster search performed within
$\phi$-windows, the search for backward and forward tracks was split in two
different steps and some "speed-flags" were introduced, allowing early cuts in
the track candidates. In 2019, the search by triplet algorithm was revisited
for parallel architectures in the context of the Allen project [23]. This new
implementation used the $\phi$-windows to reduce the combinatorics and uses
synchronization between each layer to avoid track overlap.

##  2 SIMD VELO Tracking

###  2.1 Data preparation

The VELO-PIX detector is divided into 52 L-shaped modules, as depicted in
Figure 2. Each module is itself composed by 4 sensors of 3 chips each. The
chips have 256$\times$256 pixels, so the sensors have 256 rows and 768
columns. Each pixel is a square with a length of 55 microns (except at the
chip border where the pixels are elongated). The sensor pixels are packed into
Super-Pixels (SP) of size 2$\times$4 pixels, so the sensors have 64 SP rows
and 384 SP columns [24][25]. The modules are positioned along the z axis (see
Figure 2). Figure 4 shows the format of a Super-Pixel (SP) encoded in a 32-bit
integer. The less significant byte is a bitmask representing the pixels. The
row of the SP is stored from bit 8 to 13, and the column of the SP, from bit
14 to 22. The 31th bit is a flag indicating if the SP is isolated, ie. if it
doesn’t have any neighbours containing hits. The SP are delivered in small
packet of bits called raw banks. There is one raw bank per sensor and each one
contains the number of SP in the bank followed by the encoded SP.

Figure 4: VELO Super-pixel format

Before doing any tracking, the raw pixels must be decoded and grouped into
clusters. This step is crucial, as it prevents duplication of clusters if a
particle hits the sensor at the boundary of multiple pixels. This clustering
operation is a well known problem in computer vision, where it is referred as
connected component labeling. Pioneer algorithms[26, 27] have been accelerated
continuously to match modern architectures like multi-core CPU, FPGA or GPU
[28, 29, 30, 31, 32, 33]. But these algorithms were not adapted to low density
images until they were specialized to take advantage of the data format [34]
to label a sparse list of SP instead of pixels. This allows to further reduce
the amount of memory needed and to skip a decoding step. We first start by
preparing the data: we remove the SPs that are known to be isolated and
resolve them using lookup tables. For the remaining SPs, we test if there is
more than one CC inside and split them if necessary. Figure 5 shows the two
possible configurations for a SP: one connected component or two connected
components. Because there can be at most two clusters per SP the maximum
number of clusters in the image is $2\times$ the number of SPs. Once the SP
list is prepared, we run the algorithm using a combination of bitwise
operations and a lookup table to test the adjacency. Another lookup table is
used for a fast computation of the first statistical moments and the number of
pixels within a SP. Finally, the 2D clusters coordinates are transformed from
their sensor space to the LHCb 3D global coordinate system, by multiplying
them with the sensor’s transformation matrix.

Figure 5: A Super-Pixel containing one connected component (left) and a Super-
Pixel containing two connected components, split in two SP (right)

Each cluster is stored in a Structure of Array (SoA) layout of memory to ease
the loading into SIMD registers. In addition to the 3D global position (x, y,
z), we also store the approximated $\phi$ angle, computed as $\phi=atan2(y,x)$
using a fast atan2 function, and the LHCb identifier of the cluster.

###  2.2 SIMD instructions

As clock frequencies of modern processors are expected to stay near their
current levels, or even to get lower, the primary method to improve the
computation power of a chip is to increase either the number of processing
units (cores) or the intrinsic parallelism of a core (SIMD). The speedup that
can be achieved for a particular application depends on the amount of code
that can be vectorized. Amdahl’s law [35] gives a theoretical bound for the
speedup:

$speedup(c)=\frac{1}{1-\tau+\frac{\tau}{c}}$

where $c$ is the vector cardinality, and $\tau$ is the fraction of vectorized
code. To reduce power consumption and help thermal stability, Intel CPUs use
dynamic frequency scaling to limit the frequency of cores running SIMD
instructions. There are three levels of frequency as shown in table 1. The
frequency is reduced, per core, if the process encounter a sufficiently high
density of instruction of the corresponding type. The frequency reduction
consist in multiple steps. When the CPU detect that no heavy instructions are
used anymore, it waits approximately 2 ms before reverting the changes: in the
mean time, scalar code runs at the lowered frequency [36]. If the application
interleave scalar and AVX code, it will likely run at the AVX-induced lower
frequency. We can modify Amdahl’s law to account for this frequency scaling:

$speedup(c)=\frac{1}{1-\tau+\frac{\tau}{c}}\times\frac{freq(c)}{freq(1)}$

$freq(c)$ is the maximum frequency for a vector of cardinality $c$. Figure 6
shows the theoretical speedups with frequency correction, for light and heavy
instructions, for two different Intel CPUs. As we can see, for wide vectors a
large amount of vectorized code is needed to be able to keep increasing the
performances. To counterbalance the effects of frequency scaling, vendors
added more specific instructions that can carry out complex operations in
fewer cycles.

| Base | Turbo
---|---|---
Non-AVX / Light AVX2 | 2.1 | 2.8
Heavy AVX2 / Light AVX-512 | 1.7 | 2.4
Heavy AVX-512 | 1.3 | 1.9
Table 1: Base and maximum frequencies (GHz) for an Intel Xeon Gold 6130 [37]
for all cores active

Figure 6: Amdahl’s law applied to SIMD vector width with frequency correction,
for an Intel Xeon Silver 4114 (left) and an Intel Xeon Gold 6130 (right)

Developing new algorithms that efficiently use such a kind of SIMD
architecture requires heavy algorithmic modifications and can only be done
efficiently if the specific instructions are available. Due to this complex
process, it is hard for a compiler to provide vectorization support for
irregular algorithms. Domain Specific Languages (DSLs) such as Halide [38] or
SPMD [39] do not contain all patterns necessary for our problem and would also
introduce significant additional complexity in the context of a physics
codebase almost entirely written in C++. A less invasive option is to use SIMD
libraries, like VC [40], UME::SIMD [41] or VecCore [42], that wrap the
compiler intrinsics to provide a higher abstraction level to the developer.
While these libraries work well for implementing most algorithms, they do not
currently fully implement the latest SIMD ISA extensions. We therefore
developed a set of vector length agnostic C++ template codes that can be
instantiated for different SIMD backends in order to evaluate the impact of
SIMD width on the performance and allow our algorithm to be ported on a wide
range of architectures. In order to evaluate the impact of vector size on AVX-
induced frequency scaling, we implemented an AVX256 and AVX128 backends that
use AVX-512 instruction variants for 256 and 128 bits wide vector registers.
This approach is similar to [43]. For simplicity, and because it matched this
use case, the implementation is limited to 32-bit elements for integer and
floating point types. The SIMD backend is determined by the developer, and is
resolved at compile time following the fallback scheme depicted in Figure 7.
This allows us to mix SIMD backends and provide easy debugging and testing
capabilities while ensuring portability.

Figure 7: SIMD wrappers fallback scheme on x86 architectures

###  2.3 Tracking algorithm

Like previous tracking algorithms, the proposed algorithm is a local search
approach based on track following. To take advantage of track parallelism with
SIMD, the algorithm is structured like the search by triplet algorithm [23],
consisting in a track seeding and a track extending. Because on CPU the
synchronization between vector elements is implicit, no synchronisation
between layer is needed. Each layer’s clusters are prepared on demand and
stored in a small container with SoA layout. Three layers are needed at a
time, so only three containers of clusters are allocated on the stack and we
use pointer rotation to recycle them while moving through all VELO layers.
This allows to reduce the algorithm memory footprint and to be more cache-
friendly by improving data locality. Two track containers are used to memorize
the track candidates created by the seeding and the finalized tracks produced
by the track extending. Figure 8 shows the data flow within the algorithm.

Figure 8: Data flow within the algorithm. The hits are taken from the input
planes P0 to P26, three by three, and processed in the seeding step to produce
tracks candidates, which are then extended with the hits from the next layer.
The candidates that could not have been extended are then copied in the tracks
output container.

One major algorithmic difference inspired by the SIMD requirements, is to
compress data within each container of clusters and tracks. This ensures that
useful data is always contiguous in memory, so that when loaded in SIMD
registers no vector element is wasted. It also reduces the number of elements
to process in the next steps. Instead of marking clusters like in previous
algorithms using a boolean array, they are simply removed them from their
container. Similarly, the tracks get moved from the candidate tracks container
to the finalized tracks container or are discarded at the end of each
extending step. This copy can be made efficiently using the compressstoreu
instruction available in the AVX-512 instruction set. This instruction allows
to pack some elements of a register to its left, based on a given mask and
store it in memory. Figure 9 shows an example of a compression operation on
AVX-512 and its emulation on AVX2 hardware. As this instruction is not
available in older instruction sets, it can be emulated using a lookup-table
and a permute instruction followed by a regular store [44]. Because this
instruction is used intensively, usually multiple times in a row with the same
mask, the compiler is able to optimize the code to perform the lookup once and
the core can pipeline the independent permute and store instructions, making
it efficient.

Figure 9: Emulation of AVX-512’s compressstoreu instruction on AVX2 capable
architecture.

###  2.4 Seeding tracks

The track seeding is the most compute intensive part of the algorithm. In a
typical upgrade event, one Velo layer contains an average of $\sim$100
clusters. Testing all possible triplet combination would require $O(100^{3})$
tests. Previous algorithms based on pair and triplet search reduced the
combinatorics by only testing pairs of clusters that have similar features.
State-of-the-art algorithms build pair candidates by finding all second hits
within a $\phi$-window around the first hit. This approach works well for the
majority of tracks that comes from the beam line, but needs large tolerances
to accept displaced tracks. Because a lot of LHCb’s physics programs are based
on these displaced tracks it is important to boost their reconstruction
efficiency, even if they represent only a tiny fraction of reconstructible
tracks. As shown on the left part of Figure 10, a $\phi$-window of $\pm
3^{\circ}$ allows to correctly match 95.56% of clusters by looking at a
maximum of 10 clusters (2.6 in average), while a $\phi$-window of $\pm
20^{\circ}$ is able to build 98.77% of reconstructible pairs at the cost of
having to test up to 30 candidates (10.8 in average). Apart from increasing
the combinatorics, having a large candidate count increase the probability of
generating fake tracks, and for these reasons we want to keep it as low as
possible. Also, while having a variable number of candidates can be
advantageous on a sequential architecture, a parallel architecture has to
synchronize between processing elements so the time for all elements to finish
is always the maximum of all elements’ time.

Figure 10: On the left, the % of correctly matched clusters for the
$\phi$-window algorithms, depending on the number of cluster candidates
($3^{\circ}$ window is used in the "Fast" configuration of the Search by Pair
algorithm and $20^{\circ}$ window is used in the "Best" configuration). On the
right, the % of correctly matched clusters for different number of candidates
from our SIMD algorithm. These statistics are averaged on 100 Monte-Carlo
simulated events, considering only the track seeding part of the algorithms
and without marking used clusters.

Instead of using a $\phi$-window, we implemented a nearest in $\phi$ approach
where we pick a fixed number of candidates N. As shown on the right part of
Figure 10, we can match 96.59% of clusters with only 3 candidates or 98.89% of
clusters with 10 candidates, reducing by a factor 3 the maximum number of
candidates processed. This allows the SIMD algorithm to be more regular and
less data dependent leading to a better utilisation of SIMD processing units.
As the number of candidates N is small, they can fit in registers, avoiding
costly memory accesses. The candidate positions and indices are stored in an
N-sized array of SIMD register types. As the number of candidates N is known
at compile time, the compiler is able to fully unroll the loops (loop
unwinding) over the candidates and the array to registers. If N is too large
to fit all candidates in registers, the compiler generates spill code when it
starts to overflow. By excluding used clusters when looking for the N nearest
candidates, is allows more distant clusters to be tested if the closest ones
are already used by another track, this helps to reconstruct displaced tracks
in very dense layers. The limitation of processing multiple tracks at a time
is that is allows the tracks to share some hits, potentially leading to
clones. If the number of track processed in parallel is small, it doesn’t have
a big impact on the tracking efficiencies and clone rate. Because the hit
container is not ordered the probability of sharing a hit among tracks
processed in the same SIMD register is decreased. For larger SIMD registers
widths, the conflict detection instructions available in AVX-512 can be used
to remove the clones before propagating them. However, as the clone rate was
already low, it was not necessary.

Once the initial pair candidates are built, they are extended in the third
layer to search for the cluster minimizing the L2 distance to the linearly
extrapolated position. In this step, all the hits are tested, without testing
for the $\phi$ distance. As in previous algorithms, this L2-distance is called
the _scattering parameter_ and the triplet candidate, built from the pair and
the best cluster, that minimizes the scattering is kept. The triplet is
accepted and added to the track candidate container if its scattering is lower
than a configurable threshold value called max_scatter_seeding. When a cluster
is used in a track, it is removed from the layer’s cluster container.

###  2.5 Extending tracks

After the seeding, the second step of an iteration of the tracking algorithm
consist in finding hits in the current layer to extend the track candidates.
Track candidates are processed in parallel and all non-used hits are tested
using the same scattering criteria as in the seeding. The best hit is kept if
the scattering is less than the max_scatter_extending threshold. To reduce the
number of clones due to missing hit in layer, the track candidates not matched
with a hit are kept one more iteration. The skipped layer counter is reset
each time a hit is found. If the counter is exceeded once for a track
candidate, it is moved to the output tracks container if it contains more than
three hits or if the sum of the scatterings is less than a tighter threshold
max_scatter_3hits, otherwise it is discarded. The partitioning of track
candidates into next track candidates or track output is once again done using
the compress-store pattern. Figure 11 shows an example of track seeding and
extension.

Figure 11: The first seeding considers every hit in P1, builds 3 pair
candidates with the nearest P0 hits in $\phi$ and extrapolates the doublet in
P2 to find the P2 hit that minimizes the scattering. The used hits are
removed, then every track candidate is extrapolated in P3 and extended if a
hit is found. The first cycle is complete, and the algorithm performs another
seeding in (P3,P2,P1), before continuing.

##  3 Benchmarks

###  3.1 Benchmark procedure

Following the approach of [22], all the algorithm configurations have been
tested within the GAUDI framework [45]. The framework provides an efficient
way of reading data from a local ramdisk and dispatching the events to the
different threads. To decouple the single-threaded file I/O from the multi-
threaded reconstruction, a double buffering technique was used where the first
thread to reach the end of the current event buffer, swap it with the second
one and refills the first from the next file. The sequential work of
prefetching events consist in computing the pointer to the start of every
event by doing the prefix sum of the event sizes. The decoding of the
individual events raw banks is then performed by the thread in charge of the
event reconstruction. The throughput is measured in number of events per
second or, as it is analog to a frequency, in Hertz. To measure the time, the
timing counter provided by the framework is used. It ignores the first and
last 10% of events for stability. All tested software was compiled with GCC
8.2. Unless explicitly specified, all results are given for a number of
seeding pair candidate N=3.

Two setups were evaluated: a dual-socket Intel Xeon Gold 6130 and a single
socket AMD EPYC "Rome" 7702. The Intel system features AVX-512, AVX2 and SSE
instruction sets and scales its frequency according to Table 1. The AMD system
only has AVX2 and SSE, at a frequency of 2.0 GHz.444All AMD throughput numbers
in this article are given for 2.0 GHz. The dual-socket Intel system has a
total number of 32 physical cores and 64 threads, while the single socket AMD
system has 64 physical cores and 128 threads. As every event is independent
from the others, it is important to avoid memory latency induced by NUMA
effects. On the Intel system we achieved optimal performance by launching one
process per NUMA domain using the numactl utility. While the one socket AMD
only has one NUMA domain for the whole chip, we found that best performance is
achieved when launching one process per physical compute die, and thus always
ran 8 independent jobs on this system.

In all tests, we run a full VELO reconstruction consisting in fetching the raw
banks, applying a Global Event Cut of the 7% biggest events, preparing the
data, performing the actual tracking and fitting the resulting tracks. For the
sake of fair comparison, the 2018 search by pair algorithm has been updated to
the same plain old data input/output as the new algorithm, resulting in a
speed improvement of $\sim$40%.

###  3.2 Throughput

All throughput tests were done on minimum bias Monte-Carlo simulation samples.
First, the throughput of the new SIMD VELO Tracking algorithm is compared with
the 2018 Search by Pair (SbP) algorithm, the current state-of-the-art for VELO
pattern reconstruction on CPU. The SbP algorithm was originaly coming in two
versions: the "fast" configuration favoring speed over efficiency was meant to
be used for HLT1 and the "best" configuration favoring efficiency over speed
was meant to be used for HLT2. The left side of Figures 12 and 13 shows the
SIMD algorithm is _faster_ than both the "fast" and "best" configurations of
SbP, on _every_ tested architectures, for any number of threads. Using SIMD
wrappers, different implementations of the SIMD algorithm were also compared.
Interestingly, the AVX512 backend with an SIMD register width of 16 performs
less well than the AVX256 with a register width of 8. This can be explained by
the frequency scaling issues discussed in Section 2.2. However, thanks to the
new instructions introduced with AVX-512, the AVX256 and AVX128 backends bring
a 10% improvement over plain AVX2 and SSE respectively. The scalar backend is
significantly lower than all other SIMD backends because the compiler is not
able to vectorize the filtering pattern. The slow down in speedup progression
with increased SIMD parallelism is a combination of frequency scaling and not
being able to extract enough parallelism from relatively small loops. The
right of Figure 13 presents a comparison of the Intel and AMD systems for the
relevant backends. Because the Intel setup only have 32 physical cores, the
two architecture can only be compared at threads $\times$ processes $=32$. The
AMD’s AVX2 backend provides a 28% improvement over Intel’s AVX2 and a 18%
improvement over Intel’s AVX256, despite the frequency being 20% lower for
AMD. AMD’s scalar backend also increased the throughput by 23% from Intel’s
scalar backend.

Figure 12: Throughput as a function of the number of threads for two processes
(one on each NUMA domain) on dual-socket Intel Xeon Gold 6130. On the left:
comparison of SIMD VELO Tracking with the Search by Pair (SbP) algorithm in
"fast" and "best" configurations. On the right: comparison of different SIMD
backends.

Figure 13: On the left: comparison of SIMD VELO Tracking with the Search by
Pair (SbP) algorithm in "fast" and "best" configurations, on a single socket
AMD EPYC "Rome" 7702. On the right: comparison of a single socket AMD EPYC
"Rome" 7702 and a dual-socket Intel Xeon Gold 6130 for different SIMD
backends.

As the throughput and efficiency of the algorithm depends linearly from the
number of pair candidates to consider during the seeding step, it offers a
direct tuning parameter to adjust the trade-off between speed and efficiency.
Figure 14 shows the progression of throughput as a function of the number of
pair candidates.

Figure 14: Throughput as a function of the number of pair candidates in the
track seeding step, for different SIMD backends. On the left: dual-socket
Intel Xeon Gold 6130. On the right: single socket AMD EPYC "Rome" 7702.

###  3.3 Reconstruction efficiency

While minimum bias events are representative of the data seen by the
production system in real-time, the majority of them do not contain the
physical signals whose efficiency we want to optimize. We therefore simulate a
typical signal of interest for LHCb to measure the algorithm efficiencies. We
choose $B_{s}\rightarrow\phi\phi$, which is the same signal used in all LHCb
historical publications on tracking.

We present the efficiency of different track categories as a function of
multiple physical parameters of interest. The efficiency as a function of the
distance of closest approach to beamline (docaz) is studied to ensure the
efficient reconstruction of tracks produced in the decays of long-lived
particles. Because of the geometry of the VELO, it is also particularly
interesting to plot the efficiency as a function of track pseudorapidity
($\eta$).555The pseudorapidity of a track is given by
$-\ln\left[\tan\left(\frac{\theta}{2}\right)\right]$, where $\theta$ is the
angle of the track to the beamline Figure 15 shows the efficiency as a
function of docaz and $\eta$ for the two configurations of the Search by Pair
algorithm and the AVX256 version of the SIMD VELO Tracking. The docaz
efficiencies are plotted in the range $2<\eta<5$, which represents the
acceptance of the full LHCb detector. Thanks to its nearest $\phi$ approach,
the SIMD VELO Tracking is more efficient than previous State-of-the-Art for
very displaced tracks, even if the number of evaluated pair candidates is
small (N=3). It also has significantly better efficiencies for very small
track $\eta$. While small $\eta$ tracks do not pass through the rest of the
detector, they can nevertheless play an important role in the reconstruction
of PVs, but a detailed study of this is left to a future publication.

Figure 15: Efficiency as a function of the distance of closest approach to the
z axis (docaz), in mm, and the pseudorapidity $\eta$ for Velo tracks. LHCb is
mostly interested in tracks with DOCAZ < 1 mm.

We also evaluate the integrated efficiency in the range $2<\eta<5$ for
different track types. We distinguish between:

  * •

all tracks that leaves at least 3 hits in the VELO detector ("VELO tracks")
which are mostly produced directly in the PVs,

  * •

tracks that come from the decay of a hadron containing a bottom quark and
traverse the rest of the LHCb tracking detectors ("From B"),

  * •

tracks that come from the decay of a hadron containing a charm quark and
traverse the rest of the LHCb tracking detectors ("From D"),

  * •

tracks that come from the decay of a hadron containing a strange quark and
traverse the rest of the LHCb tracking detectors ("Strange").

Table 2 compares the efficiencies for these categories and compares the fake
rate for the two configurations of SbP and AVX256 SIMD VELO Tracking. More
efficient algorithms tends to produce more fakes due to the higher number of
combinations tested. Still, the SIMD algorithm produces fewer fakes than the
"best" SbP. The SIMD algorithm is more efficient for "VELO" and "From B"
categories, while being within 1% of the "best" SbP for "From D" and "Strange"
categories. While the results presented here only allow for $N=3$ pair
candidate, the algorithm can outperform the other algorithms in all categories
for $N\geq 6$. The clone rates are similarly presented in Table 3, and the
SIMD algorithm produces fewer clones than previous approaches.

| Fakes | Velo | From B | From D | Strange
---|---|---|---|---|---
Search by Pair "fast" | 0.83 | 93.05 | 95.64 | 95.29 | 79.34
Search by Pair "best" | 1.22 | 97.62 | 98.71 | 99.05 | 97.46
VELO Tracking SIMD | 1.04 | 98.20 | 99.12 | 98.99 | 96.82
Table 2: Efficiencies for tracks that are not electrons in the range $2<\eta<5$. |  | Velo
---
clones
| From B
---
clones
| From D
---
clones
| Strange
---
clones
Search by Pair "fast" | 2.31 | 0.89 | 1.42 | 1.54
Search by Pair "best" | 2.75 | 0.84 | 1.25 | 0.82
VELO Tracking SIMD | 1.35 | 0.68 | 0.90 | 0.82
Table 3: Clone rates (in %) on 1000 $B_{S}\rightarrow\phi\phi$ events, for
$2<\eta<5$ tracks. The lower, the better.

Figure 16 shows the impact of varying the number of seeding pair candidates on
the efficiency and fake rate. As N increases, the efficiencies go up, but as
more pairs are tested, the probability of finding randomly aligned hits also
increases leading to more fakes. We noted that already at N=1, the
efficiencies are higher than the "fast" SbP algorithm and could offer a viable
mitigation for HLT1. However, to minimize the disparity between HLT1 and HLT2
track reconstructions, we choose a default value of N=3 for both
configurations as it seems to be a good trade-off between throughput,
efficiency and fake rate.

Figure 16: Efficiencies for the different track categories described in the
text as a function of the number of seeding candidates. Higher efficiencies
and lower fake rate are better.

Table 4 shows the hit efficiencies for the same track categories. The "All
hits efficiencies" section shows that in average, the SIMD algorithm finds
more correct hits than the SbP algorithms. The "First 3 hits" and "last hit"
categories are important to correctly extrapolate the track to the beamline or
to the end of the VELO detector. Again, the SIMD algorithm demonstrate better,
or within 1%, efficiencies than the SbP algorithms.

| Velo | From B | From D | Strange
---|---|---|---|---
All hits efficiencies:
Search by Pair "fast" | 90.05 | 92.40 | 92.82 | 84.69
Search by Pair "best" | 94.19 | 97.61 | 97.50 | 97.47
VELO Tracking SIMD | 96.97 | 97.96 | 98.05 | 97.58
Efficiencies of first 3 hits:
Search by Pair "fast" | 91.74 | 93.93 | 94.32 | 76.54
Search by Pair "best" | 93.86 | 97.44 | 97.54 | 96.80
VELO Tracking SIMD | 97.08 | 98.18 | 98.13 | 97.39
Efficiencies of last hit:
Search by Pair "fast" | 87.95 | 90.77 | 91.43 | 88.97
Search by Pair "best" | 94.07 | 97.64 | 97.48 | 97.72
VELO Tracking SIMD | 96.60 | 97.53 | 97.85 | 97.12
Table 4: Average hit efficiencies of reconstructed tracks in the range
$2<\eta<5$. All results are given for an SIMD register width of 8. (Best
efficiencies in bold)

##  4 Conclusion

In this article, we have presented a new tracking algorithm for the VELO
detector of the LHCb experiment specialized to take advantage of SIMD general
purpose multicore processors. We compared it to previous State-of-the-Art
pattern recognition algorithms and showed a significant speedup and in some
cases increase in efficiency over all previous alternatives. This allows the
SIMD algorithm to be used for all stages of LHCb’s real-time data processing.
We also evaluated the algorithm on two high-end systems from Intel and AMD and
showed the impact of the SIMD extensions on the performance.

## Acknowledgments

The authors would like to thank the Physics Data Processing group from Nikhef
and in particular Tristan Suerink, for lending them the AMD EPYC "Rome" 7702
system and Gvozden Nešković from the Frankfurt Institute for Advanced Studies
for the opportunity to have an early look at the AMD EPYC "Rome" architecture.
They would also like to thank the LHCb computing and simulation teams for
their support and for producing the simulated LHCb samples used in the paper.
VVG, RQ, and AH are partially supported by ERC-CoG-724777 “RECEPT”.

## References

  * [1] LHCb Collaboration, “LHCb Detector Performance,” Int. J. Mod. Phys., vol. A30, no. 07, p. 1530022, 2015.
  * [2] C. Fitzpatrick, J. M. Williams, S. Meloni, T. J. Boettcher, M. P. Whitehead, A. Dziurda, and M. A. Vesterinen, “Upgrade trigger: Bandwidth strategy proposal,” Tech. Rep. LHCb-PUB-2017-006. CERN-LHCb-PUB-2017-006, CERN, Geneva, Feb 2017.
  * [3] T. Sjöstrand, S. Mrenna, and P. Skands, “A brief introduction to PYTHIA 8.1,” Comput. Phys. Commun., vol. 178, pp. 852–867, 2008.
  * [4] S. Agostinelli et al., “Geant4: A simulation toolkit,” Nucl. Instrum. Meth., vol. A506, p. 250, 2003.
  * [5] J. Allison, K. Amako, J. Apostolakis, H. Araujo, P. Dubois, et al., “Geant4 developments and applications,” IEEE Trans.Nucl.Sci., vol. 53, p. 270, 2006.
  * [6] I. Belyaev et al., “Handling of the generation of primary events in Gauss, the LHCb simulation framework,” J. Phys. Conf. Ser., vol. 331, p. 032047, 2011.
  * [7] O. Callot, “Velo tracking for the High Level Trigger,” Tech. Rep. LHCb-2003-027, CERN, Geneva, Apr 2003.
  * [8] LHCb Collaboration, “LHCb VELO TDR: Vertex locator. Technical design report,” Tech. Rep. CERN-LHCC-2001-011, CERN, 2001.
  * [9] O. Callot, “Online Pattern Recognition,” Tech. Rep. LHCb-2004-094. CERN-LHCb-2004-094, CERN, Geneva, Oct 2004.
  * [10] D. Hutchcroft, “VELO Pattern Recognition,” Tech. Rep. LHCb-2007-013. CERN-LHCb-2007-013, CERN, Geneva, Mar 2007.
  * [11] O. Callot, “FastVelo, a fast and efficient pattern recognition package for the Velo,” Tech. Rep. LHCb-PUB-2011-001. CERN-LHCb-PUB-2011-001, CERN, Geneva, Jan 2011.  LHCb.
  * [12] LHCb Collaboration, “Measurement of the track reconstruction efficiency at LHCb. Measurement of the track reconstruction efficiency at LHCb,” JINST, vol. 10, p. P02007. 24 p, Aug 2014.
  * [13] M. Williams, “Upgrade of the LHCb VELO detector,” Journal of Instrumentation, vol. 12, pp. C01020–C01020, jan 2017.
  * [14] T. Bird, T. Britton, O. Callot, V. Coco, P. Collins, T. Evans, T. Head, K. Hennessy, W. Hulsbergen, D. Hynds, P. Jalocha, M. John, T. Ketel, M. Kucharczyk, D. Martinez-Santos, W. Qian, K. Rinnert, H. Schindler, T. Skwarnicki, H. Snoek, P. Tsopelas, and D. Vieira, “VP Simulation and Track Reconstruction,” Tech. Rep. LHCb-PUB-2013-018. CERN-LHCb-PUB-2013-018, CERN, Geneva, Oct 2013.
  * [15] LHCb Collaboration, “LHCb VELO Upgrade Technical Design Report,” Tech. Rep. CERN-LHCC-2013-021. LHCB-TDR-013, CERN, Nov 2013.
  * [16] R. Ticse, D. H. Campora Perez, R. Schwemmer, and N. Neufeld, “An SIMD parallel version of the VELO Pixel track reconstruction for the LHCb upgrade,” Tech. Rep. LHCb-PUB-2013-007. CERN-LHCb-PUB-2013-007. LHCb-INT-2013-030, CERN, Geneva, Jun 2013.
  * [17] P. V. C. Hough, “Machine Analysis of Bubble Chamber Pictures,” Conf. Proc., vol. C590914, pp. 554–558, 1959.
  * [18] L. Ristori, “An artificial retina for fast track finding,” Nucl. Instrum. Meth., vol. A453, pp. 425–429, 2000.
  * [19] A. Abba, F. Bedeschi, M. Citterio, F. Caponio, A. Cusimano, A. Geraci, F. Lionetto, P. Marino, M. J. Morello, N. Neri, D. Ninci, A. Piucci, M. Petruzzo, G. Punzi, F. Spinella, S. Stracka, D. Tonelli, and J. Walsh, “A specialized track processor for the LHCb upgrade,” Tech. Rep. LHCb-PUB-2014-026. CERN-LHCb-PUB-2014-026, CERN, Geneva, Mar 2014.
  * [20] A. Badalov, D. Campora, G. Collazuol, M. Corvo, S. Gallorini, A. Gianelle, E. Golobardes, D. Lucchesi, A. Lupato, N. Neufeld, R. Schwemmer, L. Sestini, and X. Vilasis-Cardona, “GPGPU opportunities at the LHCb trigger,” Tech. Rep. LHCb-PUB-2014-034. CERN-LHCb-PUB-2014-034, CERN, Geneva, May 2014.
  * [21] A. P. Badalov, “Coprocessor integration for real-time event processing in particle physics detectors,” 2016.
  * [22] M. De Cian, A. Dziurda, V. Gligorov, C. Hasse, W. Hulsbergen, T. E. Latham, S. Ponce, R. Quagliani, H. F. Schreiner, S. B. Stemmle, J. Van Tilburg, M. J. Zdybal, and J. M. Williams, “Status of HLT1 sequence and path towards 30 MHz,” Tech. Rep. LHCb-PUB-2018-003. CERN-LHCb-PUB-2018-003, CERN, Geneva, Mar 2018.
  * [23] D. H. Cámpora Pérez, N. Neufeld, and A. Riscos Núñez, “A fast local algorithm for track reconstruction on parallel architectures,” in 2019 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), pp. 698–707, May 2019.
  * [24] K. Hennessy and LHCb VELO Upgrade Collaboration, “LHCb VELO upgrade,” Nuclear Instruments and Methods in Physics Research A, vol. 845, pp. 97–100, Feb 2017.
  * [25] T. Poikela, M. D. Gaspari, J. Plosila, T. Westerlund, R. Ballabriga, J. Buytaert, M. Campbell, X. Llopart, K. Wyllie, V. Gromov, M. van Beuzekom, and V. Zivkovic, “VeloPix: the pixel ASIC for the LHCb upgrade,” Journal of Instrumentation, vol. 10, pp. C01057–C01057, jan 2015.
  * [26] A. Rosenfeld and J. Platz, “Sequential operator in digital pictures processing,” Journal of ACM, vol. 13,4, pp. 471–494, 1966.
  * [27] R. Haralick, “Some neighborhood operations,” in Real-Time Parallel Computing Image Analysis, pp. 11–35, Plenum Press, 1981.
  * [28] L. He, X. Ren, Q. Gao, X. Zhao, B. Yao, and Y. Chao, “The connected-component labeling problem: a review of state-of-the-art algorithms,” Pattern Recognition, vol. 70, pp. 25–43, 2017.
  * [29] F. Bolelli, M. Cancilla, L. Baraldi, and C. Grana, “Toward reliable experiments on the performance of connected components labeling algorithms,” Journal of Real-Time Image Processing (JRTIP), pp. 1–16, 2018.
  * [30] S. Gupta, D. Palsetia, M. A. Patwary, A. Agrawal, and A. Choudhary, “A new parallel algorithm for two-pass connected component labeling,” in Parallel & Distributed Processing Symposium Workshops (IPDPSW), pp. 1355–1362, IEEE, 2014.
  * [31] L. Cabaret, L. Lacassagne, and D. Etiemble, “Parallel Light Speed Labeling for connected component analysis on multi-core processors,” Journal of Real Time Image Processing, pp. 1–24, 2016.
  * [32] A. Hennequin, Q. L. Meunier, L. Lacassagne, and L. Cabaret, “A new direct connected component labeling and analysis algorithm for GPUs,” in IEEE International Conference on Design and Architectures for Signal and Image Processing (DASIP), pp. 1–6, 2018.
  * [33] M. Klaiber, D. Bailey, and S. Simon, “A single cycle parallel multi-slice connected components analysis hardware architecture,” Journal of Real-Time Image Processing, 2016.
  * [34] A. Hennequin, B. Couturier, V. V. Gligorov, and L. Lacassagne, “SparseCCL: Connected Components Labeling and Analysis for sparse images,” DASIP, no. to appear, 2019.
  * [35] G. M. Amdahl, “Validity of the single processor approach to achieving large scale computing capabilities,” in Proceedings of the April 18-20, 1967, Spring Joint Computer Conference, AFIPS ’67 (Spring), (New York, NY, USA), pp. 483–485, ACM, 1967.
  * [36] M. Gottschlag and F. Bellosa, “Mechanism to Mitigate AVX-Induced Frequency Reduction,” arXiv e-prints, p. arXiv:1901.04982, Dec 2018.
  * [37] “Intel xeon gold 6130 frequencies.” https://en.wikichip.org/wiki/intel/xeon_gold/6130#Frequencies.  Accessed: 2019-08-20.
  * [38] J. Ragan-Kelley, C. Barnes, A. Adams, S. Paris, F. Durand, and S. Amarasinghe, “Halide: a language and compiler for optimizing parallelism, locality, and recomputation in image processing pipelines,” ACM SIGPLAN Notices, vol. 48, no. 6, pp. 519–530, 2013.
  * [39] M. Pharr and W. R. Mark, “ispc: A spmd compiler for high-performance cpu programming,” in 2012 Innovative Parallel Computing (InPar), pp. 1–13, May 2012.
  * [40] M. Kretz and V. Lindenstruth, “Vc: A c++ library for explicit vectorization,” Softw. Pract. Exper., vol. 42, pp. 1409–1430, Nov. 2012.
  * [41] P. Karpiński and J. McDonald, “A high-performance portable abstract interface for explicit simd vectorization,” in Proceedings of the 8th International Workshop on Programming Models and Applications for Multicores and Manycores, PMAM’17, (New York, NY, USA), pp. 21–28, ACM, 2017.
  * [42] G. Amadio, P. Canal, D. Piparo, and S. Wenzel, “Speeding up software with VecCore,” Journal of Physics: Conference Series, vol. 1085, p. 032034, sep 2018.
  * [43] A. Hennequin, I. Masliah, and L. Lacassagne, “Designing efficient simd algorithms for direct connected component labeling,” in Proceedings of the 5th Workshop on Programming Models for SIMD/Vector Processing, WPMVP’19, (New York, NY, USA), pp. 4:1–4:8, ACM, 2019.
  * [44] “Simdprune library.” https://github.com/lemire/simdprune.  Accessed: 2019-08-20.
  * [45] LHCb Collaboration, “Upgrade Software and Computing,” Tech. Rep. CERN-LHCC-2018-007. LHCB-TDR-017, CERN, Geneva, Mar 2018.