[Beowulf] Bcast or reduce?

Ashley Pittman ashley at quadrics.com
Fri Aug 27 10:18:01 EDT 2004


It might be better to do a allreduce (max of an int) to find the maximum
number of primes per rank and then do a allgather to collect all the
data together padding as necessary on some ranks.

This may seem counter-intuitive in that you are sending padding over the
network but you have to deal with much less meta-data describing what
you want to send.

I assume that you have a MPI_Barrier somewhere in your code, if you
replace that with a AllReduce call and then conditionally only call
AllGather if the AllReduce returns > 0 then it should cost almost zero
extra time except in the case where you have found more primes.

A further optimisation would then be to find an algorithm that meant
that each rank found the same number of primes per iteration but I'll
leave that as an exercise for the reader.

Ashley,

On Thu, 2004-08-26 at 22:38, Anthony Skjellum wrote:
> Bcast would let you do 1-to-all sharing of the array from the root
> MPI_Allreduce or reduce could be finagled into concatenating disjoint sets
> of primes BUT
>    MPI_Allgatherv seems better for concatenating disjoint sets of numbers,
> preceeded by an MPI_Allgather to share the lengths of the disparate sizes.
> 
> What processes know what about what primes?  Where are new primes figured
> out?  IF in all processes, then incremental Allgatherv's might help.
> 
> Tony
> 
> ----- Original Message ----- 
> From: "Jack C" <jack at crepinc.com>
> To: <beowulf at beowulf.org>
> Sent: Thursday, August 26, 2004 3:42 PM
> Subject: [Beowulf] Bcast or reduce?
> 
> 
> > Hey,
> >
> > My project (as some of you may remember from my last post) is a prime
> finder,
> > basically just so that I can learn MPI. I've gotten to the point where
> it's
> > split up and runs great: the only thing left is that I'm testing each
> > number's divisibility agaist ALL the numbers between 2 and sqrt(number).
> > Obiously, this isn't needed.
> >
> > What I need to do is have an array of integers full of my previously found
> > primes to test against. However, I'm having problems figuring out how to
> keep
> > this running tab updated on all the nodes.
> >
> > Will MPI_Bcast or _reduce help? (just thought I'd through that out
> there...)
> >
> > Thanks guys,
> >
> > -Jack C
> > jack {at} crepinc.com
> > http://www.crepinc.com
> > _______________________________________________
> > Beowulf mailing list, Beowulf at beowulf.org
> > To change your subscription (digest mode or unsubscribe) visit
> http://www.beowulf.org/mailman/listinfo/beowulf
> >
> 
> 
> _______________________________________________
> Beowulf mailing list, Beowulf at beowulf.org
> To change your subscription (digest mode or unsubscribe) visit http://www.beowulf.org/mailman/listinfo/beowulf

_______________________________________________
Beowulf mailing list, Beowulf at beowulf.org
To change your subscription (digest mode or unsubscribe) visit http://www.beowulf.org/mailman/listinfo/beowulf



More information about the Beowulf mailing list