How to synchronize child threads-CodePudding

I'm currently creating an algorithm for solving the 0-1 knapsack problem using dynamic programming with multiple threads. My approach is to solve the n by capacity dynamic programming table by dividing it into 4 n by capacity / 4 parts which will be solved by 4 threads. Because of the knapsack having a dependency on the upper row, all the 4 threads need to be solving the same row every time. They must wait for all the threads to finish their parts on the current row before proceeding to the next row.

Here is my code:

int knapsackParallel(char *values, char *weights, int N, int capacity) {
  for (int j = 0; j < 4; j  ) {
    arguments[j].cpuNum = j;

    pthread_create(&tid[j], NULL, solveRow, (void *) &arguments[j]);

    pthread_setaffinity_np(tid[j], sizeof(cpu_set_t), &cpusets[j]);
  }

  for (int j = 0; j < 4; j  ) {
    pthread_join(tid[j], NULL);
  }
}

Here is the code of each thread that needs synchronization:

void *solveRow(void *arguments) {
  int cpuNum = ((args *) arguments)->cpuNum;
  int initial = ((args *) arguments)->cpuNum * (capacity / p);
  int limit = cpuNum == p - 1 ? capacity   1 : initial   (capacity / p);

  for (int i = 0; i < N   1; i  ) {
    for (int j = initial; j < limit; j  ) {
      // for the top and left edges, initialize to 0
      if (i == 0 || j == 0)
        table[i][j] = 0;
      // find the max between putting the value in the knapsack or not
      else if (weights[i] <= j)
        table[i][j] = fmax(values[i]   table[i - 1][j - weights[i]], table[i - 1][j]);
      // copy the value in the top of the cell
      else
        table[i][j] = table[i - 1][j];
    }

    // insert code here to wait for all the threads to finish their current iteration
    // before proceeding to the next iteration
  }

What I have tried so far:

Using multiple semaphores:

sem_post(&locks[cpuNum]);
sem_post(&locks[cpuNum]);
sem_post(&locks[cpuNum]);

for (int j = 0; j < p; j  ) {
  if (j == cpuNum) continue;
  sem_wait(&locks[j]);
}
printf("thread %d done\n", cpuNum);

Using pthread_cond_wait:

locks[cpuNum] = 1;

if (locks[0] && locks[1] && locks[2] && locks[3]) {
  pthread_cond_broadcast(&full);
}
else {
  pthread_cond_wait(&full, &lock);
}
locks[cpuNum] = 0;

Using futex:

locks[cpuNum] = 1;

futex_wait(&locks[0], 0);
futex_wait(&locks[1], 0);
futex_wait(&locks[2], 0);
futex_wait(&locks[3], 0);

locks[cpuNum] = 0;

CodePudding user response：

This sounds like a job for posix barriers:

The problem seems to be that you are not calling