[Dune-devel] SOCIS 2014: FEM assembly with threads

[Markus Blatt]

On Fri, Jun 27, 2014 at 11:27:19AM +0000, Agnese, Marco wrote:
> Dear Jö, dear Christian,
> thank you very much for your feedbacks, I appreciate it a lot. 
> 
> Actually I am not focus on an efficient assembly of the matrix but to write a class to manage a thread-safe writing on a shared vector (something like what happens with ParallelIndexSet). This should be my first goal, if I have understood it right.  
> 

Like I said in my other email is not shared in the regular
sense. Still we need to make sure that the entries do make sense. This
might require locking, but we should try to avoid it as far as we
can. I hope we can do this.

> For what concern the design, I was thinking to this strategy to find
> out the best locking system for a general case.

Let us not get too general. Basically, some of the unknowns are shared
by a few threads. Who these threads and unknowns are can be
precomputed by the parallel index sets and connected classes. 

During this {copy|add}<from_flag>To<to_flags>, do we need locks?
Basically each/some thread that holds one of the shared unknowns, needs an
updated value at sometime. But do the other threads need to write to
this value directly? No! They just need some place on the receiving
thread to write to. The place might even differ for each thread. Maybe
we can think of a dedicated place for each threads value and skip the
locking here? Then we just need to have a means to tell the receiving
thread that all the values are their now (With support for atomics
this could be a lock free counter for the thread writes. Then we need
something else for non-supporting compilers/platforms). The receiving
thread is then responsible for the reduction (copy, add, whatever).

The above could be called a push scenario (each thread pushes its
value). One could also think of a pull scenario, where the thread that
needs the values reads them from the other threads. This does not have
to be directly from the vectors used by the computation, but could be
some intermediate storage area (maybe within the parallel index sets)
that uses (fine-grained) locking. 


Coming to thinks of it there seem to be a lot of possibilities
here. If you have a another one, please do not hesitate to share!
(This is getting a fun and interesting project). Maybe Marco can 
come up with some design document before/during the coding?

> For each thread I know which elements of the vector it will
> access. I can therefore simply estimates if an element of the vector
> is shared or not. I can also describe the interactions between
> threads as graph where each node represents a thread; two nodes are
> connected if they share at least one element (a weight could be the
> number of shared elements). For this graph I extract the connected
> components; for each connected components, I choose the most
> connected node and I remove all the nodes connected to until I have
> a set of disjoint threads. All these threads can write
> simultaneously without any danger. I repeat this algorithm with the
> remaining threads, until all the threads have been considered. In
> this way I have obtained a list of sets of threads which can be
> executed simultaneously. This list is computed only once and it is
> used every time an update of the shared vector is
> performed. Obviously when the thread needs to write in a not shared
> element of the vector, it won't way anything. 

This sounds very, maybe even too, complicated IMHO.

> 
> Before implementing it I would like to know what you think about it since I would like to avoid spending a lot of coding hours for something which is useless/inefficient. 
> 

Cheers,

Markus

-- 
Do you need more support with DUNE or HPC in general? 

Dr. Markus Blatt - HPC-Simulation-Software & Services http://www.dr-blatt.de
Hans-Bunte-Str. 8-10, 69123 Heidelberg, Germany
Tel.: +49 (0) 160 97590858
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: Digital signature
URL: <https://lists.dune-project.org/pipermail/dune-devel/attachments/20140630/f7127691/attachment.sig>