Re: [Boost-users] Details of boost parallel graph implementation

Subject: Re: [Boost-users] Details of boost parallel graph implementation
From: Mayank Bakshi (mayank.bakshi_at_[hidden])
Date: 2015-07-31 08:27:34

 Thanks for the reply Marcin.  

I have some queries:

1.
  Which are the files in the source tree where I can get the details of 
implementation of queue,graph and the property map for serial as well as
 distributed (MPI ) cases. 
  
Also, I had the following query. 

With reference to document 
http://www.boost.org/doc/libs/1_58_0/libs/graph_parallel/doc/html/overview.html
For parallel version of BFS, the steps that I inferred are as below. Could you please correct me in this:

1. The root node process reads the input file which is in the gr format read by metis reader.
2. The root node process creates the adjacency list representation of the graph. 
3.
 The root node process creates the property map with "ghost cells" of the
 graph. The various entries are marked as white corresponding to each of
 the node.
4. The root node process will distribute the adjacency list and property map to each of the processes.
5.
 Each of the non-root nodes now has its own copy of adjacency list and 
property map along with details of the source node where the BFS is to 
start
6. Now the process having the source node starts the traversal of the graph. 
7. The source node is put in a queue.
8.
 The source node will dequeue the source node and mark all its neighbours
 as gray and put them in queue. Also it will mark itself as black.
9. The property maps on each of the nodes will now be updated
10. Each of the node processes will be monitoring its own property map 
 
      If any of the processes finds a node marked as gray, it will 
enqueue that particular node and start its own traversal locally.
11.
 Thus on every node the property map will be marked as gray and then 
eventually black after visit is complete. The property maps will be 
synchronised.
12. The steps from 8 to 11 are repeated till all the entries in every property map are marked as black. 

Is my interpretation of the implementation for parallel correct? 

How often are the property maps on various nodes synchronized and under what condition?

Is there any synchronisation with respect to the queues ?


Thanks & Regards
Mayank Bakshi
Tata Consultancy Services Limited
Cell:- 7083955990
Mailto: [e-mail]
Website: http://www.tcs.com
____________________________________________
Experience certainty.	IT Services
			Business Solutions
			Consulting
____________________________________________


-----"Boost-users" <[e-mail]> wrote: -----
To: [e-mail]
From: Marcin Zalewski

Sent by: "Boost-users"

Date: 07/30/2015 10:03AM
Subject: Re: [Boost-users] Details of boost parallel graph implementation



On Wed, Jul 29, 2015 at 4:26 AM Mayank Bakshi <[e-mail]> wrote:
>  Hello,
>
> I am working on mpi implementation of boost for breadth first search. 
> What is the algorithmic detail for BFS in boost.mpi? How the graph is processed by each rank which we provide in mpirun (load distribution among different processes)? 

The sequential BGL library is overloaded on distributed graphs:

https://github.com/boostorg/graph/blob/master/include/boost/graph/breadth_first_search.hpp

Look for the mpl::true_ and mpl::bool_ to see where distributed vs. not-distributed selection is made. graph_parallel provides some additional overloads of the helper, but it does not define a brand new BFS:

https://github.com/boostorg/graph_parallel/blob/master/include/boost/graph/distributed/breadth_first_search.hpp

The whole magic happens in the queue, graph, and property maps data structures. The queue distributes work, and it also implements a global "empty" check, and the property maps allow accessing remote vertices. So, if you need MPI BFS, one is already there.  
_______________________________________________
Boost-users mailing list
[e-mail]
http://lists.boost.org/mailman/listinfo.cgi/boost-users

=====-----=====-----=====
Notice: The information contained in this e-mail
message and/or attachments to it may contain 
confidential or privileged information. If you are 
not the intended recipient, any dissemination, use, 
review, distribution, printing or copying of the 
information contained in this e-mail message 
and/or attachments to it are strictly prohibited. If 
you have received this communication in error, 
please notify us by reply e-mail or telephone and 
immediately and permanently delete the message 
and any attachments. Thank you