我怎样才能使用并行归约方法来组合 c 中的部分和

Question

我必须在 C 中使用并行约简方法进行部分求和，但我对此一无所知。所以，我需要社区的指导来实现这一点。

我需要实现的目标： 例如，计算线程，然后在第一个缩减步骤中在数组中添加两个元素，线程 4 应该等待线程 0 完成，线程 5 必须等待线程 1 完成，线程 6 等待对于线程 2 和线程 7 应该等待线程 3 完成。

现在在第二步，线程 6 等待线程 4 完成，线程 7 等待线程 5 完成。 ，线程 6 等待线程 4 完成，线程 7 等待线程 5 完成。

第三步，线程7等待线程6完成。然后需要打印整个数组

请帮助我，给我一个实现这一目标的指导。

Answer 1

Intel oneTBB 库包含“parallel_reduce”算法，可直接用于此类任务。 https://spec.oneapi.io/versions/latest/elements/oneTBB/source/algorithms/functions/parallel_reduce_func.html

oneTBB只支持C++，如果只能用C的话，可以考虑改用OpenMP。但它也需要工具链支持。

https://www.intel.com/content/www/us/en/develop/documentation/advisor-user-guide/top/model-threading-designs/add-parallelism-to-your-program/replace-注释-with-openmp-code/openmp-reduction-operations.html

Answer 2

我对如何管理给定线程应该等待的计算线程感到困惑。

2^r-i

，其中

r = log(m)

.

至少有两种简单的方法可以做到这一点：

• 将所有线程 ID 保存在全局

  pthread_t ptid[N];

  数组中。
• 将所有线程 ID 保存在本地

  pthread_t ptid[N];

  数组中，并通过线程参数将该数组的地址传递给每个线程。

后者的示例伪代码（为清楚起见省略了错误处理）：

struct Arg {
  pthread_t *ptid;  // Address of ptid[N].
  int idx;          // Index of this thread.
};

void *partial_sum(void *p)
{
  struct Arg *arg = (struct Arg *)p;

  int sum = 0;
  ... // Compute my portion of the partial sum.
  
  int other_thread_idx = ...;  // Compute index of the other thread
                               // this thread should join, -1 if none.
  if (other_thread_idx >= 0) {
    int other_sum;

    // Get the result from other thread.
    pthread_join(arg->ptid[other_thread_idx], (void*) &other_sum);
    printf("Thread %d joined thread %d which returned sum %d\n",
           arg->idx, other_thread_idx, other_sum);
    sum += other_sum;
  }
  printf("Thread %d, sum: %d\n", arg->idx, sum);
  return (void*) sum;
}

int main()
{
  struct Arg args[N];
  pthread_t ptid[N];

  for (int i = 0; i < N; ++i) {
    struct Arg* arg = &args[i];
    arg->idx = i;
    arg->ptid = &ptid[0];
    pthread_create(&ptid[i], NULL, partial_sum, arg);
  }

  // Get the final result.
  int sum;

  // Note: joining only the last thread -- all others have been joined
  // already.
  pthread_join(ptid[N - 1], (void*) &sum);

  printf("Sum: %d\n", sum);
  return 0;
}