Open MPI logo

Open MPI Development Mailing List Archives

  |   Home   |   Support   |   FAQ   |   all Development mailing list

Subject: Re: [OMPI devel] Speedup for MPI_Dims_create()
From: Jeff Squyres (jsquyres) (jsquyres_at_[hidden])
Date: 2014-02-10 19:33:25


Cool.

See the other thread where I'm wondering if we shouldn't just pre-generate all the primes, hard-code them into a table, and be done with this issue.

On Feb 10, 2014, at 5:19 PM, Andreas Schäfer <gentryx_at_[hidden]> wrote:

> Jeff-
>
> I've seen that you've reverted the patch as it was faulty. Sorry about
> that! I've attached a new patch, which applies against the current
> trunk. The problem with the last patch was that it didn't catch a
> special case: of all prime factors of n, there may be at most one
> larger than sqrt(n). The old patch assumed that there was none. I've
> included a comment in the source code so that this becomes clear for
> later readers.
>
> The attached patch is more complicated than the original code, as we
> now need to calculate the prime numbers and the number of their
> occurrences in the integer factorization simultaneously. We can't
> split both (as in the trunk) anymore, as the last prime might only be
> discovered during the original getfactors().
>
> I've tested this code back to back with the original code with
> 1...10000 nodes and 1...6 dimensions, just to be on the sure side this
> time.
>
> Best
> -Andreas
>
>
> On 19:32 Mon 03 Feb , Jeff Squyres (jsquyres) wrote:
>> Andreas --
>>
>> I added the sqrt() change, which is the most important change, and then did a 2nd commit with the whitespace cleanup. The sqrt change will likely be in 1.7.5. I credited you in the commit log; you'll likely also get credited in NEWS.
>>
>> Thank you for the patch!
>>
>>
>> On Dec 19, 2013, at 9:37 AM, Andreas Schäfer <gentryx_at_[hidden]> wrote:
>>
>>> Dear all,
>>>
>>> please find attached a (trivial) patch to MPI_Dims_create(). When
>>> computing the prime factors of nnodes, it is sufficient to check for
>>> primes less or equal to sqrt(nnodes).
>>>
>>> This was not so much of a problem in the past, but now that Tier 0
>>> systems are capable of running O(10^6) MPI processes, the difference
>>> in execution time is on the order of seconds (e.g. 8.86s vs. 0.04s on
>>> my notebook, with nnproc = 10^6).
>>>
>>> Best
>>> -Andreas
>>>
>>> PS: oh, and the patch removes some trailing whitespace. Yuck. :-)
>>>
>>>
>>> --
>>> ==========================================================
>>> Andreas Schäfer
>>> HPC and Grid Computing
>>> Chair of Computer Science 3
>>> Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany
>>> +49 9131 85-27910
>>> PGP/GPG key via keyserver
>>> http://www.libgeodecomp.org
>>> ==========================================================
>>>
>>> (\___/)
>>> (+'.'+)
>>> (")_(")
>>> This is Bunny. Copy and paste Bunny into your
>>> signature to help him gain world domination!
>>> <mpi_dims_create_speedup.patch>_______________________________________________
>>> devel mailing list
>>> devel_at_[hidden]
>>> http://www.open-mpi.org/mailman/listinfo.cgi/devel
>>
>>
>> --
>> Jeff Squyres
>> jsquyres_at_[hidden]
>> For corporate legal information go to: http://www.cisco.com/web/about/doing_business/legal/cri/
>>
>> _______________________________________________
>> devel mailing list
>> devel_at_[hidden]
>> http://www.open-mpi.org/mailman/listinfo.cgi/devel
>
> --
> ==========================================================
> Andreas Schäfer
> HPC and Grid Computing
> Chair of Computer Science 3
> Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany
> +49 9131 85-27910
> PGP/GPG key via keyserver
> http://www.libgeodecomp.org
> ==========================================================
>
> (\___/)
> (+'.'+)
> (")_(")
> This is Bunny. Copy and paste Bunny into your
> signature to help him gain world domination!
> <mpi_dims_create_speedup.patch>_______________________________________________
> devel mailing list
> devel_at_[hidden]
> http://www.open-mpi.org/mailman/listinfo.cgi/devel

-- 
Jeff Squyres
jsquyres_at_[hidden]
For corporate legal information go to: http://www.cisco.com/web/about/doing_business/legal/cri/