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