
Boost Users : 
Subject: Re: [Boostusers] [BGL] parallel BGL does not scale
From: Quaglino Alessio (alessio.quaglino_at_[hidden])
Date: 20151214 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 nonparallel BGL).
Regards,
Alessio
> Date: Mon, 14 Dec 2015 16:00:21 +0100
> From: Daniel Hofmann <daniel_at_[hidden]>
> To: boostusers_at_[hidden]
> Subject: Re: [Boostusers] [BGL] parallel BGL does not scale
> MessageID: <566ED985.2000403_at_[hidden]>
> ContentType: text/plain; charset=windows1252
>
> 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