KtJet is hosted by Hepforge, IPPP Durham

KtJet Optimisation

The time taken to process events grows with the multiplicity n of the input objects as n3. As the multiplicity grows with energy, and current and future colliders have ever higher event rates, timing issues are therefore of increasing practical importance.

A few compilation options are worth considering if speed is critical.

A compile option to switch from single to double precision arithmetic is available, but single precision is used by default as this increases the speed by much more than 20%.

In gcc, setting the -0 option is essential, the level of optomisation (1,2 or 3) which gives the best results varies between platform and compiler version. We found that both -O1 and -O2 gave massive increases in speed for KtJet. Choice of architecture is also important. For example using the gcc compiler flag -march=athlon on an Athlon processor gives a performance gain of around 5%.

Studies have shown that using single precision in KtJet greatly increases the overall speed of execution of KtJet and has no significant effects on the output final jets. All profiling studies were done using gprof in conjunction with Python. All tests were run on redhat 7.* using gcc with -O2 optimisation. The processor was a PIII 866 MHz. More studies on profiling can be found here.

Comparisons were made for all settings and single precision gave significantly improved performance for all with no degradation in physics results. An example for PP events using inclusive mode is shown in table 1.0. This shows the time spent in each fuction for the most CPU time intensive functions.

function % of total time average call time (ms)
single double single double
KtJetTable::DijTable::getMin 86.72 87.17 2.16 3.19
KtDistanceDeltaR::operator() 5.88 5.76 0.0002 0.0004
KtJetTable::DijTable::operator() 1.85 2.22 0 0
KtJetTable::killJet 1.60 1.43 0.04 0.05
KtJetTable::mergeJets 0.59 0.86 0.02 0.03
fill_n 0.50 0.80 3.00 7.00
phiAngle 1.34 0.63 0.00 0.00
min_element 0.34 0.46 0.01 0.02
KtJetTable::KtJetTable 0.59 0.46 0.07 0.08

Table 1.0: Profiling of KtJet: Average call time to functions for PP events (flags 4 1 1).

Profiling in Inclusive mode

The average call time for single and double precision in KtJet and also Fortran ktclus (double precision) were calculated for all combinations of flags and for all types of inputs (PP, Pe, eP, ee). For the inclusive mode overall call time was calculated as the time to call KtEvent constructor plus the call to KtEvent::GetJets(), for Fortran ktclus the time was the call to ktclus plus the call ktincl. For each collision type 10 events were generated and these were run over 10 times each to calculate the average call time. For inclusive mode, Table 2.0 shows the results for PP events, Table 2.1 shows the results for Pe events and Table 2.2 shows the results for eP events.

Process KtJet (double) Fortran (double) KtJet (single)
4 1 1 1.6497 +/- 0.0245 1.9716 +/- 0.0076 1.1315 +/- 0.0230
4 1 2 1.6391 +/- 0.0235 1.9772 +/- 0.0070 1.1252 +/- 0.0232
4 1 3 1.641 +/- 0.0106 1.9745 +/- 0.0076 1.124 +/- 0.0331
4 2 1 1.6918 +/- 0.0084 2.0733 +/- 0.0086 1.1517 +/- 0.0137<
4 2 2 1.6926 +/- 0.0140 2.0741 +/- 0.0076 1.1545 +/- 0.0153
4 2 3 1.6975 +/- 0.0155 2.0559 +/- 0.0332 1.1536 +/- 0.0075
4 3 1 1.7692 +/- 0.0188 2.0239 +/- 0.0107 1.1534 +/- 0.0127
4 3 2 1.7325 +/- 0.0347 2.0253 +/- 0.0161 1.1697 +/- 0.0104
4 3 3 1.7051 +/- 0.0155 2.0131 +/- 0.0159 1.1748 +/- 0.0170

Table 2.0 : Average call time (seconds) to reconstruct jets in inclusive mode from PP events.

Process KtJet (double) Fortran (double) KtJet (single)
3 1 1 0.0469 +/- 0.0038 0.0601 +/- 0.0017 0.0336 +/- 0.0042
3 1 2 0.0473 +/- 0.0047 0.0596 +/- 0.0019 0.0354 +/- 0.0026
3 1 3 0.0469 +/- 0.0050 0.0618 +/- 0.0026 0.0308 +/- 0.0030
3 2 1 0.0537 +/- 0.0037 0.0622 +/- 0.0027 0.0389 +/- 0.0035

3 2 2 0.0539 +/- 0.0044 0.0618 +/- 0.0021 0.0377 +/- 0.0047 3 2 3 0.0526 +/- 0.0047 0.0621 +/- 0.0018 0.0388 +/- 0.0028 3 3 1 0.0535 +/- 0.0068 0.0637 +/- 0.0027 0.0407 +/- 0.0034 3 3 2 0.0574 +/- 0.0051 0.0653 +/- 0.0045 0.0399 +/- 0.0027 3 3 3 0.055 +/- 0.0049 0.066 +/- 0.0035 0.0381 +/- 0.0034

Table 2.1 : Average call time (seconds) to reconstruct jets in inclusive mode from Pe events.

Process KtJet (double) Fortran (double) KtJet (single)
2 1 1 0.0174 +/- 0.0027 0.0225 +/- 0.0021 0.0148 +/- 0.0015
2 1 2 0.0176 +/- 0.0024 0.0238 +/- 0.0020 0.0156 +/- 0.0032
2 1 3 0.0186 +/- 0.0022 0.024 +/- 0.0011 0.0174 +/- 0.0031
2 2 1 0.0203 +/- 0.0024 0.0255 +/- 0.0012 0.0178 +/- 0.0022
2 2 2 0.0209 +/- 0.0037 0.0245 +/- 0.0023 0.0189 +/- 0.0031
2 2 3 0.0224 +/- 0.0035 0.0256 +/- 0.0027 0.0193 +/- 0.0036
2 3 1 0.0224 +/- 0.0038 0.0268 +/- 0.0026 0.0213 +/- 0.0026
2 3 2 0.0217 +/- 0.0027 0.0266 +/- 0.0026 0.0192 +/- 0.0035
2 3 3 0.0237 +/- 0.0021 0.0263 +/- 0.0027 0.0196 +/- 0.0025

Table 2.2 : Average call time (seconds) to reconstruct jets in inclusive mode from eP events.

Profiling in Exclusive mode

Studies were also done for the exclusive mode. For both KtJet and Fortran ktclus the y-cut value for the transition between 7 and 6 jets was calculated and then this was used to force the event into 6 jets. Timings were thus calculated as follows: KtJet calls to KtEvent(), KtEvent::getYMerge() and KtEvent::findJetsY(). Fortran ktclus calls to ktclus and ktreco. Table 3.0 shows the results for PP events, Table 3.1 shows the results for Pe events, Table 3.2 shows the results for eP events and Table 3.3 shows the results for ee events.

Process KtJet (double) Fortran (double) KtJet (single)
4 1 1 1.672 +/- 0.0140 1.7809 +/- 0.0041 1.2215 +/- 0.4256
4 1 2 1.6529 +/- 0.0128 1.7831 +/- 0.0072 1.142 +/- 0.0683
4 1 3 2.0518 +/- 0.7852 1.7821 +/- 0.0040 1.0787 +/- 0.0146
4 2 1 1.7394 +/- 0.0179 1.8053 +/- 0.0098 1.152 +/- 0.0114
4 2 2 1.9092 +/- 0.5304 1.8411 +/- 0.0145 1.2814 +/- 0.3574
4 2 3 1.751 +/- 0.0177 1.8497 +/- 0.0087 1.2462 +/- 0.0380
4 3 1 1.9525 +/- 0.5381 1.8638 +/- 0.0077 1.1504 +/- 0.0180
4 3 2 1.7702 +/- 0.0199 1.8442 +/- 0.0150 1.1526 +/- 0.0196
4 3 3 1.9469 +/- 0.5334 1.8461 +/- 0.0131 1.1693 +/- 0.0207

Table 3.0 : Average call time (seconds) to reconstruct jets in exclusive mode from PP events. Event was forced into 6 jets.

Process KtJet (double) Fortran (double) KtJet (single)
3 1 1 0.0585 +/- 0.0300 0.0519 +/- 0.0034 0.0411 +/- 0.0207
3 1 2 0.0528 +/- 0.0047 0.0527 +/- 0.0027 0.0378 +/- 0.0028
3 1 3 0.059 +/- 0.0293 0.0529 +/- 0.0030 0.0399 +/- 0.0222
3 2 1 0.0666 +/- 0.0164 0.0551 +/- 0.0025 0.0415 +/- 0.0050
3 2 2 0.0616 +/- 0.0048 0.0522 +/- 0.0044 0.0425 +/- 0.0044
3 2 3 0.0604 +/- 0.0033 0.0515 +/- 0.0032 0.0484 +/- 0.0127
3 3 1 0.0633 +/- 0.0084 0.0573 +/- 0.0035 0.0521 +/- 0.0199
3 3 2 0.0627 +/- 0.0053< 0.0545 +/- 0.0028 0.0461 +/- 0.0056
3 3 3 0.0685 +/- 0.0195 0.0558 +/- 0.0047 0.0498 +/- 0.0087

Table 3.1 : Average call time (seconds) to reconstruct jets in exclusive mode from Pe events. Event was forced into 6 jets

Process KtJet (double) Fortran (double) KtJet (single)
2 1 1 0.0223 +/- 0.0116 0.0195 +/- 0.0027 0.0212 +/- 0.0120
2 1 2 0.0199 +/- 0.0021 0.0199 +/- 0.0016 0.0167 +/- 0.0030
2 1 3 0.0197 +/- 0.0032 0.0188 +/- 0.0018 0.0185 +/- 0.0032
2 2 1 0.0252 +/- 0.0047 0.021 +/- 0.0014 0.0205 +/- 0.0033
2 2 2 0.0263 +/- 0.0043 0.0214 +/- 0.0015 0.019 +/- 0.0025
2 2 3 0.0252 +/- 0.0043 0.0212 +/- 0.0024 0.02 +/- 0.0041
2 3 1 0.0274 +/- 0.0039 0.0231 +/- 0.0025 0.0205 +/- 0.0022
2 3 2 0.0285 +/- 0.0029 0.0216 +/- 0.0037 0.0256 +/- 0.0101
2 3 3 0.0296 +/- 0.0075 0.0242 +/- 0.0024 0.0211 +/- 0.0044

Table 3.2 : Average call time (seconds) to reconstruct jets in exclusive mode from eP events. Event was forced into 6 jets.

Process KtJet (double) Fortran (double) KtJet (single)
1 1 1< 0.0089 +/- 0.0013 0.0096 +/- 0.0017 0.0095 +/- 0.0020
1 1 2 0.0097 +/- 0.0016 0.0098 +/- 0.0016 0.0111 +/- 0.0065
1 1 3 0.0079 +/- 0.0022 0.0099 +/- 0.0017 0.0077 +/- 0.0017
1 2 1 0.0138 +/- 0.0027 0.0107 +/- 0.0020 0.0117 +/- 0.0038
1 2 2 0.0133 +/- 0.0033 0.0115 +/- 0.0012 0.0129 +/- 0.0017
1 2 3 0.0129 +/- 0.0029 0.0104 +/- 0.0023 0.0112 +/- 0.0035
1 3 1 0.0122 +/- 0.0015 0.0125 +/- 0.0010 0.0122 +/- 0.0016
1 3 2 0.0125 +/- 0.0015 0.0111 +/- 0.0018 0.0155 +/- 0.0028
1 3 3 0.0155 +/- 0.0029 0.0108 +/- 0.0019 0.0123 +/- 0.0036

Table 3.3 : Average call time (seconds) to reconstruct jets in exclusive mode from ee events. Event was forced into 6 jets.

Run time increase as function of n3

Figure 1.0 shows that the time taken to process events grows with the multiplicity of the input objects as n3 for all three programs.

Figure 1.0: Average time to process events versus number of input particles. (Black - Fortran, Blue - KtJet Double precision, Red - KtJet Single precision.)

Further Studies