Хабраиндекс
426,09
10 мая 2012 в 13:54

Делиться не всегда полезно: оптимизируем работу с кэш-памятью

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

Мы все «немного читали» об оптимизации работы с памятью, и у нас отложилось, что полезно, когда «кэш остается горячим», то есть данные, к которым часто обращаются потоки, должны быть компактными и находиться в ближайшем к процессорному ядру кэше. Все так, но когда дело доходит до того, чтобы делиться доступом, потоки становятся злейшими врагами [производительности], а кэш не просто горячий, он аж «горит адским огнем» – такая во круг него разворачивается борьба.

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


Рассмотрим случай, который хорошо описан в Intel®64 and IA-32 Architectures Optimization Manual, однако про который программисты часто забывают, работая со массивами структур в могопоточном режиме. Они допускают обращение (с модификацией) потоков к данным структур, расположенных очень близко друг к другу, а именно в блоке, равном длине одной кэш-линии (64 байт). Мы это называем Сache line sharing. Существует два типа разделения кэш-линий: true sharing и false sharing.
True sharing (истинное разделение) – это когда потоки имеют доступ к одному и тому же объекту памяти, например, общей переменной или примитиву синхронизации. False sharing (от лукавого) – это доступ к разным данным, но по каким-то причинам, оказавшимся в одной кэш-линии процессора. Сразу отметим, что и тот, и другой случай вредит производительности из-за необходимости аппаратной синхронизации кэш-памяти процессора, однако если первый случай часто неизбежен, то второй можно и нужно исключать.

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

image
Условия для возниконовения проблемы:
Два или более потока пишут в одну кэш-линию;
Один поток пишет, остальные читают из кэш-линии;
Один поток пишет, в остальных ядрах стработал HW prefetcher.


Может оказаться, что переменные в полях разных структур так расположились в памяти, что будучи считанными в L1 кэш процессора, находятся в одной кэш-линии, как на рисунке. При этом, если один из потоков модифицирует поле своей структуры, то вся кэш-линия в соответствии с cache coherency протоколом объявляется невалидной для остальных ядер процессора. Другой поток уже не сможет пользоваться своей структурой, несмотря на то, что она уже лежит в L1 кэше его ядра. В старых процессорах типа P4 в такой ситуации потребовалась бы долгая синхронизация с основной памятью, то есть модифицированные данные были бы отправлены в основную память и потом считаны в L1 кэш другого ядра. В текущем поколении процессоров (кодовое имя Sandy Bridge) синхронизационным механизмом используется общий кэш третьего уровня (или LLC – Last Level Cache), который является инклюзивным для подсистемы кэш-памяти и в котором располагаются все данные, находящиеся как в L2, так и в L1 всех ядер процессора. Таким образом, синхронизация происходит не с основной памятью, а с LLC, являющегося частью реализации протокола механизма когерентности кэшей, что намного быстрее. Но она все равно происходит, и на это требуется время, хотя и измеряемое всего несколькими десятками тактов процессора. А если данные в кэш-линии разделяются между потоками, которые выполняются в разных физических процессорах? Тогда уже придется синхнонизироваться между LLC разных чипов, а это намного дольше — уже сотни тактов. Теперь представим, что программа только и занимается тем, что в цикле обрабатывает поток данных, получаемых из какого-либо источника. Теряя сотни тактов на каждой итерации цикла, мы рискуем «уронить» свою производительность в разы.

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

Потоковая функция в цикле пробегает по двум массивам float a[i] и b[i], перемножает их значения по индексу массива и складывает в локальные переменные потоков localSum[tid]. Для усиления эффекта эта операция делается несколько (ITERATIONS) раз.

int work(void *pArg) 
{
	int j = 0, i = 0;
	int tid = (int) pArg;
	for (j = 0; j < ITERATIONS; j++){
	  for (i = tid; i < MAXSIZE; i+= NUM_PROCS){
		a[i] = i + a[i] * b[i];
		localSum[tid] += a[i];}}
}


Беда в том, что для разделения данных между потоками выбран способ перемежевания индексов цикла. То есть, если у нас работают два потока, первый будет обращаться к элементам массивов a[0] и b[0], второй — к элементам a[1] и b[1], первый — a[2] и b[2], второй — a[3] и b[3], и так далее. При этом элементы массива a[i] модифицируются потоками. Не трудно видеть, что в одну кэш-линию попадут 16 элементов массива, и потоки будут одновременно доступаться к соседним элементам, «сводя с ума» механизм синхрониции кэшей процессора.

image

Самое неприятное в том, что мы даже не заметим по работе программы существование этой проблемы. Она будет просто работать медленнее, чем может, вот и все. Как оценить эффективность программы с помощью профилировщика VTune Amplifier XE, я уже описывал в одном из постов на Хабре. Используя профиль General Exploration, о котором я там упоминал, можно увидеть описываемую проблему, которая будет «подсвечена» инструментом в результатах профилировки в колонке Contested Access. Эта метрика как раз и измеряет соотношение циклов, потраченых на синхронизацию кэшей процессора при их модификации потоками.

image

Если кому-то интересно, что стоит за этой метрикой, то во время комплексной профилировки инструмент среди других аппаратных счетчиков собирает и данные счетчика:
MEM_LOAD_UOPS_LLC_HIT_RETIRED.XSNP_HITM_PS – Точный счетчик(PS) выполненной(RETIRED) операции(OUPS) загрузки(LOAD) данных(MEM), которые оказалиcь(HIT) в LLC и модифицированны(M). «Точный» счетчик означает, что данные, собранные таким счетчиком в семплировании, относятся к указателю инструкции (IP), следующему после инструкции, которая была той самой загрузкой, приведшей к синхронизации кэшей. Набрав статистику по этой метрике, мы можем с определенной точностью указать адрес инструкции, и, соответственно, строку исходного кода, где производилось чтение. VTune Amplifier XE может показать, какие потоки читали эти данные, а дальше мы уже должны сами сориентироваться, как реализован многопоточный доступ к данным и как исправить ситуацию.

image

Относительно нашего простого примера ситуацию исправить очень легко. Нужно просто разделить данные на блоки, при этом количество блоков будет равно количеству потоков. Кто-то может возразить: если массивы достаточно большие, то блоки могут просто не вместиться в кэш, и данные, загружаемые из памяти для каждого потока, будут вытеснять друг друга из кэша. Это будет верно в случае, если все данные блока используются постоянно, а не один раз. Например, при перемножении матриц мы пройдемся по элементам двумерного массива сначала по строкам, потом по столбцам. И если обе матрицы не помещаются в кэш (любого уровня), то они буду вытеснены, а повторный доступ к элементам потребует повторной загрузки из следующего уровня, что негативно влияет на производительность. В общем случае с матрицами применяется модифицированное перемножение матриц поблочно, при этом матрицы разбиваются на блоки, которые заведомо помещаются в заданную кэш-память, что значительно увеличивает производительность алгоритма.

int work(void *pArg) 
{
	int j = 0, i = 0;
	int tid = (int) pArg;

	for (j = 0; j < ITERATIONS; j++){
		chunks = MAXSIZE / NUM_PROCS;
		for (i = tid * chunks; i < (tid + 1) * chunks; i++){
			a[i] = i + a[i] * b[i];
			 localSum[tid] += a[i];}}
}


False sharing
image
No False sharing
image
Сравнение доступа потоков к элементам массива в случае False sharing и в исправленном коде

В нашем простом случае данные используются всего один раз, и даже если они будут вытеснены из кэш-памяти, они нам уже не понадобятся. А о том, чтобы данные обоих массивов a[i] и b[i], расположенные далеко друг от друга в адресном пространстве, вовремя оказались в кэше позаботится аппаратный prefetcher – механизм подкачки данных из основной памяти, реализованный в процессоре. Он отлично работает, если доступ к элементам массива последовательный.

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

Если вы работаете со структурами данных в многопоточном режиме, уделите внимание их размеру. Используйте «подкладки» (padding), чтобы нарастить размер структуры до 64 байт:
struct data_packet
{
	int address[4];
	int data[8];
	int attribute;
	int padding[3];
}

Выделяйте память под структуры по выровненному адресу:
__declspec(align(64)) struct data_packet sendpack

Используйте массивы структур вместо структур массивов:
data_packet sendpack[NUM];

вместо
struct data_packet
{
	int address[4][NUM];
	int data[8][NUM];
	int attribute[NUM];
}

Как видно, в последнем случае потоки, модифицирующие одно из полей, приведут к запуску механизма синхронизации кэш-памяти.

Для объектов, аллоцируемых в динамической памяти с помощью malloc или new, cоздавайте локальные пулы памяти для потоков, либо используйте параллельные библиотеки, которые сами умеют это делать. Например, библиотека TBB содержит масштабируемые и выравнивающие аллокаторы, которые полезно использовать для масштабируемости многопоточных программ.

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

P.S. Попробуйте мой примерчик, и расскажите, на сколько процентов увеличилось быстродействие теста на вашей платформе.
+64
17289
146
vtsymbal 18,6

Комментарии (30)

0
mejedi, #
Я думаю, читателям было бы интересно узнать, как именно обеспечивается когерентность кешей на нескольких ядрах (MESI протокол?).
+5
vtsymbal, #
MESI — это базовый протокол синхронизации кэшей, ранее использовавшийся в микроархитектурой с общей шиной (FSB). Сейчас, с переходом на QPI используют модифицированный протокол MESIF. Программистам, даже тем, кто оптимизирует для микроархитектуры, подробности реализации алгоритма будут в основном скучны — мне так кажется. Но если действительно интересно, то можно почитать интересную статейку, где сравниваются несколько протоколов, актуальных на данный момент.
0
mejedi, #
Может быть с точки зрения программиста разницу между MESI и MESIF понимать не нужно. Но не рассказав про тот же MESI крайне сложно объяснить, в чем проблема с false sharing.
+5
vtsymbal, #
Если честно, я не согласен, что для понимания проблемы false sharing необходимо объяснять весь принцип работы протокола когерентности кэша. Я просто упомянул следствие его работы — перевод кэш-линии в состояние невалидной при модификации ее элементов. И далее, заметил, что для восстановления идентичности данных в кэшах ядер (синхронизация) требуется некоторое время (которое теряет наша программа).

Понять прицип работы протокола можно, пойдя по ссылкам. А загружать свой пост такими подробностями было бы жестоко по отношению к читателям. Меня и так слегка пинают за излишнюю избыточность и сложность моих обзоров. Поэтому я попробовал соблюсти разумный баланс.
+7
OnYourLips, #
Метод с картинкой для привлечения внимания работает.
0
DaHacka, #
Открыл топик и первым делом стал искать подобные комментарии :)
+2
OnYourLips, #
Именно это я и хотел написать, но такого комментария не нашел.
0
mark_ablov, #
Конкурентная read-read производительность при обращение к одной линейки же ок.
В статье это не указано явно, и может создаться неверное впечатление, что false sharing это всегда плохо, и нужно его лечить.
Кстати, меня всегда волновал вопрос актуальности оптимизации операций с кэшем в современных не-RT осях. Там же запущенно 100500 процессов в фоне, которые вполне вероятно обращаются к данным в памяти, и мусорят в L1/L2 кэше и портят производительность оптимизированным программам!
0
vtsymbal, #
Обращение к одной кэш-линии по чтению всеми потоками с высокой производительностью — это, собственно, главное назначение и сама суть системы организации памяти, поэтому я даже не догадался об этом написать. Но замечание верное.

Что касается 100500 потоков в системе — нас это не должно сильно волновать, так как эти потоки принадлежат разным процессам, которым операционная система предоставляет доступ, переключая контекст. Это все-рано приводит к вытеснению данных из кэшей, если все процессы активно работают и используют память. С этим ничего не поделать. Другое дело — одни процесс, наша программа, которую мы оптимизируем. Мы можем иметь сколько угодно потоков (число ограничено лимитами ресурсов ОС), но они должны «спать», а активными, т.к. готовыми к исполнению, должно быть количество потоков, равное числу логических процессоров в системе — тогда баланс будет соблюден. Дальше уже требуется работать над оптимизацией расположения данных в кэш-памяти.
0
mark_ablov, #
> Это все-рано приводит к вытеснению данных из кэшей, если все процессы активно работают и используют память

Дык о том и речь, что может получиться так что оптимизация по кэшу срабатывать будет крайне редко, ибо есть другие процессы, которые портят кэш. Вот поэтому и возникает вопрос, насколько это эффективно в реальных, а не эталонных, системах.
Правда, с другой стороны само переключение контекстов занимает сотни, а то и тысячи тактов, и можно, наверно, забить на потери при cache-miss'ах при возобновлении потока.
+3
vtsymbal, #
В случае системы, в которой работают много процессов, нагружающих память, оптимизация будет работать в рамках кванта времени, выделенного на наш процесс. Но это тоже важно, так как в относительных величинах программа бутет все-рано работать быстрее.
Вы правы, переключение контекстов занимает больше тысячи тактов, и забить можно на потери при cache-miss'aх которые возникнут при заполнении кэшей данными заново, а вот на остальные cache-miss'ы забивать не надо )
0
izard, #
Проблема, которую вы описываете, играет существенную роль для систем с общим LLC, на которых на разных ядрах исполняются RT и GPOS, с или без виртуализации. Если цикл для RT системы порядка сотен микросекунд с толерантностью в десятки микросекунд, вытеснения данных RT процесса из LLC действительно будет критичным.

В ARM есть Cache lock down, которые это решает, в x86 (пока) нет.
0
spanasik, #
Так на сколько, в результате, увеличивается скорость?
0
leventov, #
Подскажите пожалуйста, кто ответственен за распределение потоков по ядрам на процессоре с HyperThreading (для уменьшения борьбы за L1/L2) — программист или ОС?
+3
vtsymbal, #
По-умолчанию, ОС сама назначает исполнение потоков в логических процессорах. Но в случаях, когда это оправдано с точки зрения производительности, программист может сам привязывать потоки к процессорам с помощью механизма аффинитизации — наиболее часто применяется для NUMA-платформ, где бывает важно данные локализовать в «своей» памяти процессора. Привязка к процессорам для улучшения работы кэшей неэффективна.
Вот есть статейка про HT, как его использовать эффективно.
0
leventov, #
Спасибо
0
shodan, #
> P.S. Попробуйте мой примерчик, и расскажите, на сколько процентов увеличилось быстродействие теста на вашей платформе.

Ну, для этого полную готовую программу выложить было бы неплохо, наверное? Хотя бы исходник, про бинарник уж молчу.
+4
vtsymbal, #
Да, было бы неплохо…

«Так вы что, и конфеты за меня есть будете?!.. — АГА!!!»
[Вовка в Тридевятом царстве]
0
vtsymbal, #
Это был ответ на:
>Ну, для этого полную готовую программу выложить было бы неплохо, наверное?
–1
gricom, #
Т.к. начинаю понемногу баловаться с OpenCL, то написал простенький kernel (в OpenCL так называется код, который выполняется на устройстве в несколько потоков) для заполнения матрицы размером 16*16. Запустил 5 млн итераций. Процессор Intel Core i5 650 (3.2 GHz), OS Ubuntu 10.04 x64

1) Кол-во потоков: 256, время выполнения: 69 сек
2) Кол-во потоков: 16, время выполнения: 63 сек
+1
mark_ablov, #
Оптимальное количество потоков обычно берут как 2 * количество логических процессоров.
Больше — редко когда эффективно для вычислительных задач.
+5
vtsymbal, #
Оптимальное количество _активных_ потоков, все же, мы считаем = количество логических процессоров.
+1
SysHalt, #
Работаю с SoC имеющей 2 ядра с кешем, но с отсутствующим механизмом когерентности кешей. Основные правила:
+1
SysHalt, #
1. Не использовать глобальные переменные
+1
SysHalt, #
2. Если все же без глобальных переменных не обойтись, то выравнить их по длине кеш линии (16 байт в моем случае).
3. Попытаться сгруппировать глобальные переменные в структуры, чтобы избежать траты памяти из-за padding байт.
3. Использовать некешируемый доступ к этой переменной/структуре.

0
vtsymbal, #
Кстати, о масштабируемых аллокаторах TBB теперь можно почитать в HTML версии Справочного руководства Intel® TBB на нашем опен-сорс сайте: threadingbuildingblocks.org/docs/help/
0
sluge, #
осталость выяснить, сохранится ли выигрыш в производительности, если пользователь запустит эту программу под Atom, AMD Fusion или вообще под виртуальной машиной
0
vtsymbal, #
Под Atom не думаю, что будет сильный прирост, а вообще, для любой сисиемы актуально, где используется кэширование памяти. Особенно если это многопроцессорная система.
0
etl, #
перестали работать картинки
The server encountered an internal error or misconfiguration and was unable to complete your request.
0
vtsymbal, #
Исправлено. Спасибо.

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