数组元素看似任意变化[平行quicksort/prefix求和]

Question

所以我正在使用 Cilk 在 C 中实现并行快速排序，我运行遇到了一个奇怪的问题。我的代码的相关部分，供参考（并提前为长度道歉）：

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <math.h>
#include <cilk/cilk.h>
#include <cilk/cilk_api.h>

void prefixSum(int* input,int* output, int length){
   if(length == 1){
      output[0] = input[0];
      return;
   }
   int i;
   int nPairs = (int) floor(((double)length)/2);
   int pairs = (int) ceil(((double)length)/2);
   int z[pairs];
   int w[pairs];
   cilk_for(i=0;i<nPairs;i++){
      z[i] = input[2*i]+input[2*i+1];
   }

   if(pairs>nPairs){
      z[pairs-1] = input[length-1];
   }
   prefixSum(z,w,pairs);
   cilk_for(i=0;i<length;i++){
      if(i==0){
         output[i] = input[i];
      } 
      else if((i-1)%2==0){
         output[i] = w[(i-1)/2];
      }
      else{
         output[i] = w[(i-2)/2] + input[i];
      }
   }
   return;
}

void prefixScan(int* input, int length){
   int i;
   for(i=length-1;i>0;i--){
      input[i] = input[i-1];
   }
   input[0] = 0;
}

void paraSort(double* array, int length){
   if(length==1){
      return;
   }
   int pivot = rand() % length;
   int lowSet[length];
   int highSet[length];
   int equalSet[length];
   int i;
   cilk_for(i=0;i<length;i++){
      if(array[i]==array[pivot]){
         lowSet[i] = 0;
         highSet[i] = 0;
         equalSet[i] = 1;
      } else if(array[i]<array[pivot]){
         lowSet[i] = 1;
         highSet[i] = 0;
         equalSet[i] = 0;
      } else {
         lowSet[i] = 0;
         highSet[i] = 1;
         equalSet[i] = 0;
      }
   }
   int lowIndex[length];
   int highIndex[length];
   int equalIndex[length];
   prefixSum(lowSet,lowIndex,length);
   int numLow = lowIndex[length-1];
   prefixScan(lowIndex,length);

   prefixSum(highSet,highIndex,length);
   int numHigh = highIndex[length-1];
   prefixScan(highIndex,length);

   prefixSum(equalSet,equalIndex,length);
   int numEqual = equalIndex[length-1];
   prefixScan(equalIndex,length);

   double lowList[imin(numLow,1)];
   double highList[imin(numHigh,1)];
   double equalList[numEqual];

   cilk_for(i=0;i<length;i++){
      if(lowSet[i]==1){
         lowList[lowIndex[i]] = array[i];
      } else if(highSet[i]==1){ 
         highList[highIndex[i]] = array[i];
      } else if(equalSet[i]==1){
         equalList[equalIndex[i]] = array[i];
      }
   }

   if(numLow>0 && numHigh>0){
      cilk_spawn paraSort(lowList,numLow);
      paraSort(highList,numHigh);
      cilk_sync;
   } else if(numLow==0 && numHigh>0){
      paraSort(highList,numHigh);
   } else if(numLow>0 && numHigh==0){
      paraSort(lowList,numLow);
   }
   cilk_for(i=0;i<length;i++){
      if(i<numLow){
         array[i] = lowList[i];
      } else if(i<numLow+numEqual){
         array[i] = equalList[i-numLow];
      } else {
         array[i] = highList[i-(numLow+numEqual)];
      }
   }
   return;
}

现在，当我运行在一个包含 50 个元素的测试用例上（按顺序，为了便于调试），我深入递归一层，然后遇到了一个分段错误，这似乎是由通过 equalList[equalIndex[i]] = array[i]; 行中的越界索引。

进一步检查，分配equalIndex后，其中的值完全是任意的。这是可以预料的；我还没有分配任何东西。 prefixSum 在除倒数第二个元素之外全为零的元素列表上调用，该元素为一。（这是一个标记元素等于主元的位图。）它将前缀和运算的结果放入 equalIndex，我将其作为指向数组的指针传入，以便结果在调用之外保留。

执行此操作后，调试 printf 命令显示 equalIndex 现在全为零，除了最后两个元素，它们都是 1。这是预期的前缀和结果；到目前为止，一切都很好。 prefixScan 是一个简单的辅助函数，可以帮助我解决从零开始的索引问题；它将给定数组 one space 中的所有元素向右移动，用零填充第一个元素。将 equalIndex 传递给它后，调试语句显示 equalIndex 除了最后一个元素为 1 之外全为零。

问题紧随其后，在 cilk_for 循环中将每个元素复制到其正确的数组中。在此循环的主体中，printf 语句现在显示的值与之前的值丝毫不匹配 - 有些值正确地为零，其他值非常大的正整数或负整数，就像我在使用 prefixSum 初始化此数组之前看到的那种.一旦它达到这些极值之一并尝试将其用作数组索引，程序就会崩溃。

我最好的猜测是 equalIndex 中的值以某种方式没有被正确分配（因此奇怪的行为就好像我没有初始化数组一样），但我很难弄清楚到底是什么哪里出错了。

Answer 1

你自相矛盾。有一次你说

equalIndex is all zeroes except for the last element, which is one

但后来你推测

somehow the values in equalIndex aren't being assigned properly

。不能两全其美。

我不了解 Cilk，但从 C 推断，我倾向于认为您在破坏自己的数据。特别考虑这段代码，它似乎是问题所在：

double lowList[imin(numLow,1)];
double highList[imin(numHigh,1)];
double equalList[numEqual];

cilk_for(i=0;i<length;i++){
    if(lowSet[i]==1){
       lowList[lowIndex[i]] = array[i];
    } else if(highSet[i]==1){ 
       highList[highIndex[i]] = array[i];
    } else if(equalSet[i]==1){
       equalList[equalIndex[i]] = array[i];
    }
}

数组 lowList 和 highList 有多长？在你回答之前研究他们的声明。现在，如果您尝试为这些数组的元素赋值超出其边界，您认为会发生什么？

数组元素看似任意变化[平行quicksort/prefix求和]

Array elements changing seemingly arbitrarily [parallel quicksort/prefix sum]

c

parallel-processing

cilk