Элементы массива изменяются, казалось бы, произвольно [parallel quicksort/prefix sum]

Question

Итак, я работаю над реализацией параллельной quicksort в 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 вызывается в списке элементов, который равен нулю, за исключением второго-последнего элемента, который является одним. (Это растровое изображение, обозначающее элементы, равные оси.) Он помещает результаты операции префикса sum в equalIndex, который я передаю как указатель на массив, чтобы результаты сохранялись вне вызова.

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

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

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

Answer 1

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

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

за исключением, но позже вы предположили, что

как-то значения в equalIndex не является надлежащим образом назначается

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

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