0

2 バイト基数ソートを実装しています。概念は、Counting Sort を使用して整数の下位 16 ビットをソートし、次に上位 16 ビットをソートすることです。これにより、2 回の繰り返しで並べ替えを実行できます。私が持っていた最初のコンセプトは、ネガを処理する方法を見つけようとすることでした. 符号ビットは負の数に対して反転されるため、16 進数形式では、負の数が正の数よりも大きくなります。これに対抗するために、[0, 2 bil) = [128 000 000 000, 255 255...) を作成するために、正の符号ビットを反転させました。そして、それが負の場合、すべてのビットを反転して、範囲を (000 000 .., 127 255 ..) にしました。このサイトは、その情報を得るのに役立ちました。最後に、パスに基づいて整数を上位または下位の 16 ビットに分割します。以下は、それを可能にするコードです。

static uint32_t position(int number, int pass) {
    int mask;
    if (number <= 0) mask = 0x80000000;
    else mask = (number >> 31) | 0x80000000;
    uint32_t out = number ^ mask;
    return pass == 0 ? out & 0xffff : (out >> 16) & 0xffff;
}

実際の基数ソートを開始するには、サイズ 65536 要素のヒストグラムを作成する必要がありました。私が遭遇した問題は、入力された要素の数が非常に多い場合でした。ヒストグラムの作成には時間がかかるため、プロセスと共有メモリを使用して並行して実装しました。配列をサイズ / 8 のサブセクションに分割しました。次に、サイズが 65536 * 8 の共有メモリの配列で、各プロセスに独自のヒストグラムを作成させました。その後、すべてを合計して 1 つのヒストグラムを作成しました。そのためのコードは次のとおりです。

for (i=0;i<8;i++) {
    pid_t pid = fork();
    if (pid < 0) _exit(0);
    if (pid == 0) {
        const int start = (i * size) >> 3;
        const int stop  = i == 7 ? size : ((i + 1) * size) >> 3;
        const int curr  = i << 16;
        for (j=start;j<stop;++j)
            hist[curr + position(array[j], pass)]++;
        _exit(0);
    }
}
for (i=0;i<8;i++) wait(NULL);

for (i=1;i<8;i++) {
    const int pos = i << 16;
    for (j=0;j<65536;j++)
        hist[j] += hist[pos + j];
}

次の部分では、キャッシュがプレフィックスサムのパフォーマンスにどのように影響するかを分析することにほとんどの時間を費やしました。8 ビットおよび 11 ビットのパス基数ソートでは、すべてのヒストグラムが L1 キャッシュ内に収まります。16 ビットでは、L2 キャッシュ内にのみ収まります。最終的に、16 ビット ヒストグラムが最も速く合計を実行しました。また、CUDA Web サイトの推奨事項に従って、プレフィックスの合計も並行して実行しました。2 億 5000 万の要素で、これは 16 ビット整数よりも約 1.5 秒遅く実行されました。したがって、私のプレフィックスの合計は次のようになりました。

for (i=1;i<65536;i++)
    hist[i] += hist[i-1];

残された唯一のことは、配列を逆方向にトラバースし、すべての要素を一時配列のそれぞれの場所に配置することでした。temp から配列にコピーしてコードを再度実行する代わりに、2 回だけ実行する必要があったためです。最初に入力として配列を使用し、出力として temp を使用して並べ替えを実行しました。次に、temp を入力として、array を出力として使用して、2 回目の実行を行いました。これにより、両方の回でメモリコピーを配列に戻すことができなくなりました。実際の並べ替えのコードは次のようになります。

histogram(array, size, 0, hist);
for (i=size-1;i>=0;i--)
    temp[--hist[position(array[i], 0)]] = array[i];

memset(hist, 0, arrSize);
histogram(temp, size, 1, hist);
for (i=size-1;i>=0;i--)
    array[--hist[position(temp[i], 1)]] = temp[i];

このリンクには、これまでの完全なコードが含まれています。クイックソートに対してテストを実行したところ、整数と浮動小数点で 5 倍から 10 倍高速になり、8 バイト データ型で約 5 倍高速になりました。これを改善する方法はありますか？

4

1 に答える 1