LINUX.ORG.RU

Паралельный доступ к памяти

 , , , ,


1

6

Имеем два ядра и массив структур. Этот массив хочется обрабатывать параллельно и без блокировок и синхронизаций. Данные меньше размера кеш линии поэтому если передать как есть две структуры будут лежать в одной кеш линии и попадут вместе в L1 каждого из ядер и даже если запись происходит в разные места то будет взаимоблокировка с синхронизацией. Поэтому я увеличиваю размер структур до размера кеш линии теперь каждое ядро загружает в L1 независимые данные и могут их обработать без блокировок. Также и то и то лежит в одном массиве размером со страницу памяти. Что исключает работы ядер с двумя таблицами адресации и переключениями между ними.

Помимо этого я ещё передаю в оба потока указатель на одну и туже структуру но эту структуру потоки будут только читать.

Вопрос - всегда ли данные которые лежат в 1 кеш линии попав в L1 отдельных ядер вызывают процесс синхронизации? Или это происходит только тогда когда данные изменяются? Ну тоесть память помечается как неактуальная и L1 другого ядра вынуждено перезагрузить данные снова. Хотя они уже были.

Я сейчас не говорю про атомарность, мутексы и прочее. Тут дело в том что всё должно быть без этого.

Ответ на: комментарий от LINUX-ORG-RU

если честно, для человека далекого ...

это всё выглядит как попытка обмануть компилятор :) Но результаты будут интересны.

Наивный вопрос: использование OpenMP для цикла будет не достаточно?

sshestov
()

отвечаем на ваш вопрос.

есть протокол MESI. изучи его.

как он работает:

у тебя есть ДВЕ очереди записи. они именуются очередью записи адреса и очередью записи данных например в Pentium 2 но это не важно - оно везде так. то же самое кстати на AMD K6 только там это честно рассказано в доках.

суть первой очереди в том, что данные пишутся в миникэш а вовсе не в L1. а вторая очередь из миникэша данные копирует в L1.

Соответсвенно чтения сперва идут из очереди миникэша а только потом из кэша. Отсюда такие АДОВЫЕ просеры скрости когда пишешь байт а читаешь 4-8-16 байт. Я видел сам как оптимизированный код + такая кака вместо х3-х5 производительности давал 80% от сишного. Привет сраному gcc.

атомарные операции кстати работают используя MESI. как минимум на интеле. То есть: они просто вытаскивают линейку кэша к себе, делают операцию а дальше ЕСЛИ линейку утащили идут на новый цикл. Я кажется знаю ещё одну уязвимость в штеудах :)

TSX точно также работает но лочит много линеек. Лочит - это надо понимать в кавычках и даже для обычного lock. Просто обычный lock походу транслируется в цикл внутри проца.

example_cat
()

Вопрос - всегда ли данные которые лежат в 1 кеш линии попав в L1 отдельных ядер вызывают процесс синхронизации?

Нет никакого процесса синхронизации. Следующий вопрос.

byko3y ★★★★
()
Ответ на: комментарий от example_cat

у тебя есть ДВЕ очереди записи. они именуются очередью записи адреса и очередью записи данных например в Pentium 2 но это не важно - оно везде так. то же самое кстати на AMD K6 только там это честно рассказано в доках.
суть первой очереди в том, что данные пишутся в миникэш а вовсе не в L1. а вторая очередь из миникэша данные копирует в L1.
Соответсвенно чтения сперва идут из очереди миникэша а только потом из кэша. Отсюда такие АДОВЫЕ просеры скрости когда пишешь байт а читаешь 4-8-16 байт. Я видел сам как оптимизированный код + такая кака вместо х3-х5 производительности давал 80% от сишного. Привет сраному gcc.

Я в курсе очередей записи в x86, но я первый раз слышу про такие странные выводы про «АДОВЫЕ просеры скрости когда пишешь байт а читаешь 4-8-16 байт». Можно подробности?

атомарные операции кстати работают используя MESI. как минимум на интеле. То есть: они просто вытаскивают линейку кэша к себе, делают операцию а дальше ЕСЛИ линейку утащили идут на новый цикл. Я кажется знаю ещё одну уязвимость в штеудах

Блокируется доступ ко всей линии кэша, по крайней мере на однопроцессорной машине x86 последние лет 10-15.

byko3y ★★★★
()
Ответ на: комментарий от byko3y

подробности можешь проверить сам, записывая байт и читая __m128i.

Блокируется доступ ко всей линии кэша

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

так вот, на х86 уже давно ничего не блокируется. просто строка помечается как M, а дальше если она была «утащена» операция просто перезапускается.

example_cat
()
Ответ на: комментарий от byko3y

Ты не работаешь что ли? Как не зайдешь в каждой бочке затычка.

Liz812
()

Поэтому я увеличиваю размер структур до размера кеш линии

Похоже, ты пытаешься обрабатывать данные как 1234123412341234 вместо 1111222233334444. Зачем? Не проще поделить массив структур на сплошные куски по количеству нитей обработки?

i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

то что ты пишешь - это ближе к какому нибудь tiling, когда данные пересовываются с учётом доступа как в GPU.

example_cat
()
Ответ на: комментарий от example_cat

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

Мне так сказал интель. А откуда ты свою инфу почерпнул - я не знаю.
https://www3.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-3...

For the P6 and more recent processor families, if the area of memory being locked during a LOCK operation is cached in the processor that is performing the LOCK operation as write-back memory and is completely contained in a cache line, the processor may not assert the LOCK# signal on the bus. Instead, it will modify the memory location internally and allow it’s cache coherency mechanism to ensure that the operation is carried out atomically. This operation is called “cache locking.” The cache coherency mechanism automatically prevents two or more processors that have cached the same area of memory from simultaneously modifying data in that area.

Еще для справки могу добавить, что x86 не работает по MESI - они используют MOESI.

byko3y ★★★★
()
Ответ на: комментарий от byko3y

это всё сказки из документации.

в реальности оно не так как на самом деле.

в реальности LOCK просто означает что на старте линейка кэша делается M, а инструкция перезапустится если тэги кэша не будут=M. отсюда

всё. а то что там в документации - там 100 лет не правили.

example_cat
()
Ответ на: комментарий от example_cat

это всё сказки из документации.

Ага, на ЛОР-е знают, как сделаны процессоры интеля, лучше, чем люди из интеля.

в реальности LOCK просто означает что на старте линейка кэша делается M, а инструкция перезапустится если тэги кэша не будут=M. отсюда

Внутри ядра x86 вообще MESI(O/F) не используется - это межпроцессорные протоколы. То, что фактически происходит конкретно в кэшах интеля внутри процессора, нельзя назвать никак иначе, как «блокировка записи в линию кэша». Между процессорами - да, пойдет F на интеле и O на амуде. Но и даже при MESI E-M не использовались для атомарных операций - в «сказках» из «устаревшей» документации явно указано, что раньше просто блокировалась вся память на время атомарной операции.

Делай свои процессоры - ради бога, зачем ты лезешь со своими уставами в чужие процессоры?

byko3y ★★★★
()

Вопрос - всегда ли данные которые лежат в 1 кеш линии попав в L1 отдельных ядер вызывают процесс синхронизации?

Явной синхронизации нет, (упрощенно) запись вызывает инвалидацию в чужих кешах.

Или это происходит только тогда когда данные изменяются?

Упрощенно - да.

Ну то есть память помечается как неактуальная и L1 другого ядра вынуждено перезагрузить данные снова. Хотя они уже были.

Упрощенно - да.


Для хорошей производительности достаточно избегать явных пенальти - писать только в «свои» блоки памяти и с выравниванием. На NUMA также важно чтобы блоки были в «своей» локальной памяти NUMA-узла.

Если хочется предельной производительности, то следует:

  • утаптывать данные в L1/L2/L3, в том числе оценивать пользу от non-temporary store/load (в «обход» кеша);
  • использовать prefetch, если данные лежат не последовательно или на разных страницах.
  • размещать данные с учетом (анти)итерливинга кеш-линий по каналам DDR-памяти;

Но на практике достаточно мало случаев, в которых это дает заметный выигрыш.

Deleted
()
Ответ на: комментарий от byko3y

не знаю как на лоре, но я знаю. нужно просто ещё патенты читать, там всё написано.

Внутри ядра x86 вообще MESI(O/F) не используется

внутри любых современных процов используется схема Томассуло. там MESI не существует by-design. и чо? Не надо рассказывать про то, что рассказывалось в документации. Это «видимая часть». А в реальности всё совсем по другому. Ничего там не лочится вообще.

Делай свои процессоры - ради бога, зачем ты лезешь со своими уставами в чужие процессоры?

дак я просто констатирую что говно есть говно.

example_cat
()

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

Вместо увеличения размера структур можно использовать __attribute__ ((aligned (размер) ))

Для выделения в хипе можно использовать posix_memalign

См. https://stackoverflow.com/questions/7281699/aligning-to-cache-line-and-knowin...

SZT ★★★★★
()

Это ты для развития или уже встрял после бенчей и давишь соки из mem/cpu?

anonymous
()

Вопрос - всегда ли данные которые лежат в 1 кеш линии попав в L1 отдельных ядер вызывают процесс синхронизации? Или это происходит только тогда когда данные изменяются? Ну тоесть память помечается как неактуальная и L1 другого ядра вынуждено перезагрузить данные снова. Хотя они уже были.

Чтобы ответить на этот и многие другие вопросы наверное стоит сначала посмотреть что показывает VTune и от этого уже отталкиваться. Ты уверен, что сейчас у тебя есть проблема?

xpahos ★★★★★
()
Ответ на: комментарий от example_cat

внутри любых современных процов используется схема Томассуло. там MESI не существует by-design. и чо? Не надо рассказывать про то, что рассказывалось в документации. Это «видимая часть». А в реальности всё совсем по другому. Ничего там не лочится вообще.

На уровне MESIF/MOESI лочится, на уровне memory bus лочилось, а тут вдруг раз - и перестало. Ты им подсказал, да?

А знаешь, почему им нужно блокировать линию вместо linked-load/store-conditional? Потому что у x86 упорядочены операции записи и они атомарны при выровненом доступе, в том числе между процессорами, то есть, если один процессор записал данные в ячейки 1, потом 2, то любая операция на любом процессоре при этом увидит атомарную запись в ячейку 1, а потом атомарную запись в ячейку 2. По сути это значит барьер release для писателя и барьер acquire для читателя, которые x86 делает всегда. Потому, например, единственный барьер на x86 - это mfence - полная упорядоченость, которая, по сути, задает только StoreLoad барьер.

Для того, чтобы реализовать такую упорядоченость, при пропытке записи до записи процессор x86 переводит кэш линию в состояние E - это уже межпроцессорный протокол. Если же умник, вроде тебя, решит при этом делать LL/SC вместо блокировки, то при трениях между ядрами произойдет лютейший вынос конкретно этой линии кэша, который распространится на другие процессоры, что уронит производительность многопроцессорной системы в этом алгоритме в десятки или даже сотни раз. Именно по этой причине создатели SPARC позволили читать слегка тухлый кэш и не гарантировать сохранение порядка видимости данных по умолчанию, а соблюдать порядок только по явным запросам (fence, PSO, TSO).

byko3y ★★★★
()
Ответ на: комментарий от example_cat

кто тебе сказал, что там лочилось?

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

byko3y ★★★★
()
Ответ на: комментарий от example_cat

читай что ли умных людей https://fgiesen.wordpress.com/2014/08/18/atomics-and-contention/

И что ты хотел сказать этой статьей? Что я не так писал? По состоянию на 2014 год он более-менее прав, хоть у меня и есть замечания:
- он не тестировал многопроцессоры, где помойность MESI на трениях проявляется во всей красе;
- он упоминает MESI в контексте многоядер, где MESI не используется;
- снижение производительности атомарной операции на одном ядре не обосновано, «requires a lot of communication to maintain a consistent» - это просто художественный оборот. А вызвано оно исключительно необходимостью работать с кэшем последнего уровня (LLC) вместо L1 - это примерно в 10-20 раз медленнее.

Ну а вообще, очень мало ссылок на документы и фактические цифры тестов.

byko3y ★★★★
()

Ой вы тут подрались уже ::) Ща попозже приду и выложу всё что нарыл и к каким выводам пришёл. Но один хрен всё надо будет ещё проверять.

LINUX-ORG-RU ★★★★★
() автор топика
Ответ на: комментарий от byko3y

он упоминает MESI в контексте многоядер, где MESI не используется;

кот и лампа, жпг.

А вызвано оно исключительно необходимостью работать с кэшем последнего уровня (LLC) вместо L1

откуда ты это взял? ты упоротый иди букварь читай умным станешь.

example_cat
()
Ответ на: комментарий от example_cat

атомарные операции кстати работают используя MESI. как минимум на интеле. То есть: они просто вытаскивают линейку кэша к себе, делают операцию а дальше ЕСЛИ линейку утащили идут на новый цикл.

Хочешь сказать, ABA problem больше не актуальна для intel?

anonymous
()
Ответ на: комментарий от pon4ik

А какой протокол когерентности кэша используется в случае многих ядер

MSI/MESI/MOESI/MESIF - это протоколы распределенного одноуровневого кэша. Но в многоядерном однопроцессоре кэши иерархичны, и совать туда M*SI* - значит натягивать сову на глобус. Методы взаимодействия разных уровней кэшей сложны и они меняются от одной линейки процессоров к другой. Никто их не стандартизирует потому, что разработчик у одного процессора всегда один, и этот разработчик не спешит делиться с другими деталями работы своего устройства.

А если отвечать коротко, то в современных многоядерных процессорах кэш один и протоколы когерентности ему не нужны.

byko3y ★★★★
()
Ответ на: комментарий от byko3y

во-первых не так уж и не спешит, вполне себе тот же интел выкладывает доки.

во-вторых, утверждение что «кэш один» это очень бодрое утверждение. «оно работает на магии!».

далее, L3 (LLC твой) часто не инклюзивный, и он лишь прикрывает дальнейшие missы. а между L2 работает тупой MESI потому что ничего лучше не придумали. более того, TSX использует ту же самую методику и его предел объема записываемых данных - примерно размер L1.

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

но в итоге всё равно кэш снупают, линейку отбирают и тащат к себе.

example_cat
()
Ответ на: комментарий от example_cat

во-вторых, утверждение что «кэш один» это очень бодрое утверждение. «оно работает на магии!».

Ну у интеля кэши точно единые, абсолютно все операции с памятью проходят через единый LLC, а проблемы с когерентностью появляются уже у L1/L2, которые как бы являются процессором внутри процессора, где LLC, по сути, является оперативной памятью (RAM). При этом, в LLC стоят ссылки на L1/L2, что ни разу не является частью протокола MESI, например. И еще целая гора механизмов, которая с MESI общего имеет разве что «и там кэши, и там кэши». Как я уже писал, это сложная система, составная.

далее, L3 (LLC твой) часто не инклюзивный, и он лишь прикрывает дальнейшие missы

Да, в оптероне была возможность независимо работать с внешней памятью по MESI на всех уровнях кэша - получались эдакие несколько независимых кэшей. Больше они так не делают, потому что производительность у такой системы плохая. Хоть амуда и не делает инклюзивные кэши, но и эксклюзивные она тоже не делает - теперь она использует смешанную модель, когда ядра могут взаимодействовать между собой через LLC и процессор приоритизирует кэширование именно общих линий. Если линия кэширована в LLC, то по MESI* со внешней памятью работает LLC, если линия только в L1/L2, то эти кэши самостоятельно по MESI* могут работать со внешней памятью.

byko3y ★★★★
()
Ответ на: комментарий от byko3y

Да, в оптероне

skylake например. то есть элементарно не везде есть LLC. и как тут быть?

понятно что если L3 инклюзивный, то он вынужден знать, где лежат данные. и то. толку то? это МАКСИМУМ. операция производится только с L1. в принципе процессор работает только с L1. то есть данные должны быть в L1 а значит туда данные должны быть перемещены.

«это сложная система» это фигня полная. всё - сложная система. и чо.

example_cat
()
Ответ на: комментарий от example_cat

skylake например. то есть элементарно не везде есть LLC. и как тут быть?

Для этого обычно используется модель Non-inclusive Cache, Inclusive Directory - правда, это только догадки, официального подтверждения я не находил. То есть, по сути кэш всё так же инклюзивный, только данные в L3 не всегда хранятся, а хранится лишь ссылка на L1/L2. Да, судя п овсему. производители уже поняли, что ни одна из чистых моделей не является оптимальной, а лучше всего работает модель «общие данные - в общем кэше, личные данные - в частных кэшах», что есть очень даже разумно.

byko3y ★★★★
()
Ответ на: комментарий от byko3y

ну а толку то. процессор не умеет работать с данными не в L1. всё, финита ля комедия.

то есть атомарная операция всегда засасывает линейку в L1. детали протоколов ничем тут не помогают - они все в этой ситуации редуцируются до MESI ибо по сути являются немного мутантными MESI.

example_cat
()
Ответ на: комментарий от example_cat

процессор не умеет работать с данными не в L1. всё, финита ля комедия

вот это поворот :) даже не вникая во внутренности интеловских процессоров

The non-temporal move instructions (MOVNTI, MOVNTQ, MOVNTDQ, MOVNTPS, and MOVNTPD) allow data to be moved from the processor’s registers directly into system memory without being also written into the L1, L2, and/or L3 caches. These instructions can be used to prevent cache pollution when operating on data that is going to be modified only once before being stored back into system memory. These instructions operate on data in the general-purpose, MMX, and XMM register

anonymous
()
Ответ на: комментарий от example_cat

skylake например. то есть элементарно не везде есть LLC. и как тут быть?

Для этого обычно используется модель Non-inclusive Cache, Inclusive Directory - правда, это только догадки, официального подтверждения я не находил.

ну а толку то. процессор не умеет работать с данными не в L1. всё, финита ля комедия.

4.2.
Есть некэшируемый режим, есть write combining, есть еще более тонкие комибнации режимов и отдельных операций, которые могут использовать L1, а могут и не использовать.

Нужно понимать, что перемещение из L2 в L1 и обратно - это быстрый процесс, чуть медленнее из L3 в L1, но все равно быстрее, чем с памятью. У Cortex-A9, например, вообще опциональный внешний L2 кэш, потому что далеко не всегда он нужен, а только для быстрых процессоров и/или для многоядер пришлось так мучаться с организацией кэшей.

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

byko3y ★★★★
()
Ответ на: комментарий от byko3y

Есть некэшируемый режим, есть write combining

ты вот когда всё это пишешь, ты хотя бы отчёт себе отдаёшь, в каких условиях это все работает?

тебе надо попасть в MTRR с соответсвующими настройками, либо в PTE должно быть PCD=1, либо в PAT должны быть соответствующие биты.

далее, атомарные операции над non-cacheable памятью это вообще-то известный вектор dos-атаки на хост из виртуалки. против этого юзают Memory Bandwidth Allocation.

example_cat
()
Ответ на: комментарий от example_cat

тебе надо попасть в MTRR с соответсвующими настройками, либо в PTE должно быть PCD=1, либо в PAT должны быть соответствующие биты.

Речь шла о том, что «процессор не умеет работать с данными не в L1. всё, финита ля комедия», что есть не так. Сложно ли обойти L1 или просто - уже нет разницы.

далее, атомарные операции над non-cacheable памятью это вообще-то известный вектор dos-атаки на хост из виртуалки. против этого юзают Memory Bandwidth Allocation.

Можно банально атомарную операцию по невыравненному указателю делать.

byko3y ★★★★
()
Ответ на: комментарий от byko3y

ну то есть то что ты пишешь - это бред. атомарные операции в норме идут над кэшируемой памятью.

далее

inclusive directory

давай ты прочитаешь как работает MESIF, который ты же и упоминал

https://researchspace.auckland.ac.nz/bitstream/handle/2292/11594/MESIF-2009.pdf?sequence=6

вот просто давай прекратишь нести херню, прочитаешь мануал. может быть покажешь где у xeon эта directory.

example_cat
()
Ответ на: комментарий от example_cat

ну то есть то что ты пишешь - это бред. атомарные операции в норме идут над кэшируемой памятью.

Сначала читаем официальные доки - потом выдумываем:

The Intel Core 2 Duo, Intel Atom, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon, and P6 family processors provide bus control signals that permit external memory subsystems to make split accesses atomic; however, nonaligned data accesses will seriously impact the performance of the processor and should be avoided

Атомарные невыравненные операции над кэшируемой памятью идут мимо кэша. Так и живем.

давай ты прочитаешь как работает MESIF, который ты же и упоминал
https://researchspace.auckland.ac.nz/bitstream/handle/2292/11594/MESIF-2009.p...

Это тут вообще при чем? Здесь вообще не затрагивается внутренняя организация процессора. Inclusive directory внутри процессора в Intel QPI никуда не исчезал.

byko3y ★★★★
()
Ответ на: комментарий от example_cat

то есть ты реально не понимаешь разницу между misaligned атомиками и обычными атомарными операциями? ну ладно.

И в каком месте я продемонстрировал это непонимание?

byko3y ★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.