Hillis and Steele on a prefix sum multithreading assignment in C-CodePudding

I'm working on a CS assignment, where I have to use p_threads to compute an array's prefix sum. The professor told us to use the Hillis and Steele algorithm. I found some pseudocode on wikipedia (

I'm a little stuck on implementing this in real code. The way our program is supposed to work, the user passes in an array through a file or stdin, then the next 2 arguments are the size of the input array, and how many threads we need to use. So, I assume "n" in this picture is "amount of threads we need to use". Then, I'm not sure what the notation on the x's mean. Wikipedia says "In the above, the notation ... means the value of the jth element of array x in timestep i." but...what? How do I implement this "timestep"? I assumed that it meant: "do j to the i 1th power, then find that index element in array x". With that assumption, I wrote this code:

void scan(int numThreads, int* vector, pthread_t* threads){
  for(int i = 0; i < logbase(numThreads, 2); i  ){
    for(int j = 0; j < numThreads - 1; j  ){
      // create a thread here to perform parallel()
      int* args = calloc(3,sizeof(int));
        args[0] = i;
        args[1] = j;
        args[2] = *vector;
      pthread_create(&threads[j], NULL, parallel, (void*)args);
      free(args);
    }
  }
}

// each thread runs this function
void* parallel(void *arg){
    int i = ((int*)arg)[0];
    int j = ((int*)arg)[1];
    int* vector = ((int**)arg)[2];

    if(j < pow(2, i)){
      // store current element (jth element of array x to the power of i) 
      // in the jth element of array x to the power of i   1 
    vector[(int)pow(j, i 1)] = vector[(int)pow(j, i)]; // ISSUE IS HERE
    }
    else{
      // store current element plus element at j-2^i ^i in current^i 1
        vector[(int)pow(j, i 1)] = vector[(int)pow(j, i)]   vector[(int)pow(j - 
                pow(2, i), i)];
    }
    return NULL;
}

The line commented "ISSUE IS HERE" segfaults. I can step through in gdb and figure out why it's segfaulting myself, but I want to know if I'm even doing this right. This is my first time doing anything with multithreading. We're also supposed to create our own barriers using a combination of locks and condition variables, but I'm not even sure how to do that.

Also, some code isn't pictured, such as my "logbase" function and the function that reads in the input array. I know those work fine.

Thank you for your time.

CodePudding user response：

You problem is here, you are trying to pass a pointer to vector

 args[2] = *vector;

but instead you just pass in the first element and then treat it as a pointer after wards, that wont work. You need to pass in the pointer but that probably wont fit in the space you have reserved.

If you have to pass the args like that (as opposed to simply creating some static globals) then you should do this

struct args_t
{
    int i;
    int j;
    int * vector;
 };

then

  struct args_t *args = malloc(sizeof(struct args_t));
  args->i = i;
  args->j = j;
  args->vector = *vector;
  pthread_create(&threads[j], NULL, parallel, (void*)args);

then add corresponding code at the receiving side