Add detection of strongly connected components in the data flow precedence rules

The feature detects strongly connected components (SCCs) of any topology, with cycles and loops being the simplest instances. The check is performed at initialization and produces an error upon detection of an SCC (am open to turn this into a warning if needed). It can be disabled by setting PrecedenceSvc::VerifyTaskPrecedenceRules to False.

The PRG validator is based on Tarjan's algorithm (with minor modifications), which matches the lower bound of O(V+E) for the problem of this type.

added C++ framework task scheduling tests labels

changed milestone to %v33r0

• [2019-11-08 08:05] Validation started with lhcb-gaudi-merge#852
• [2019-12-11 13:10] Automatic merge failed in lhcb-gaudi-head#2480
• [2019-12-12 01:18] Automatic merge failed in lhcb-gaudi-head#2481
• [2019-12-13 00:09] Validation started with lhcb-gaudi-head#2482

changed the description

It looks like you do not have CI enabled in your fork. Can you enable it, please? so we can more quickly spot problems in MRs.

Hm.. CI/CD pipelines in my fork are actually enabled and have always been. Please see #1209563 for this MR. Or you meant some other CI?

mentioned in issue #104

resolved all threads

assigned to @clemenci

added lhcb-gaudi-head label

added 71 commits

• 55778da5...dc858532 - 62 commits from branch gaudi:master
• add0ce81 - add a PRG validator for searching strongly connected components in the DF realm
• 716c7497 - fix formatting
• ce098fb4 - fix false positive SCC detection
• edd39d23 - partial fix of false positive SCC detection
• d6277f6f - reimplement the algorithm to avoid false positives
• 0777c3df - add a test for detection of a SCC in data flow graph
• 62fe1752 - add a TODO comment
• 68cab6f7 - handle loops (aka 1D cycles) properly and modify the error message
• 4bd2ead4 - fix post-rebase issues

Compare with previous version

added 1 commit

• 6c741386 - report an SCC in a reproducible manner

Compare with previous version

approved this merge request

merged

mentioned in commit eddbf3a2

mentioned in merge request atlas/athena!29054 (merged)