MPI Sieve of Eratosthenes for prime numbers below N

MPI Installation

Linux

Beforedoing any MPI programming, make sure to load the MPI module on Unix:

$ module load mpi/openmpi-x86_64

Mac

Or, if you are using Mac, just:

$ brew install open-mpi

Module

Executable

You can make the module with <dir> $make

$ make

on make you will have an executable compiled with debug and compilation warnings turned on. -lm stands for <math.h> library inclusion.

Clean

$ make clean

this will remove the executable as well as all of the generated .txt files.

Usage

$ mpiexec -n <P> genprimes <N>

Where <P> stands for the number of MPI processes and <N> is the upper bound on the prime range.

#P vs N	1k	10k	100k	1M	10M	1B
1	0.249s	0.25s	0.273s	0.701s	10.946s	Absolutely huge
2	0.265s	0.265s	0.273s	0.457s	4.485s	Ridiculously big
5	0.298s	0.296s	0.301s	0.380s	1.645s	Big
10	0.370s	0.372s	0.377s	0.417s	1.023s	289.819s
100	3.721s	3.766s	3.703s	3.678s	4.072s	42.161s

the numbers are averaged over 10 consecutive runs of the program.

Note: 100 processes perform worse due to the fact that for N < 1B the communication between the processes is more expensive than the computation.

These measurements were taken on a Four AMD Opteron 6272 (2.1 GHz) (64 cores), with 256GB RAM and Cent OS 7 in a virtual environment with 4GB RAM available and 1 CPU available.

---

Copyright 2020 Andrii Lunin.
Open source code available under MIT Licence.