[Dune-devel] Thread-safe quadrature rules

[Jö Fahlke]

Hi!

I'd like to start the discussion on thread-safe quadrature rules.  In about a
week I plan to start a vote on merging this, unless discussion turns up
something serious.

The quadrature rules are usually obtained from a cache Dune::QuadratureRules.
This currently stored the quadrature rules in a std::map and creates them the
first time they are requested.  This is obviously not thread safe, see
<https://dune-project.org/flyspray/index.php?do=details&task_id=1544>.

We considered several options in the bug above, and I tried out the following
one: Instead of using a map to store quadrature rules keyed by a tuple of
quadrature type, geometry type, and quadrature order, I use a hierarchy of
vectors where the levels in the hierarchy are indexed by quadrature type,
geometry type and quadrature order, respectively.  To solve the race condition
when first requesting a quadrature rule, I protect each vector entry
(lower-level vector or quadrature rule) with a std::once_flag, which is the
standard construct from C++11 for such occasions.  This implementation is in
the branches feature/fs1544-threadsafe-quadrature of dune-common and
dune-geometry.

I benchmarked this on amd64, Xeon Phi and an ARMv7 processor.  (I used the
ARMv7 since it is said[1] to be quiet bad at synchronization across threads,
and I wanted to have an idea how bad it can become.)  The new code is most of
the time faster than or as fast as the old code.  The case where it is slower
is on the ARM processor for some compilers and workloads, then even then the
factor is no more than 1.25.  I also was on the lookout for bad weak
scalability leading to unacceptable slowdowns with many threads, possibly due
to bad implementations of std::once_flag, but everything looks fine.

Although code using quadrature rules should work without any changes, there
are some things that we will need to vote on.

- Linking with threads ::

  I added code to both build systems to ensure that libdunecommon is linked
  with -phtread or whatever is appropriate.  I added this to dune-common since
  it is likely to be required by other modules in the future, but in fact it
  would be possible to add it to dune-geometry instead (and probably move it
  to dune-common later when need actually arises).

  This inhibits compilation of dune on armhf with g++-4.4, since std::thread
  is broken there and dune-common now checks that it works.  It does work with
  g++-4.4 on amd64 and g++-4.6 on armhf.

- Use of C++11 features ::

  This uses std::call_once() and std::once_flag which are C++11 features.
  They are present and work in g++-4.4 which is the earliest version of g++ we
  support, I believe.

- Addition of QuadratureRules::maxOrder(qt, gt) ::

  This is a new function that returns the maximum order of quadrature rules
  supported for a given quadrature type and geometry type.  This is necessary
  since I now need to correctly size each vector that holds the quadrature
  rules on the cache *when I first initialize it*, so I need some upper bound
  on the possible number of quadrature rules.  I need this function on
  QuadratureRules, since QuadratureRules creates quadrature rules with the
  help of several other classes, which eventually request lower-dimensional
  quadrature rules from the cache, i.e. recursively from QuadratureRules.  To
  correctly compute the maximum supported quadrature order, the control flow
  has to take a similar path as for computing the actual rules.

The is also a new helper class NoCopyVector.  This class is meant to be
internal to the QuadratureRules implementation, and thus does not comprise a
new interface.  This vector is needed to store once_flags.  These cannot be
stored in a std::vector, since they cannot be copy-constructed.  They cannot
be stored in a std::deque, since that is broken with g++-4.4.  It can be
replaced by std::deque once we discontinue support for g++-4.4 (although
someone should redo the benchmarks then).

Regards,
Jö.

[1] http://herbsutter.com/2013/02/11/atomic-weapons-the-c-memory-model-and-modern-hardware/
    Part 2, 48:48 and 51:38.
- 
-- 
Jorrit (Jö) Fahlke, Institute for Computational und Applied Mathematics,
University of Münster, Orleans-Ring 10, D-48149 Münster
Tel: +49 251 83 35146 Fax: +49 251 83 32729

Interpunktion, Orthographie und Grammatik der Email ist frei erfunden.
Eine Übereinstimmung mit aktuellen oder ehemaligen Regeln wäre rein
zufällig und ist nicht beabsichtigt.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 828 bytes
Desc: Digital signature
URL: <https://lists.dune-project.org/pipermail/dune-devel/attachments/20150118/7a043354/attachment.sig>