如何提高图中心度计算的并行性能？

Question

我得到的性能下降后，并行化的代码，计算图中心。图比较大，100K顶点。单线程应用程序大约需要7分钟。根据julialang站点（http://julia.readthedocs.org/en/latest/manual/parallel-computing/#man-parallel-computing）的建议，我修改了代码并使用pmap api来并行计算。我开始计算8个过程（julia-p 8calc_centrality.jl）。令我惊讶的是，我慢了10倍。并行过程现在需要一个多小时。我注意到并行进程初始化和开始计算需要几分钟。即使在所有8 html" target="_blank">CPU是0忙于julia应用程序，计算是超级慢。

任何关于如何提高并行性能的建议都将不胜感激。

calc_centrality.jl：

using Graphs
require("read_graph.jl")
require("centrality_mean.jl")

function main()
    file_name = "test_graph.csv"
    println("graph creation: ", file_name)
    g = create_generic_graph_from_file(file_name)
    println("num edges: ", num_edges(g))
    println("num vertices: ", num_vertices(g))

    data = cell(8)
    data[1] = {g, 1, 2500}
    data[2] = {g, 2501, 5000}
    data[3] = {g, 5001, 7500}
    data[4] = {g, 7501, 10000}
    data[5] = {g, 10001, 12500}
    data[6] = {g, 12501, 15000}
    data[7] = {g, 15001, 17500}
    data[8] = {g, 17501, 20000}
    cm = pmap(centrality_mean, data)
    println(cm)

end
println("Elapsed: ", @elapsed main(), "\n")

你的意思是中心性。jl

using Graphs

function centrality_mean(gr, start_vertex)
    centrality_cnt = Dict()
    vertex_to_visit = Set()
    push!(vertex_to_visit, start_vertex)

    cnt = 0
    while !isempty(vertex_to_visit)
        next_vertex_set = Set()
        for vertex in vertex_to_visit
            if !haskey(centrality_cnt, vertex)
                centrality_cnt[vertex] = cnt
                for neigh in out_neighbors(vertex, gr)
                    push!(next_vertex_set, neigh)
                end
            end
        end
        cnt += 1
        vertex_to_visit = next_vertex_set
    end
    mean([ v for (k,v) in centrality_cnt ])
end

function centrality_mean(data::Array{})
    gr = data[1]
    v_start = data[2]
    v_end = data[3]
    n = v_end - v_start + 1;
    cm = Array(Float64, n)
    v = vertices(gr)
    cnt = 0
    for i = v_start:v_end
        cnt += 1
        if cnt%10 == 0
            println(cnt)
        end
        cm[cnt] = centrality_mean(gr, v[i])
    end
    return cm
end

Answer 1

从Julia关于并行计算的页面：

Julia提供了一个基于消息传递的多处理环境，允许程序同时在不同内存域中的多个进程上运行。

如果我正确地解释这一点，Julia的并行性需要消息传递来同步进程。如果每个单独的进程只做很少的工作，然后进行消息传递，那么计算将被消息传递开销所主导，而不做任何工作。

我从你的代码中看不到，我也不太了解朱莉娅，看不到并行中断在哪里。但是你有一个很大的复杂的图，它可以随意地分布在多个过程中。如果他们需要在跨图链接时进行交互，你就会有这样的开销。

您可以通过将图的分区预先计算成大小大致相等、高度内聚的区域来修复它。我怀疑分手需要你已经想做的那种复杂的图形处理，所以你可能有一个鸡和蛋的问题要启动。

可能是朱莉娅给你提供了错误的并行模型。您可能需要一个共享地址空间，这样在图中行走的线程就不必使用消息来遍历弧。

Answer 2

下面是作者在评论中建议的带有@everywhere的代码https://stackoverflow.com/users/1409374/rickhg12hs.解决了性能问题！！！

test_parallel_pmap.jl

using Graphs
require("read_graph.jl")
require("centrality_mean.jl")

function main()
   @everywhere file_name = "test_data.csv"
   println("graph creation from: ", file_name)
   @everywhere data_graph = create_generic_graph_from_file(file_name)
   @everywhere data_graph_vertex = vertices(data_graph)
   println("num edges: ", num_edges(data_graph))
   println("num vertices: ", num_vertices(data_graph))

   range = cell(2)
   range[1] = {1, 25000}
   range[2] = {25001, 50000}
   cm = pmap(centrality_mean_pmap, range)
   for i = 1:length(cm)
       println(length(cm[i]))
  end
end

println("Elapsed: ", @elapsed main(), "\n")

你的意思是中心性。jl

using Graphs

function centrality_mean(start_vertex::ExVertex)
    centrality_cnt = Dict{ExVertex, Int64}()
    vertex_to_visit = Set{ExVertex}()
    push!(vertex_to_visit, start_vertex)

    cnt = 0
    while !isempty(vertex_to_visit)
        next_vertex_set = Set()
        for vertex in vertex_to_visit
            if !haskey(centrality_cnt, vertex)
                centrality_cnt[vertex] = cnt
                for neigh in out_neighbors(vertex, data_graph)
                    push!(next_vertex_set, neigh)
                end
            end
        end
       cnt += 1
       vertex_to_visit = next_vertex_set
    end
    mean([ v for (k,v) in centrality_cnt ])
end

function centrality_mean(v_start::Int64, v_end::Int64)
    n = v_end - v_start + 1;
    cm = Array(Float64, n)
    cnt = 0
    for i = v_start:v_end
        cnt += 1
        cm[cnt] = centrality_mean(data_graph_vertex[i])
    end
    return cm
end

function centrality_mean_pmap(range::Array{})
    v_start = range[1]
    v_end = range[2]
    centrality_mean(v_start, v_end)
end

Answer 3

我猜这和平行无关。您的第二个centrality_mean方法不知道什么类型的对象gr，v_start和v_end。所以它将不得不为那个“外环”使用非优化的、缓慢的代码

虽然有几种可能的解决方案，但最简单的方法可能是分解从pmap接收“命令”的函数：

function centrality_mean(data::Array{})
    gr = data[1]
    v_start = data[2]
    v_end = data[3]
    centrality_mean(gr, v_start, v_end)
end

function centrality_mean(gr, v_start, v_end)
    n = v_end - v_start + 1;
    cm = Array(Float64, n)
    v = vertices(gr)
    cnt = 0
    for i = v_start:v_end
        cnt += 1
        if cnt%10 == 0
            println(cnt)
        end
        cm[cnt] = centrality_mean(gr, v[i])
    end
    return cm
end

所有这些只是创建了一个中断，并给julia一个机会来优化第二部分（包含性能关键循环）的实际输入类型。