我一直在尝试做一些关于多线程的研究,一个我用c++写的质数生成器,我发现我想做的是所谓的"并行处理"。在过去的45分钟里,我一直在研究这个问题,但我似乎就是想不明白。
我想这样做的代码大约有95行,这太长了,不能在这里发布,但这是基本的概念:
unsigned long long i, total;
for(i;true;i++){
total = total + i;
cout << "Your new total is " << total << endl;
}
是否有办法我可以流这两个处理器,使他们一起工作,而不是竞争?如果是的话,我该如何编码呢?我对c++有点熟悉,但还有很多我不知道的,所以一个深入的答案将是非常感谢的。
EDIT:第一次算法类型错误。我想就是这样了。
EDIT 2:由于很多答案都说这取决于我的算法,我将只发布我的代码,因为它只有95行。
/*Generic GPL stuff, coded by me */
#include <iostream>
#include <list>
#include <fstream>
using namespace std;
int main(){
//Declare some variables and what not.
unsigned long long count = 0, misc = 0, length = 0, limit = 0;
list <long long> primes;
ifstream inFile;
ofstream outFile;
cout << "Initializing starting values based on your existing file of generated prime numbers.n";
//Now let's get our starting values;
inFile.open("/home/user/Desktop/primes.txt");
//First, we need to find the prime generator thus far
for(unsigned long long x=0;inFile.good();x++){
inFile >> count;
if(!(bool)(x%100000000) && x!=0){
misc = x/100000000;
cout << misc << "00000000 primes read so far...n";
}
}
inFile.close();
cout << "Highest generated prime found.n";
//Now, as much as I hate to say it, we need to parse part of the file again now that we have the largest prime.
inFile.open("/media/ssd/primes_src.txt");
for(length; limit < count; length++){
inFile >> misc;
}
inFile.close();
limit = misc * misc;
cout << "Initialization complete. Now generating primes.n";
//Loop time
l:
//We're just going to flat-out skip even numbers
count++;
count++;
//This checks to see if the number it's trying to test is beyond the current limit of accuracy.
if(count >= limit){
// Now if we are, we have 1 more possible prime factor
length++;
inFile.open("/media/ssd/primes_src.txt");
for(unsigned long long x=0; x < length; x++){
inFile >> misc;
}
inFile.close();
limit = misc * misc;
}
inFile.open("/media/ssd/primes_src.txt");
inFile >> misc; //We don't care about 2
for(unsigned long long x=1; x < length; x++){
inFile >> misc;
if(!(bool)(count%misc)){
inFile.close();
goto l;
}
}
inFile.close();
outFile.open("/home/user/Desktop/primes.txt", ios::out | ios::app);
//Now if we haven't been "goto"d, we add it to the file.
outFile << count << endl;
outFile.close();
goto l;
return 0;
}
/home/user/Desktop/prime .txt是我所有生成的质数文件。
/media/ssd/primes_src.txt是我的文件,里面包含了2^32 + 1以内的质数
我不知道你的算法是否适合这种方法,但我做并行工作的一种方法是创建多个线程,这些线程都完全独立运行,除了一个点,它更新"下一个候选人"(我正在计算奇怪的数字,所以我的更新是一个i = __sync_fetch_and_add(¤t, 2);
-电流是"到目前为止的数字进程")。__sync_fetch_and_add()是c++中的标准函数,但是Microsoft编译器也有同样的功能,称为InterLockedAdd()
。
当我运行我的"基准测试"时,我只比我的机器上的4核提高了400%(100% = 1核)。
我使用了普通的pthread_create(),当我达到给定输入范围内的"最大值"时,每个线程结束。
如承诺:一个简单的质数查找器:
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <pthread.h>
using namespace std;
static int current;
static int max_value = 7780;
static void *find_prime(void *)
{
for(;;)
{
int i = __sync_fetch_and_add(¤t, 2);
bool prime = true;
if (i > max_value)
{
pthread_exit(NULL);
}
for(int j = 2; j < i && prime; j++)
{
if (!(i % j))
{
prime = false;
}
}
if (prime)
{
cout << i << " " << flush;
}
}
}
int main(int argc, char **argv)
{
int start = 3;
int threads = 1;
pthread_t *thread_id;
for(int i = 1; i < argc; i++)
{
if (strcmp(argv[i], "-t") == 0 && argc > i+1)
{
i++;
threads = strtol(argv[i], NULL, 0);
}
if (strcmp(argv[i], "-e") == 0 && argc > i+1)
{
i++;
max_value = strtol(argv[i], NULL, 0);
}
}
current = start;
cout << "1 2 " << flush;
thread_id = new pthread_t[threads-1];
for(int i = 0; i < threads; i++)
{
int rc = pthread_create(&thread_id[i], NULL, find_prime, NULL);
if (rc != 0)
{
cerr << "Huh? Pthread couldn't be created. rc=" << rc << endl;
}
}
for(int i = 0; i < threads; i++)
{
pthread_join(thread_id[i], NULL);
}
cout << endl;
}
注释:主启动"线程"线程数(由-t num
在命令行上指定-也有一个-e num
定义了"最大")。每个线程使用__sync_fetch_and_add()函数"选择"一个数字。线程检查它是否是素数,然后迭代j来尝试除这个数。如果这个数字是质数,它就被打印出来,否则就选择下一个数字。
如果你想,而不是打印数字[和给定足够大的数字,你可能会遇到问题,从线程内调用cout <<
],你可以使用数组,并使用int my_index = __sync_fetch_and_add(&index, 1);然后用它来存储到数组中。
当然,如果每个循环不能完全独立地运行,那么这个方法就不起作用了——然后事情变得更加复杂。
编辑:请注意,这段代码中缺少许多有用的错误检查。如果你给零线程,它不会做任何事情,如果你给一个负的结束值,谁知道呢,等等。
$ time ./prime -t 1 -e 100000>/dev/null
real 0m5.574s
user 0m5.553s
sys 0m0.009s
and:time ./prime -t 4 -e 100000>/dev/null
real 0m1.762s
user 0m5.572s
sys 0m0.010s
正如你所看到的,它几乎快了4倍。
假设i = iterator
,所显示的代码这样做,即total
的值不依赖于for循环的先前迭代。你的算法似乎很容易并行化。
#pragma omp parallel for
for(...)
注意,这个答案假设你的算法的每次迭代都不依赖于前一次(否则你将不得不输入一些代码来防止竞争条件)。
EDIT:你的算法现在不容易并行化。一些笔记:
- 如果你可以把计算分成独立的块,那么算法很容易并行化(每个块一个线程)
- 如果算法创建新数据而不修改旧数据,并且不读取新数据的状态,则它也是可并行的 如果你必须拥有迭代
n - 1
的结果才能执行迭代n
,那么你就完蛋了。这里最好的选择是拿一张纸和一支铅笔,并在数学上(或逻辑上)尝试以不同的方式格式化你的算法(即,改变你的算法!)。并行化的唯一方法是跟踪N个总数,并在循环后将它们加在一起。或者,如果加法表示一些更复杂的函数,请尝试使用互斥锁来访问共享变量。这很可能会影响性能…
您可以查看使用openMP计算素数的代码