Элементы массива меняются произвольно [параллельная быстрая сортировка / сумма префикса]

Question

Поэтому я работаю над реализацией параллельной быстрой сортировки в C, используя Cilk, и сталкиваюсь со странной проблемой. Соответствующие части моего кода, для справки (и заранее извиняюсь за длину):

#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, который я передаю как указатель на массив, чтобы результаты сохранялись вне вызова.

После этого команды debug printf показывают, что equindex теперь представляет собой все нули, кроме последних двух элементов, которые являются одним. Это ожидаемый результат суммы префикса; Все идет нормально. prefixScan - это простая вспомогательная функция, которая помогает мне справиться с индексацией с нуля; он перемещает все элементы в данном массиве на один пробел вправо, заполняя первый элемент нулем. После передачи equalIndex к этому операторы отладки показывают, что equalIndex - это все нули, кроме последнего элемента, который равен единице.

Где проблема возникает сразу же, в цикле cilk_for, который копирует каждый элемент в свой собственный массив. В теле этого цикла операторы printf теперь отображают значения, которые не совпадают с предыдущими в малейшей степени - некоторые из них должным образом равны нулю, другие - большие положительные или отрицательные целые числа, которые я видел ранее, до того как я инициализировал этот массив с помощью prefixSum., Как только оно достигает одного из этих крайних значений и пытается использовать его в качестве индекса массива, программа справедливо завершает работу.

Мое лучшее предположение состоит в том, что каким-то образом значения в equalIndex не назначаются должным образом (отсюда и странное поведение, как будто я не инициализировал массив), но у меня много проблем с определением, что именно происходит и где происходит.

Answer 1

Вы противоречите себе. В какой-то момент вы говорите

equalIndex это все нули, кроме последнего элемента, который является одним

но позже вы предполагаете, что

почему-то значения в equalIndex назначаются неправильно

, Вы не можете иметь это в обоих направлениях.

Я не знаю, Силк, но экстраполируя из 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? Изучите их заявления, прежде чем ответить. Как вы думаете, что может произойти, если вы попытаетесь присвоить значения элементам этих массивов за их пределами?