Project

General

Profile

Actions

Development #2275

open

Development #2256: Demonstrator for digi-based trigger, STS-only

Development #2269: Offline integration

Reconstruction from time slice level

Added by Volker Friese 8 months ago. Updated 2 months ago.

Status:
Resolved
Priority:
Normal
Assignee:
Target version:
Start date:
11/15/2021
Due date:
11/19/2021 (about 6 months late)
% Done:

100%

Estimated time:
15.00 h
Spent time:

Description

Steering class for reconstruction from time slice data (recorded mCBM data). Includes unpacker, trigger and event builder. Plus corresponding run macro.

Deliverables:
  • reco/steer/CbmRecoTs
  • macro/run/run_reco_ts.C

Related issues

Follows Framework - Development #2273: Reconstruction from digi levelAssignedVolker Friese11/08/202111/12/2021

Actions
Precedes Framework - Development #2276: Test of time slice processingAssignedShreya Roy11/22/202111/26/2021

Actions
Precedes Framework - Development #2278: Device class for reconstruction from time slicesIn ProgressPierre-Alain Loizeau11/22/202111/26/2021

Actions
Precedes Framework - Development #2281: Standalone executableAssignedJan de Cuveland11/22/202112/03/2021

Actions
Actions #1

Updated by Volker Friese 8 months ago

  • Due date set to 11/15/2021
  • Start date changed from 09/28/2021 to 11/15/2021
  • Follows Development #2273: Reconstruction from digi level added
Actions #2

Updated by Volker Friese 8 months ago

  • Due date changed from 11/15/2021 to 11/19/2021
Actions #3

Updated by Volker Friese 8 months ago

Actions #4

Updated by Volker Friese 8 months ago

  • Related to Development #2278: Device class for reconstruction from time slices added
Actions #5

Updated by Volker Friese 8 months ago

  • Related to deleted (Development #2278: Device class for reconstruction from time slices)
Actions #6

Updated by Volker Friese 8 months ago

Actions #7

Updated by Volker Friese 8 months ago

Actions #8

Updated by Volker Friese 3 months ago

  • Status changed from Assigned to In Progress
  • % Done changed from 0 to 80

Strategy: establish first separate tasks for unpacking, triggering and event building and provide a macro to run them in a chain. Second step is to establish a single tasks comprising all three processing steps.

The first scheme is approached with MR 761. A ru macro for all three steps is available but requires MR 750 to be merged.

A hindrance is that the event building on real timeslices from mCBM consumes a lot of CPU time. Tests with simulated data show a quadratic dependence of run time with size of input data (events / digis) per timeslice. This needs to be investigated, understood and improved.

Actions #9

Updated by Pierre-Alain Loizeau 3 months ago

If I understand properly the TODO comment at 95-99 of EventBuilder.h , this is completely normal.
Assuming the following:
  • event are close to flatly spread within the TS and have all the same window
  • events are sufficiently numerous to cover the TS up to the end edge
  • the number of event in a TS and the TS size is more or less proportional to its duration if we assume a flat spill

the search complexity for the selection grows with something close to

Sum(Number of events, i * Timeslice Size / Number of events in TS) = Number of event in TS * (Number of event in TS + 1)  / 2 * Timeslice Size / Number of events in TS
                                                                   = Timeslice size * (Number of event in TS + 1)  / 2
                                                                   ~ Timeslice duration ^ 2

This is only taking into account the search for the start point. The search for the end point should be less impactful as (hopefully) the events combined length do not cover too much of the TS length (otherwise we would not see a real diminution of the data size).

That was in fact the reason why we used "smart looping" with storage of the start point of the previous event in the "non-optimized" version of the event builder, to take advantage of the fact that in the worst case event N+1 will have complete overlap with event N and can therefore only start at the same point (due to time sorting). The search complexity then tend toward Timeslice duration with a worst case of 2 x Timeslice duration. Without this kind of book keeping, I am not sure if we can avoid a close to quadratic dependence on the size of the TS.
Rejecting all overlaps means that the start point of N+1 can be set to the end point of N and that the TS is scanned only once in total, so it should lead to a further reduction of complexity of around 2.

If you do not want to store it in the algo itself as mentioned in the TODO, I would try add it as a reference I/O to the calls:
  • std::iterator<std::vector<Data> searchStart local variable in the calling task/device
  • static typename std::vector<Data> CopyRange(const std::vector<Data>& source, double tMin, double tMax, std::iterator<std::vector<Data> searchStart)
    {
    [...]
    auto lower = std::lower_bound(searchStart, source.end(), tMin, comp1);
    searchStart = lower;
    [...]
    }

Not sure however how well it would work with all the auto and templating nor how to provide the full set of start points to the call of EventBuilder::BuildEvent without a custom struct

Actions #10

Updated by Volker Friese 2 months ago

  • Status changed from In Progress to Resolved
  • % Done changed from 80 to 100

I am not sure whether I can follow your argument. The searches for the first and last digi in the vector is done with std::lower_bound and std::upper_bound, respectively, which have O(log(n)) behaviour.

The reason for the excessive runtime of the event builder was an embarrassingly stupid thing: an assert that the input vector is sorted (using std::is_sorted) inside the algorithm. This has linear behaviour (O(n)). The stupid thing was that it was called for each trigger. The number of triggers being proportional to the number of events and so to the number of digis, this resulted in an O(n2) complexity.

The assert is now removed, and the event building takes only some 50 ms per timeslice. This is without "smart" searches keeping the knowledge of the previous one, so it probably can still be improved, but in our small "chain", this is currently the least consumptive step (unpacker about 730 ms, trigger about 250 ms).

By the way: the unpacker is about a factor of two ore so less performant than previously reported, which owes to the time sorting of the output vector not having been performed before. Since time sorting is required by both the digi trigger and the event builder, doing it in the unpacker seems the proper place. I think, however, that this sorting is an artefact of writing all STS digis into one vector, which will not stay. From the algorithm and the logic of the data stream I think that the output of each component is already time-sorted, and a more appropriate implementation of StsDigiData can make use of that. But this is for optimisation to come yet.

For now, a macro for reconstruction from timeslice level is delivered with MR 766.

Actions #11

Updated by Pierre-Alain Loizeau 2 months ago

I am not sure whether I can follow your argument. The searches for the first and last digi in the vector is done with std::lower_bound and std::upper_bound, respectively, which have O(log(n)) behaviour.

Sorry, my bad, I once again forgot/missed the fact that you had the standard library search functions which are using the binary search or something even more efficient. (I think I did the same mistake when reviewing the original algo... proof that I am not efficient as I was at some point)
Actions

Also available in: Atom PDF