<html>#2211: gh::regrid contains code whose runtime is quadratic in number of components
<table style='border-spacing: 1ex 0pt; '>
<tr><td style='text-align:right'> Reporter:</td><td>Roland Haas</td></tr>
<tr><td style='text-align:right'> Status:</td><td>resolved</td></tr>
<tr><td style='text-align:right'>Milestone:</td><td>ET_2019_02</td></tr>
<tr><td style='text-align:right'> Version:</td><td>development version</td></tr>
<tr><td style='text-align:right'> Type:</td><td>bug</td></tr>
<tr><td style='text-align:right'> Priority:</td><td>minor</td></tr>
<tr><td style='text-align:right'>Component:</td><td>Carpet</td></tr>
</table>
<p>Changes (by Roland Haas):</p>
<p><table>
<tr><td>status:</td><td>resolved (was open)</td></tr>
</table></p>
<p>The member function gh::regrid contains this code</p>
<div class="codehilite"><pre><span></span> // 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());
}
}
}
}
</pre></div>
<p>which b/c of the <code>c</code> and <code>cc</code> loops is quadratic in the number of components (MPI ranks). </p>
<p>For many (tens of thousands) components this becomes a dominant cost of the regrid operation.</p>
<p>The Carpet branch <code>rhaas/quadratic_regrid_time</code> contains a test thorn ArrayTest and a hacked version of Carpet that can simulate a number of MPI ranks using just one rank.</p>
<p>One can run:</p>
<div class="codehilite"><pre><span></span>mpirun -n 1 exe/cactus_sim arrangements/Carpet/ArrayTest/par/array.par
</pre></div>
<p>and control the number of pretend ranks by setting <code>ArrayTest::size</code> in array.par.</p>
<p>On my workstation regrid takes ~3.5s for 16k ranks with the consistency check and ~0.5s without. </p>
<p>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.</p>
<p>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).</p>
<p>The branch actually arranges for the consistency check to be skipped if one defines <code>CARPET_OPTIMISE</code>.</p>
<p>I attach a gnuplot script that takes carpet-timing-statistics.0000.txt and shows how much
<p>Comment (by Roland Haas):</p>
<p>Applied as git hash <a data-is-external-link="true" href="https://bitbucket.org/eschnett/carpet/commits/a2e72a970a78395fb25853f3a696ace6d369043d" rel="nofollow">a2e72a97</a> “CarpetIOHDF5: send active string to IO rank” or <a data-is-external-link="true" href="https://bitbucket.org/eschnett/carpet" rel="nofollow">carpet</a>.</p>
<p>--<br/>
Ticket URL: <a href='https://bitbucket.org/einsteintoolkit/tickets/issues/2211/gh-regrid-contains-code-whose-runtime-is'>https://bitbucket.org/einsteintoolkit/tickets/issues/2211/gh-regrid-contains-code-whose-runtime-is</a></p>
</html>