[Boost-users] Why does the creating of distributed adjacency list cost so much time?

Subject: [Boost-users] Why does the creating of distributed adjacency list cost so much time?
From: Yan (yan_z_y_at_[hidden])
Date: 2011-10-13 09:53:12

Hi all,
I'm learning to use the distributed adjacency list and distributed dijkstra
SP-algorithm. I use some 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 
distributed 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:
Parallel bgl:
Creating of Graph g costs *10080 seconds*; dijkstra computing costs 28.281
seconds.
Sequential bgl:
Creating of Graph g costs *4.563 seconds*; 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?

Any advice would be appreciated. 

Thanks, 
Yan

--
View this message in context: http://boost.2283326.n4.nabble.com/Why-does-the-creating-of-distributed-adjacency-list-cost-so-much-time-tp3901559p3901559.html
Sent from the Boost - Users mailing list archive at Nabble.com.