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

[ Thread Index | Date Index | More Archives ]


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




Lorenzo Botti <bottilorenzo@xxxxxxxxx> writes:

Dear all,
I'm having troubles assembling a sparse matrix in parallel, from multiple
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

 Dr.-Ing. Christoph Hertzberg

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

 Postadresse der Hauptgeschäftsstelle Standort Bremen:
 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:
 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

Mail converted by MHonArc 2.6.19+