Boost Users :
Subject: [Boost-users] Some questions about the time-costing of distributed adjacency list
From: Yan (yan_z_y_at_[hidden])
Date: 2011-09-26 22:57:34
I'm sorry for disturbing you again for some more help.
These days I have done some more test using the distributed adjacency list and distributed dijkstra SP-algorithm. The test data contains about 3,800,000 edges and 2,800,000 vertices. I use a pair of iterators to pass the data to the adjacency list, like that:
Graph g(reader.begin(), reader.end(), reader.weight_begin(), reader.num_vertices(), pg, dist);
Â Â Â Â "reader" is an user-defined class which supplys required data (edges, vertices, weights).
Â Â Â "pg" is definedÂ like that "mpi_process_group pg;"
Â Â Â "dist" isÂ supplied by the readerÂ like that "graph::metis_distribution dist = reader.distribution();". It is based on a metis partition file coordinating the test data.
I run 2 processes on my notebook computer(Intel core2 2.0G, Ram 2G, WinXPsp3).
I also test the same data using a sequential bgl dijkstra SP-algorithm on this computer.
The result is that:
Creating of Graph g costs 10080 seconds; dijkstra computing costs 28.281 seconds.
Creating of Graph g costs 4.563seconds; dijkstra computing costs 1.703 seconds.
As you see,Â when usingÂ distributedÂ adjacency list, it costs soÂ much time to create the graph. Is it nomal?
IÂ have doneÂ some more comparison between 2-processes parallel dijkstra on one core2 computer and sequential dijkstra on the same computer, using different scale data set. Always, the sequential bgl dijkstra costs less time than the 2-processes parallel dijkstra. What's the problem? I have read the boost document on "boost_1_46_1\libs\graph_parallel\doc\html\dijkstra_shortest_paths.html", which shows a good performance and speedup in the charts. Doesn't that mean less time costing than the sequential program?
By the way, when using distributed dijkstra, how to invoke the delta-stepping algorithm? Is it also through the dijkstra_shortest_paths(g, start, ...)?
Thank you very much for all your help.
åä»¶äººï¼ Nick Edmonds [via Boost] <ml-node+s2283326n3837765h68_at_[hidden]>
æ¶ä»¶äººï¼ Yan <yan_z_y_at_[hidden]>
åéæ¥æï¼ 2011å¹´9æ24æ¥, ææå , ä¸å 3:03
ä¸»é¢: Re: [BGL] Distributed adiacency_list memory allocation
> This is exactly what I was looking for, though I don't understand all of
> your words, but most. At least now I'm sure its not an error but normal. By
> the way, I'm new to PBGL, would you please tell me some forums or websites
> that good for beginers of PBGL.
I think this list is the best place I can suggest. Â I'm not sure how many people are using the Boost release but most of the people actively using the development version are people I know personally or professionally and they tend to just contact me directly. Â The folks on this list ought to be able to help with some of the basic parts though and I'll try to chime in when something about the internals comes up (i.e. your question about memory consumption).
Boost-users mailing list
If you reply to this email, your message will be added to the discussion below:http://boost.2283326.n4.nabble.com/BGL-Distributed-adiacency-list-memory-allocation-tp3488161p3837765.html
To unsubscribe from [BGL] Distributed adiacency_list memory allocation, click here.
-- View this message in context: http://boost.2283326.n4.nabble.com/BGL-Distributed-adiacency-list-memory-allocation-tp3488161p3846031.html Sent from the Boost - Users mailing list archive at Nabble.com.
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net