求和程序 继续

时间:2022-07-02 17:33:16
在文章 "第一个多线程程序——使用pthread"中讨论了一个序列的求和程序。后来把这个程序重写了一下,用了一种并行度更高的算法,这一算法用了二叉树的算法。
用了以下的递归算法:
if right-left < N 直接求和
else
    SUM(int* A, int left, int right) =
        SUM(int* A, int left, int((left+right)/2)) + SUM(int* A, int((left+right)/2)+1, right)
我们将每一个分支计算用一个线程执行,写出以下算法:

#define SMALL 4000
struct add_arg
{
    int* data;
    int  size;
    int  left;
    int  right;
    long long* sum;
};

void *add(void* addarg)
{
    struct add_arg *arg;
    arg = (struct add_arg*)addarg;
    int i;
   
    if(arg->right-arg->left<=SMALL){
        arg->sum[0] = 0;
        for(i=arg->left;i<=arg->right;i++){
            arg->sum[0]+=arg->data[i];
    }
    }
    else{
    pthread_t thread[2];
        struct add_arg args[2];
   
        args[0].data = arg->data;
        args[0].size = arg->size;
        args[0].left = arg->left;
        args[0].right = int((arg->left+arg->right)/2);
        args[0].sum = new long long;

        args[1].data = arg->data;
        args[1].size = arg->size;
        args[1].left = args[0].right+1;
        args[1].right = arg->right;
        args[1].sum = new long long;
        for(i=0;i<2;i++){
            pthread_create(&thread[i],NULL,add,(void* )&args[i]);
            pthread_join(thread[i],NULL);
        }
       arg->sum[0] = args[0].sum[0]+args[1].sum[0];
    }
}

int main()
{
    int N = 100000000;
    int* A = new int[N];
    int i;
    for(i=0;i<N;i++){
        if(i%2==0) A[i] = i;
          else A[i] = i;
    }
    struct add_arg arg;
    arg.data = A;
    arg.size = N;
    arg.left = 0;
    arg.right = N-1;
    arg.sum = new long long;
    add((void* )&arg);
    cout<<"the sum is : "<<arg.sum[0]<<endl;  
}

我们求1-100000000的和。
我在单核处理器上针对不同的SMALL值运行了算法,得出结果如下

    SMALL      cost time(s)
    100           19.51
    1000          3.60
    10000         1.60
    100000        1.31
    1000000       1.28
    10000000      1.28
    100000000     1.28

在SMALL=100时,系统创建了2097150个线程。
不知道这一算法在多核处理器上运行怎么样,如果有人试过,希望告诉我。