Справочная информация: мне было поручено написать программу MPI на C, которая вычисляет все простые числа до заданного числа. Эта программа работает правильно.
Я компилирую программу, используя openmpi и оптимизацию -O3.
При запуске его на моем персональном компьютере (Ubuntu 11.10 x64) с использованием 1 процесса я получаю ожидаемые результаты (~ 13 секунд для всех простых чисел до 4E9). То же самое верно для машин моего отдела CS.
Однако, когда я запускаю его на Carver в NERSC, время резко скачет (~ 61 секунда на 1 процесс).
Я пытался использовать компиляторы openmpi и intel ... без разницы. Я заставил его запускаться с нужным временем один раз, но я не помню, что (если вообще что-то) я делал по-другому, и в моем коде была небольшая ошибка индекса, которую я с тех пор исправил (не связанный с выполнением вычислений, поэтому время было точным).
Я старался быть максимально ясным; если у вас есть еще вопросы, я буду рад ответить. Спасибо!
#include <stdio.h>
#include <mpi.h>
#include <stdlib.h>
#include <math.h>
#define MAX(x,y) ((x)>(y) ? (x) : (y) )
#define MIN(x,y) ((x)>(y) ? (y) : (x) )
#define A(i,j) A[(i)*M+j]
#define b(i) b[i]
#define c(i) c[i]
long* preamble(long N,char* mark){
N = sqrt(N)+1;
long size;
long curr, index;
long i, j,n;
long count;
long* primes;
//Pierre Dusart proven upper bound for number of primes up to N
//found at http://primes.utm.edu/howmany.shtml
size = (N/log(N))*(1+(1.2762/log(N)))*sizeof(long);
primes = (long *)malloc(size);
if(N%2)
n=N/2 - 2;
else
n=(N-1)/2 -1;
index = 0;
curr = 3;
while (curr*curr<=N) {
for (i=(curr*curr-3)/2; i<=n; i+=curr){
mark[i]=1;
}
while (mark[++index]) ;
curr = index*2+3;
}
/*number of primes*/
count = 0;
for(i = 0; i <=n; i+=1){
if(mark[i] == 0) {
primes[++count]=i*2+3;
}
}
primes[0]=count;
return primes;
}
long FMIB(long p, long b){
if(b%p==0 && b!=p) return b;
long i = b + p - b % p;
if(i%2){return i;}else{return i+p;}
}
int main(int argc, char **argv) {
long N = 4000000000;
long BKSIZE = 500000;
char *mark;
long *primes;
long *loopprimes;
long size, offset;
long numprimes;
long i, j, n, ii, start, index;
long count, total;
double time;
if ( argc > 1 ) N = atol(argv[1]);
if ( argc > 2 ) BKSIZE = atol(argv[2]);
int id, p;
BKSIZE = (BKSIZE-3)/2 +1;
if(N%2)
n=N/2 - 2;
else
n=(N-1)/2 -1;
MPI_Init(&argc, &argv);
MPI_Comm_rank(MPI_COMM_WORLD, &id);
MPI_Comm_size(MPI_COMM_WORLD, &p);
MPI_Barrier(MPI_COMM_WORLD);
if(id==0) time = MPI_Wtime();
size = (n/p+1)*sizeof(char);
mark = (char *)malloc(size);
for (i=1; i<=n/p+1; i++){
mark[i]=0;
}
primes = preamble(N,mark);
if(id!=0){
for (i=0; i<=n/p+1; i++){
mark[i]=0;
}
}
offset = (1+n/p)*id;
numprimes=primes[0];
if(id==0){
start = (sqrt(N)-3)/2+1; //mark index to start at
}else{
start = offset;
}
//MAIN COMPUTATION - BLOCKING
for(ii=start; ii<=MIN(ii+BKSIZE,offset+n/p); ii+=BKSIZE){
for(j=0; j < numprimes; j++){
for(i=(FMIB(primes[j+1],ii*2+3)-3)/2; i<=MIN(ii+BKSIZE,offset+n/p); i+=primes[j+1]){
mark[i-offset]=1;
}
}
}
/*number of primes*/
if(id==0){
count = 1;
}else{
count = 0;
}
for(i = 0; i <= n/p && (i+offset)*2+3 <= N; i++){
if(mark[i] == 0) {
++count;
}
}
MPI_Barrier(MPI_COMM_WORLD);
MPI_Reduce(&count, &total, 1, MPI_LONG, MPI_SUM, 0, MPI_COMM_WORLD);
MPI_Barrier(MPI_COMM_WORLD);
if(id==0){
time = MPI_Wtime() - time;
printf("There are %ld primes less than %ld\n", total, N);
printf("First three primes:");
j = 1;
printf(" %d", 2);
for ( i=0 ; i <= n && j < 3; i+=1 ) {
if (mark[i]==0){
printf(" %ld", (i*2+3));
++j;
}
}
printf("\n");
}
MPI_Barrier(MPI_COMM_WORLD);
if(id == p-1){
printf("Last three primes:");
j = 0;
for (i = n-offset; i >= 0 && j < 3; i--){
if (mark[i]==0){
printf(" %ld", ((offset+i)*2+3));
j++;
}
}
if(j < 3){
printf(" %d",2);
}
printf("\n");
}
MPI_Barrier(MPI_COMM_WORLD);
if(id == 0){
printf("Elapsed time: %f seconds\n",time);
fflush(stdout);
}
MPI_Finalize();
//free(mark);
return 0;
}
Сценарий:
#!/bin/csh
#used for intel compiler
#module unload pgi openmpi
#module load intel openmpi-intel mkl
make clean
make
set x = "sieve_mpi"
set n = 4000000000
set b = 500000
foreach p ( 1 2 3 4 5 6 7 8 )
cat > ${x}${p}.pbs <<EOF
#PBS -q regular
#PBS -l nodes=1:ppn=8
#PBS -l walltime=00:01:00
#PBS -N ${x}${p}
#PBS -e err/${x}${p}.err
#PBS -o out/${x}${p}.out
#used when using intel compiler
#module unload pgi openmpi
#module load intel openmpi-intel mkl
cd \$PBS_O_WORKDIR
echo ${x}
echo ${p}
mpirun -np ${p} ${x} ${n} ${b}
EOF
qsub ${x}${p}.pbs
end
Makefile:
CC = mpicc
EXEC = pi_cyc pi_block sieve_mpi
OBJS =
H_FILE =
MATHFLAG = -lm
FLAGS = -O3
SEQFLAGS = -O3
all: $(EXEC)
pi_cyc: pi_cyc.c $(OBJS) $(H_FILE)
$(CC) $(FLAGS) -o $@ pi_cyc.c $(OBJS) $(MATHFLAG)
pi_block: pi_block.c $(OBJS) $(H_FILE)
$(CC) $(FLAGS) -o $@ pi_block.c $(OBJS) $(MATHFLAG)
sieve_mpi: sieve_mpi.c $(OBJS) $(H_FILE)
$(CC) $(FLAGS) -o $@ sieve_mpi.c $(OBJS) $(MATHFLAG)
clean:
rm -f *.o *.pgm $(OBJS) $(EXEC)