parallel betweenness

Development
1

Hi,
I want to implement parallel betweenness algorithm (answering this issue) .

I want to use threads (using pthreads library). Does igraph have auxiliary functions (such as IGRAPH_CHECK) for pthread, or to any other parallel computing library? should I write one (for handling errors)? should I even use pthread or different library?

thanks for the help…

2

Windows does not have pthreads natively, so that would bring in an extra dependency on Windows, and maybe a full POSIX compatibility layer (not sure, I haven’t tried pthreads on Windows). Also, the igraph data structures are not thread-safe so I would be very, very cautious when attempting this with threads. Also, be prepared that such a PR would have to go through a very careful (and probably slow) review and a thorough stress-testing on large graphs as race conditions and other errors in the implementation are not immediately obvious and could be very hard to debug.

I feel that OpenMP is probably better suited for this task, and it has better support on Windows. The parallelization of the betweenness task would basically involve spreading the outer for (source = 0; source < no_of_nodes; source++) { loop over multiple CPU cores. Each OpenMP job would then need its own copy of the q queue, the stack stack, the distance, nrgeo and tmpscore vectors and they would need to coordinate parallel writes to tmpres. (Maybe there is more, these are the ones I could find right now).

1 Like
3

Hi, actually we don’t even need to share the variable tmpres. Each function can return a different result vector and than sum the vectors together. I think this would eliminate all possibilities for race conditions.
What do you think?

4

yes, that’s also an option.

5

I need help with linking openMP using cmake.
I found that in order to link I need to add this text to CMakeLists.txt:

find_package(OpenMP)
if(OpenMP_C_FOUND)
    target_link_libraries(MyTarget private OpenMP::OpenMP_C)
endif()

but I am getting an error with MyTarget. Do you know how to continue?
thanks…

6

Replace MyTarget with the name of the CMake target that you want to use OpenMP features in. If oyu are modifying src/CMakeLists.txt directly, then this target is called igraph

7

My attempts with OpenMP failed, because the stack doesn’t seem to be thread safe? Various stack sanity checks directly fail when used with shared().

# pragma omp parallel for default(none) shared(S, parents, inclist, adjlist, dist, tmpscore, tmpres) firstprivate(no_of_nodes, graph, nrgeo, cutoff, weights) private(j, neighbor)

In addition tmpres and tmpscore can not be added together with reduction() or require a custom “reduction identifier”?

And IGRAPH_CHECK always triggers:

error: cannot return from OpenMP region

Still looking around for sections to parallelize…