Re: [boost] [BGL] Multithread problem inserting edges and exploring the same graph

Subject: Re: [boost] [BGL] Multithread problem inserting edges and exploring the same graph
From: Christoph Heindl (christoph.heindl_at_[hidden])
Date: 2009-09-20 15:25:32

Cosimo,

Here are some ideas:
Do you need all of the properties in the explorer threads? maybe you
can construct a somewhat cheap copy of the graph of just vertices,
edges and weights?

When each explorer thread runs an instance of Dijkstra you might
consider a parallel version of Dijkstra [1,2] working on disjoint
graph regions? That might allow you to cut the graph into pieces and
assigning a 'local' version of the graph to each explorer thread and
joining them later on?

[1] http://www.mcs.anl.gov/~itf/dbpp/text/node35.html
[2] J. McHugh, Algorithmic Graph Theory

Unfortunately I'm not used to Boost.BGL so I don't know if any of the
suggested methods will work.

Best regards,
Christoph

On Sun, Sep 20, 2009 at 4:50 PM, Cosimo Calabrese
<cosimo.calabrese_at_[hidden]> wrote:
> Christoph,
>
> unfortunately my graph has about 5 million of vertices and 10 million of
> edges large, with many properties attached to them. A single graph takes
> about 1 Gb of RAM. The "copy solution" is the one I've used till now.
>
> But now:
> - the copy time is heavy, so with a shared graph I would resolve this
> problem;
> - every explorer thread has need of a different view of the graph, so with a
> single shared graph and with the filtered_graph adaptor, I would resolve
> this problem too;
> - the thread number specific of my application is increasing, so the copy of
> the graph is too much onerous.
>
> I think that with this task list, I'm practically obliged to having an only
> one shared graph. The graph is too much large. What do you think about?
>
> Thanks in advance,
> Cosimo Calabrese.
>
>
> Christoph Heindl ha scritto:
>>
>> Cosimo,
>>
>> you might also consider using a snapshot of the graph (i.e copy) in
>> each explorer thread. This might well outperform a mutexed solution
>> when the number of concurrent accesses to edges is high. The only
>> thing to be synchronized then is generating a copy of the graph.
>>
>> Best regards,
>> Christoph
>>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>