Improvements to prefix sum, sorting algorithms and VELO clustering by Arthur.

This MR is a rebased version of !1509 (closed).

Description copied from !1509 (closed).

Introduce a new test and benchmark to compare different implementations of the prefix_sum:

• cpu1: default implementation of host_prefix_sum
• cuda1: blelloch's scan implementation using 1 element per thread
• cuda2: blelloch's scan implementation using 4 element per thread
• cuda3: blelloch's scan implementation using a single kernel, sliding on the array

Closes #500 (closed)

Implements a new sorting algorithm.

Implements a new velo clustering algorithm.

Details in https://indico.cern.ch/event/1370609/contributions/5928258/attachments/2847533/4979150/SumSortClustHLT1.pdf

Throughput Test on Real Data

The throughput on real data with varying levels of mu shows a 10-15% increase in throughput with the HLT1 matching without and with UT sequences (hlt1_pp_matchig_no_ut and hlt1_pp_matching):

Checks of D0 and D+ Reconstruction

This MR and 2024-patches have been tested on real data. The dataset is the MEP dumps of Run 297083 with mu=4 which contains a total of 29.5M events. The sequence used was hlt1_pp_matching_and_downstream. The number of D0 and D+ reconstructed and triggered by Hlt1OneTrackMVA || Hlt1TwoTrackMVA is identical between this MR and 2024-patches.

added 1 commit

• 418e1764 - Fixed formatting

Compare with previous version

added RTA label

marked this merge request as draft

Is device/utils/sorting/src/regsort_kernels.cu really supposed to be submitted? As it is auto-generated file, isn't something like this supposed to be generated during compilation?

requested review from @ahennequ

assigned to @dtou

/ci-test

/ci-test

added 1 commit

• 051c49d4 - Reverted change in ci test.

Compare with previous version

/ci-test

added ci-test-triggered label

marked this merge request as ready

• [2024-06-15 12:18] Validation started with lhcb-2024-patches-mr#771
• [2024-06-15 12:18] Validation started with lhcb-2024-patches-mr#770
• [2024-06-15 12:19] Validation started with lhcb-2024-patches-mr#772
• [2024-06-18 10:39] Validation started with lhcb-2024-patches-mr#799
• [2024-06-20 09:30] Validation started with lhcb-2024-patches-mr#831
• [2024-06-25 17:18] Validation started with lhcb-2024-patches-mr#880

added needs ref update label

approved this merge request

@ahennequ Thanks for the review. However, @dtou reported some changes in results which are still not fully understood, seems to me there is still some work to be done on this code.

changed the description