Cache coherency #3: false sharing

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

False sharing

...Или ложное разделение. По-правде, не очень понятно, почему именно ложное — оно самое что ни на есть настоящее, только неожиданное. Что такое true sharing? — Это когда у нас есть ячейка памяти, используемая одновременно более чем одним потоком. В предыдущих статьях я уже рассказывал, что конкурентный доступ на чтение протоколы когерентности разруливают без особого труда, а вот конкурирующие чтение и запись, и особенно запись и запись заставляют их попотеть — здесь все понятно. А false sharing это когда ячейки памяти разные, но физически попадают на один и тот же cache line. С точки зрения программиста — никакого разделения данных нет, никакого конкурирующего доступа тоже. А с точки зрения подсистемы памяти каждый cache line — это одна ячейка, и операции доступа к разным частям одной строки кэша из разных ядер конкурируют друг с другом за эту ячейку-строку. И неожиданно оказывается, что обычная запись в какую-то локальную (казалось бы) переменную стоит в несколько раз дороже, чем должна была бы:

int threadId = 0, 1, 2, ... THREADS_COUNT;
int distance = 1..8; 
long[] area = new long[THREADS_COUNT*distance];

for(int i=0...Inf){
   area[threadId*distance] = i;
}

(Готовый к исполнению код здесь). Если увеличивать distance, то можно наблюдать, как время на выполнение цикла уменьшается, вплоть до distance=8 — для интелловских архитектур, где cache line 64 байта. (Строго говоря, нужно еще убедиться, что все потоки сели на разные физические ядра, но как правило, в случае незагруженной машины системный планировщик их сам так и раскидает)

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

У false sharing есть два ощутимых эффекта: увеличение в разы времени выполнения конкретной операции записи (memory latency), и увеличение нагрузки на шину. Чтобы заметить увеличение нагрузки на шину нужно либо специально ее мониторить, либо уже использовать шину близко к режиму насыщения. Но интелловский InterConnect имеет пропускную способность что-то вроде 20Гб/с в каждую сторону — а это 20 миллионов килобайтных сообщений в секунду (в нереальном случае 100% КПД). Не то, чтобы это было недостижимо круто, но не каждая птица долетит до середины Днепракаждое приложение подходит хотя бы близко к тому, чтобы насытить шину.

А что насчет memory latency? Ну, проблема медленной памяти перед разработчиками процессоров стоит уже лет 15, за это время было придумано масса трюков, позволяющих ее как-то обойти. Часть из них — те, что про введение иерархии кэшей — в случае с false sharing не помогут, потому что они сами и являются причиной. Но на уровне процессора остается еще пара тузов в рукаве, связанных с асинхронным выполнением операций с памятью. Например, современные процессоры содержат блок префетчинга, который может предсказать доступ к памяти до того, как исполнение дойдет до соответствующей инструкции, и отправить запрос на упреждающее чтение нужного блока в кэш. Другой пример: инструкции записи тоже обычно не ждут, пока запись фактически будет выполнена — команда на запись просто сохраняется в т.н. store buffer-е, и исполнение идет дальше, а команды из буфера спускаются контроллеру памяти в асинхронном режиме.

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

И отсюда можно попробовать порасуждать на тему, в каких случаях false sharing имеет наибольшую вероятность стать заметным.

Во-первых, когда нам важно именно время выполнения конкретной (небольшой) операции (latency, response time), а не пропускная способность в целом (throughput). Если наша операция содержит всего-то пару сотен инструкций, и несколько обращений к памяти, то заметное удорожание даже одного из этих обращений все-таки будет заметно. Процессору просто не за чем будет спрятать замедлившуюся операцию. Да, он может параллельно начать выполнять инструкции хоть из другого потока (через hyper threading), тем самым удерживая на уровне общую пропускную способность — но время выполнения конкретной операции от этого не уменьшится. Мы можем получить такую картину: система по-прежнему выполняет N операций в секунду, только время одной операции выросло с 1мкс до 2мкс. Поскольку далеко не каждого волнует время выполнение конкретной операции (особенно, когда масштаб этого времени — микросекунды), то на этой стадии false sharing часто остается просто незамеченным.

Дальше идут ситуации, когда операции с false sharing составляют заметную долю всех операций (по крайней мере, на критическом маршруте). Это как раз пример выше. Почему false sharing там заметен? Потому что там, кроме самой записи, только обвязка цикла, которая едва тянет на пару тактов. И одна-единственная запись, которая contended (счетчик цикла скорее всего будет сидеть в регистре). Даже если запись идет в L1 (~5ns) — она здесь будет доминирующей, и никакие трюки этого не замаскируют, потому что маскировать нечем. И если запись станет в разы дороже — это будет просто бросаться в глаза.

Ну и последний очевидный вариант — это когда у вас шина памяти уже близка к насыщению, и тут еще добавляется false sharing, и все становится грустно.

Т.е. получается, что в первую очередь false sharing беспокоит тех, кто разрабатывает latency-critical системы, и уж во-вторую — тех, кто разрабатывает очень high throughput, где-то близко к пиковой производительности железа.

P.S. Есть у меня еще такая любопытна идея: кажется, что чем мягче аппаратная модель памяти, тем больше у процессора возможностей "прятать" memory latency. Т.е. и прятать false sharing у него тоже больше возможностей. Однако сравнивать разные процессоры сложновато — они обычно отличаются слишком много чем, не только моделью памяти (да и где бы их все взять для тестов-то). Но можно ужесточить аппаратную модель памяти программно — расставляя барьеры памяти. Если взять тот пример, выше, и вместо обычной записи в ячейку массива делать volatile store (придется заменить массив на AtomicIntegerArray, или дергать Unsafe.putIntVolatile) — то сопутствующий lock xadd скорее всего приведет к принудительному сбросу store buffer-а. А значит не будет возможности отложить запись на "попозже", ее придется делать синхронно. Кажется, что это сделать false sharing еще более заметным.

Еще интереснее будет проверить это для Disruptor-а. На Java One меня спрашивали, почему padding в моих экспериментах никак себя не проявил — вот я сейчас думаю, что причина может быть как раз в том, что я экспериментировал с padding после того, как заменил volatile store для курсоров на lazySet (что эффект от оптимизаций некоммутативен — это не новость). Будет интересно, как появится возможность, проверить, что получится если сделать наоборот: вернуть volatile store, и поиграться с padding.

P.P.S. Вообще-то, эта статья планировалась как продолжение цикла про cache coherency. И про false sharing задумывалось как вступление и разминка. Но я что-то увлекся, и false sharing вылез на место главного героя, не оставив места запланированным атомикам. Ну я и подумал — пусть остается как есть, а атомики получат свою главную роль чуть позже :)

Cache-coherency #2: от MSI к MESI и далее к звездам (MESIF, MOESI)

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

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

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

Что же, исходя из этих целей, мы можем сделать с MSI?

Битва за эксклюзив

Любопытной особенностью MSI является то, что любой немодифицированный блок данных (не-М) считается потенциально "разделяемым" (Shared). Что здесь любопытного? -- то, что такое утверждение сильно не соответствует реалиям работы абсолютного большинства приложений.

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

А что, собственно, такого неудобного в состоянии Shared? Неудобно то, что разделяемое состояние -- это состояние, об изменениях которого нужно отчитываться (оповещать по шине). Точнее, нас волнует один из самых частых переходов: S -> M. Сделаем мысленный эксперимент: представим себе, что у нас в кэше 1000 строк в состоянии S (это начальное состояние после загрузки из основной памяти в MSI). Сейчас, чтобы изменить любую из них, нам обязательно нужно пустить по шине "я изменяю строку №ХХХ!". Зададимся вопросом -- а в каком проценте случаев это оповещение действительно кому-то будет интересно? Для какого процента строк "может быть shared" будет означать "в самом деле shared"? Если прочитать еще раз предыдущий параграф, то можно предположить, что с большой вероятностью таких случаев будет немного. Значительная, может быть даже доминирующая часть "может быть Shared" строк на самом-то деле нифига не Shared вообще. Но мы, "на всякий случай", вынуждены заполнять шину оповещениями об их изменениях.

Возникает свежая идея: дополнить граф состояний строки еще одним состоянием -- "единственная, немодифицированная (в отличие от М) копия". Забегая вперед, это состояние мы будем называть E(xclusive). (Нам даже не придется расширять поле состояния -- для 3 состояний MSI нужно было 2 бита, и для 4 состояний нашего нового протокола все еще достаточно 2 битов).

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

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

Но это все еще цветочки -- самый главный вопрос состоит в том, каким образом поддерживать актуальность этого поля "количество копий"? Положим, если у меня есть копия строки, и текущее количество ее копий, то увеличение количества копий я могу фиксировать просто слушая шину на предмет запросов "хочу строку №ХХХ" (хотя уже даже здесь надо допридумывать метод, как я узнаю текущее количество копий изначально -- когда еще только буду запрашивать свою копию -- но этот-то вопрос еще обозрим). А вот как мониторить уменьшение количества копий? Основная причина "пропадания" копии -- это просто вытеснение ее из чьего-то кэша новыми данными. Но если оглашать по шине все вытеснения -- это будет очень существенное увеличение трафика!

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

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

За неимением гербовой -- попробуем писать на туалетной...

Ок, давайте попробуем не требовать слишком многого. Кажется, что строго разделить Shared и Exclusive состояния будет стоить нам слишком дорого -- ладно, попробуем разделить их не совсем строго. Попытаемся найти, при каких обстоятельствах можно легко гарантировать, что какая-то строка сейчас принадлежит только одному кэшу -- и оставим более сложные случаи без специальной обработки. Т.е. Exclusive у нас будет точным состоянием -- мы гарантируем, что строка с таким состоянием действительно существует только в одном кэше. А Shared останется не точным -- может, есть еще другие копии, а может быть и нет.

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

Вторая возможность -- это если у нас сейчас строка в M, и мы выполнили сброс изменений в основную память. В этом случае мы знаем, что больше ни у кого пока этой строки нет (состояние М это нам гарантирует), поэтому мы имеем право сменить статус не на S, а на E.

Эта часть выглядит логично, но ее применимость весьма условна -- потому что модифицированные строки у нас нигде по собственному желанию в память не сбрасываются, это всегда происходит по необходимости. Либо строка просто вытесняется из кэша новой строкой -- тогда возможность ее поставить в E бесполезна, ведь она вытесняется. Либо сброс значения спровоцирован чьей-то сторонней попыткой чтения той же строки -- и тогда, опять же, завершив write back, кэш сбросит строку в Invalid.

Подведем итог. Чтобы реализовать возможность загружать строки сразу в E нам нужно, чтобы каждый кэш мониторил шину на предмет запросов на чтение всех строк, которые он сам содержит (в любом состоянии, кроме I, разумеется -- а раньше было достаточно мониторить шину только на предмет запросов строк, которые у меня в M).

Если кэш обнаруживает запрос, на строку, которая есть у него -- он проверяет, в каком она у него состоянии. Если состояние M -- тут все, как и раньше (прерываем транзакцию, форсируем write back...). Если состояние S -- просто запускаем по шине сообщение "у меня такая есть". Если состояние E -- запускаем по шине "у меня такая есть" и меняем свое состояние на S.

Кэш, желающий загрузить строку, посылает на шину обычный запрос "хочу строку №ХХХ". Но теперь он еще и продолжает мониторить шину на предмет обратной связи. Если на шине появляются комментарии "а у меня такая есть" -- он запоминает этот факт, и, когда дождется получения строки, ставит ей статус Shared. Если же комментарии отсутствуют -- строка загружается в Exclusive.

Какой профит мы получаем от всех этих усложнений? Мы получаем возможность модифицировать строки в E без дополнительных оповещений по шине, просто молча меняя их состояние на M.

Встречайте, MESI

Увы, но все вышеперечисленное, к сожалению, уже было придумано до нас. Причем задолго до нас. В общих чертах это похоже на протоколы когерентности Write-once и его чуть более оптимизированного наследника, MESI. MESI, придуманный некогда (не смог сходу нагуглить когда именно) в университете Иллинойса, используется для поддержания когерентности начиная с Pentium, и, с некоторыми усовершенствованиями, до наших дней.

Собственно, прочитать про него в подробностях (по правде говоря -- очень кратких подробностях) можно по ссылке выше. Для удобства я скопировал из статьи сюда ссылку на диаграмму переходов для его состояний (по клику открывается в полный размер). От "изобретенного" нами протокола он отличается только одной деталью -- два-в-одном запросом RFO, request for ownership. RFO это запрос на чтение строки, принудительно загружающий ее в Exclusive. RFO примерно эквивалентен склееным в одну транзакцию запросам "дай строку №ХХХ" и "модифицирую строку №ХХХ".

Действие RFO такое: я получаю запрошенную строку, а все остальные, у кого еще есть ее копия, эту копию выкидывают (переводят в I). В случае, если у кого-то строка была в M, и выбросить ее просто так нельзя, используется уже знакомый нам механизм: владелец строки в состоянии M прерывает транзакцию, сбрасывает в память модифицированную строку, меняет ее состояние у себя на E. Через какое-то время исходный кэш повторяет RFO.

С этим сдвоенным запросом есть некоторые разночтения, относительно его точной семантики. Например, на приведенной выше диаграмме его нет -- вместо него есть запрос RWIM, read with intent to modify, который сразу переводит строку в M (т.е. это будет точный аналог "дай строку №ХХХ" и "модифицирую строку №ХХХ"). RFO же загружает строку в E. Я не уверен, является ли эта разница реально существующей (например, зависит от реализации протокола), или это просто кто-то что-то неправильно понял. Но это не так важно -- с точки зрения именно трафика на шине разницы между RFO и RWIM по сути нет -- если уж я загружаю строку в E, то я собираюсь ее модифицировать, но переход E->M трафика на шине не порождает, это, по-сути, внутреннее дело того кэша, в котором строка сейчас содержится.

Еще на диаграмме есть приятный бонус для внимательных читателей -- в виде небольшой неточности, которую вы можете попробовать поискать сами :) А кто нетерпелив -- может просто выделить ответ: На пути "read" -> "miss" -> "1 copy" из узла "snooping core's state: E/M" есть, на самом деле, еще один, третий выход: "snooping core's state: S". Как мы уже обсуждали, состояние S не точное, поэтому, даже если физически на данный момент копия строки есть только в одном кэше, она вполне может быть там в состоянии S. Добавить этот выход несложно -- мы просто присоединяемся к маршруту "Multiple copies of state S" шагом раньше.

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

Что дальше: Intel MESIF

До сих пор мы старались выполнить программу оптимизации по одному направлению -- уменьшение трафика на шине. Но, возвращаясь к началу статьи, есть еще одно направление -- уменьшение количества запросов к основной памяти (пора бы уже уточнить, что "основная память" -- это не обязательно прямо-таки RAM, в нашем контексте это "общая память", в отличие от "локальных" кэшей каждого CPU. То есть чаще всего в роли "основной памяти" будет выступать тандем L2[+L3]+RAM, а в роли локальных кэшей -- L1).

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

Позволить локальным кэшам, имеющим копию строки, отвечать на запросы ее копии вместо основной памяти -- это довольно очевидная оптимизация базового MESI. У меня нет точных сведений, с какого момента она начала применяться, но кажется, что уже довольно давно. Однако, у простейшей реализации этой идеи есть подводные камни. Один из них -- это множественные ответы для часто используемых (читаемых) строк. В самом деле, пусть строка №42 сейчас уже сэширована в 3-х различных кэшах (как Shared, разумеется), и по шине приходит очередной запрос на ее копию. Легко понять, что либо запрашивающий получит 3 ответа подряд (с идентичным содержимым, разумеется), либо необходимо придумывать дополнительный протокол арбитража, позволяющий решить, кто именно из 3-х счастливых обладателей просимых данных сейчас будет отвечать. (Легко видеть, что проблема возникает только с Shared строками -- у E строк есть эксклюзивный владелец, а с M-строками мы будем разбираться далее)

Intel в своих Nehalem'ах постаралась уменьшить мусорный трафик множественных ответов за счет добавления еще одного состояния -- F(orwarded). Получился протокол MESIF. Состояние Forwarded -- это подтип Shared -- выделенный Shared, первый среди равных. То есть, если сейчас копии строки присутствуют в нескольких кэшах, то (скорее всего, хотя не обязательно) одна из этих копий будет F, а остальные S. Как несложно догадаться, именно та копия, которая F, и будет отвечать на запросы.

Любопытно, каким образом назначается состояние F. Алгоритм назначения напоминает эстафетную палочку -- в F всегда оказывается та копия, которая была создана последней. Т.е. начинаем мы, как обычно, с того, что в каком-то кэше лежит строка в Exclusive. При запросе копии другим кэшом -- кэш-владелец E-строки отвечает на запрос вместо основной памяти, и одновременно меняет состояние своей строки на Shared. А вот новая копия, созданная по его ответу, будет как раз в Forwarded. И на следующий запрос копии будет отвечать уже ее владелец -- и, ответив, он сбросит состояние своей строки на обычное S, а только что созданная копия в другом кэше станет новым F -- и так далее...

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

Дополнительные бонусы возникают в случае NUMA архитектуры -- собственно, Nehalem именно ей и является. В случае NUMA ответственная F-копия будет чаще оказываться в "территориально" более близком блоке кэша -- более близком к тому, который следующим захочет получить копию.

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

AMD: MOESI

Еще одно интересное расширение к MESI предлагает AMD в своих Opteron-ах -- пожалуй, даже более интересное, чем предыдущее. Целью здесь тоже выступает снижение трафика с основной памятью, но здесь мы стараемся оптимизировать трафик записи. А именно, в MESI любое чтение строки, которая у кого-то находится в модифицированном состоянии, вызовет сложную последовательность телодвижений. Ну, вы уже, наверное, выучили эту мантру: отмена транзакции, сброс модифицированных данных в основную память, смена состояния своей копии на Shared, перезапрос копии... Возникает вопрос: зачем так сложно (и долго), когда кэш, владеющий M-копией может просто ответить на запрос чтения, переслав свои (самые актуальные!) данные? Это позволит убить трех ушастых сразу: и запрос чтения будет выполнен гораздо быстрее, и трафик на межпроцессорной шине будет меньше, и сброс данных в основную память можно отложить до более удобного случая.

Идея здравая, хотя ее реализация чуть сложнее, чем кажется поначалу. Проблема, которую нужно решить -- как быть с повторными модификациями строки, если ее данные уже размножены? AMD решила ее дополнив MESI состоянием O(wned). Получившийся MOESI работает, насколько мне удалось понять, таким образом: во-первых, функции M-состояния расширяются -- кэш, который содержит строку в таком состоянии, должен отвечать на запросы копии этой строки. Отвечая на такой запрос, он меняет свое состояние строки с M на O, а получивший копию кэш ставит ее в S.

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

Разумеется, любой запрос на вытеснение Owned строки будет задержан на время сброса ее данных в основную память.

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


Продолжение следует: в следующей серии я попробую разобрать, как на уровне протокола кэш-когерентности выглядят типичные шаблоны concurrency.

Ссылки

MESI @ wikipedia -- оттуда же ссылки на MESIF/MOESI протоколы

MESIF/MOESI

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