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

[Jö Fahlke]

Am Fri, 27. Jun 2014, 11:27:19 +0000 schrieb Agnese, Marco:
> 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.  
> 
> For what concern the design, I was thinking to this strategy to find out the best locking system for a general case. 
> 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.
> 
> 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. 

I think you're describing coloring: you have a set of connected partitions,
you assign each partition a color such that no two partitions of the same
color share a connection, and then you can handle all partitions of the same
color in parallel.  You need a global barrier between handling different
colors.

Since you're basically iterating over plain vectors, the overhead of
entity-wise locking may be noticeable, so it is reasonable to try coloring.
In particular if you can compute the coloring as easily as in the 1D case.
But unfortunately, I cannot tell you a-priory whether locking or coloring will
be superior.

(I tried coloring for assembling data on meshes from dune-grid.  I found that
there was not noticable benefit for up to 240 threads over entity-wise
locking.  The crucial point here is that iteration over dune's grids can be
quiet expensive, in particular if intersection iterators are involved, so the
benefit of doing coloring is not noticable.  You're iterating over pretty
plain vectors AFAIK, so the outcome may well be different.)

-- 
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

Spaß mit I18N.  Hier StumpWM/clisp:
WARNUNG: DEFUN/DEFMACRO(GET-WM-CLASS): #<PACKAGE XLIB> ist abgeschlossen.
         Das Schloss umgehen und weitermachen.
-------------- 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/20140627/383d1354/attachment.sig>