"Хорошо распараллеленный" алгоритм не ускоряется несколькими потоками
Извините, что задаю вопрос по теме, о которой я так мало знаю, но эта идея действительно беспокоила меня, и я не смог найти никаких ответов в Интернете.
Фон: я разговаривал с одним из моих друзей, который занимается компьютерными науками. Я занимаюсь в основном специальными разработками, поэтому мое понимание большинства концепций CS находится на функциональном уровне (я знаю, как их использовать, а не как они работают). Он говорил, что преобразование "хорошо распараллеленного" алгоритма, работавшего в одном потоке, в алгоритм, работающий в нескольких потоках, не привело к ожидаемому увеличению скорости обработки.
Обоснование: я спросил его, какова архитектура компьютера, на котором он запускал этот алгоритм, и он ответил, что он 16-ядерный (не виртуализированный). Согласно тому, что я знаю о многоядерных процессорах, увеличение скорости обработки алгоритма, работающего на нескольких ядрах, должно быть примерно пропорционально тому, насколько хорошо он распараллелен.
Вопрос: Как алгоритм, который "хорошо распараллелен" и правильно запрограммирован для работы на настоящем многоядерном процессоре, не может работать в несколько раз быстрее? Есть ли какая-то информация, которую я здесь упускаю, или это скорее проблема с реализацией?
Другие вещи: я спросил, могут ли потоки потреблять больше энергии, чем было доступно любому отдельному ядру, и, очевидно, каждое ядро работает на частоте 3,4 ГГц. Это намного больше, чем нужно алгоритму, и при выполнении диагностики ядра не достигают максимума во время выполнения.
2 ответа
Вероятно, что-то делится. То, что делится, может быть неочевидным.
Одним из наиболее распространенных неочевидных общих ресурсов является кеш процессора. Если потоки обновляют ту же строку кэша, что строка кэша должна отскочить между процессорами, замедляя все.
Это может произойти из-за обращения к (даже доступным только для чтения) переменным, которые находятся рядом друг с другом в памяти. Если все обращения доступны только для чтения, это нормально, но если хотя бы один процессор записывает в эту строку кэша, это вызовет отскок.
Метод грубой силы исправления этого заключается в размещении общих переменных в структурах, которые выглядят следующим образом:
struct var_struct {
int value;
char padding[128];
};
Вместо жесткого кодирования 128 вы можете исследовать, какой системный параметр или макросы препроцессора определяют размер строки кэша для вашего типа системы.
Другое место, где может происходить совместное использование, находится внутри системных вызовов. Даже, казалось бы, невинные функции могут брать глобальные блокировки. Кажется, я вспоминаю, как читал о том, как Linux исправил проблему, подобную этой, с помощью блокировок функций, которые возвращают идентификаторы процессов, потоков и родительские идентификаторы.
Производительность в зависимости от количества ядер часто представляет собой S-образную кривую - сначала она, очевидно, увеличивается, но поскольку блокировка, общий кэш и т. П. Берут на себя долги, другие ядра не добавляют так много и даже могут ухудшиться. Отсюда ничего загадочного. Если бы мы знали больше деталей об алгоритме, возможно, было бы возможно найти идею, чтобы ускорить его.