我正在尝试使用 C++ 在 CPU 上实现双调排序的多线程版本。目前，即使我使用 16 个线程，我通过此实现可以获得的最佳加速约为 4.3（订购 128 MB 的数组）。我使用的代码如下：
void compareAndSwap(std::vector<uint32_t>& paddedValues, unsigned int threadId,
unsigned int chunkSize, unsigned int mergeStep, unsigned int bitonicSequenceSize)
{
unsigned int startIndex = threadId * chunkSize;
unsigned int endIndex = (threadId + 1) * chunkSize;
// Process the chunk assigned to this thread
for (unsigned int currentIndex = startIndex; currentIndex < endIndex; currentIndex++)
{
// Find the element to compare with
unsigned int compareIndex = currentIndex ^ mergeStep;
// Only compare if the compareIndex is greater (to avoid duplicate swaps)
if (compareIndex > currentIndex)
{
bool shouldSwap = false;
// Determine if we should swap based on the current subarray's sorting direction
if ((currentIndex & bitonicSequenceSize) == 0) // First half of subarray (ascending)
{
shouldSwap = (paddedValues[currentIndex] > paddedValues[compareIndex]);
}
else // Second half of subarray (descending)
{
shouldSwap = (paddedValues[currentIndex] < paddedValues[compareIndex]);
}
// Perform the swap if necessary
if (shouldSwap)
{
std::swap(paddedValues[currentIndex], paddedValues[compareIndex]);
}
}
}
}
void bitonicSort(uint32_t values[], unsigned int arrayLength, unsigned int numThreads, int sortOrder)
{
// Step 1: Pad the array to the next power of 2
unsigned int paddedLength = 1 << static_cast<int>(std::ceil(std::log2(arrayLength)));
std::vector paddedValues(paddedLength, std::numeric_limits<uint32_t>::max());
std::copy(values, values + arrayLength, paddedValues.begin());
// Step 2: Determine chunk size for each thread
unsigned int chunkSize = paddedLength / numThreads;
// Step 3: Iteratively build and merge bitonic sequences
// Outer loop: controls the size of bitonic sequences
for (unsigned int bitonicSequenceSize = 2; bitonicSequenceSize <= paddedLength; bitonicSequenceSize *= 2)
{
// Middle loop: controls the size of sub-sequences being merged
for (unsigned int mergeStep = bitonicSequenceSize / 2; mergeStep > 0; mergeStep /= 2)
{
// Step 4: Use multiple threads to compare and swap elements in parallel
std::vector<std::thread> threads;
threads.reserve(numThreads);
// Thread creation loop
for (unsigned int threadId = 0; threadId < numThreads; threadId++)
{
threads.emplace_back(compareAndSwap,
std::ref(paddedValues),
threadId,
chunkSize,
mergeStep,
bitonicSequenceSize);
}
// Wait for all threads to complete this stage
for (auto& thread : threads)
{
thread.join();
}
}
}
// Step 5: Copy back the sorted values
std::copy(paddedValues.begin(), paddedValues.begin() + arrayLength, values);
// Step 6: If descending order is required, reverse the array
if (sortOrder == 0)
{
std::reverse(values, values + arrayLength);
}
}
问题似乎是我得到的失败次数很高（我通过使用 amd uProf 进行了验证，我使用 Ryzen 9 7940hs 来执行测试）。特别是，当我使用更高的线程数时，未命中次数会更高，这似乎抵消了增加可用线程数的潜在好处。我该如何解决这个问题？
排序算法一旦并行运行，通常会受到“内存限制”。对于大型数组上的双调排序尤其如此，因为当合并数组太大时，它往往会在无法位于 cache 中的相同内存块上迭代很多时间。 这个问题不仅适用于双调排序，而且适用于大多数进行比较的算法。例如，快速排序（对缓存友好）对此效果更好，但还远远不够。这个问题导致大多数排序算法无法扩展（至少当比较运算符是廉价的时）。您可以通过
通过实验测量机器的 DRAM 吞吐量并将其与其（实际）带宽进行比较来测试这一假设（著名的 Stream Triad 基准测试 可以像当今许多其他软件一样进行测量）。我不知道你的 Zen4 CPU 上是否有硬件计数器（据我所知 AMD Zen2 无法直接测量，而 Intel Skylake 可以）。 对于大型数组，最好的解决方案就是按照 1 或 2 个步骤将项目放入
桶中，从而避免大多数内存限制步骤。然后，您可以并行地独立对存储桶进行排序。这种排序算法的组合产生了我迄今为止设计的最有效的并行排序算法（对于 CPU）之一。这假设项目可以存储到存储桶中，因此不需要“比较”项目（这对于具有简单比较运算符的整数和浮点数等本机类型来说是可以的）。您可以在here找到高效的并行 C++ 实现（供 Python 脚本使用）。块的排序是使用外部（特定于 x86）库完成的，据我所知，它内部使用了积极优化的 SIMD 感知双调排序。 请注意，双调排序非常适合对小数组进行排序，特别是因为它SIMD 友好。这在经过优化以受益于 SIMD 指令的 CPU 上非常有用（对于本机类型），对于 GPU 甚至更好（只要要排序的数组不是很大）。对于大型数组，与介绍排序（或基数排序）相比，双调排序的复杂性相当糟糕。这就是为什么人们在这种情况下往往不使用它（即使在 GPU 上，只要不需要比较）。
顺便说一句，您标记了问题
openmp，但我在代码中没有看到 OpenMP 指令。它可以使你的代码更简单。例如，您可以仅使用 #pragma omp parallel for
创建线程。这也避免了一遍又一遍地重新创建线程，这是低效的。如果需要，您可以使用
#pragma omp barrier 轻松进行全局线程同步。您还可以使用 #pragma omp task#pragma omp taskwait