2

1900 個の数字を含むランダムに生成された数字のリストがあり、上位 190 個の数字の並べ替えられたリストを取得したいと考えています。部分的な並べ替えアルゴリズムの 2 つのバージョンを作成しました。1 つ目は CPU バージョンで、2 つ目は Cudafy.net で実行できるように作成されています。しかし、それらの間には実行時間に大きな違いがあります.CPUで実行すると、誰かがその理由を明らかにできるのではないかと思っていました+ 2番目のバージョンをさらに高速化することは可能ですか?

注: 2 番目のアルゴリズムは GPU で実行されるため、cudafy.net を使用してコードを実行するため、linq や C で実行されないものは使用できません。残念ながら cudafy.net もジャグ配列をサポートしていません。

バージョン 1:

/// <summary>
/// Sequentially runs through all the values in the array and identifies if 
/// the current number is less than the highest number in the sorted list.
/// </summary>
/// <param name="numbers"> Unsorted array of numbers.</param>
/// <param name="sortedNumbers"> Array used to hold the partial list of sorted numbers.</param>
public static void NewSorter(int[] numbers, int[] sortedNumbers)
{
    for (int i = 0; i < numbers.Length; i++)
    {
        if (sortedNumbers[sortedNumbers.Length - 1] > numbers[i])
        {
            //Update numbers
            IdentifyPosition(sortedNumbers, numbers[i]);
        }
    }
}

/// <summary>
/// Identifies the position the number should be placed in the partial list of sorted numbers.
/// </summary>
/// <param name="sortedNumbers"> Array used to hold the partial list of sorted numbers.</param>
/// <param name="NewNumber"> Number to be inserted.</param>
static void IdentifyPosition(int[] sortedNumbers, int NewNumber)
{
    for (int i = 0; i < sortedNumbers.Length; i++)
    {
        if (NewNumber < sortedNumbers[i])
        {
            //Offset and add.
            ArrayShifter(sortedNumbers, i, NewNumber);
            break;
        }
    }
}

/// <summary>
/// Moves all the elements to the right of a point up one and 
/// then places the new number in the specified point.
/// </summary>
/// <param name="SortedNumbers"> Array used to hold the partial list of sorted numbers.</param>
/// <param name="position"> Position in the array where the new number should be place.</param>
/// <param name="NewNumber"> Number to include in the array.</param>
static void ArrayShifter(int[] SortedNumbers, int position, int NewNumber)
{
    for (int i = SortedNumbers.Length - 1; i > position; i--)
    {
        SortedNumbers[i] = SortedNumbers[i - 1];
    }

    SortedNumbers[position] = NewNumber;
}

上記のバージョンは ~ 0.65 ミリ秒で実行されました。

バージョン 2:

/// <summary>
/// Sequentially runs through all the values in the array and identifies if 
/// the current number is less than the highest number in the sorted list.
/// </summary>
/// <param name="unsortedNumbers"> Unsorted numbers.</param>
/// <param name="lookbackCount"> Length of the array.</param>
/// <param name="sortedNumbers"> Array which will contain the partial list of sorted numbers.</param>
[Cudafy]
public static void CudaSorter(GThread thread, long[,] unsortedNumbers, int[] lookbackCount, long[,] sortedNumbers)
{
    int threadIndex = thread.threadIdx.x;
    int blockIndex = thread.blockIdx.x;
    int threadsPerBlock = thread.blockDim.x;
    int gpuThread = (threadIndex + (blockIndex * threadsPerBlock));

    if (gpuThread < 32)
    {
        int maxIndex = (lookbackCount[gpuThread] * 10) / 100;
        int maxLookback = lookbackCount[gpuThread];

        for (int i = 0; i < maxLookback; i++)
        {
            if (sortedNumbers[gpuThread, maxIndex] > unsortedNumbers[gpuThread, i])
            {
                //Update numbers
                IdentifyPosition2(sortedNumbers, unsortedNumbers[gpuThread, i], maxIndex, gpuThread);
            }
        }
    }
}


/// <summary>
/// Identifies the position in the sortedNumbers array where the new number should be placed.
/// </summary>
/// <param name="sortedNumbers"> Sorted numbers.</param>
/// <param name="newNumber"> Number to be included in the sorted array.</param>
/// <param name="maxIndex"> length of sortedNumbers array. </param>
/// <param name="gpuThread"> GPU thread index.</param>
[Cudafy(eCudafyType.Device)]
public static void CudaIdentifyPosition(long[,] sortedNumbers, long newNumber, int maxIndex, int gpuThread)
{
    for (int i = 0; i < maxIndex; i++)
    {
        if (newNumber < sortedNumbers[gpuThread, i])
        {
            //Offset and add.
            ArrayShifter2(sortedNumbers, i, newNumber, maxIndex, gpuThread);
            break;
        }
    }
}


/// <summary>
/// Shifts all the elements to the right of the specified position, 1 position
/// to the right, and insert the new number in the specified position.
/// </summary>
/// <param name="sortedNumbers"> Sorted Numbers.</param>
/// <param name="position"> Where the new number needs to be inserted.</param>
/// <param name="newNumber"> New number to insert.</param>
/// <param name="maxIndex"> Length of sortedNumbers array.</param>
/// <param name="gpuThread"> GPU thread index.</param>
[Cudafy(eCudafyType.Device)]
public static void CudaArrayShifter(long[,] sortedNumbers, int position, long newNumber, int maxIndex, int gpuThread)
{
    for (int i = maxIndex - 1; i > position; i--)
    {
        sortedNumbers[gpuThread, i] = sortedNumbers[gpuThread, i - 1];
    }

    sortedNumbers[gpuThread, position] = newNumber;
}

上記は 2.8 ミリ秒で実行されます。つまり、約 4 倍遅くなります。

私はすでに次のことを試しました：

  1. countのローカル変数を宣言maxLookBackし、それを for ループで使用 => 改善なし。
  2. データ型をlong[,]からint[,]=> 2.6 ミリ秒に変更しました (長い時間を使用する必要があるため、これは実現できません)。
  3. => 1.3 ミリ秒に変更int[,]されint[]ました (GPU を占有し続けるために複数の配列を GPU に渡す必要があるため、これも現実的ではありません)。これが時間にどれだけ影響するかに驚きました。

編集: Henk のコメントのためにコードを修正しました。GPU で GPU バージョンを実行unsortedNumbers[32,1900]し、CPU で 1 つの配列をソートする単一のスレッドと比較しました。CPU 時間を 32 倍しても、GPU の時間よりもかなり低いです。

4

1 に答える 1

0

ここで恥をかいた後、私はそれが何であるかを理解するために、その仕事について少し読むことにしました.

したがって、大きな配列から最小数のサブ配列を選択する必要があり、それを並べ替える必要があります。おそらく、CPU のオプションを考え出さないほうがよいでしょう。配列全体を実行し、低値を選択し、要素をシフトして最終的な配列にすぐに挿入します。明らかに、選択中にソートが行われます。

ただし、並列でサンプリングする方法が想像できません。さらに、適切に並列化された並べ替えアルゴリズムを使用する必要があります。そうしないと、タスクが順番に解決される場合、グラフィックス コアは、周波数が高く、データ アクセスが高速な CPU コアよりも確実に速度が低下します。

マージソートがこれに役立つと思います。安値を取得してから並べ替える代わりに、すべてをすぐに並べ替えてみてください。次に、N 個の最初または最後の要素を選択します。

残念ながら、今はあなたのコードを編集する準備ができていません。しかし、それが少なくとも少し役立つことを願っています。

于 2020-01-08T14:34:45.867 に答える