The aggregation repository contains a set of algorithms for grouping vertices of DAGs coming from loop-carried dependencies. For more information see Sympiler website
Modify example/SpTRSV_runtime.cpp so it throws error as reported in #9
Add Catch_tests/hdagg_tests.cpp to sweep over many input random matrices. 36 out of 768 test cases fail.
Add the above unit test to github workflow for better CI. Here is an example run.
To run:
cmake -B build_debug -DCMAKE_BUILD_TYPE=Debug
cmake --build build_debug --target hdagg_tests
./build_debug/Catch_tests/hdagg_tests -s # show all cases
./build_debug/Catch_tests/hdagg_tests -r compact # only show failed cases
The test sweeps over combinations of (n, density, seed, use_metis, nthreads, bin_pack) via Catch generators:
auto n = GENERATE(20, 50, 100, 200);
auto density = GENERATE(0.05, 0.1, 0.2, 0.5);
auto seed = GENERATE(1U, 2U, 3U);
bool use_metis = GENERATE(false, true);
int nthreads = GENERATE(2, 4);
auto bin_pack = GENERATE(false, true);
The failed ones are:
```
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 20; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 20; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 20; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 20; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 20; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 1' and 'nthreads = 2' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 20; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 1' and 'nthreads = 2' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 20; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 1' and 'nthreads = 4' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 20; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 1' and 'nthreads = 4' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 50; density = 0.5; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 50; density = 0.5; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 50; density = 0.5; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 50; density = 0.5; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 50; density = 0.5; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 1' and 'nthreads = 2' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 50; density = 0.5; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 1' and 'nthreads = 2' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 50; density = 0.5; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 1' and 'nthreads = 4' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 50; density = 0.5; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 1' and 'nthreads = 4' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 50; density = 0.5; seed = 3'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 50; density = 0.5; seed = 3'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 50; density = 0.5; seed = 3'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 50; density = 0.5; seed = 3'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 100; density = 0.2; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 100; density = 0.2; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 100; density = 0.2; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 100; density = 0.2; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 100; density = 0.5; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 100; density = 0.5; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 100; density = 0.5; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 100; density = 0.5; seed = 1'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 100; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 100; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 100; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 100; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 200; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 200; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 2' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 200; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 0' and 'cannot create std::vector larger than max_size()'
/workdir/Catch_tests/hdagg_tests.cpp:56: failed: unexpected exception with message: 'n = 200; density = 0.5; seed = 2'; expression was: {Unknown expression after the reported line} with 4 messages: 'use_metis = 0' and 'nthreads = 4' and 'bin_pack = 1' and 'cannot create std::vector larger than max_size()'
Failed 1 test case, failed 36 assertions.
```
In summary, failed cases are (n, density, seed, use_metis) =:
(20, 0.5, 2, false/true)
(50, 0.5, 1, false/true)
(50, 0.5, 3, false)
(100, 0.2, 2, false)
(100, 0.5, 1/2, false)
(200, 0.5, 2, false)
So it seems like, denser patterns are more likely to trigger bugs (no bugs for density = 0.05 or 0.1); and the cases with Metis are less likely to trigger bugs than without Metis. The choice of nthreads and bin_pack does not affect the bug (except that nthreads = 1 will fail due to https://github.com/sympiler/aggregation/issues/5#issuecomment-1357255720).
This PR is not intended to be merged right away. It is aimed as an example for fixing #9. After the bug is fixed, the unit tests can be added to enhance code robustness.
A more clear demonstration of #9
example/SpTRSV_runtime.cppso it throws error as reported in #9Catch_tests/hdagg_tests.cppto sweep over many input random matrices. 36 out of 768 test cases fail.To run:
The test sweeps over combinations of
(n, density, seed, use_metis, nthreads, bin_pack)via Catch generators:The failed ones are:
In summary, failed cases are
(n, density, seed, use_metis) =:(20, 0.5, 2, false/true)(50, 0.5, 1, false/true)(50, 0.5, 3, false)(100, 0.2, 2, false)(100, 0.5, 1/2, false)(200, 0.5, 2, false)So it seems like, denser patterns are more likely to trigger bugs (no bugs for
density = 0.05 or 0.1); and the cases with Metis are less likely to trigger bugs than without Metis. The choice ofnthreadsandbin_packdoes not affect the bug (except thatnthreads = 1will fail due to https://github.com/sympiler/aggregation/issues/5#issuecomment-1357255720).This PR is not intended to be merged right away. It is aimed as an example for fixing #9. After the bug is fixed, the unit tests can be added to enhance code robustness.