osrm-backend icon indicating copy to clipboard operation
osrm-backend copied to clipboard

Parallelize graph compression

Open TheMarex opened this issue 6 years ago • 0 comments

Right now the GraphCompressor is a serial algorithm. The reason for this is that it is not trivial to find a set a of nodes that won't cause conflicts when contracted. For example:

a -----> b -----> c -----> d
  <-----   <-----   <-----

If thread 1 contracts the node b at the same time that thread 2 would contract d we will end up with race conditions: Both would try to modify the edges of c and would potentially create a wrong graph.

To fix this we need to find an "independent set": A set of nodes that don't share any neighbor nodes (note this is different from the classical independent set because we don't just require that they are not adjacent).

The graph compression algorithm would then work in multiple stages:

  1. Compute an independent set.
  2. Split up the independent set over all threads
  3. On each thread contract the nodes.

There are a few places in the GraphCompressor that need to be made thead-safe, like the bucket management.

/cc @oxidase

TheMarex avatar Jul 09 '17 20:07 TheMarex