Продолжение статьи: часть 1, часть 2, часть 4

Объем общего кэша

Ухудшение масштабируемости вследствие перегруженности общего кэша означает, что совместное использование КЭШа приводит к большим количествам выгрузок и последующих перезагрузок кэш-линий. В процессорах Intel Core 2 промах на линии кэша последнего уровня (LLC) считается событием L2_LINES_IN.SELF.ANY. Это событие подсчитывает LLC промахи при загрузках, выгрузках, выборке инструкций и аппаратных и программных предвыборках. Для двух обсуждаемых сценариев признаки отличаются, но разница достаточно очевидна. Если объем работы фиксирован, то при непересекающемся параллельном исполнении суммарное количество LLC промахов с ростом числа задействованных ядер не изменится. Если же объем растет с увеличением числа ядер, тогда неизменным остается число промахов на ядро. В любом случае это лишь общее количество, а не метрика, свидетельствующая о характере причины.

Есть несколько причин, по которым эти числа не будут следовать сказанным выше правилам. Например:

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

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

Вторая причина как раз и является главной в этом разделе. Типичным примером может послужить приложение, которое перемножает большие матрицы, при этом данные разбиты на блоки больше чем на половину (полностью?) использующие объем LLC. Распараллеливание может привести к тому, что хотя размер матриц, решаемых каждым потоком или процессом, из-за декомпозиции данных и окажется меньше, но если разбиение на блоки не изменилось, два решателя потребуют для своих данных вдвое больший объем в LLC, что может превысить весь его физический объем. Это выльется в «пробуксовку» КЭШа, когда два таких потока или процесса конкурируют за пространство в КЭШе, вытесняя кэш-линии друг друга. В результате существенно возрастает общее количества загрузок кэш-линий (L2_LINES_IN.SELF.ANY) во всей программе, не связанное с hitm (попадание в строку в состоянии «изменено») доступом к кэш-линии.

Другая методика, позволяющая оценить, насколько ухудшение производительности от случая идеального масштабирова��ия зависит от чрезмерных замещений в КЭШе, состоит в том, чтобы измерить размер рабочего набора данных приложения в случаях с большым и малым количеством узлов. Для этого можно использовать утилиту PIN, которая измеряет Размер Стека КЭШа (CSD) во время двух запусков. Эта методика создает стек КЭШ-линий, добавляя каждое новое обращение к кэш-линии на вершину и считая к стеку, пока предыдущий элемент не найден и удален. Распределение полученных размеров стека – это распределение размеров рабочего набора данных приложения. Относительные расположения существенных пиков или «плеч» в распределении относительно доли каждого ядра в LLC, покажет в какой степени отдельные потоки или процессы преждевременно выгружают кэш-линии друг друга. Таким образом, если два потока или процесса должны работать одновременно с общим LLC, не вмешиваясь друг в друга, размеры рабочих наборов данных должны были бы подогнаны в пределах половины размера КЭШа LLC.

Если такое взаимное вытеснение все же происходит, то степень разбиения данных на блоки была достигнута только для случая, когда один поток или процесс имел доступ ко всему КЭШу. Решение проблемы взаимного вытеснения потоков/процессов требует, чтобы достигнутое разбиение на блоки также масштабировалось во время исполнения так, что множественные потоки/процессы могут сосуществовать в пределах своих долей ограниченного размера КЭШа.

Конечно, при декомпозиции данных, предназначенной для запуска, на множестве ядер и систем (MPI?) возможна ситуация, когда каждому ядру сложно полностью уписаться в кэш, что приводит к большому увеличению трафика по шине, так что это стоит иметь в виду.

Объем буфера трансляции адресов данных (DTLB)

У каждого ядра процессора Intel Core 2 есть специализированная 2-х уровневая система DTLB. Следовательно, в нашем первом сценарии приложение с «разумной» декомпозицией данных должно использовать пропорционально меньшее число записей в DTLB и постоянное число во втором. Если число DTLB промахов увеличивается, это означает, что декомпозиция данных увеличила количество обращений к страницам памяти, в то время как общий размер рабочего набора данных уменьшился или остался прежним.

Одно ясно, что страничное размещение декомпозиции данных в этом случае может быть в значительной степени улучшено. Происходит это обычно в многопоточном приложении, поскольку при разбиении на процессы каждый существует в непересекающемся с другими виртуальном адресном пространстве. Такая ситуация может возникнуть в многопоточном приложении, либо при использовании общей памяти, когда приложение использует многомерные массивы, а разбиение данных произведено по первичной размерности вместо конечной. Такая ситуации легко обнаружима подсчетом события MEM_LOAD_RETIRED.DTLB_MISS (только загрузки и точный режим счета), или DTLB_MISSES.ANY (загрузки и выгрузки, не точный режим).

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

Можно применить другой метод анализа, например, нарисовать гистограмму обращения к виртуальным адресам. Если области доступа не окажутся смежными и последовательными, то тут явно сокрыто множество проблем.

Индивидуальный доступ к кэш-линиям

В процессорах Intel Core 2 доступ и передача данных производится кэш-линиями, представляющими собой 64 смежных байта. При параллельном выполнении с общей памятью возможна конкуренция за доступ к отдельным кэш-линиям. Так, всякий раз, когда два потока, работающие в одном и том же адресном пространстве, оба обращаются к данным в пределах одной из этих кэш-линий на 64 байта, тут возможно возникновение конкуренции за доступ, при которой поток, не являющийся текущим владельцем строки, блокируется. Эта проблема не возможна в случае параллельно исполняющихся процессов, так как каждый из них имеет свое адресное пространство.

Совместное использование кэш-линии не обязательно вызывает конкуренцию за доступ. Протокол работы с кэшем (MESI) учитывает совместное использование данных многоядерной, мультисокетной платформой. Кэш-линия, используемая только для чтения, может использоваться совместно, протокол работы с КЭШем позволяет иметь множество копий кэш-линии у множества ядер. В таком случае копии кэш-линии будут пребывать в так называемом Распределенном состоянии (Shared, S). Как только одна из копий изменена, состояние кэш-линии меняется на Измененное (Modified, M). Эта смена состояния не остается без внимания других ядер, копии которых переходят в Ошибочное состояние (Invalid, I). Кэша-линия может быть помещена в Эксклюзивное состояние (Exclusive, E), если применен префикс блокировки к инструкции доступа к памяти или при использовании инструкции xchg и так далее. В этом случае гарантирован эксклюзивный доступ к кэш-линии. Таков базовый механизм методов синхронизации на основе мьютекс-блокировки, используемых для координирования многопоточной деятельности.

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

Конкуренция за незаблокированные распределенные кэш-линии часто выливается в нестабильное время выполнения, нестабильные значения счетчиков событий производительности и даже результаты. Это происходит из-за того, что разрешение конкурентного состояния зависят от конкретной дискретизации конкурирующих обращений. Если время выполнения нестабильно, но результаты устойчивы, то виной тому неблокируемое ложное совместное использование. Если результаты и время выполнения нестабильны тогда, это — явный признак обращений к неблокируемым действительно совместно используемым кэш-линиям, и часто причиной тому состояние гонки. В этом случае использование Intel Thread Checker чрезвычайно полезно для поиска состояний гонки и сопутствующих условий доступа.

Блокированное совместное использование — основа синхронизации потоков. Конкуренция за блокированную переменную или кэш-линию приводит к последовательному доступу. Это снижает количество работы, которая может выполняться одновременно, что приводит к ухудшению масштабируемости приложения.

События производительности позволяют оценить трафик этих оспариваемых линий. Конкурентный доступ к кэш-линии может вызвать рост числа LLC промахов, вызванных управляемыми загрузками или даже блоками аппаратной предвыборки. Когда загрузка вызывает LLC промах, выполнение может быть приостановлено на полное время ожидания загрузки кэш-линии из памяти. Когда предпринимается выгрузка переменной, необходим запрос на монопольное использование (RFO), чтобы перевести кэш-линии в эксклюзивное состояние. Какие при этом будут последствия для трафика по шине и масштабируемости приложения мы уже обсуждали. Эти аспекты взаимосвязаны, но тут мы рассматриваем проблему с несколько другой стороны.

Есть целый спектр событий, которые полезны для обнаружения подобных проблем доступа. Ниже приведены лишь наиболее очевидные:

EXT_SNOOP.ALL_AGENTS.HITM
MEM_LOAD_RETIRED.L2_LINE_MISS
MEM_LOAD_RETIRED.L2_MISS
BUS_TRANS_BURST.SELF
BUS_TRANS_RFO.SELF
BUS_HITM_DRV
L2_LD.SELF.E_STATE
L2_LD.SELF.I_STATE
L2_LD.SELF.S_STATE

Событие EXT_SNOOP считает, сколько раз LLC промах вызвал ответ «hit-modified» (hitm) от другого ядра на шине. Событие BUS_HITM_DRV имеет «обратное» действие: сколько раз указанное ядро отправило этот ответ. Событие MEM_LOAD_RETIRED работает в режиме точного счета, позволяя узнать точное количество загрузок, вызвавших L2 промах. За время, пока кэш-линия недоступна, этот промах вызовет лишь единичную транзакцию по шине. Так, вариант L2_LINE_MISS этого события считает число запрошенных кэш-линий, а вариант L2_MISS подсчитывает общее количество промахов. Разница между ними указывает на количество обращений к указанной линии, которые произошли между первым промахом, вызвавшим запрос кэш-линии и моментом прихода линии по шине.

Случай неблокируемого ложного совместного использования несколько усложняет ситуацию, в особенности, если блок предвыборки IP L1D идентифицирует кэш промах как некий шаблон доступа и попытается произвести выборку из памяти. Это в частности относится к ситуации ложного совместного использования линии, происходящей в циклах, когда они одновременно выполняются множеством потоков. Трудность здесь в том, что точное событие MEM_LOAD_RETIRED.L2_LINE_MISS проигнорирует промах, так как он приписывается не LLC, а блоку предвыборки IP. Эти LLC промахи будут включены в событие L2_LD.SELF.I_STATE. Однако и тут локализовать проблему поможет MEM_LOAD_RETIRED.L2_MISS. При сравнении значений счетчиков в случае одно и многопоточного счета, внезапный всплеск этого события при большом количестве EXT_SNOOP на графиках VTune Analyzer позволит обнаружить проблемное место.

Поиск и решение проблем масштабируемости на примере многоядерных процессоров Intel Core 2 (часть 3)