Open MPI logo

Open MPI Development Mailing List Archives

  |   Home   |   Support   |   FAQ   |   all Development mailing list

Subject: Re: [OMPI devel] Reviewing MPI_Dims_create
From: Jeff Squyres (jsquyres) (jsquyres_at_[hidden])
Date: 2014-02-10 14:12:08


Nice! Can you verify that it passes the ibm test? I didn't look closely, and to be honest, I'm not sure why the previous improvement broke the IBM test because it hypothetically did what you mentioned (stopped at sqrt(freenodes)).

I think patch 1 is a no-brainer. I'm not sure about #2 because I'm not sure how it's different than the previous one, nor did I have time to investigate why the previous one broke the IBM test. #3 seems like a good idea, too; I did't check the paper, but I assume it's some kind of proof about the upper limit on the number of primes in a given range.

Two questions:

1. Should we cache generated prime numbers? (if so, it'll have to be done in a thread-safe way)

2. Should we just generate prime numbers and hard-code them into a table that is compiled into the code? We would only need primes up to the sqrt of 2billion (i.e., signed int), right? I don't know how many that is -- if it's small enough, perhaps this is the easiest solution.

On Feb 10, 2014, at 1:30 PM, Christoph Niethammer <niethammer_at_[hidden]> wrote:

> Hello,
>
> I noticed some effort in improving the scalability of
> MPI_Dims_create(int nnodes, int ndims, int dims[])
> Unfortunately there were some issues with the first attempt (r30539 and r30540) which were reverted.
>
> So I decided to give it a short review based on r30606
> https://svn.open-mpi.org/trac/ompi/browser/trunk/ompi/mpi/c/dims_create.c?rev=30606
>
>
> 1.) freeprocs is initialized to be nnodes and the subsequent divisions of freeprocs have all positive integers as divisor.
> So IMHO it would make more sense to check if nnodes > 0 in the MPI_PARAM_CHECK section at the begin instead of the following (see patch 0001):
>
> 99 if (freeprocs < 1) {
> 100 return OMPI_ERRHANDLER_INVOKE(MPI_COMM_WORLD, MPI_ERR_DIMS,
> 101 FUNC_NAME);
> 102 }
>
>
> 2.) I rewrote the algorithm stopping at sqrt(n) in getprimes(int num, int *nprimes, int **pprimes)
> which makes mathematically more sens (as the largest prime factor of any number n cannot exceed \sqrt{n}) - and should produce the right result. ;)
> (see patch 0002)
> Here the improvements:
>
> module load mpi/openmpi/trunk-gnu.4.7.3
> $ ./mpi-dims-old 1000000
> time used for MPI_Dims_create(1000000, 3, {}): 8.104007
> module swap mpi/openmpi/trunk-gnu.4.7.3 mpi/openmpi/trunk-gnu.4.7.3-testing
> $ ./mpi-dims-new 1000000
> time used for MPI_Dims_create(1000000, 3, {}): 0.060400
>
>
> 3.) Memory allocation for the list of prime numbers may be reduced up to a factor of ~6 for 1mio nodes using the result from Dusart 1999 [1]:
> \pi(x) < x/ln(x)(1+1.2762/ln(x)) for x > 1
> Unfortunately this saves us only 1.6 MB per process for 1mio nodes as reported by tcmalloc/pprof on a test program - but it may sum up with fatter nodes. :P
>
> $ pprof --base=$PWD/primes-old.0001.heap a.out primes-new.0002.heap
> (pprof) top
> Total: -1.6 MB
> 0.3 -18.8% -18.8% 0.3 -18.8% getprimes2
> 0.0 -0.0% -18.8% -1.6 100.0% __libc_start_main
> 0.0 -0.0% -18.8% -1.6 100.0% main
> -1.9 118.8% 100.0% -1.9 118.8% getprimes
>
> Find attached patch for it in 0003.
>
>
> If there are no issues I would like to commit this to trunk for further testing (+cmr for 1.7.5?) end of this week.
>
> Best regards
> Christoph
>
> [1] http://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-01037-6/home.html
>
>
>
> --
>
> Christoph Niethammer
> High Performance Computing Center Stuttgart (HLRS)
> Nobelstrasse 19
> 70569 Stuttgart
>
> Tel: ++49(0)711-685-87203
> email: niethammer_at_[hidden]
> http://www.hlrs.de/people/niethammer<0001-Move-parameter-check-into-appropriate-code-section-a.patch><0002-Speeding-up-detection-of-prime-numbers-using-the-fac.patch><0003-Reduce-memory-usage-by-a-better-approximation-for-th.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/