c - How to parallelize my n queen puzzle with Pthreads? -

i have following pthreads code n-queen puzzle. compiles successfully, wrong answer. whatever value type answer zero. guess have kind of logic error in code. guess problem happens somewhere in backtracking/recursion part. if suggest me solution, glad.

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <pthread.h> #include <assert.h>  int nthreads, size;  int *hist; int count = 0;  int solve(int col, int tid) {     int start = tid * size/nthreads;     int end = (tid+1) * (size/nthreads) - 1;     int i, j;     if (col == size)      {         count++;     }      #define attack(i, j) (hist[j] == || abs(hist[j] - i) == col - j)     (i = start; <= end; i++) {         (j = 0; j < col && !attack(i, j); j++);         if (j < col) continue;          hist[col] = i;         solve(col + 1, tid);     }      return count; }  void *worker(void *arg) {     int tid = (int)arg;     solve(0, tid); }  int main(int argc, char* argv[]) {     pthread_t* threads;     int rc, i;      // checking whether user has provided needed arguments     if(argc != 3)     {         printf("usage: %s <number_of_queens> <number_of_threads>\n", argv[0]);         exit(1);     }       // passing provided arguments size , nthreads      // variable, initializing matrices, , allocating space      // threads     size = atoi(argv[1]);     nthreads = atoi(argv[2]);     threads = (pthread_t*)malloc(nthreads * sizeof(pthread_t));     hist = (int*)malloc(size * sizeof(int));      // declaring needed variables calculating running time     struct timespec begin, end;     double time_spent;      // starting run time     clock_gettime(clock_monotonic, &begin);      for(i = 0; < nthreads; i++) {         rc = pthread_create(&threads[i], null, worker, (void *)i);         assert(rc == 0); // checking whether thread creation successful     }      for(i = 0; < nthreads; i++) {         rc = pthread_join(threads[i], null);         assert(rc == 0); // checking whether thread join successful     }      // ending run time     clock_gettime(clock_monotonic, &end);      // calculating time spent during calculation , printing     time_spent = end.tv_sec - begin.tv_sec;     time_spent += (end.tv_nsec - begin.tv_nsec) / 1000000000.0;     printf("elapsed time: %.2lf seconds.\n", time_spent);      printf("\nnumber of solutions: %d\n", count);      free(hist);     return 0;  } 

well there quite mistakes, first 1 caused 0. note program works fine if 1 thread used.

1. inside solve split work per thread computing start , end, should not done once col > 0, because in recursion have go on rows again.

2. you share variables hist , count amongst threads without protecting them in critical section, using example semaphores. in case can without semaphores giving each thread own version of these variables , accumulating count entries in join of threads. sharing count cause problems low probability, sharing nevertheless wrong because can not assume count++ atomic read-modify-write operation. sharing hist algorithmically wrong.

3. if nthreads doesn't divide size exactly, calculation of last end not yield size-1.

4. if nthreads > size start , end -1.

5. as practice should check if malloc (and friends) don't return null means ran out of memory. respectful user of program if check command line arguments correctness.

if solve these mistakes 92 every time run on regular sized chess board regardless number of threads. luck.

as code examples (asked below), i'm bit bit reluctant, here go. have made many more changes, stuck closest code possible:

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <pthread.h> #include <assert.h>  int nthreads, size; int ** hist = null; int * count = null;  static void oof(void) {     fprintf(stderr, "out of memory.\n");     exit(1); }  void solve(int col, int tid) {     /* if nthreads not divide size,      * not cover rows.      * make sure size >= nthreads, otherwise start 0.      */     int start = (col > 0) ? 0 : tid * (size/nthreads);     int end = (col > 0 || tid == nthreads-1) ? size-1 : (tid+1) * (size/nthreads) - 1;     int i, j;     if (col == size)     {         count[tid]++;     }      #define attack(i, j) (hist[tid][j] == || abs(hist[tid][j] - i) == col - j)     (i = start; <= end; i++) {         (j = 0; j < col && !attack(i, j); j++);         if (j < col) continue;          hist[tid][col] = i;         solve(col + 1, tid);     } }  void *worker(void *arg) {     int tid = (int)arg;     count[tid] = 0;     solve(0, tid); }   int main(int argc, char* argv[]) {     pthread_t* threads;     int rc, i, j, sum;      // checking whether user has provided needed arguments     if(argc != 3)     {         printf("usage: %s <number_of_queens> <number_of_threads>\n", argv[0]);         exit(1);     }       // passing provided arguments size , nthreads      // variable, initializing matrices, , allocating space      // threads     size = atoi(argv[1]);     nthreads = atoi(argv[2]);     threads = (pthread_t*)malloc(nthreads * sizeof(pthread_t));     hist = malloc(size * sizeof(int*));     count = malloc(size * sizeof(int));     if (hist == null || count == null) oof();     (i = 0; < size; i++)     {         hist[i] = malloc(size * sizeof(int));         if (hist[i] == null) oof();         (j = 0; j < size; j++)         {             hist[i][j] = 0;         }     }      // declaring needed variables calculating running time     struct timespec begin, end;     double time_spent;      // starting run time     clock_gettime(clock_monotonic, &begin);      for(i = 0; < nthreads; i++) {         rc = pthread_create(&threads[i], null, worker, (void *)i);         assert(rc == 0); // checking whether thread creation successful     }      sum = 0;     for(i = 0; < nthreads; i++) {         rc = pthread_join(threads[i], null);         assert(rc == 0); // checking whether thread join successful         sum += count[i];     }       // ending run time     clock_gettime(clock_monotonic, &end);      // calculating time spent during calculation , printing     time_spent = end.tv_sec - begin.tv_sec;     time_spent += (end.tv_nsec - begin.tv_nsec) / 1000000000.0;     printf("elapsed time: %.2lf seconds.\n", time_spent);      printf("\nnumber of solutions: %d\n", sum);      (i = 0; < size; i++)     {         free(hist[i]);     }     free(hist); free(count);     return 0;  }