在文章
"第一个多线程程序——使用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个线程。
不知道这一算法在多核处理器上运行怎么样,如果有人试过,希望告诉我。