Я сейчас работаю над научным моделированием (Gravitational nbody). Сначала я написал его наивным однопоточным алгоритмом, и это было приемлемо для небольшого числа частиц. Затем я многопоточный этот алгоритм (это смущающе параллельно), и программа заняла примерно 3 раза. Ниже приведен минимальный, полный, проверяемый пример тривиального алгоритма со схожими свойствами и выводом в файл в / tmp (он предназначен для работы в Linux, но C ++ также является стандартным). Имейте в виду, что если вы решите запустить этот код, он создаст файл размером 152,62 МБ. Данные выводятся, чтобы компилятор не мог оптимизировать вычисления вне программы.
#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([¤tIndex, 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;
}
Когда я запускаю это (скомпилировано с clang 7.0.1 в Linux), я получаю следующие команды Linux time. Разница между ними похожа на то, что я вижу в моей настоящей программе. Запись, помеченная как «реальная», является релевантной для этого вопроса, поскольку это время часов, необходимое программе для запуска.
однопоточный:
real 6m27.261s
user 6m27.081s
sys 0m0.051s
Многопоточная:
real 14m32.856s
user 216m58.063s
sys 0m4.492s
В связи с этим я спрашиваю, что вызывает такое значительное замедление, когда я ожидаю, что оно значительно ускорится (примерно в 8 раз, поскольку у меня 8-ядерный 16-поточный ЦП). Я не реализую это на графическом процессоре, так как следующим шагом является внесение некоторых изменений в алгоритм, чтобы перевести его с O (n²) на O (nlogn), но они также не являются дружественными для GPU. Измененный алгоритм будет иметь меньшую разницу с моим в настоящее время реализованным алгоритмом O (n²), чем включенный пример. И наконец, я хочу заметить, что субъективное время выполнения каждой итерации (судя по времени между появлением линий итерации) существенно изменяется как в многопоточных, так и в непотоковых запусках.