2

我有一个随机生成的数字列表，其中包含 1900 个数字，我想获得前 190 个数字的排序列表。我编写了两个版本的部分排序算法，第一个是 CPU 版本，第二个是为了在 Cudafy.net 上运行而编写的。但是它们之间的执行时间存在很大差异，当在 CPU 上运行时，我想知道是否有人可以解释为什么，+ 是否可以进一步加快第二个版本的速度？

注意：第二个算法将在 GPU 上运行，所以我不能使用 linq 或任何不能在 C 上运行的东西，因为我将使用 cudafy.net 来运行代码。不幸的是 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 毫秒（这是不可行的，因为我需要使用 long。）
  3. 更改int[,]为int[]=> 1.3 毫秒（这也不可行，因为我需要将多个数组传递给 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 回答