 # Boost Users :

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:
"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.
```