我有一个用于埃拉斯托尼筛法的 C 语言 BSP 实现,请参阅下面的代码。
当使用 ./bspsieve 2 100 执行时,它会给出以下输出:
“过程 0 花费了 0.000045 秒(共 2 秒)。 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,"
对于 ./bspsieve 1 100 它给出相同的结果,即:
“./bspsieve 1 100
1 中的 proc 0 花费了 0.000022 秒。
23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,"
对于 ./bspsieve 8 100(因此使用 8 个处理器),它会出现段错误。 IE “./bspsieve 8 100 过程 0(共 8 个)花费了 0.000146 秒。 段错误(核心转储)" 这意味着我认为我的界限不太好?
找不到第一个素数!我找不到我的错(对C真的没有经验)。除此之外,你们还可以建议对我的代码进行其他改进吗?该算法不需要很快,但在可理解性和可读性方面的任何改进都是值得欢迎的。
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <mcbsp.h>
/*
Note: To compile, this file has to be in the same folder as mcbsp.h and you need the 2 following commands:
gcc -Iinclude/ -pthread -c -o bspsieve.o bspsieve.c
gcc -o bspsieve bspsieve.o lib/libmcbsp1.1.0.a -lpthread -lrt
*/
int procs;
int upperbound;
int *primes;
//SPMD function
void bspSieve(){
bsp_begin(procs);
int p = bsp_nprocs(); // p = number of procs obtained
int s = bsp_pid(); // s = proc number
float blocksize; // block size to be used, note last proc has a different size!
if( s != p-1){
blocksize = ceil(upperbound/p);
} else {
blocksize = upperbound - (p-1)*ceil(upperbound/p);
}
// Initialize start time and end time, set start time to now.
double start_time,end_time;
start_time = bsp_time();
// Create vector that has block of candidates
int *blockvector;
blockvector = (int *)malloc(blocksize*sizeof(int));
int q;
for(q = 0; q<blocksize; q++){
//List contains the integers from s*blocksize till blocksize + s*blocksize
blockvector[q] = q + s*blocksize;
}
//We neglect the first 2 'primes' in processor 0.
if(s == 0){
blockvector[0] = 0;
blockvector[1] = 0;
}
// We are using the block distribution. We assume that n is large enough to
// assure that n/p is larger than sqrt(n). This means that we will always find the
// sieving prime in the first block, and so have to broadcast from the first
// processor to the others.
long sieving_prime;
int i;
bsp_push_reg( &sieving_prime,sizeof(long) );
bsp_sync();
for(i = 2; i * i < upperbound; i++) {
//Part 1: if first processor, get the newest sieving prime, broadcast. Search for newest prime starting from i.
if(s == 0){
int findPrimeNb;
for(findPrimeNb = i; findPrimeNb < blocksize; findPrimeNb++) {
if( blockvector[findPrimeNb] != 0) {
sieving_prime = blockvector[findPrimeNb];
//broadcast
int procNb;
for(procNb = 0; procNb < p; ++procNb){
bsp_put(procNb, &sieving_prime,&sieving_prime,0,sizeof(long));
}
break;
}
}
}
bsp_sync();
//Part 2: Sieve using the sieving prime
int sievingNb;
for(sievingNb = 0; sievingNb < blocksize; sievingNb++){
//check if element is multiple of sieving prime, if so, pcross out (put to zero)
if( blockvector[sievingNb] % sieving_prime == 0){
blockvector[sievingNb] = 0;
}
}
}
//part 3: get local primes to central area
int transferNb;
long transferPrime;
for(transferNb = 0; transferNb < blocksize; transferNb++){
transferPrime = blockvector[transferNb];
primes[transferPrime] = transferPrime;
}
// take the end time.
end_time = bsp_time();
//Print amount of taken time, only processor 0 has to do this.
if( s == 0 ){
printf("It took : %.6lf seconds for proc %d out of %d. \n", end_time-start_time, bsp_pid(), bsp_nprocs());
fflush(stdout);
}
bsp_pop_reg(&sieving_prime);
bsp_end();
}
int main(int argc, char **argv){
if(argc != 3) {
printf( "Usage: %s <proc count> <upper bound> <n", argv[ 0 ] );
exit(1);
}
//retrieve parameters
procs = atoi( argv[ 1 ] );
upperbound = atoi( argv[ 2 ] );
primes = (int *)malloc(upperbound*sizeof(int));
// init and call parallel part
bsp_init(bspSieve, argc, argv);
bspSieve();
//Print all non zeros of candidates, these are the primes.
// Primes only go to p*p <= n
int i;
for(i = 0; i < upperbound; i++) {
if(primes[i] > 0) {
printf("%d, ",primes[i]);
fflush(stdout);
}
}
return 0;
}
最佳答案
问题可能来自
blockvector[q] = q + s*blocksize;
只要所有进程上的blocksize
等于ceil(upperbound/p)
,就没有问题。由于 1 和 2 是 100 的约数,因此您的程序运行良好。
正如您在代码中所写,情况并非总是如此......调用 ./bspsieve 8 100
时,最后一个进程的情况并非如此。 blockvector中有些值超过100,写入prime
数组时很可能出现段错误。
纠正此行为的方法是:
blockvector[q] = q + s*ceil(upperbound/p);
(存储ceil(...)
以运行得更快。)
在使用 prime
数组之前将其清零可能会更好。
我没有检查它是否有效...尝试一下!
再见,
弗朗西斯
关于c - 埃拉托斯特尼筛法 BSP C 实现未找到所有素数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20881956/