[ET Trac] [Einstein Toolkit] #2211: gh::regrid contains code whose runtime is quadratic in number of components

[Einstein Toolkit]

#2211: gh::regrid contains code whose runtime is quadratic in number of components
---------------------------------+--------------------
 Reporter:  Roland Haas          |       Type:  defect
   Status:  new                  |   Priority:  minor
Milestone:                       |  Component:  Carpet
  Version:  development version  |   Keywords:
---------------------------------+--------------------
 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.

-- 
Ticket URL: <https://trac.einsteintoolkit.org/ticket/2211>
Einstein Toolkit <http://einsteintoolkit.org>
The Einstein Toolkit