Improvements to forward triplet search
This MR adds a linear search and optimizes the forward triplet search algorithm a bit.
-
linear_search
is a new algorithm that takes a similar input tobinary_search_leftmost
. It accepts an optional starting index, from which the array is sought in either increasing or decreasing order as required. It outperforms binary search in specific circumstances.
lf_triplet_seeding
got the following improvements:
- It now uses a shared memory array
shared_xs
, which holds all x coordinate values of the three modules in consideration. - It additionally uses
shared_indices
andshared_number_of_elements
to store x0 and x2 indices that passed the cut. - Adding the hit in the middle module
x1
is done afterwards by iteratingshared_indices
, improving thread usage. -
syncwarp
instead ofsyncthread
are used. It is more technically correct, although it doesn't seem to have an impact on performance.
Physics efficiency is expected to improve ever-so-slightly due to the better load balancing of candidate analysis between threads.
- Throughput change: 162.35 kHz -> 165.71 kHz (1.02x)
- Physics change: https://gitlab.cern.ch/lhcb/Allen/-/jobs/9592025
Built on top of !414 (merged)
Edited by Roel Aaij