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

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

Предположим, у меня есть макет памяти, как показано ниже

int output[100];

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

3 ответа

Решение

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

В большинстве ситуаций 0,2,4.../1,3,5... значительно замедляют производительность, вплоть до, возможно, медленнее, чем один процессор. Херб Саттерс "Устранить ложный обмен" демонстрирует это очень хорошо.

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

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

Например, недавние многоядерные процессоры Intel имеют кэши L1 для каждого ядра и кэш L2, которые совместно используются ядрами в одном и том же пакете CPU; однако разные пакеты ЦП будут иметь свои собственные кэши 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 с помощью этого вывода - например, вы можете вручную добавить некоторые отступы, чтобы ваш struct кратно размеру строки кэша.

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

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

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

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

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

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

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

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

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

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

Другие вопросы по тегам