
Boost Users : 
Subject: Re: [Boostusers] [BGL] parallel BGL does not scale
From: Daniel Hofmann (daniel_at_[hidden])
Date: 20151214 10:00:21
Can you try a problem size that takes longer than the subsecond
workload your posted? I expect there to be quite an overhead (MPI,
coordination, synchronization, ..) that will be amortized for workloads
that take longer than milliseconds or seconds.
Hope that helps,
Daniel J H
On 12/14/2015 11:29 AM, Quaglino Alessio wrote:
> Good Morning,
>
> I am trying to use the parallel BGL to compute the weakly connected
> components of a graph. I have managed to obtain the correct results with
> the code pasted below, however I am getting the following times:
>
>  Sequential BGL 0.01 seconds
>  Parallel BGL on 1 core 0.04 seconds
>  Parallel BGL on 2 cores 0.64 seconds
>
> That doesn’t look right to me. What am I doing wrong?
>
> usingnamespaceboost;
> using boost::graph::distributed::mpi_process_group;
> typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>,
> undirectedS> Graph;
> typedef iterator_property_map<std::vector<int>::iterator,
> property_map<Graph, vertex_index_t>::type> LocalMap;
>
> int getConnectedComponents(std::vector< std::pair<int,int> > &arcs,
> const std::vector<int> &isActive) {
>
> // Allocate structures
> Graph G(nV+1);
> std::vector<int> localComponent(nV+1);
> std::vector<int> globalComponent(nV+1);
>
> // Only rank 0 has got the arc data structure
> if( rank == 0 ) {
>
> // Add dummy edges to each vertex (required to avoid BGL crash
> for a single node with no edges)
> for( int i=0; i<nV; i++ ) add_edge(vertex(i,G),vertex(i,G),G);
>
> // Add edges to the graph
> for(std::vector<std::pair<int,int> >::iterator it =
> arcs.begin(); it != arcs.end(); ++it)
> if( isActive[arcCnt++]==0 )
> add_edge(vertex(it>first,G),vertex(it>second,G),G);
> }
>
>
>
> synchronize(G);
>
> // Compute number of connected components
> LocalMap components(localComponent.begin(),get(vertex_index, G));
> int num = connected_components_ps(G, components);
>
> // Let rank 0 collect the global component vector
> if( rank == 0 ) {
> components.set_max_ghost_cells(0);
> for( PetscInt i = 0; i < nV+1; i++ ) globalComponent[i] =
> get(components, vertex(i, G));
> }
>
> synchronize(components);
> }
>
>
> Regards,
> 
> Alessio Quaglino
> Postdoctoral Researcher
> University of Lugano
>
>
>
>
>
> _______________________________________________
> Boostusers mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
>
Boostusers 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