20 января 2012 г.

Cache-coherency #1: Basics, MSI

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

Что такое когерентность кэшей (cache coherence)? Это (применительно к многопроцессорным системам с кэш-памятью) свойство согласованности данных, вообще говоря разбросанных по различным кэшам. Очевидно, что если у нас одни и те же данные могут быть скэшированы в кэш-памяти разных уровней, и в локальных блоках кэш-памяти разных процессоров/ядер -- при модификации этих данных легко может случиться, что существует множество несогласованных версий одних и тех же данных. Можно, конечно, возложить обязанность разруливать все эти конфликты на программиста -- но это слишком жестоко. Поэтому производители процессоров обычно реализуют какой-либо аппаратный механизм поддержания согласованности данных различных кэшей между собой, и с основной памятью. Где-то (как например на Интеллах) этот протокол весьма функционален, и делает для программиста почти все, кроме, разве что, минета. Где-то (тут я затрудняюсь с точными примерами, на ум приходят только ARM и почившая Alpha) заметная часть работы возложена на программиста (или компилятор) -- от него требуется явно расставлять в коде инструкции барьеров памяти, форсирующие синхронизацию данных.

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

Возможных вариантов организации когерентности -- пруд пруди. Поскольку меня интересуют многоядерные системы -- я буду рассматривать наиболее часто используемую здесь реализацию когерентности через "подслушивание" (snooping).

Что такое подслушивание (snooping): у нас есть общая шина, к которой подключены кэши всех ядер, и к ней же подключен контроллер основной памяти (InterConnect -- это как раз она). Любые запросы отправляются бродкастом на шину, и видны (слышны?) всем участникам вечеринки сразу. Принципы коммуникации через шину:
  1. Шина считается надежной средой -- т.е. нет никаких циклов запрос-подтверждение. Если я запустил по шине какую-то транзакцию, и она завершилась -- значит все участники ее видели, и все с ней согласны. Не возможна ситуация, что кто-то мог не получить сообщение, или кто-то мог не успеть ответить. Разумеется, это все с точки зрения высокоуровневых протоколов -- на уровне реализации в железе, возможно, такие циклы и есть, но с этим уровнем я не знаком. При этом, все-таки, довольно очевидно, что это свойство ограничивает масштабируемость snoop-based систем поддержания когерентности -- реализовать надежный протокол без подтверждений в больших масштабах будет сложно.
  2. "It's more blessed to ask forgiveness then permission": если я хочу что-то сделать, я не спрашиваю остальных участников "согласны ли вы?" -- я просто начинаю транзакцию, реализующую мое намерение. Начатую мной транзакцию видят все участники, поэтому если кто-то из них имеет что-то сказать против -- он прерывает транзакцию, и начинает свою. Влезать в чужую транзакцию -- это вполне регулярный элемент протоколов кэш-когерентности.
  3. При этом все участники действуют все-таки кооперативно -- например, "протестующий" участник не тянет тупо одеяло на себя, а помогает исходной транзакции, которую он прервал -- просто выполняя свою дополнительную транзакцию, он в чем-то подправляет исходную. Другой пример: если я прервал чью-то транзакцию, все участники коммуникации полагают, что мне есть что сказать важного, поэтому, на ближайший такт все (кроме меня) добровольно замолкают, давая мне возможность спокойно высказаться.

MSI: plain and easy

Придумать протокол поддержания когерентности начального уровня не так уж сложно. Особенно это становится просто, когда знаешь ответ. Сколько состояний элементарного блока данных (такой блок называется cache line -- строка кэша) нам нужно для самого минимального протокола кэш-когерентности? Как минимум, нам нужна возможность различать, когда строка в моем локальном кэше "свежая" (т.е. ее содержимое не отличается от содержимого основной памяти), и когда она "несвежая" (изменена мною, и еще не синхронизирована с памятью). Отсюда мы и будем плясать.

Второе ("грязное") состояние логично называется M(odified), и его особенность в том, что если допустить возможность иметь одну и ту же строку в нескольких разных кэшах в таком состоянии -- мы получим проблему слияния изменений. То есть если у нас копия одного участка памяти в кэшах разных процессоров, и каждый процессор внес в нее свои изменения -- то результат в основной памяти будет зависеть от порядка сброса данных в основую память. Нам нужно либо как-то формализовывать этот порядок (что само по себе отдельный гемморой), либо допускать, что результат будет неопределенным (зависеть от порядка сброса кэшей). По-сути, и в том, и в другом случае мы заметно усложняем модель памяти, поддерживаемую нашим протоколом -- что, безусловно, будет добавлять седых волос программистам. Возможно, кто-то так и делает -- но не мы :)

В протоколе MSI принято решение разрубить этот гордиев узел на корню -- мы просто не допускаем такой ситуации. А именно -- Modified это по смыслу Exclusive Modified, и конкретная строка кэша в каждый момент времени может быть в таком состоянии не более чем в одном из кэшей. Другими словами: если я вижу в кэше процессора №2 строку №42 со статусом M -- я могу утверждать, что сейчас больше ни в чьем другом кэше строка №42 не скэширована.

Теперь мы можем перейти к первому состоянию -- когда строка "свежая", не модифицированная. Или, что то же самое, ее содержимое совпадает с содержимым основной памяти. Это состояние (неожиданно) называется S(hared). Почему "разделяемое"? -- потому что в этом состоянии есть важное свойство: строка с таким состоянием может быть свободно скэшированной в хоть во всех кэшах сразу. Что дает возможность эффективно читать одни и те же данные хоть всем ядрам одновременно, не мешая друг другу -- просто каждый получит свою копию в своем персональном кэше. Это свойство "разделяемости" для нас очень важно, поэтому и Shared, а не, скажем, Clean (хотя можно читать и как Sync'ed, при желании).

Третье, и последнее состояние -- I(nvalid). Это, по смыслу, просто отсутствие такой строки в кэше. Флаг "removed".

MSI в движении

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

...Итак, процессор №1 делает запрос на блок данных №42. Его локальный кэш обнаруживает, что таких данных в нем нет (либо нет вообще, либо они есть в состоянии Invalid). Кэш открывает на шине транзакцию "дайте мне кто-нибудь блок данных №42". Если больше ни у кого этот блок не скэширован, то на запрос отвечает основная память -- просто пересылает ему нужный блок. То же самое происходит, если блок у кого-нибудь скэширован, и находится в состоянии Shared: на запрос по-прежнему отвечает основная память, остальные участники молчаливо со всем соглашаются.

Жизнь становится чуть сложнее, если блок есть у кого-нибудь в состоянии Modified. Если процессор №2, слушая шину, видит на ней транзакцию чтения строки, которая у него в состоянии M -- он отменяет транзакцию (посылает на шину всем стоять, трамвай, прижаться к стенке #ABORT). Транзакция чтения отменяется, в следующий такт (в который -- помните? -- все остальные будут вежливо молчать) процессор №2 начинает процедуру write-back -- транзакцию сохранения измененных им данных в основную память. Завершив ее, процессор №2 изменит состояние своей копии строки №42 на Shared. Процессор №1, дождавшись освобождения шины, повторит запрос на чтение строки №42 -- и теперь уже беспрепятственно получит ее от основной памяти (т.е. мы возвращаемся к предыдущему абзацу).

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

Отдельного внимания достоин вопрос о том, когда же я все-таки сброшу свои M-строки в основную память. Один из таких случаев рассмотрен выше -- я вынужден это сделать немедленно, если кто-то другой потребует модифицированные мною данные. Другой, довольно очевидный случай -- когда строка будет вытесняться из кэша другими данными (кэш-то, увы, не резиновый). Собственно, в простейшем варианте этих двух триггеров достаточно. Как видно, мы стараемся отложить запись в основную память насколько возможно. Такая стратегия называется "отложенная запись" (write back). Есть более раритетная стратегия "сквозной записи" (write through) -- при этом каждая запись в кэш сразу же дублируется в основную память. Сейчас, насколько мне известно, этот способ почти не применяется

Вернемся к модификации -- она чуть сложнее, если строка у меня в данный момент в состоянии Shared. Тогда я уже не могу быть уверен, что ее больше нет ни у кого (S это не "гарантированно shared", это "может быть shared"). Поэтому я вынужден, на всякий случай, оповестить всех о своих гнусных планах испортить девственно чистую строку: я объявляю по шине что-то вроде "я модифицирую строку №42". Если у кого-то эта строка есть (а если она есть -- она может быть только тоже в Shared) -- эти кэши, услышав мое оповещение, переводят ее в Invalid (==удаляют).

Последний вариант: если строки в моем кэше еще вообще нет. Простейшим способом здесь будет вылить чайник на плиту и свести задачу к предыдущей: начать так же, как в случае чтения, получить строку в S, и потом, отдельной транзакцией, перевести ее в M.

Собственно, на этом про MSI, в его простейшем варианте -- все. Продолжение (MESI, MESIF, MOESI) в следующих сериях...


UPD:

А, собственно, зачем нам что-то лучшее?


Недостатков и возможностей оптимизации в описанной версии протокола -- не счесть. Для затравки -- парочка самых интересных.

Во-первых, передача строки из одного кэша в другой получается нерационально дорогой. Пусть у нас есть простейшая модель Поставщик-Потребитель, когда один процессор пишет данные в какую-то область памяти, а второй их оттуда читает. Как эта штука будет выглядеть с точки зрения протокола: сначала Поставщик затребует себе строку в S, потом объявит по шине что хочет перевести ее в M, потом запишет в нее данные. Затем Потребитель дойдет до этого же участка памяти, запросит строку из памяти. Поставщик вмешается, и отменит транзакцию чтения, взамен ее запустит транзакцию сброса своей строки в основную память. Потребитель дожидается окончания этой транзакции, запрашивает данные из памяти -- и получает их в Shared. Итого: 5 транзакций, из них 2 чтения из основной памяти и одна запись в нее. При этом легко себе представить идеальный протокол, который, в этом случае, потребует одного чтения, одной пересылки кэш-кэш, и одной записи в основную память, отложенной на неопределенное время.

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

19 комментариев:

  1. Можешь какие-нибудь ссылки на литературу, по которой ты все это блотал дать? А то гугл все время на какой-то другой MSI контент выдает...

    Еще, смотри, в начале топика ты начал рассуждать о том, нужно ли программисту напрягаться, чтобы достичь когерентности на кэшах. И ты приводил примеры как это сильно зависит от архитектуры. А можешь все таки пролить немного свет, как это все сказывается на java программистах? Я так понимаю вся эта эта канитель будет действовать только на volatile переменные? Хотелось бы услышать такой же подробный пример, только чтобы ноги у него росли не от намерений процессора, а от java кода с его ребрами happens-before.

    ОтветитьУдалить
  2. Основная литература, ты не поверишь -- википедия. Ссылка на описание MSI есть в самом начале статьи. Гуглить надо "MSI cache coherence" -- тогда все находится правильно. Точного списка литературы я дать уже не могу -- основная часть на вики, какие-то отдельные моменты я помню уточнял через гугл.

    Для примеров еще равновато -- MSI реально нигде не используется. Я взял его как стартовую точку, чтобы показать эволюцию инженерных решений. Если ты хочешь сразу к современному состоянию -- ищи в википедии MESIF (Nehalem). На мой взгляд, интереснее проследить, откуда возникли существующие решения, почему они такие, между чем и чем их создателям приходилось искать компромис, чем просто запомнить, что вот сейчас оно работает так-то и так-то.

    ОтветитьУдалить
  3. Абсолютно с тобой согласен. С нетерпением жду развития событий!

    ОтветитьУдалить
  4. Прошу прощения, но самый интересный момент пропущен: что происходит при одновременных запросах на запись (модификацию строки)?
    Как процессоры "договариваются" между собой кто будет модифицировать "первым"?

    ОтветитьУдалить
    Ответы
    1. Я не знаю деталей -- это все vendor-specific. То, что я здесь описываю -- это логическое описание протокола, физических деталей реализации я не знаю.

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

      Удалить
    2. П.С.
      хм.. можно тут задать один (давно интересовавший) вопрос по устройству hotspot 1.7 && 1.8.
      Внутри самой JVM используется механизм связывания. Причём у этого механизма 2 особенности:
      1. Связывание ленивое (или отложенное, не знаю какой термин используется в java)
      2. В течении работы программы -- интенсивность связывания не падает (в отличии от inline, интенсивность которого заметно падает с течением времени).

      Можно ли как-то побороть этот эффект. Вполне устроили бы варианты:
      а) не производить связывание вообще (всегда ходить через функцию-обёртку) или делать его очень редко
      б) делать связыание немедленно
      или ещё какие-то варианты уменьшающие частоту записей в JIT-код

      Удалить
    3. Я не очень понял, о каком именно связывании вы сейчас говорите.

      Удалить
    4. может быть не очень удачное место, но всё же:

      // контекст
      При запуске HotSpot через бинарную трансляцию на производительность очень сильно влияет изменение JIT-кода.
      Самым частым изменением является связывание.
      Мы его видим (на 32-битном HotSpot 1.7 / 1.8) как прописывание JVM-ом 4 байт (которые будучи интерпретированы как адрес указывают на область исполняемого кода).

      При этом частота (раз\секунду) этих записей не меняется со временем (в отличии от добавлений нового кода \ inline в существующий).

      // предположительно что происходит
      Предположительно это такая реализация (дающая какие-то преимущества на х86) виртуальных вызовах в HotSpot (вместо стандартных техник обращения к VMT через смещение ф-ии \ или через трамплин адресации виртуальных ф-ий).

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



      Удалить
    5. хм.. это не цитаты (там не было ни одной цитаты, я бы вязл их в кавычки) это вопрос.
      история такова:
      >>Можно ли как-то побороть этот эффект[связывания]. >>Вполне устроили бы варианты:
      >>а) не производить связывание вообще (всегда ходить через функцию-обёртку) или делать его очень редко
      >>б) делать связыание немедленно
      или ещё какие-то варианты уменьшающие частоту записей в JIT-код

      >Ruslan Cheremin15 июля 2016 г., 15:20
      >Я не очень понял, о каком именно связывании вы сейчас говорите.

      Далее идёт пояснение что и для чего нужно.

      П.С.
      если "тонкая настройка hot spot" -- не ваша тема, значит зря поднял вопрос.

      Удалить
    6. Я спросил, откуда эти цитаты, потому что я не могу привязать их к тому, что я сам знаю о JIT, и мне хотелось понять, откуда вы вообще взяли все эти утверждения и терминологию.

      Попробуйте обратиться в лист рассылки hotspot-dev.

      Удалить
    7. хм... это ровно то, что я наблюдал при запуске HotSpot под двоичным транслятором (мои личные предположения отмечены:
      //предположительно

      Если вы видите что-то заведомо ложное (или сильно расходящееся с известным вам) -- напишите об этом. Возможно я исхожу из каких-то неверных предпосылок.

      П.С.
      терминология "не джавовская" потому, что как С-программист плотно с джавой (и их терминологией) дела не имел.
      Набрёл на вашу статью по MSI/MSI+ и увидев, что вы Java-программист решил задать вопрос.

      Удалить
    8. П.С.
      "запуск HotSpot через бинарную трансляцию" -- это берём процессорную архитектуру, под которой нет HotSpot (нужной нам версии), запускаем там бинарный транслятор,

      запускаем под ним x86-HotSpot
      Смотрим на результаты работы.
      Выясняем, что производителность нас не устраивает;
      начинаем разбираться с какими действиями HotSpot бинарный транслятор плохо справился.

      Видим идущие постоянным потоком 4-байтные записи в область JIT-кода.

      Удалить
    9. А, ну наконец-то я более-менее понял. Точных данных у меня нет -- совсем детально я с JIT-ом не разбирался. Но да, JVM же адаптивный рантайм, она активно собирает профиль исполнения кода, и регулярно перекомпилирует код в соответствии с профилем. Чисто теоретически этот процесс должен сходиться к некой финальной версии, но на практике сходимость может быть довольно медленной, если профиль нестабилен. Например, входные данные для программы сначала шли одного типа, и в каком-то месте все время мы шли в одну ветку условного перехода. JIT это заметил, и перекомпилировал код в стиле "высокооптимизированная частая ветка или ссылка на деоптимизацию и рекомпиляцию". И это отлично работало, а потом пришли данные другого типа, и нечастая ветка стала частой -- JIT-у пришлось все переделать. И такое может происходить неоднократно.

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

      С целом, конечно, для бинарного транслятора JVM неудобный клиент. Как можно уменьшить агрессивность компиляции? Ну, для крупной программы, боюсь, изменением кода мало что сделаешь, потому что множество кода в ней за пределами вашего контроля -- в библиотеках.

      Вы можете попробовать выключить JIT вообще, заставив JVM работать в режиме интерпретатора, добавив флаг -Xint (http://docs.oracle.com/javase/6/docs/technotes/tools/windows/java.html). Честно говоря, вряд ли это улучшит производительность, даже с учетом уменьшения геммороя для транслятора, но можно попробовать.

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

      Удалить
    10. Спасибо огромное.
      Очень похоже на то,что это "временно включающийся сбор профиля" (*). К своему стыду об этом варианте сам не подумал -- как-то привык к схеме "профиль сошёлся, ух теперь работаем в полную мощность".
      А поскольку сходимость -- около 2х минут, то и грешил на то, что это такая Run-Time оптимизация VMT.

      *) (т.е. по-умолчанию включен высокопроизводительный режим, но чтобы вовремя отреагировать на изменение поведения -- версию кода со сбором профиля сохраняют и периодически на неё переключаются.

      Удалить
    11. Ключ -XX:+PrintCompilation позволит вам увидеть все методы, которые JVM компилирует. Можно будет понять, когда процесс компиляции более-менее сходится (если сходится).

      * Не совсем. Насколько я понимаю, если код уже скомпилирован в высокопроизводительном режиме, уже без сбора профиля, то назад его откатят только если какое-то из спекулятивных охранных условий не выполнится. Тогда код просто откатывается в интерпретатор, и все начинается заново. А просто "периодической пере-проверки" -- нет, я не встречал никаких указаний на это.

      Удалить
  5. хм... по-моему мой вопрос лежит всё-таки в области логического описания протокола. Может быть я его сумбурно сформулировал, но вопрос в том чья М-заявка отменится, при "одновременной" (*) подаче 2х М-заявок по одному адресу:

    Чуть подробнее:
    1. состояние
    core-1: cacheline addr-x:S
    core-2: cacheline addr-x:s

    2. Запрос ("одновременный"):
    core-1: cacheline addr-x: -> M
    core-2: cacleline addr-x: -> M

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

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

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

      Удалить