Skip to content

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 to binary_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 and shared_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 iterating shared_indices, improving thread usage.
  • syncwarp instead of syncthread 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.

Built on top of !414 (merged)

Edited by Roel Aaij

Merge request reports