Hillis 和 Steele 关于 C 中的前缀和多线程分配

Question

我正在处理 CS 作业，我必须在其中使用 p_threads 来计算数组的前缀和。教授告诉我们使用 Hillis 和 Steele 算法。我在维基百科 (here) 上找到了一些伪代码，具体来说：

我对在实际代码中实现它有点犹豫。我们的程序应该以这种方式工作，用户通过文件或标准输入传入一个数组，然后接下来的 2 个参数是输入数组的大小，以及我们需要使用的线程数。所以，我假设这张图片中的“n”是“我们需要使用的线程数量”。然后，我不确定 x 上的符号是什么意思。维基百科说“在上面，符号......表示时间步长 i 中数组 x 的第 j 个元素的值。”但是……什么？我如何实现这个“时间步长”？我假设它的意思是：“执行 j 的 i+1 次方，然后在数组 x 中找到该索引元素”。有了这个假设，我写了这段代码：

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

该行注释为“问题在这里”段错误。我可以在 gdb 中单步执行并弄清楚为什么它会自己出现段错误，但我想知道我是否做对了。这是我第一次用多线程做任何事情。我们还应该使用锁和条件变量的组合来创建我们自己的障碍，但我什至不知道该怎么做。

此外，有些代码没有显示出来，例如我的“logbase”函数和读取输入数组的函数。我知道这些工作正常。

感谢您的宝贵时间。

Answer 1

你的问题就在这里，你正试图传递一个指向 vector 的指针

 args[2] = *vector;

但是您只是传入第一个元素，然后将其视为 wards 之后的指针，这是行不通的。您需要传入指针，但它可能不适合您保留的 space。

如果你必须像那样传递参数（而不是简单地创建一些静态全局变量）那么你应该这样做

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

然后

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

然后在接收端添加相应的代码

Hillis 和 Steele 关于 C 中的前缀和多线程分配

Hillis and Steele on a prefix sum multithreading assignment in C

c

multithreading

algorithm

prefix-sum