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

Question

我目前正在进行科学模拟（引力体）。我首先使用朴素的单线程算法编写了该代码，并且对于少量粒子而言，该代码的性能令人满意。然后，我对该算法进行了多线程处理（令人尴尬的是，它是并行的），程序花了大约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”的条目与此问题相关，因为这是程序运行所需的时钟时间。

单线程：

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时间，这是整个列表减去初始偏移量的时间。

通过此更新，代码运行速度明显加快。我不确定它是否完成了所有必需的工作，因为很难确定这是否真的在发生，因此输出很小。