C++算法循环-并行处理?

3

我一直在尝试研究如何将我用C++编写的质数生成器多线程化,我发现我想做的就是“并行处理”。我已经研究了大约45分钟,但似乎无法弄清楚。

我想要进行此操作的代码大约有95行,这里不方便贴出,但基本概念如下:

unsigned long long i, total;

for(i;true;i++){
    total = total + i;
    cout << "Your new total is " << total << endl;
}

有没有办法将它流式传输到两个处理器,让它们一起工作而不是竞争?如果可以的话,我该如何编码呢?我对C++有一定的了解,但还有很多我不知道的东西,所以非常感谢详细的答案。
编辑:第一次使用了错误类型的算法。我认为这就是它。
编辑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/primes.txt 是保存所有生成的质数的文件。
/media/ssd/primes_src.txt 是保存所有小于 2^32 的质数加上一个好的测量值的文件。


1
该任务通常不能并行化,因为每个总和都依赖于前一个循环,使得它基本上是一个顺序任务...但根据您实际的算法,可能有办法进行并行化。 - Ronny Brendel
4个回答

1
假设i = 迭代器,所示代码的作用是total的值不依赖于for循环的先前迭代。您的算法似乎可以轻松并行化。
最简单的方法是在编译器选项中启用OpenMP,然后在for循环之前添加以下代码:
#pragma omp parallel for
for(...)

请注意,此答案假定您的算法的每次迭代都不依赖于前一次迭代(否则您将需要输入一些代码以防止竞争条件)。
编辑:您的算法现在不容易并行化。以下是一些注意事项:
  • 如果您可以将计算分成独立的块,则算法很容易并行化(每个块一个线程)
  • 如果算法创建新数据而不修改旧数据,并且不读取新数据的状态,则也可以并行化
  • 如果您必须获得迭代n-1的结果才能进行迭代n,则您将陷入困境。最好的选择是拿起纸和笔,在数学上(或逻辑上)尝试以不同的方式格式化您的算法(即更改您的算法!)。

抱歉,这不是我想问的问题。给我一分钟重新写一下。它应该依赖于它之前的迭代。 - user1846065
我相信这是我试图创建的模式更准确的再现。对此很抱歉。 - user1846065

1

我不知道你的算法是否适用于这种方法,但我做并行工作的一种方式是创建多个线程,它们完全独立运行,除了一个点更新“下一个候选项”(我正在计算奇怪的数字,所以我的更新是i = __sync_fetch_and_add(&current, 2); - current 是“到目前为止处理的数字”。__sync_fetch_and_add()是g++中的标准函数,但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(&current, 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指定(还有一个定义“max”的-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

并且:time ./prime -t 4 -e 100000 > /dev/null

real    0m1.762s
user    0m5.572s
sys     0m0.010s

正如您所看到的,速度快了4倍。


你能解释一下 __sync_fetch_and_add() 是如何工作的,以及我如何将其放入我的代码中,或者指导我去哪里可以展示它吗?我使用的是 g++。 - user1846065
好的,我会编辑代码来展示一个简单的“寻找质数”应用程序 [朴素方法!],以便让您明白我的意思。 - Mats Petersson
编辑如下,请查收:希望对您有所帮助。 - Mats Petersson
非常感谢。我稍微试一下看看是否正好符合我的需求。一旦确认无误,我会将其接受为答案。 - user1846065

0

唯一的并行化方法是跟踪N个总数,并在循环后将它们相加。或者,如果加法表示某些更复杂的函数,请尝试使用互斥锁来访问共享变量。但这很可能会影响性能...


0
你可以查看这个代码,它使用openMP计算质数。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接