我有:
input1: n to generate primes up to
input2: no of threads to generate primes
我实现了这一点,它的工作,但的问题是,每个线程生成自己的素数列表[2, n]
。
但是我希望两个线程都处理生成素数的相同任务,彼此切换,而不是独立地。如何将n
划分为线程数?
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void *BusyWork(void *threadid)
{
long tid;
tid = (long)threadid;
printf("Hello World! It's me, thread # %ldn", tid);
double s,d;
int n,i,c,k,p,cs,nsqrt;
printf( "Input an integer n > 1 to generate primes upto this n: " ); // prompt
scanf("%d",&n);
printf( "Entered integer: %dn",n);
int array[n];
for(i=0;i<n;i++)
array[i]=0;
s=sqrt(n);
d=floor(s);
nsqrt = (int) d;
for ( c= 2; c <= nsqrt; c++ )// note here < is not working <= is working here.
{
if(array[c]==0)
{
cs = c*c;
k=0;
for(p=cs; p<n; p=(cs+k*c))
{
k++;
array[p] = 1;
}//for
}//if
}//for
for ( i = 2; i < n; i++ )
{
if (array[i]==0)
{
printf("%5d",i);
}//if
}// for
printf("n");
printf("Above prime numbers are generated from me i.e. thread # %ld GOOD BYE!!! n ", tid);
pthread_exit((void*) threadid);
}
int main (int argc, char *argv[])
{
//////// time cal ///////////////////
struct timespec start, finish;
double elapsed;
clock_gettime(CLOCK_MONOTONIC, &start);
/////////////////////////////////////
int NUM_THREADS;
printf("Please Input Total Number of Threads you want to make:- ");
scanf("%d",&NUM_THREADS);
pthread_t thread[NUM_THREADS];
pthread_attr_t attr;
int rc;
long t;
void *status;
/* Initialize and set thread detached attribute */
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
for(t=0; t<NUM_THREADS; t++) {
printf("Main: creating thread %ldn", t);
rc = pthread_create(&thread[t], &attr, BusyWork, (void *)t);
if (rc) {
printf("ERROR; return code from pthread_create() is %dn", rc);
exit(-1);
}
}
/* Free attribute and wait for the other threads */
pthread_attr_destroy(&attr);
for(t=0; t<NUM_THREADS; t++) {
rc = pthread_join(thread[t], &status);
if (rc) {
printf("ERROR; return code from pthread_join() is %dn", rc);
exit(-1);
}
printf("Main: completed join with thread %ld having a status of %ldn",t, (long)status);
}
printf("Main: program completed. Exiting.n");
////////////// time end ////////////////////////
clock_gettime(CLOCK_MONOTONIC, &finish);
elapsed = (finish.tv_sec - start.tv_sec);
elapsed += (finish.tv_nsec - start.tv_nsec) / 1000000000.0;
printf("Total time spent by the main: %e n", elapsed);
//////////////////////////////////////////////////////////
pthread_exit(NULL);
}
你想要的远不是微不足道的。但这里有一个想法,为两个线程进行思考,研究和测试。
要做到这一点,您需要在两个线程之间"分割"作业。例如,让第一个线程查找[ 2, k ]
之间的素数,让第二个线程查找[ k+1, x ]
之间的素数。
这是不重要的部分。问题来了——如何找到x
?(k
是容易的- x / 2
).
N ~~ x / ln(x)
其中N
为小于x的素数个数。
好吧,我不是数学家,我现在不能给你答案,但应该有一个方法,用N
找到x
。
注意,这对于大的数字很有效。
所以,有了这个,一旦你找到x,你就可以在两个线程之间分割任务了。
正如你所看到的,这真的远非微不足道,没有确切的(精确的)方法来找到x
(N
)。
当然,另一种简单的方法(更简单,但不是那么好)是知道N
的范围,然后把它分成两个区间。或者,找到前100个质数也不是什么大事。但是找到前1000个是另一回事。在这种情况下,您可以为每个+500质数启动额外的线程,例如。
另一个想法是做一个寻找N
-素数近似值的研究。这可能会有帮助:有没有办法找到第n个素数的近似值?
抱歉,如果我误解了你的帖子,但我怀疑你误解了什么是多线程。您的代码和最后一个问题表明,您认为启动多个相同的线程意味着它们以某种方式自动将任务分配给它们自己。这是根本不正确的。我们都希望如此,但事实并非如此。
有几种方法。有一种"手动"方法,在这种方法中,您可以利用问题中的并行性,并为每个位编写一个线程(或者使用不同的参数多次启动同一个线程)。无论哪种方式,线程+数据都不相同)。然后可以并行运行这些线程。从本质上讲,这就是Kirol Kirov建议的方法。
对于长循环的数学问题,另一个可以很好地工作的方法是使用一个编译器,它可以在运行时自动将循环分解为单独的线程。这意味着您编写普通的单线程代码,并告诉编译器在它可以确定安全的地方生成线程。节省您大量的工作,并在适当的情况下产生有效的结果。Sun C编译器可以在Solaris上做到这一点,Intel的编译器也可以做到(可能只在Windows上)。对最新、最伟大的技术进行一些研究也许是值得的。然而,这并不能教会你任何关于多线程编程的知识。
另一种方法是使用像openMPI这样的东西,(我认为)允许你在for循环之前放#pragma语句,说你想并行执行平铺循环。有点像Intel和Sun编译器的手动版本