new Hough cluster search for the UV (stereo) hits in the SciFi Hybrid Seeding

This merge request includes several improvements to the SciFi hybrid seeding algorithm, particularly the step where UV (stereo) hits are added to the xz track candidates.

The new Hough cluster search is implemented in a generic template class. For each track candidate in the x-z projection, the y-z slopes corresponding to the hits from each of the 6 UV layers are collected in 6 separate histograms implemented as fixed-size arrays. The histograms are added together to form clusters. The largest clusters are promoted to candidate hits for the full track.

The code has also been reorganized, templating some methods and classes to avoid code repetition without affecting the performance.

The new algorithm was tested on a Monte Carlo sample (upgrade_DC19_01_Bd2KsteeMU) of 35k events with Moore. The physics performance are equivalent to the previous algorithm (see tables below with efficiency and ghost rates).

The code was also tested with the callgrind profiler. The new hybrid seeding algorithm results in -15% instruction fetch counts, with the Hough cluster search counting -40% instruction fetch.

Efficiency from master

SeedTrackChecker                       INFO Results
SeedTrackChecker                       INFO **** Seed                         3785456 tracks including         240976 ghosts [ 6.37 %], Event average  5.73 % ****
SeedTrackChecker                       INFO   01_hasT                       : 2509335 from  3020640 [ 83.07 %]    366 clones [ 0.01 %], purity: 99.50 %, hitEff: 97.94 %
SeedTrackChecker                       INFO   02_long                       : 1839150 from  1977324 [ 93.01 %]    159 clones [ 0.01 %], purity: 99.65 %, hitEff: 98.53 %
SeedTrackChecker                       INFO   03_long>5GeV                  : 1313194 from  1368948 [ 95.93 %]     92 clones [ 0.01 %], purity: 99.65 %, hitEff: 99.09 %
SeedTrackChecker                       INFO   04_long_fromB                 :  101294 from   107958 [ 93.83 %]      5 clones [ 0.00 %], purity: 99.71 %, hitEff: 98.81 %
SeedTrackChecker                       INFO   05_long_fromB>5GeV            :   78402 from    81750 [ 95.90 %]      4 clones [ 0.01 %], purity: 99.71 %, hitEff: 99.21 %
SeedTrackChecker                       INFO   06_noVelo+UT+T                :  269373 from   299637 [ 89.90 %]     34 clones [ 0.01 %], purity: 99.63 %, hitEff: 97.66 %
SeedTrackChecker                       INFO   07_noVelo+UT+T>5GeV           :  127490 from   133142 [ 95.75 %]      7 clones [ 0.01 %], purity: 99.64 %, hitEff: 98.91 %
SeedTrackChecker                       INFO   08_noVelo+UT+T_strange        :   98458 from   107262 [ 91.79 %]     10 clones [ 0.01 %], purity: 99.65 %, hitEff: 98.16 %
SeedTrackChecker                       INFO   09_noVelo+UT+T_strange>5GeV   :   58136 from    60598 [ 95.94 %]      2 clones [ 0.00 %], purity: 99.66 %, hitEff: 99.02 %
SeedTrackChecker                       INFO   10_noVelo+noUT+T              :  400812 from   743679 [ 53.90 %]    173 clones [ 0.04 %], purity: 98.74 %, hitEff: 95.39 %
SeedTrackChecker                       INFO   11_noVelo+noUT+T>5GeV         :  188883 from   239284 [ 78.94 %]    105 clones [ 0.06 %], purity: 98.50 %, hitEff: 96.51 %
SeedTrackChecker                       INFO   12_noVelo+noUT+T_strange      :   49208 from    63493 [ 77.50 %]     10 clones [ 0.02 %], purity: 99.24 %, hitEff: 97.29 %
SeedTrackChecker                       INFO   13_noVelo+noUT+T>5GeV_strange :   33143 from    36646 [ 90.44 %]      6 clones [ 0.02 %], purity: 99.23 %, hitEff: 98.10 %
SeedTrackChecker                       INFO   14_long_electrons             :  187546 from   215333 [ 87.10 %]     17 clones [ 0.01 %], purity: 99.72 %, hitEff: 97.92 %
SeedTrackChecker                       INFO   15_noVelo+UT+T_electrons      :  209189 from   246648 [ 84.81 %]     33 clones [ 0.02 %], purity: 99.69 %, hitEff: 97.36 %
SeedTrackChecker                       INFO   16_noVelo+noUT+T_electrons    :  149147 from   533945 [ 27.93 %]     65 clones [ 0.04 %], purity: 99.24 %, hitEff: 96.48 %

Efficiency with new algorithm

SeedTrackChecker                       INFO Results
SeedTrackChecker                       INFO **** Seed                         3767476 tracks including         195001 ghosts [ 5.18 %], Event average  4.76 % ****
SeedTrackChecker                       INFO   01_hasT                       : 2529299 from  3020640 [ 83.73 %]    101 clones [ 0.00 %], purity: 99.49 %, hitEff: 97.80 %
SeedTrackChecker                       INFO   02_long                       : 1838689 from  1977324 [ 92.99 %]     41 clones [ 0.00 %], purity: 99.62 %, hitEff: 98.36 %
SeedTrackChecker                       INFO   03_long>5GeV                  : 1311833 from  1368948 [ 95.83 %]     35 clones [ 0.00 %], purity: 99.61 %, hitEff: 98.92 %
SeedTrackChecker                       INFO   04_long_fromB                 :  101372 from   107958 [ 93.90 %]      2 clones [ 0.00 %], purity: 99.68 %, hitEff: 98.63 %
SeedTrackChecker                       INFO   05_long_fromB>5GeV            :   78404 from    81750 [ 95.91 %]      1 clones [ 0.00 %], purity: 99.67 %, hitEff: 99.05 %
SeedTrackChecker                       INFO   06_noVelo+UT+T                :  270212 from   299637 [ 90.18 %]     12 clones [ 0.00 %], purity: 99.63 %, hitEff: 97.55 %
SeedTrackChecker                       INFO   07_noVelo+UT+T>5GeV           :  127746 from   133142 [ 95.95 %]      3 clones [ 0.00 %], purity: 99.63 %, hitEff: 98.82 %
SeedTrackChecker                       INFO   08_noVelo+UT+T_strange        :   98445 from   107262 [ 91.78 %]      3 clones [ 0.00 %], purity: 99.63 %, hitEff: 98.01 %
SeedTrackChecker                       INFO   09_noVelo+UT+T_strange>5GeV   :   58099 from    60598 [ 95.88 %]      1 clones [ 0.00 %], purity: 99.62 %, hitEff: 98.87 %
SeedTrackChecker                       INFO   10_noVelo+noUT+T              :  420398 from   743679 [ 56.53 %]     48 clones [ 0.01 %], purity: 98.83 %, hitEff: 95.49 %
SeedTrackChecker                       INFO   11_noVelo+noUT+T>5GeV         :  197584 from   239284 [ 82.57 %]     35 clones [ 0.02 %], purity: 98.64 %, hitEff: 96.83 %
SeedTrackChecker                       INFO   12_noVelo+noUT+T_strange      :   50021 from    63493 [ 78.78 %]      5 clones [ 0.01 %], purity: 99.25 %, hitEff: 97.25 %
SeedTrackChecker                       INFO   13_noVelo+noUT+T>5GeV_strange :   33502 from    36646 [ 91.42 %]      3 clones [ 0.01 %], purity: 99.23 %, hitEff: 98.09 %
SeedTrackChecker                       INFO   14_long_electrons             :  187248 from   215333 [ 86.96 %]      3 clones [ 0.00 %], purity: 99.70 %, hitEff: 97.78 %
SeedTrackChecker                       INFO   15_noVelo+UT+T_electrons      :  208831 from   246648 [ 84.67 %]     10 clones [ 0.00 %], purity: 99.67 %, hitEff: 97.21 %
SeedTrackChecker                       INFO   16_noVelo+noUT+T_electrons    :  148969 from   533945 [ 27.90 %]     12 clones [ 0.01 %], purity: 99.28 %, hitEff: 96.42 %

I attach also the callgrind graphs for master and for the new algorithm, obatined running Moore on 100 events from the same MC sample.

Callgrind for master: total Ir = 1,776,909,692

Callgrind for new algorithm: total Ir = 1,513,821,530 (-15% compared to master)

@lohenry @sstahl @graven @gligorov

Could you please review and provide comments/suggestions?

Bravo! cc @rquaglia who will I think enjoy seeing this

Could you post the callgrind profiles before/after?

Do I understand correctly the seeding is now running at around 3.3 kHz on our usual quanta test node?

changed the description

@saiola very good, it's very nice to see this. Is this hough cluster search implemented still working under the assumption that the track comes from the origin? I meant is still the peak finding done using the y/z values directly? In general to improve physics performances this assumption is what one need to remove and i wonder what is with this method the only hope to find those large y/z spreads clusters. Before with the old method the chance to find them relied on increasing the maximum number of clusters to consider (not the 3x3 matrix of candidates) and enlarging the tolTy tolérance, altough this was costing a lot of throughput.(also rerunning the yz search on the recovery routine)

added 1 commit

• 023bbac9 - Apply suggestion to Pr/PrAlgorithms/src/HoughSearch.h

Compare with previous version

Thanks for the nice improvement @saiola. I have one nitpicky question, more driven by wanting to understand better the histogram approach (without looking too much in the code) than thinking it is a problem.

All performance metrics seem to be the same or better except the hit purity which slightly drops. The hit purity is quite biased to high values as one only calculates it for tracks matched to an MC particle. So I think the drop is significant. Do you know why this happens?

@saiola Is it possible to add some comments to the HoughCluster.h code? That would help future review.