Opened 7 weeks ago

Last modified 11 days ago

#2211 review defect

gh::regrid contains code whose runtime is quadratic in number of components

Reported by: Roland Haas Owned by:
Priority: minor Milestone: ET_2019_02
Component: Carpet Version: development version
Keywords: Cc:

Description (last modified by Roland Haas)

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()));
      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.

Attachments (1)

timing.plt (650 bytes) - added by Roland Haas 7 weeks ago.

Download all attachments as: .zip

Change History (10)

Changed 7 weeks ago by Roland Haas

Attachment: timing.plt added

comment:1 Changed 7 weeks ago by Erik Schnetter

For obvious reasons, I am in the unique position to confirm that the person who wrote this code wasn't thinking straight. There are several straightforward ways to improve this code.

  1. There is no need to first calculate the intersection and then check whether it is empty. It is much more efficient to check whether b and extent are disjoint.
  2. Instead of checking whether the bounding boxes are pairwise disjoint, one can calculate their union, and then compare the cardinality of the union with the sum of the cardinality of the individual boxes. This algorithm has complexity n * log(n).
  3. This check is most likely superfluous, as dh::regrid, which does the actual work, contains much more stringent checks. In fact, to my recollection, none of the gh consistency checks ever caught a bug. We could put all of them into an #ifdef CARPET_DEBUG clause.
Last edited 7 weeks ago by Erik Schnetter (previous) (diff)

comment:2 Changed 7 weeks ago by Steven R. Brandt

So, Erik, do you want to accept Roland's changes, eliminate the check altogether, or provide alternate code?

comment:3 Changed 7 weeks ago by Erik Schnetter

Which changes? Where are they?

comment:4 Changed 7 weeks ago by Steven R. Brandt

See above, branch rhaas/quadratic_regrid_time

comment:5 Changed 7 weeks ago by Erik Schnetter

I would use CARPET_DEBUG instead of CARPET_OPTIMISE.

comment:6 Changed 7 weeks ago by Roland Haas

My branch isn't really changes that should be applied (since it hacks Carpet and adds a testing thorn).

The possibly applicable changes are surrounding the consistency checks in gh::regrid with a


and the same for the consistency checks in dh::regrid (the part timed by the "tests" timer).

Erik's suggestion is basically to surround the gh::regrid stuff with


which makes disables the tests unless explicitly asked for while my suggestion would have left them in unless explicitly disabled. The ones in dh::regrid are already (mostly) no-ops for CARPET_OPTIMISE since the ASSERT_XXX macros become no-ops in that case.

comment:7 Changed 7 weeks ago by Roland Haas

Description: modified (diff)

comment:9 Changed 11 days ago by Roland Haas

Milestone: ET_2019_02

Modify Ticket

Change Properties
Set your email in Preferences
as review The ticket will remain with no owner.
Next status will be 'reviewed_ok'.
as The resolution will be set.
The resolution will be deleted.
to The owner will be changed from (none) to the specified user.
to The owner will be changed from (none) to the specified user.
The owner will be changed from (none) to anonymous.

Add Comment

E-mail address and name can be saved in the Preferences.

Note: See TracTickets for help on using tickets.