c - 在 C 中使用 pthreads 在一维数组中查找最大值的有效方法

Question

我想在 C 中使用 pthreads 找到一维数组中的最大值。

我有这样的代码:

void* findmax(void* arg){
  double temp_max;
  astruct *td=(astruct *)arg;

  P[td->idx]=d*P[td->idx]+sth;
  temp_max= fabs(P[td->idx]-P_old[td->idx]);

   pthread_mutex_lock(&lockP);
    if(max<temp_max){   
       max=temp_max;
    }   
    pthread_mutex_unlock(&lockP);
}

main(){
...
  //give to each thread an element of P 
  TD[i].idx;
....
  for(i=0;i<thread_number;i++){
   pthread_create(&threads[i],NULL,&findmax,(void*)&TD[i]);
  }
...
  /* when the above threads are done give them new element and start the
   loop again till the end of array P */

}

所以问题是互斥量是找到正确结果所必需的，但是它们使程序变慢了很多，以至于最终串行代码比这个实现更快。

有没有比寻找最大值的串行简单代码更快的使用 pthreads 解决这个问题的有效方法？

Answer 1

使用分而治之的方法。

1. 从长度为N 的数组A 开始。 A(i) 是数组 A 的第 i 个元素。 A(i,j) 是 A 的子集，即第 i 到 (j-1) 个元素。
2. 将数字N 除以机器上可用的内核数C。这个数字是W，工作量大小
3. 定义一个函数 maxOnSubset(i,j)，它返回一个与 A 的元素类型相同的值。该函数在 A(i,j) 中找到最大值。如果 j 大于 A 的长度，则函数将 j 设置为 A 的长度。<
4. 启动编号为 [0,C) 的 C 线程。与每个线程关联的编号是c。每个线程负责调用函数 maxOnSubset(c*W,(c+1)*W) 并存储值。您可以使用信号量来了解每个线程何时计算出该值。这允许每个线程独立于任何其他线程进行处理。
5. 等待每个线程完成并将存储的值收集到第二个数组 B 中。数组 B 的长度为 C。
6. 在B 中找到最大值。 B的最大值也是A的最大值。