#2211: gh::regrid contains code whose runtime is quadratic in number of components --------------------------+--------------------------------- Reporter: Roland Haas | Owner: (none) Type: defect | Status: new Priority: minor | Milestone: Component: Carpet | Version: development version Resolution: | Keywords: --------------------------+--------------------------------- Description changed by Roland Haas:
Old description:
The member function gh::regrid contains this code
{{{ // Check component consistency for (int ml = 0; ml < mglevels(); ++ml) { for (int rl = 0; rl < reflevels(); ++rl) { assert(components(rl) >= 0); for (int c = 0; c < components(rl); ++c) { ibbox const &b = extent(ml, rl, c); ibbox const &b0 = extent(ml, rl, 0); assert(all(b.stride() == b0.stride())); assert(b.is_aligned_with(b0)); for (int cc = c + 1; cc < components(rl); ++cc) { assert((b & extent(ml, rl, cc)).empty()); } } } } }}}
which b/c of the {{{c}}} and {{cc}} loops is quadratic in the number of components (MPI ranks).
For many (tens of thousands) components this becomes a dominant cost of the regrid operation.
The Carpet branch {{{rhaas/quadratic_regrid_time}}} contains a test thorn ArrayTest and a hacked version of Carpet that can simulate a number of MPI ranks using just one rank.
One can run: {{{ mpirun -n 1 exe/cactus_sim arrangements/Carpet/ArrayTest/par/array.par }}} and control the number of pretend ranks by setting {{{ArrayTest::size}}} in array.par.
On my workstation regrid takes ~3.5s for 16k ranks with the consistency check and ~0.5s without.
This is per grid array and per grid scalar. So for a typical setup with ~400 grid arrays and grid scalars (no matter whether they have storage or not) this amounts to 400 * 3s = 1200s of time spent in the consistency check.
This happens only once per simulation (since grid arrays and grid scalars are only regrid once) but for a test simulation can be quite significant (at scale).
The branch actually arranges for the consistency check to be skipped if one defines {{{CARPET_OPTIMISE}}}.
I attach a gnuplot script that takes carpet-timing-statistics.0000.txt and shows how much time is spent in dh and gh regrid.
New description:
The member function gh::regrid contains this code
{{{ // Check component consistency for (int ml = 0; ml < mglevels(); ++ml) { for (int rl = 0; rl < reflevels(); ++rl) { assert(components(rl) >= 0); for (int c = 0; c < components(rl); ++c) { ibbox const &b = extent(ml, rl, c); ibbox const &b0 = extent(ml, rl, 0); assert(all(b.stride() == b0.stride())); assert(b.is_aligned_with(b0)); for (int cc = c + 1; cc < components(rl); ++cc) { assert((b & extent(ml, rl, cc)).empty()); } } } } }}}
which b/c of the {{{c}}} and {{{cc}}} loops is quadratic in the number of components (MPI ranks).
For many (tens of thousands) components this becomes a dominant cost of the regrid operation.
The Carpet branch {{{rhaas/quadratic_regrid_time}}} contains a test thorn ArrayTest and a hacked version of Carpet that can simulate a number of MPI ranks using just one rank.
One can run: {{{ mpirun -n 1 exe/cactus_sim arrangements/Carpet/ArrayTest/par/array.par }}} and control the number of pretend ranks by setting {{{ArrayTest::size}}} in array.par.
On my workstation regrid takes ~3.5s for 16k ranks with the consistency check and ~0.5s without.
This is per grid array and per grid scalar. So for a typical setup with ~400 grid arrays and grid scalars (no matter whether they have storage or not) this amounts to 400 * 3s = 1200s of time spent in the consistency check.
This happens only once per simulation (since grid arrays and grid scalars are only regrid once) but for a test simulation can be quite significant (at scale).
The branch actually arranges for the consistency check to be skipped if one defines {{{CARPET_OPTIMISE}}}.
I attach a gnuplot script that takes carpet-timing-statistics.0000.txt and shows how much time is spent in dh and gh regrid.
--