CKF branch factor limits are applied inconsistently

[stephenswat]

The track finding configuration contains two distinct variables that aim to limit the branching factor in the combinatorial Kálmán filter:

traccc/core/include/traccc/finding/finding_config.hpp

Lines 22 to 26 in 701f55b

	/// Maxmimum number of branches per seed
	unsigned int max_num_branches_per_seed = 10;
	/// Maximum number of branches per surface
	unsigned int max_num_branches_per_surface = 10;

In a naive reading, I would assume max_num_branches_per_surface to mean the maximum number of branches per track per surface, while I would assume max_num_branches_per_seed to mean the maximum number of tracks that can branch from a single seed throughout all steps in the CKF. Unfortunately, the reality seems to differ somewhat, and the behaviour also differs between CPU and GPU code.

On the CPU, the max_num_branches_per_seed variable is used to control the track finding (https://github.com/acts-project/traccc/blob/701f55b2000a59e0cce6c0bb31beeeae34b34a50/core/include/traccc/finding/details/find_tracks.hpp) through the use of a n_trks_per_seed array which is incremented whenever we branch on a surface.

On the CPU, the max_num_branches_per_surface variable is used to count the number of branches per surface for each particle, as expected:

traccc/core/include/traccc/finding/details/find_tracks.hpp

Lines 234 to 236 in 701f55b

	if (n_branches > config.max_num_branches_per_surface) {
	break;
	}

On the GPU, the max_num_branches_per_seed , the use is similar to on the CPU and can be found here:

traccc/device/common/include/traccc/finding/device/impl/propagate_to_next_surface.ipp

Lines 51 to 54 in 701f55b

	if (s_pos >= cfg.max_num_branches_per_seed) {
	params_liveness[param_id] = 0u;
	return;
	}

On the GPU, the max_num_branches_per_surface parameter is used only in the product of itself with the number of tracks. Thus, it does not limit the branching factor per track, it only limits the total number of tracks. If one track produces an excessive number of tracks, it will not be stopped by max_num_branches_per_surface if other tracks use less than the quota.

Thus, it seems to me that max_num_branches_per_surface is used to mean different things depending on the platform on which it is used.

But there is a bigger problem which is that the array against which we compare max_num_branches_per_seed is reset at every CKF step. It is reset here for the CPU code:

traccc/core/include/traccc/finding/details/find_tracks.hpp

Line 164 in 701f55b

std::fill(n_trks_per_seed.begin(), n_trks_per_seed.end(), 0u);

And it is reset here in the GPU code:

traccc/device/cuda/src/finding/finding_algorithm.cu

Line 305 in 701f55b

m_copy.memset(n_tracks_per_seed_buffer, 0)->ignore();

Notice that this resetting happens every CKF step. Therefore, we are limiting the branching per track per surface as you would expect. In actual fact, max_num_branches_per_surface and max_num_branches_per_seed are doing the same thing.

Pinging @beomki-yeo as he wrote this code originally; is this behaviour intended?

[beomki-yeo]

Thus, it seems to me that max_num_branches_per_surface is used to mean different things depending on the platform on which it is used.

This is also what I realized right after our discussion in the #846, so this may need to be fixed - Also found that the fix won't be trivial..

Notice that this resetting happens every CKF step. Therefore, we are limiting the branching per track per surface as you would expect. In actual fact, max_num_branches_per_surface and max_num_branches_per_seed are doing the same thing.

We need to ask @shimasnd because she introduced this variable in the past. I also need time to think about this..
Nah it seems I introduced it

But I don't think the following test will pass when we use max_num_branches_per_surface

traccc/tests/cpu/test_ckf_combinatorics_telescope.cpp

Line 179 in a54d64a

n_truth_tracks * cfg_limit.max_num_branches_per_seed);