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@tellus.it> 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