[dune-pdelab] New istl MatrixBackend considered less user friendly

[Dominic Kempf]

Hey Oli,

as I was implementing the new matrix build mode back then, I can give you
some numbers and an idea of why it is so important.
The way it was implemented before, the following steps were done strictly
sequentially
1) Determine sparsity pattern and store it in a suitable (map-like) data
structure
2) Allocate storage for the BCRSMatrix
3) Build the sparsity pattern on the matrix using the data from 1)

The key problem here is peek memory usage: Step 1) has memory complexity
n*log(n) (n being the number of matrix entries),
Step 2) has complexity n. Both data structures need to be kept around until
step 3 is finished. Only then, the data structure
from 1) can be discarded.

The new algorithm works more like this:
1) Get some pattern statistics from the user
2) Allocate storage for the BCRSMatrix based on the given statistics
3) Build the sparsity pattern on-the-fly directly into the allocated storage
4) "Compress" the matrix (remove holes from underfill etc.)

Given a vanilla 2D Q1 poisson problem with around a million unknowns, the
peak usage dropped from 3.6 GB to 1.1 GB.
You can definitely see that the log(n) factor on the pattern-map's
complexity really does contribute here. You might
also extrapolate that for even larger problems (both in number of dofs and
in entries per row), the problem potentially poses a
bottleneck for the entire simulation code.

I agree, that some good documentation on the why and how of this would be
important.

Best,
Dominic



On Mon, Jul 20, 2015 at 2:50 PM, Steffen Müthing <
steffen.muething at iwr.uni-heidelberg.de> wrote:

> Hi Oliver,
>
> > Am 13.07.2015 um 11:58 schrieb Oliver Sander <sander at igpm.rwth-aachen.de
> >:
> >
> > Dear pdelab,
> >
> > I just switched from the old ISTLMatrixBackend to the new
> istl::BCRSMatrixBackend.
> > Everything appears to work nicely, but I find the new implementation
> more cumbersome
> > to use.
> >
> > Before, I could simple instantiate GridOperator with the correct matrix
> > backend type, and the corresponding object was created automatically for
> me.
> > With the new interface, I have to create a backend object myself (that's
> acceptable),
> > and additionally I have to give it information about the expected matrix
> density.
> > But I am solving small problems on small grids.  Memory consumption and
> wall-clock
> > time are not important to me.  Therefore I don't want to be forced to
> think about
> > matrix occupation patterns.  Is it possible to make the backend object
> default
> > constructible again (maybe choosing 3^d as a default value), so people
> like me
> > don't have to think about issues that only affect HPC projects?
>
> The new construction method is important not just for HPC, but also for
> people just using PDELab
> on a small scale (laptops etc.). I don’t have the exact numbers right now
> (Dominic did the benchmarks
> back when this was implemented), but for a simple Poisson problem with P1
> elements, the new method
> reduces the maximum memory consumption by a factor of 2 - 3 and can cut
> down the run time (of the
> overall program) by an order of magnitude for larger problems.
> Unfortunately, it’s really not possible to
> specify a sensible global default (your idea of using 3^d is e.g. way too
> small for non-blocked DG spaces,
> where a good formula would be (average_number_of_neighbor_intersections +
> 1) * (k+1)^d ).
>
> That said, we really need to document this a lot better somewhere and give
> people some good "cooking
> recipes" for calculating these numbers. I’ll open a bug for that…
>
> Steffen
>
> >
> > Thanks,
> > Oliver
> >
> >
> > _______________________________________________
> > dune-pdelab mailing list
> > dune-pdelab at dune-project.org
> > http://lists.dune-project.org/mailman/listinfo/dune-pdelab
>
>
> _______________________________________________
> dune-pdelab mailing list
> dune-pdelab at dune-project.org
> http://lists.dune-project.org/mailman/listinfo/dune-pdelab
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.dune-project.org/pipermail/dune-pdelab/attachments/20150721/44ac213f/attachment.htm>