Groups


169 of 99+  



julia-users ›
help with parallelization
5 posts by 2 authors  



Seth 	

8/28/15


I'm not understanding the docs on parallelization. I'd like to parallelize a betweenness centrality calculation:

    for s in nodes
        state = dijkstra_shortest_paths(g, s; allpaths=true)
        if endpoints
            _accumulate_endpoints!(betweenness, state, g, s)
        else
            _accumulate_basic!(betweenness, state, g, s)
        end
    end


nodes is a vector of ints over which the calculation should be run (by default, this is every vertex in the graph). Because both state() and _accumulate_* are independent calculations, it seems to me that I could take advantage of multiple cores / processors to speed things up. However, I don't know where to start. Any advice would be greatly appreciated.

State has arrays of ints called "dists" and "parents" - each run through this loop alters these arrays, but there's no dependence between loop iterations.
 


Seth 	

8/29/15


Following up - this doesn't seem to work and I don't know why:

julia> nprocs()
4

julia> @everywhere d = Vector{LightGraphs.DijkstraState}(3000)

julia> @everywhere g = readgraph("/Users/seth/dev/julia/wip/LightGraphs.jl/test/testdata/pgp2.jgz")["pgp"]

julia> @everywhere h = g[1:3000]

julia> a = @sync @parallel for v in 1:nv(h)  # iterate over the vectors
       d[v] = dijkstra_shortest_paths(h,v)   # put the return value of d_s_p into the array
       end
3-element Array{Any,1}:
 RemoteRef{Channel{Any}}(2,1,61)
 RemoteRef{Channel{Any}}(3,1,63)
 RemoteRef{Channel{Any}}(4,1,65)


Why is @sync @parallel returning an array of RemoteRefs, and is there something straightforward I need to do to make this work properly?
- show quoted text -
 


Nils Gudat 	

8/29/15


There could be different problems with your code:

1. dijkstra_shortest_paths might not be defined on the remote workers (your snippet doesn't show where you define this); you can check this by doing remotecall_fetch(3,isdefined,:dijkstra_shortest_paths)
2. d has to be a SharedArray if you want to write on it from the worker processors directly, but this only works for bits types so far if I'm not mistaken 
 


Seth 	

8/29/15


Thanks.  Dijkstra is defined, but the shared array is probably an issue. Is there a way to parallelize this?
 


Seth 	

8/30/15


OK, following up:

I have a function that calculates Dijkstra shortest paths for a vector of source vertices and will return a DijkstraState object for each vertex. This function runs in 15 seconds over 500 vertices on one thread.

I wrote a function to split the source vertices into N different equal-sized* vectors and use pmap() to run each "chunk" in a separate thread. This new function takes 4x as long as the single thread on my 4-core machine. Activity monitor shows each core running at about 50% for a little while, then cores 3 and 4 drop to zero.

Code is here: https://gist.github.com/sbromberger/93e503ab3ea87a5a1630

I can't figure out why parallelizing this code results in a time increase. The graph is large (about 8 gigs) but it's read-only for this function. Any advice would be greatly appreciated as I'd love to be able to scale this to 100+ cores at some point.


On Saturday, August 29, 2015 at 7:33:45 PM UTC-7, Seth wrote:
Thanks.  Dijkstra is defined, but the shared array is probably an issue. Is there a way to parallelize this?