并行Bitonic Sort实现性能优化：解决多线程缓存缺失问题

问题背景 #

使用C++实现的多线程Bitonic Sort处理128MB数组时，16线程下最高加速比仅约4.3。通过amd uProf（基于Ryzen 9 7940hs测试）分析，核心问题是大量缓存缺失，且线程数越高缓存缺失越严重，抵消了多线程的并行优势。

原始实现代码 #

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);
        }
    }

优化方案 #

1. 重构线程任务划分，提升缓存局部性 #

原始实现按连续chunk分配线程任务，但Bitonic Sort的compareIndex = currentIndex ^ mergeStep会导致线程访问跨大范围内存，缓存命中率极低。改为按线程ID步长划分任务，让每个线程遍历数组中所有满足currentIndex % numThreads == threadId的元素，这样线程的内存访问更有规律，能更好利用缓存行。

修改后的compareAndSwap函数：

void compareAndSwap(std::vector<uint32_t>& paddedValues, unsigned int threadId,
                    unsigned int numThreads, unsigned int mergeStep, unsigned int bitonicSequenceSize,
                    unsigned int arrayLength) // 添加原数组长度，用于跳过填充元素
{
    unsigned int paddedLength = paddedValues.size();
    // 按线程ID步长遍历，而非连续chunk
    for (unsigned int currentIndex = threadId; currentIndex < paddedLength; currentIndex += numThreads)
    {
        unsigned int compareIndex = currentIndex ^ mergeStep;
        // 跳过超出原数组的填充元素，减少无效缓存访问
        if (currentIndex >= arrayLength || compareIndex >= arrayLength)
        {
            continue;
        }
        if (compareIndex > currentIndex)
        {
            bool shouldSwap = false;
            if ((currentIndex & bitonicSequenceSize) == 0)
            {
                shouldSwap = (paddedValues[currentIndex] > paddedValues[compareIndex]);
            }
            else
            {
                shouldSwap = (paddedValues[currentIndex] < paddedValues[compareIndex]);
            }
            if (shouldSwap)
            {
                std::swap(paddedValues[currentIndex], paddedValues[compareIndex]);
            }
        }
    }
}

对应的线程创建逻辑修改：

// 在bitonicSort函数的线程创建循环中
for (unsigned int threadId = 0; threadId < numThreads; threadId++)
{
    threads.emplace_back(compareAndSwap,
                         std::ref(paddedValues),
                         threadId,
                         numThreads,
                         mergeStep,
                         bitonicSequenceSize,
                         arrayLength); // 传递原数组长度
}

2. 减少伪共享冲突 #

Ryzen 9 7940hs的缓存行大小为64字节（可容纳16个uint32_t元素）。多个线程访问同一缓存行的不同元素会导致缓存行频繁失效。在步长划分的基础上，可进一步调整任务分配，让每个线程的访问位置错开缓存行边界：

// 修改compareAndSwap的遍历起始点和步长
unsigned int cacheLineElements = 64 / sizeof(uint32_t); // 16
unsigned int startIndex = threadId * cacheLineElements;
unsigned int step = numThreads * cacheLineElements;
for (unsigned int currentIndex = startIndex; currentIndex < paddedLength; currentIndex += step)
{
    // ... 原有逻辑
}

这样每个线程处理的元素都位于独立缓存行，避免伪共享导致的缓存失效。

3. 显式数据预取 #

当mergeStep较大时，compareIndex与currentIndex内存距离远，可通过GCC内置的__builtin_prefetch提前加载目标元素到缓存，减少缓存缺失等待时间：

unsigned int compareIndex = currentIndex ^ mergeStep;
// 预取compareIndex对应的元素到L3缓存
__builtin_prefetch(&paddedValues[compareIndex], 0, 3);

参数说明：第二个0表示预取用于读操作，第三个3表示预取到所有缓存层级（L1/L2/L3）。

4. 匹配线程数与硬件缓存容量 #

Ryzen 9 7940hs为8核16线程（超线程），超线程的两个线程共享同一物理核心的缓存资源。过多线程会加剧缓存竞争，建议测试**8线程（物理核心数）**的性能，此时每个线程能获得更多缓存资源，缓存缺失率会显著降低，可能获得更高的加速比。

5. 直接实现降序排序，避免额外反转 #

原始实现先升序排序再反转数组，会导致额外的内存遍历和缓存访问。可直接在排序阶段根据需求调整比较逻辑，省去反转步骤：

// 在compareAndSwap函数中添加sortOrder参数，调整判断逻辑
bool shouldSwap = false;
if (sortOrder == 1) { // 升序
    if ((currentIndex & bitonicSequenceSize) == 0)
    {
        shouldSwap = (paddedValues[currentIndex] > paddedValues[compareIndex]);
    }
    else
    {
        shouldSwap = (paddedValues[currentIndex] < paddedValues[compareIndex]);
    }
} else { // 降序
    if ((currentIndex & bitonicSequenceSize) == 0)
    {
        shouldSwap = (paddedValues[currentIndex] < paddedValues[compareIndex]);
    }
    else
    {
        shouldSwap = (paddedValues[currentIndex] > paddedValues[compareIndex]);
    }
}

同时移除bitonicSort函数末尾的反转逻辑。

测试建议 #

优化后优先测试缓存缺失率变化（通过amd uProf），对比不同线程数（8/16）、不同优化组合的性能，找到最优配置。

内容的提问来源于stack exchange，提问作者salbh