how can I do parallel reduction approach to combine the partial sums in c

I have to do partial sums using parallel reduction approach in C. but I doesn't have any idea about it. So, I need guidance of Community to achieve this.

What I need to achieve: for example, computational thread, then in first reduction step add two element in array, thread 4 should wait for thread 0 done, same as thread 5 has to wait for thread 1 done, thread 6 waits for thread 2 & thread 7 should waits for thread 3 done .

now in second step, , thread 6 waits for thread 4 finished, and thread 7 waits for thread 5 finished. , thread 6 waits for thread 4 finished, and thread 7 waits for thread 5 finished.

In the third step, thread 7 waits for thread 6 done. then need to print whole array

Please help me, give me a guidance to achieve this one.

I'm confused about how to manage computing thread a given thread should wait. 2^r-i, where r = log(m).

There are at least two easy ways to do that:

• save all thread-ids in a global pthread_t ptid[N]; array.
• save all thread-ids in a local pthread_t ptid[N]; array, and pass the address of that array into each thread via the thread argument.

Example pseudo-code for the latter (error handling omitted for clarity):

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;
}