だから私は、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 要素のテスト ケースで実行すると (デバッグを容易にするために順次)、1 つのレイヤーを再帰の奥深くまで進めてから、範囲外のインデックスが原因であると思われるセグメンテーション エラーに遭遇します。ラインequalList[equalIndex[i]] = array[i];。
さらに調べてみると、 equalIndex を割り当てた直後、その中の値は完全に任意です。これは当然のことです。まだ何も割り当てていません。prefixSum は、1 である最後から 2 番目の要素を除いてすべてゼロである要素のリストで呼び出されます。(これは、ピボットと等しい要素をマークするビットマップです。) これは、プレフィックス合計操作の結果を equalIndex に入れます。これを配列へのポインターとして渡し、結果が呼び出しの外でも持続するようにします。
これを行った後、debug printf コマンドは、equalIndex が最後の 2 つの要素 (両方とも 1) を除いてすべてゼロになっていることを示します。これは予想されるプレフィックス合計の結果です。ここまでは順調ですね。prefixScan は、ゼロからインデックス作成に取り組むのに役立つ単純なヘルパー関数です。指定された配列内のすべての要素を 1 スペース右に移動し、最初の要素をゼロで埋めます。これに equalIndex を渡した後、デバッグ ステートメントは、1 である最後の要素を除いて equalIndex がすべてゼロであることを示します。
問題が発生するのは、各要素を適切な配列にコピーする cilk_for ループの直後です。このループの本体で、printf ステートメントは、以前の値とは少しでも一致しない値を表示するようになりました。一部は適切にゼロであり、その他は、この配列を prefixSum で初期化する前に見たような非常に大きな正または負の整数です。 . これらの極端な値の 1 つに到達し、それを配列インデックスとして使用しようとすると、プログラムは正しくクラッシュします。
私の最善の推測は、どういうわけか equalIndex の値が適切に割り当てられていないことです (したがって、配列を初期化していないかのような奇妙な動作です)。