Почему N независимых вычислений N раз быстрее в N потоках?
У меня процессор N core (4 в моем случае). Почему N полностью независимых вызовов функций в N потоках примерно в N раз быстрее (конечно, накладные расходы на создание потоков, но читайте дальше)?
Посмотрите на следующий код:
namespace ch = std::chrono;
namespace mp = boost::multiprecision;
constexpr static unsigned long long int num = 3555;
// mp_factorial uses boost/multiprecision/cpp_int, so I get legit results
ch::steady_clock::time_point s1 = ch::steady_clock::now();
auto fu1 = std::async(std::launch::async, mp_factorial, num);
auto fu2 = std::async(std::launch::async, mp_factorial, num);
auto fu3 = std::async(std::launch::async, mp_factorial, num);
auto fu4 = std::async(std::launch::async, mp_factorial, num);
fu1.get(); fu2.get(); fu3.get(); fu4.get();
ch::steady_clock::time_point e1 = ch::steady_clock::now();
ch::steady_clock::time_point s2 = ch::steady_clock::now();
mp_factorial(num);
mp_factorial(num);
mp_factorial(num);
mp_factorial(num);
ch::steady_clock::time_point e2 = ch::steady_clock::now();
auto t1 = ch::duration_cast<ch::microseconds>(e1 - s1).count();
auto t2 = ch::duration_cast<ch::microseconds>(e2 - s2).count();
cout << t1 << " " << t2 << endl;
Я получаю результаты, такие как:
11756 20317
Это примерно в 2 раза быстрее. Я также попробовал это с огромным количеством, как num = 355555, Я получил действительно похожие результаты:
177462588 346575062
Почему это так? Я прекрасно знаю закон Амдаля, и что многоядерный процессор не всегда number_of_cores раз быстрее, но когда у меня независимый операции, я бы ожидал лучших результатов. По крайней мере, что-то рядом number_of_cores,
Обновить:
Как видите, все потоки работают как положено, так что это не проблема:
Решение
Проблема здесь в том, что у вас, конечно, есть несколько больших кусковых чисел, которые не помещаются в кэши L1 и L2 вашего процессора, а это означает, что процессор сидит и вертит своими маленькими пальцами ALU, в то время как контроллер памяти перепрыгивает повсюду, пытаясь прочитайте немного памяти для каждого процессора.
Когда вы работаете в ОДНОМ потоке, этот поток будет, по крайней мере, в основном работать только в трех разных областях памяти (a = b * c, чтение из b а также cписать в a).
Когда вы делаете 4 потока, у вас есть четыре разных a = b * c; с тремя различными потоками данных каждый, что приводит как к большему перерасходу кэшей, так и к контроллеру памяти и «открытым страницам» [страницы здесь — это термин DRAM, не имеющий ничего общего со страницами MMU, но вы также можете обнаружить, что пропуски TLB являются фактор также].
Таким образом, вы получаете лучшую производительность от запуска большего количества потоков, но не в 4 раза, поскольку из-за большого объема данных, потребляемых и производимых каждым потоком, интерфейс памяти является узким местом. Кроме получения машины с более эффективным интерфейсом памяти [и это может быть не так просто], вы ничего не можете с этим поделать — просто примите во внимание, что для этого конкретного случая память является более ограничивающим фактором, чем расчет.
Идеальный пример для решения с многопоточностью — это те, которые требуют больших вычислений, но не используют много памяти. У меня есть простой калькулятор простых чисел и калькулятор, который вычисляет «странные числа», оба дают почти точно Nx улучшение производительности при работе на N ядрах [но я бы начал использовать их для чисел, которые во много раз больше, чем 64-битные, он остановится давая ту же выгоду]
Изменить: Есть также возможность:
- некоторые функции, которые ваш код вызывает много, блокируют / блокируют другие потоки [возможно, в режиме «занятого ожидания», если реализация ожидает короткое время ожидания, так как бессмысленно вызывать ОС для ожидания нескольких десятков тактов ] — вещи как
newа такжеmallocи их освобождающие коллеги — вероятные кандидаты. - Верно ложное совместное использование — данные распределяются между ядрами ЦП, в результате чего содержимое кеша пересылается между процессорами. Особенно маленькие общие массивы, к которым обращаются [и обновляют] из каждого потока, могут привести к неправильной работе, даже если обновления выполняются без блокировки и с атомарными операциями.
Термин «ложный» обмен используется, когда у вас есть что-то вроде этого
// Some global array.
int array[MAX_THREADS];
....
// some function that updates the global array
int my_id = thread_id();
array[my_id]++;
Хотя каждый поток имеет свою собственную запись массива, одна и та же строка кэша перебрасывается с одного процессора на другой. Однажды у меня был SMP (до многоядерного) тест Dhrystone, который работал в 0,7 раза быстрее производительности одного процессора при работе на 2 процессорах — потому что ОДИН из общедоступных элементов данных хранился как int array[MAX_THREADS], Это, конечно, довольно экстремальный пример …
Другие решения
Ваш ответ в некотором роде зависит от пользовательских потоков или потоков ядра. Если используемые вами потоки реализованы в пользовательском пространстве, ядро не знает о них, поэтому они не могут работать в истинном «параллельном» режиме для нескольких физических ядер ЦП.
Если потоки реализованы в пространстве ядра, то ядро знает о потоках и может обрабатывать их параллельно с несколькими физическими ядрами процессора.
Существует также накладные расходы на создание потоков, уничтожение и переключение контекста. Каждый раз, когда контекст потока переключается, библиотека потока должна хранить значения и загружать значения и т. Д.