23 января 2012 г.

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

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

18 января 2012 г.

False sharing: @Contended, etc...

В статье про false sharing я рассуждал о том, как можно было бы решить проблему на разных уровнях качественности. Одно из предложений было ввести аннотацию типа @PreventFalseSharing, которая бы намекала JVM, что объекты этого типа недурно бы аллоцировать выравнивая их в памяти по границам кэш-строк. Уже в комментариях Алексей мне признался, что аннотация @Contended уже какое-то время обсуждается во внутренностях Оракла.

Другое мое предложение было что JIT мог бы и сам определять в рантайме, какие объекты испытывают contention, и перемещать их в памяти с тем, чтобы contention уменьшить. Это не кажется особо фантастической идеей -- у интелловских процессоров есть внутренние performance counter-ы, считывая которые можно многое узнать о том, на что тратит время процессор. Поскольку узнать о существовании false sharing можно, остальное кажется обычной адаптивной оптимизацией, в которой JIT традиционно силен.

Так вот, вчера, в concurrency-interest Nathan Reynolds (из Оракла) признался, что эта идея тоже уже разрабатывается -- ему известно о целых двух группах. Одна в Интеле, одна в Оракле. У Интела даже был прототип, который, правда, требовал перезапуска JVM для применения собранного профиля.

Правда, по его словам, от обеих групп "что-то уже давно ничего не слышно" :)

12 января 2012 г.

Disruptor #3.2: Эксперименты с производительностью -- update

Последняя серия экспериментов закончилась на том, что между самой оптимизированной реализацией очереди и Disruptor-ом все еще оставалось порядка 10% разницы (27 против 30*10^6 сообщений/сек на моем сервере). По косвенным данным, оставшиеся 10% можно было списать на записи ссылок в массив -- в очереди это делается при каждом enqueue, Д же заполняет массив только однажды (Тут надо заметить, что в моем бенче этот эффект так заметен, потому что я тестирую холостой ход -- полезная нагрузка, передаваемая в сообщении у меня всего 1 long. В реальной жизни полезная нагрузка будет побольше, так что одна дополнительная операция записи ссылки потеряется за несколькими операциями записи полей сообщения -- инфа 100%). Еще я грешил на false sharing by card marking -- поскольку ячейки массива идут подряд, их dirty flags должны быть тоже рядом, и должны обновляться при каждой перезаписи. Из этого я сделал вывод, что в 1.7 с +UseCondCardMark все будет шоколадно -- но это фиг проверишь, потому что 1.7 ставить я все еще не готов.

По зрелому размышлению я пришел к выводу, что card marking здесь не при делах. У меня же ссылки в массив пишутся только одним потоком -- который выполняет enqueue. Вот если бы я на dequeue очищал ссылку в null (как, собственно, стоило бы делать в production-ready коде) -- тогда другое дело. Но же я выкинул очистку на одной из первых оптимизаций -- так что у меня по любому single writer получается.

А вот как проверить, что сама запись ссылки порождает 10% оверхеда -- мне пришло в голову вчера. Все довольно просто: у меня же очереди используют пул сообщений (чтобы не плодить лишнюю аллокацию). Пул, естественно, имеет тот же размер, что и очередь (зачем ему больше?), поэтому после первого же прохода все элементы во внутреннем буфере очереди фиксированы -- на следующих проходах они перезаписываются поверх себя же. Достаточно вместо set сделать там test-and-set -- и можно будет проверять.

Эксперименты были запущены, и -- бинго! -- наконец-то мы совершенно догнали Д :) 30*10^6 msg/sec. Предположение о том, что во всем (в оставшихся 10%) виновата запись ссылки в буфер таким образом, похоже, оправдывается. Процесс разборки магии Д на компоненты на этом можно считать закрытым.

Единственное, что остается для меня все еще не понятным -- это нестабильность результатов. Типичные результаты запуска выглядят так:

Turn # 1 takes 67058 ms; 7456232 ops/sec
Turn # 2 takes 15854 ms; 31537782 ops/sec
Turn # 3 takes 16058 ms; 31137128 ops/sec
Turn # 4 takes 16201 ms; 30862292 ops/sec
Turn # 5 takes 16111 ms; 31034697 ops/sec
Turn # 6 takes 15794 ms; 31657591 ops/sec
Turn # 7 takes 60603 ms; 8250417 ops/sec

Это совершенно не похоже на нормальное распределение вокруг среднего :) Ощущение, что система может функционировать в одном из 2 режимов -- либо все хорошо, либо случается какое-то гавно. ЖопойИнтуитивно я ощущаю, что это тот же случай, что и у Питера -- где-то тут недостаточно полей (padding), из-за чего при неудачной дефрагментации после GC внезапно возникает false sharing. Но вот где именно я пока понять не могу. Вроде бы все важные переменные у меня обложены полями по самые гланды...