Я работаю над высококонкурентной программой на C, она хорошо масштабируется, когда число ядер меньше 8, но отказывается масштабировать более 8 ядер.
Я подозреваю, что пропускная способность памяти является узким местом, как я могу проверить, верно ли это?
Есть ли какой-либо инструмент/метод/функция ОС, которые могут помочь в диагностике?
У меня была эта проблема самостоятельно на машине NUMA 96x8.
В 90% случаев проблема связана с синхронизацией памяти/кэша. Если вы часто вызываете процедуры синхронизации (атомы, мьютексы), то соответствующая строка кэша должна быть недействительной во всех сокетах, что приводит к полной блокировке всей шины памяти в течение нескольких циклов.
Вы можете профилировать это, запустив профайлер, например Intel VTune или Perfsuite и запишите, как долго их атомы берут. Если вы используете их правильно, они должны взять что-то между 10-40 циклами. Худший сценарий, который у меня был, был 300 циклов при масштабировании моего многопоточного приложения до 8 сокетов (8x8 ядер на Intel Xeon).
Другой простой шаг профилирования, который вы можете сделать, заключается в компиляции без каких-либо атомических/мьютексов (если это позволяет ваш код) и запускать его на нескольких сокетах, тогда он должен работать быстро (неправильно, но быстро).
Причина, по которой ваш код работает быстро на 8 ядрах, заключается в том, что процессоры Intel используют кеш-блокировку при выполнении атомарности, пока вы держите все на одном физическом чипе (сокете). Если блокировка должна идти на шину памяти - это когда вещи становятся уродливыми.
Единственное, что я могу предложить: уменьшить масштаб, как часто вы вызываете процедуры атомизации/синхронизации.
Что касается моего приложения: мне пришлось реализовать практически блокирующую структуру данных, чтобы масштабировать мой код за пределами одного сокета. Каждый поток накапливает действия, требующие блокировки, и регулярно проверяет его на свою очередь, чтобы очистить их. Затем пропустите маркер и по очереди промойте действия синхронизации. Очевидно, что работает только в том случае, если у вас есть достаточная работа для ожидания.
+1 для хорошего вопроса.
Сначала я хочу сказать, что есть другие факторы, которые следует учитывать, например. синхронизацию кэш-памяти или неизбежную часть сериализации, такую как операции с атомной памятью, которые также являются возможными узкими местами и легче проверять пропускную способность памяти.
Что касается пропускной способности памяти, то у меня сейчас есть наивная идея, которая заключается в том, чтобы запустить простой демон для использования пропускной способности памяти при профилировании вашего приложения, просто повторив доступ к основной памяти (обязательно рассмотрите вопрос о существовании кэш). С демоном вы можете настраивать и записывать используемую пропускную способность памяти и сравнивать этот результат с производительностью вашего приложения.
Извините за предоставление такого неряшливого ответа.. хотя это выполнимо XD
EDITED: Также см. Как измерить пропускную способность памяти, используемую в настоящее время в Linux? и Как я могу наблюдать за пропускной способностью памяти?
Хотя было бы полезно получить больше информации об алгоритме и платформе, в целом существует целый ряд причин, по которым приложение не масштабируется:
Использование явной синхронизации (мьютексы/атоматика/транзакции и т.д.): синхронизация в параллельной программе означает, что вы создаете несколько секвенциальных секций, когда вам нужно разделить ресурс между несколькими потоками. Чем больше потоков, которые хотят получить доступ к критическому разделу (атомная операция - очень маленький критический раздел), тем больше у вас конкурентов и тем больше ваша масштабируемость ограничена, так как ядра чередуются в критический раздел. Уменьшение размера критических разделов и выбор различных структур данных/алгоритмов может уменьшить это, если приватизация ресурса невозможна.
Ложное совместное использование: два или более потока, совместно использующих несвязанные объекты, которые попадают в один и тот же блок кэша. Это обычно легко обнаружить, увидев увеличение пропусков кеша при масштабировании приложения от одного ядра к другому и от одного сокета до более одного сокета. Выравнивание структур данных с размером блока кэша обычно решает это. См. Также Устранить False Sharing - Dr Dobb's
Распределение памяти/освобождение памяти: в то время как выделение памяти даст вам фрагменты памяти для работы, которые могут работать, у вас может возникнуть конфликт либо при распределении, либо даже при освобождении памяти. Может быть решена с помощью масштабируемого потокобезопасного распределителя памяти, такого как масштабируемый распределитель Intel TBB, Hoard и другие.
Холостые потоки: есть ли у вашего алгоритма модель производителя/потребителя, и может быть, вы потребляете быстрее, чем вы производите? Является ли ваш размер данных достаточно большим, чтобы амортизировать стоимость распараллеливания и что вы не теряете скорость, теряя местность? Является ли ваш алгоритм неотъемлемым по какой-либо другой причине? Вы, вероятно, должны рассказать нам что-то о вашей платформе и вашем алгоритме. Советник Intel - достойный инструмент для проверки наилучшего способа распараллеливания.
Параллельная структура: что вы используете? OpenMP, Intel TBB, что-то еще? Чистые потоки? Вы, может быть, развиваете/присоединяетесь слишком много или перераспределяете свою проблему? Является ли ваша среда выполнения самой масштабируемой?
Другие технические причины: неправильное связывание потоков с ядрами (возможно, несколько потоков заканчиваются на одном и том же ядре), функции параллельной среды выполнения (Intel OpenMP runtime имеет дополнительный скрытый поток, эта дополнительная нить на том же ядре, что и основной поток, разрушая ваш день) и т.д.
По моему опыту, я считаю, что как только вы устраните все вышеперечисленное, вы можете начать подозревать пропускную способность памяти. Вы можете легко проверить это с помощью STREAM, который может рассказать вам, является ли ваша пропускная способность памяти ограничивающим фактором. В веб-узле Intel есть article, в котором объясняется, как определить насыщенность полосы пропускания памяти.
Если ни одно из вышеперечисленных не является окончательным, у вас может быть ограниченная масштабируемость по протоколу когерентного протокола и/или NUMA (неравномерный доступ к памяти, хорошая статья в acmqueue). Всякий раз, когда вы обращаетесь к некоторому объекту в памяти, вы либо генерируете запросы о недопустимости кэширования (вы делитесь чем-то, и запускаете протокол согласованности кеша), либо вы получаете доступ к памяти, которая живет в банке ближе к другому сокету (вы проходите через межсоединение процессора).