Re: [Boost-users] [BGL] parallel BGL does not scale

Subject: Re: [Boost-users] [BGL] parallel BGL does not scale
From: Quaglino Alessio (alessio.quaglino_at_[hidden])
Date: 2015-12-14 11:05:57

Dear Daniel,

Yes that’s a good suggestion and I’ve tried it, discovering the following:

1) The call to connected_components_ps gets really slow only if I run the program with mpirun -np 2, but it is ok with mpirun -np 1. Why is this the case? I need to be able to control how many cores I am using to do scaling tests, is this possible with the parallel BGL?

2) Apart from the above, the really slow part is now the graph construction. This takes about 10 times more than the call to connected_components_ps (but it wasn’t the case with the non-parallel BGL).

Regards,
Alessio


> Date: Mon, 14 Dec 2015 16:00:21 +0100
> From: Daniel Hofmann <daniel_at_[hidden]>
> To: boost-users_at_[hidden]
> Subject: Re: [Boost-users] [BGL] parallel BGL does not scale
> Message-ID: <566ED985.2000403_at_[hidden]>
> Content-Type: text/plain; charset=windows-1252
> 
> Can you try a problem size that takes longer than the sub-second
> 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
>> 
>> 
>> 
>> 
>> 
>> _______________________________________________
>> Boost-users mailing list
>> Boost-users_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/boost-users

>>