Несколько потоков и кэш процессора

Question

Я реализую операцию фильтрации изображений в C с использованием нескольких потоков и максимально оптимизирую ее.У меня есть один вопрос: если поток доступен к потоку-0, и одновременно, если поток-1 обращается к той же памяти, он получит его из кэша?Этот вопрос связан с возможностью того, что эти два потока могут работать в двух разных ядрах ЦП.Итак, еще один способ выразить это: все ли ядра используют одну и ту же общую кэш-память?

Предположим, у меня есть структура памяти, подобная следующей

int output [100];

Предположим, что есть два ядра ЦП, и поэтому я порождаю два потока для одновременной работы.Одной из схем может быть разделение памяти на два фрагмента, 0-49 и 50-99, и позволить каждому потоку работать с каждым фрагментом.Другой способ может позволить потоку 0 работать с четными индексами, такими как 0 2 4 и т. Д., В то время как другой поток работает с нечетными индексами, такими как 1 3 5 .... Этот более поздний метод проще реализовать (особенно для 3Dданные), но я не уверен, что смог бы эффективно использовать кеш таким образом.

Answer 1

Ответ на этот вопрос сильно зависит от архитектуры и уровня кэша, а также от того, где на самом деле работают потоки.

Например, недавние многоядерные процессоры Intel имеют кэш-память L1 для каждого ядра.и кэш L2, который совместно используется ядрами в одном и том же пакете ЦП;однако разные пакеты ЦП будут иметь свои собственные кэши L2.

Даже в том случае, если ваши потоки работают на двух ядрах в одном пакете, даже если оба потока обращаются к данным в пределах одной и той же кеш-линии, у вас будет эта подпрыгиваниемежду двумя кешами L1. очень неэффективно, и вы должны разработать свой алгоритм, чтобы избежать этой ситуации.

---

В нескольких комментариях спрашивалось, как избежать этой проблемы.

В сущности, это на самом деле не особенно сложно - вы просто хотите избежать одновременной попытки доступа двух потоков к данным, расположенным в одной строке кэша, где по крайней мере один поток записывает данные.(Поскольку все потоки только читают данные, проблем нет - на большинстве архитектур данные только для чтения могут присутствовать в нескольких кэшах).

Для этого вам нужнонеобходимо знать размер строки кэша - это зависит от архитектуры, но в настоящее время большинство чипов семейства x86 и x86-64 используют 64-байтовую строку кэша (обратитесь к руководству по архитектуре для других архитектур).Вам также необходимо знать размер ваших структур данных.

Если вы попросите свой компилятор выровнять интересующую общую структуру данных по границе в 64 байта (например, ваш массив output), то выЗнайте, что он начнется в начале строки кэша, и вы также можете вычислить, где находятся границы последующих строк кэша.Если ваш int равен 4 байта, то каждая строка кэша будет содержать ровно 8 int значений.До тех пор, пока массив начинается на границе линии кеша, с output[0] по output[7] будет на одной строке кеша, а с output[8] до output[15] на следующей.В этом случае вы должны разработать свой алгоритм так, чтобы каждый поток работал с блоком смежных int значений, кратных 8.

Если вы храните сложные struct типы, а не простые int, утилита pahole будет полезна.Он проанализирует типы struct в вашем скомпилированном двоичном файле и покажет вам макет (включая отступы) и общий размер.Затем вы можете настроить struct s, используя этот вывод - например, вы можете вручную добавить некоторые отступы, чтобы ваш struct был кратным размеру строки кэша.

В системах POSIXФункция posix_memalign() полезна для выделения блока памяти с указанным выравниванием.

Answer 2

Как правило, плохая идея - совместно использовать перекрывающиеся области памяти, например, если один поток обрабатывает 0,2,4 ... а другой обрабатывает 1,3,5 ... Хотя некоторые архитектуры могут поддерживать это, большинство архитектурнет, и вы, вероятно, не можете указать, на каких машинах будет выполняться ваш код.Также ОС может свободно назначать ваш код любому ядру (одному, двум на одном физическом процессоре или двум ядрам на разных процессорах).Кроме того, каждый ЦП обычно имеет отдельный кэш первого уровня, даже если он находится на одном и том же процессоре.

В большинстве случаев 0,2,4 ... / 1,3,5 ... значительно снижает производительностьвплоть до, возможно, медленнее, чем один процессор.Херб Саттерс «Ликвидация ложного обмена» демонстрирует это очень хорошо.

Использование схем [... n / 2-1] и [n / 2 ... n] будет значительно лучше масштабироваться в большинстве систем.Это даже может привести к суперлинейной производительности, поскольку возможно использование размера кеша всех процессоров в сумме.Количество используемых потоков должно быть всегда настраиваемым и по умолчанию должно соответствовать числу найденных ядер процессора.

Answer 3

Документация Intel

Intel публикует таблиц для каждого поколения , которые могут содержать такую ​​информацию.

Например, для процессора i5-3210M, который у меня был на моем старом компьютере, я ищу 3-го поколения - Таблица данных Том 1 3.3 «Технология Intel Hyper-Threading (Intel HT Technology)» говорит :

Процессор поддерживает технологию Intel Hyper-Threading (Intel HT Technology) это позволяет ядру выполнения функционировать как два логических процессора. Хотя некоторые ресурсы выполнения, такие как кэши, блоки выполнения и шины, являются общими, каждый Логический процессор имеет свое собственное архитектурное состояние с собственным набором регистров общего назначения и регистров управления.

, который подтверждает, что кэши являются общими в данной гиперпотоке для этого поколения процессоров.

Смотри также:

• аналогичный вопрос для совместного использования кэша между ядрами: Как кэш-память распределяется в многоядерных процессорах Intel?
• дальнейший анализ потоков против ядер: https://superuser.com/questions/133082/what-is-the-difference-between-hyper-threading-and-multiple-cores/995858#995858
• сама спецификация архитектуры также содержит раздел о совместном использовании определенных ресурсов, который должен быть действителен во всех реализациях, хотя в нем не упоминаются кэши: Как выглядит многоядерный язык ассемблера?

Answer 4

Возможно, я ошибаюсь, но от того, используется ли кэш ядра, зависит от реализации процессора.Вам нужно поискать технические листы на странице производителя, чтобы проверить, имеет ли каждое ядро ​​в вашем ЦП свой кеш или общий кеш.

Я также работал над обработкой изображений для безопасности.компания и иногда мы получили поврежденные изображения после запуска пакетных операций над потоками.После долгих исследований мы пришли к выводу, что кэш был разделен между ядрами ЦП и что в редких случаях данные перезаписывались или заменялись неверными данными.

Является ли это чем-то, что следует учитывать или скореередкое событие, которое я не могу ответить.