c++ - 为什么在 CPU 上进行线程化浮点计算会使它们花费更长的时间？

Question

我目前正在研究科学模拟(引力 nbody)。我首先用一个朴素的单线程算法编写它，这对少量粒子的表现是可以接受的。然后我对这个算法进行了多线程处理(它是令人尴尬的并行)，程序花费了大约 3 倍的时间。下面是一个最小的、完整的、可验证的简单算法示例，它具有类似的属性并输出到/tmp 中的文件(它被设计为在 Linux 上运行，但 C++ 也是标准的)。请注意，如果您决定运行此代码，它将生成一个 152.62MB 的文件。输出数据是为了防止编译器优化程序外的计算。

#include <iostream>
#include <functional>
#include <thread>
#include <vector>
#include <atomic>
#include <random>
#include <fstream>
#include <chrono>

constexpr unsigned ITERATION_COUNT = 2000;
constexpr unsigned NUMBER_COUNT = 10000;

void runThreaded(unsigned count, unsigned batchSize, std::function<void(unsigned)> callback){
    unsigned threadCount = std::thread::hardware_concurrency();
    std::vector<std::thread> threads;
    threads.reserve(threadCount);

    std::atomic<unsigned> currentIndex(0);

    for(unsigned i=0;i<threadCount;++i){
        threads.emplace_back([&currentIndex, batchSize, count, callback]{
            unsigned startAt = currentIndex.fetch_add(batchSize);

            if(startAt >= count){
                return;
            }else{
                for(unsigned i=0;i<count;++i){
                    unsigned index = startAt+i;
                    if(index >= count){
                        return;
                    }
                    callback(index);
                }
            }
        });
    }

    for(std::thread &thread : threads){
        thread.join();
    }
}

void threadedTest(){
    std::mt19937_64 rnd(0);
    std::vector<double> numbers;

    numbers.reserve(NUMBER_COUNT);
    for(unsigned i=0;i<NUMBER_COUNT;++i){
        numbers.push_back(rnd());
    }

    std::vector<double> newNumbers = numbers;

    std::ofstream fout("/tmp/test-data.bin");

    for(unsigned i=0;i<ITERATION_COUNT;++i) {
        std::cout << "Iteration: " << i << "/" << ITERATION_COUNT << std::endl;
        runThreaded(NUMBER_COUNT, 100, [&numbers, &newNumbers](unsigned x){
            double total = 0;
            for(unsigned y=0;y<NUMBER_COUNT;++y){
                total += numbers[y]*(y-x)*(y-x);
            }
            newNumbers[x] = total;
        });
        fout.write(reinterpret_cast<char*>(newNumbers.data()), newNumbers.size()*sizeof(double));
        std::swap(numbers, newNumbers);
    }
}

void unThreadedTest(){
    std::mt19937_64 rnd(0);
    std::vector<double> numbers;

    numbers.reserve(NUMBER_COUNT);
    for(unsigned i=0;i<NUMBER_COUNT;++i){
        numbers.push_back(rnd());
    }

    std::vector<double> newNumbers = numbers;

    std::ofstream fout("/tmp/test-data.bin");

    for(unsigned i=0;i<ITERATION_COUNT;++i){
        std::cout << "Iteration: " << i << "/" << ITERATION_COUNT << std::endl;
        for(unsigned x=0;x<NUMBER_COUNT;++x){
            double total = 0;
            for(unsigned y=0;y<NUMBER_COUNT;++y){
                total += numbers[y]*(y-x)*(y-x);
            }
            newNumbers[x] = total;
        }
        fout.write(reinterpret_cast<char*>(newNumbers.data()), newNumbers.size()*sizeof(double));
        std::swap(numbers, newNumbers);
    }
}

int main(int argc, char *argv[]) {
    if(argv[1][0] == 't'){
        threadedTest();
    }else{
        unThreadedTest();
    }
    return 0;
}

当我运行它时(在 Linux 上用 clang 7.0.1 编译)，我从 Linux time 命令中得到以下时间。这些之间的区别与我在真实程序中看到的相似。标记为“真实”的条目与此问题相关，因为这是程序运行所需的时钟时间。

单线程:

real    6m27.261s
user    6m27.081s
sys     0m0.051s

多线程:

real    14m32.856s
user    216m58.063s
sys     0m4.492s

因此，当我期望它会显着加速(大约是 8 倍，因为我有一个 8 核 16 线程 CPU)时，我会问是什么导致了这种巨大的减速。我没有在 GPU 上实现它，因为下一步是对算法进行一些更改以将其从 O(n²) 变为 O(nlogn)，但这对 GPU 也不友好。与包含的示例相比，更改后的算法与我当前实现的 O(n²) 算法的差异较小。最后，我想观察运行每次迭代的主观时间(根据出现的迭代线之间的时间来判断)在线程化和非线程化运行中都有显着变化。

Answer 1

遵循这段代码有点困难，但我认为您正在大规模重复工作，因为每个线程都完成几乎所有工作，只是在开始时跳过一小部分。

我假定 runThreaded 的内部循环应该是:

unsigned startAt = currentIndex.fetch_add(batchSize);

while (startAt < count) {
  if (startAt >= count) {
    return;
  } else {
    for(unsigned i=0;i<batchSize;++i){
      unsigned index = startAt+i;

      if(index >= count){
        return;
      }

      callback(index);
    }
  }

  startAt = currentIndex.fetch_add(batchSize);
}

在哪里i < batchSize是这里的关键。你应该只做批处理指示的工作，而不是 count次，这是整个列表减去初始偏移量。

通过这次更新，代码运行速度显着更快。我不确定它是否完成了所有必需的工作，因为很难判断这是否真的发生了，输出非常少。