Placeholder for graph parallelism about lightgraphs.jl HOT 6 CLOSED

Graph algorithms building blocks are a way to phrase parallel graph algorithms in terms of parallel primitives a brief slides description with many references ipdps summary and a julia paper that implements some of them.

from lightgraphs.jl.

paging @amitmurthy (since I seem to recall that he's done a lot of work with parallelism) for whatever input he would care to give here :)

from lightgraphs.jl.

After some testing, the issue becomes one of (lack of) shared memory for Graph objects. Using @parallel to try to get multiple-source Dijkstra shortest paths resulted in worse performance than just single-threading the algorithm.

If there were a way to do d_s_p using spectral analysis, we could make the adjacency or whatever other matrix a shared array and that might solve things, but it would require a complete rewrite of the Dijkstra implementation to work. @jpfairbanks - have you heard of an implementation of Dijkstra using graphs represented by matrices?

from lightgraphs.jl.

See also https://groups.google.com/d/msg/julia-dev/yhZ5_gEgUJw/2oPZMXugCQAJ

from lightgraphs.jl.

Some more documents on this. Intel, GaBB14, SharedSparseMatrix Implementation

Based on a discussion with @sbromberger,
Accessing Sparse Matrices without copying the columns:

function column(a::SparseMatrixCSC, i::Integer)
    return sub(a.rowval, a.colptr[i]:a.colptr[i+1]-1)
end

for u in 1:nv(g)
    for v in column(g, u)
         print("Operating on edge $u-->$v")
    end
end

An update to SharedSparseMatrixCSC should make sure to support indexing with sub.

from lightgraphs.jl.

Moving discussion to #150

from lightgraphs.jl.