Мифы о кэше процессора, в которые верят программисты

Как компьютерный инженер, который пять лет занимался проблемами кэша в Intel и Sun, я немного разбираюсь в когерентности кэша ^[1]. Это одна из самых трудных концепций, которые пришлось изучить ещё в колледже. Но как только вы действительно её освоили, то приходит гораздо лучшее понимание принципов проектирования систем.

Вы можете удивиться: зачем же разработчику ПО думать о механизме кэширования в CPU? Отвечу. С одной стороны, многие понятия из концепции когерентности кэша непосредственно применимы в распределённых системах ^[2] и на уровнях изоляции СУБД ^[3]. Например, представление реализации когерентности в аппаратных кэшах помогает лучше понять разницу в моделях согласованности ^[4] (консистентности) — отличие строгой согласованности (strong consistency) от согласованности в конечном счёте (eventual consistency). У вас могут появиться новые идеи, как лучше обеспечить согласованность в распределённых системах, используя исследования и принципы из аппаратного обеспечения.

С другой стороны, неправильные представления о кэшах часто приводят к ложным утверждениям, особенно когда речь идёт о параллелизме и состоянии гонки. Например, часто говорят о трудности параллельного программирования, потому что «у разных ядер в кэшах могут быть разные/устаревшие значения». Или что квалификатор volatile ^[5] в языках вроде Java нужен, чтобы «предотвратить локальное кэширование общих данных» и принудительно «читать/записывать только в основную память» ^[6].

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

Или ещё пример. Если переменные volatile действительно каждый раз пишутся/считываются из основной памяти, то они будут чудовищно медленными — ссылки в основной памяти в 200 раз медленнее, чем в кэше L1 ^[7]. На самом деле volatile-reads (в Java) часто настолько же производительны, как из кэша L1 ^[8], и это развенчивает миф, будто volatile принуждает читает/записывать только в основную память. Если вы избегали volatile из-за проблем с производительностью, возможно, вы стали жертвой вышеуказанных заблуждений.

Важность согласованности

Но если у разных ядер собственный кэш, хранящий копии одних и тех же данных, не приведёт ли это к несоответствию записей? Ответ: аппаратные кэши в современных процессорах x86, как у Intel, всегда синхронизируются. Эти кэши не просто тупые блоки памяти, как многие разработчики, похоже, думают. Наоборот, очень сложные протоколы и встроенная логика взаимодействия между кэшами обеспечивает согласованность во всех потоках. И всё это происходит на аппаратном уровне, то есть нам, разработчикам программного обеспечения/компиляторов/систем, не нужно об этом думать.

Кратко объясню, что имеется в виду под «синхронизированными» кэшами. Здесь много нюансов ^[9], но в максимальном упрощении: если два разных потока в любом месте системы читают с одного и того же адреса памяти, то они никогда не должны одновременно считывать разные значения.

В качестве простого примера, как непротиворечивые кэши могут нарушить вышеупомянутое правило, просто обратитесь к первому разделу этого учебника ^[6]. Ни один современный процессор x86 не ведёт себя так, как описано в учебнике, но глючный процессор, безусловно, может. Наша статья посвящена одной простой цели: предотвращению таких несоответствий.

Наиболее распространённый протокол для обеспечения согласованности между кэшами известен как протокол MESI ^[10]. У каждого процессора своя реализация MESI, и у разных вариантов есть свои преимущества, компромиссы и возможности для уникальных багов. Однако у всех них есть общий принцип: каждая строка данных в кэше помечена одним из следующих состояний:

1. Модифицированное состояние (M).
   1. Эти данные модифицированы и отличаются от основной памяти.
   2. Эти данные являются источником истины, а все остальные источники устарели.
2. Эксклюзивное (E).
   1. Эти данные не модифицированы и синхронизированы с основной памятью.
   2. Ни в одном другом кэше того же уровня нет этих данных.
3. Общее (S).
   1. Эти данные не модифицированы и синхронизированы.
   2. В других кэшах того же уровня тоже (возможно) есть те же данные.
4. Недействительное (I).
   1. Эти данные устарели и не должны использоваться.

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

Запись в память

Предположим, что поток на core-1 хочет записать в память по адресу 0xabcd. Ниже приведены некоторые возможные последовательности событий.

Попадание в кэш

1. В L1-1 есть данные в состоянии E или M.
2. L1-1 производит запись. Всё готово.
   1. Ни в одном другом кэше нет данных, так что немедленная запись будет безопасной.
   2. Состояние строки кэша изменяется на M, поскольку она теперь изменена.

Промах локального кэша, попадание одноуровневого кэша

1. В L1-1 есть данные в состоянии S.
   1. Это значит, что в другом одноуровневом кэше могут быть эти данные.
   2. Та же последовательность применяется, если в L1-1 вообще нет этих данных.
2. L1-1 отправляет Request-For-Ownership в кэш L2.
3. L2 смотрит по своему каталогу и видит, что в L1-2 сейчас есть эти данные в состоянии S.
4. L2 отправляет snoop-invalidate в L1-2.
5. L1-2 помечает данные как недействительные (I).
6. L1-2 отправляет запрос Ack в L2.
7. L2 отправляет Ack вместе с последними данными в L1-1.
   1. L2 проверяет, что в L1-1 эти данные хранятся в состоянии E.
8. В L1-1 теперь последние данные, а также разрешение войти в состояние E.
9. L1-1 осуществляет запись и изменяет состояние этих данных на M.

Чтение памяти

Теперь предположим, что поток на core-2 хочет считать с адреса 0xabcd. Ниже приведены некоторые возможные последовательности событий.

Попадание кэша

1. L1-2 имеет данные в состоянии S, E или M.
2. L1-2 считывает данные и возвращает в поток. Готово.

Промах локального кэша, промах кэша верхнего уровня

1. L1-2 имеет данные в состоянии I (недействительное), то есть не может их использовать.
2. L1-2 отправляет запрос Request-for-Share в кэш L2.
3. В L2 тоже нет данных. Он считывает данные из памяти.
4. L2 возвращает данные из памяти.
5. L2 отправляет данные в L1-2 с разрешением войти в состояние S.
   1. L2 проверяет, что в L1-2 эти данные хранятся в состоянии S.
6. L1-2 получает данные, сохраняет их в кэше и отправляет в поток.

Промах локального кэша, попадание кэша верхнего уровня

1. В L1-2 есть данные в состоянии I.
2. L1-2 отправляет запрос Request-for-S в кэш L2.
3. L2 видит, что в L1-1 данные в состоянии S.
4. L2 отправляет Ack в L1-2, вместе с данными и разрешением войти в состояние S.
5. L1-2 получает данные, сохраняет их в кэше и отправляет в поток.

Промах локального кэша, попадание одноуровневого кэша

1. В L1-2 есть данные в состоянии I.
2. L1-2 отправляет запрос Request-for-S в кэш L2.
3. L2 видит, что в L1-1 данные в состоянии E (или M).
4. L2 отправляет snoop-share в L1-1
5. L1-1 понижает состояние до S.
6. L1-1 отправляет Ack в L2 вместе с модифицированными данными, если это применимо.
7. L2 отправляет Ack в L1-2 вместе с данными и разрешением войти в состояние S.
8. L1-2 получает данные, сохраняет их в кэше и отправляет в поток.

Вариации

Выше приведены лишь некоторые из возможных сценариев. На самом деле существует много вариаций и нет двух одинаковых реализаций протокола. Например, в некоторых конструкциях используется состояние O/F ^[11]. В некоторых есть кэши обратной записи, а другие используют сквозную запись ^[12]. Некоторые используют snoop-трансляции, а другие — snoop-фильтр ^[13]. В некоторых инклюзивные кэши, а в других — эксклюзивные ^[14]. Вариации бесконечны, а мы даже не затронули буферы хранения ^[15] (store-buffers)!

Кроме того, в приведённом примере рассматривается простой процессор всего с двумя уровнями кэширования. Но обратите внимание, что этот же протокол можно применить рекурсивно. Легко добавляется кэш L3, который, в свою очередь, координирует несколько кэшей L2, используя тот же протокол, что приведён выше. У вас может быть многопроцессорная система ^[16] с «домашними агентами», которые координируют работу нескольких кэшей L3 на совершенно разных чипах.

В каждом сценарии каждому кэшу нужно взаимодействовать только с кэшем верхнего уровня (для получения данных/разрешений) и его потомками (для предоставления/отмены данных/разрешений). Всё это происходит невидимо для программного потока. С точки зрения софта подсистема памяти выглядит как единый, консистентный монолит… с очень переменными задержками.

Почему синхронизация по-прежнему важна

Мы обсудили удивительную мощность и согласованность системы памяти компьютера. Остался один вопрос: если кэши настолько последовательны, то зачем вообще нужны volatile в языках вроде Java ^[17]?

Это очень сложный вопрос, на который лучше ответить в другом месте ^[18]. Позвольте только немного намекнуть. Данные в регистрах CPU ^[19] не синхронизируются с данными в кэше/памяти. Программный компилятор выполняет всевозможные оптимизации, когда дело доходит до загрузки данных в регистры, записи их обратно в кэш ^[20] и даже переупорядочивания инструкций ^[21]. Всё это делается при условии, что код будет выполняться в одном потоке. Поэтому любые данные, подверженные риску состояния гонки, следует защищать вручную с помощью параллельных алгоритмов и языковых конструкций вроде atomic и volatile.

В случае квалификатора volatile в Java решение отчасти состоит в том, чтобы заставить все операции чтения/записи идти в обход локальных регистров, а вместо этого немедленно обращаться к кэшу для чтения/записи ^[8]. Как только данные считаны/записаны в кэш L1, вступает в силу протокол аппаратного согласования. Он обеспечивает гарантированную согласованность во всех глобальных потоках. Таким образом, если несколько потоков читают/записывают в одну переменную, все они синхронизированы друг с другом. Вот как достигается координация между потоками всего за 1 наносекунду.

Автор: m1rko

Источник ^[22]