Re: [eigen] assembling a sparse matrix from multiple threads

[Christoph Hertzberg <chtz@xxxxxxxxxxxxxxxxxxxxxxxx>]

Hi!

On 2018-07-05 10:42, Dan Čermák wrote:
> Hi Lorenzo,
>
> I haven't used Eigen in a while, but afaik it uses the compressed column
> storage scheme which (at least I imagine it) makes it complicated to
> insert new values efficiently in parallel.

Yes, it uses CCS (or CRS in RowMajor mode), but as soon as you use the 
`.insert(r,c)` method (or some related methods) it will get into a 
non-compressed state -- making it slightly less costly (but still 
sub-optimal) to insert in random order.
However, there is no synchronization happening. If you insert from 
multiple threads, you need to lock the access to the matrix, which most 
certainly is less efficient than inserting from a single thread.
You have the same problem when inserting values into a std::vector from 
multiple threads.

> Also the documentation of insert states that it is optimized for
> sequential insertion
> (https://eigen.tuxfamily.org/dox/classEigen_1_1SparseMatrix.html#title22),
> which you probably aren't performing.
>
> I guess you are probably better of assembling the matrix entries in the
> vector of triplets and then creating the matrix afterwards. But someone
> more familiar with Eigen should probably confirm that.

Inserting into a single std::vector has similar synchronization 
problems, so maybe collecting a vector for each thread is an option 
(which then need to be concatenated, ideally without actually copying 
the data).

The ideal solution will depend a lot on whether you know something about 
the structure of the matrix, or the order in which values will be 
inserted (e.g., if different threads never insert into the same column).


Christoph

> Cheers,
>
> Dan
>
> Lorenzo Botti <bottilorenzo@xxxxxxxxx> writes:
>
> > Dear all,
> > I'm having troubles assembling a sparse matrix in parallel, from multiple
> > threads.
> > In particular if I use matrix.insert(i,j)  to set the nonzero entries in
> > several concurrent threads the code fails randomly in optimized mode while,
> > in debug mode, an Eigen's error message is triggered saying that one of the
> > matrix entries already exists. The code behavior is pretty unpredictable
> > when repeatedly assembling a sparse matrix in a loop.
> >
> > I'm confident that my code is thread safe and matrix entries are unique as
> > confirmed by the following: if I collect matrix entries in vectors of
> > triplets (one vector for each thread) and then I assemble the matrix
> > serially (using matrix.insert(triplet.row(),triplet.col()) =
> > triplet.value()) everything works fine.
> >
> > I guess that concurrent insertion is not allowed/supported. Am I right?
> >
> > Thanks for help
> > Lorenzo

--
 Dr.-Ing. Christoph Hertzberg

 Besuchsadresse der Nebengeschäftsstelle:
 DFKI GmbH
 Robotics Innovation Center
 Robert-Hooke-Straße 5
 28359 Bremen, Germany

 Postadresse der Hauptgeschäftsstelle Standort Bremen:
 DFKI GmbH
 Robotics Innovation Center
 Robert-Hooke-Straße 1
 28359 Bremen, Germany

 Tel.:     +49 421 178 45-4021
 Zentrale: +49 421 178 45-0
 E-Mail:   christoph.hertzberg@xxxxxxx

 Weitere Informationen: http://www.dfki.de/robotik
 -----------------------------------------------------------------------
 Deutsches Forschungszentrum fuer Kuenstliche Intelligenz GmbH
 Firmensitz: Trippstadter Straße 122, D-67663 Kaiserslautern
 Geschaeftsfuehrung: Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster
 (Vorsitzender) Dr. Walter Olthoff
 Vorsitzender des Aufsichtsrats: Prof. Dr. h.c. Hans A. Aukes
 Amtsgericht Kaiserslautern, HRB 2313
 Sitz der Gesellschaft: Kaiserslautern (HRB 2313)
 USt-Id.Nr.:    DE 148646973
 Steuernummer:  19/672/50006
 -----------------------------------------------------------------------