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

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

  1. С большим интересом прочитал. К кэшам процессоров конечно никакого отношения не имею, но для себя представлял это в виде нескольких узлов, соединенных MQ шиной.

    Интересно было-бы попробовать реализовать это из чисто практического интереса.

    ОтветитьУдалить
  2. Реализовать -- в смысле "построить модель"? Я сам подумывал о симуляционной модели -- хотел просчитать кривую пропускной способности при увеличении contention, например. Но пока не до того, да и мне больше хотелось чисто математическую модель, чем симуляционную

    ОтветитьУдалить
  3. Да - именно модель, првда сами эксперименты не очень интересуют. Больше интересует не разучился ли я программировать такие модели.

    ОтветитьУдалить
  4. Чётко всё описал. Могёшь! Разработчик вообще инженер! Буду тебя пиарить ссылкой на эту статью :)

    Только вот лично я не понял, почему:

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

    Откуда следует, что тот, кто следующим захочет себе в кеш копию, будет ближе к тому, у кого F?

    И да, не хватает разъяснений про Store Buffers, Invalidate Queue и т.п.

    ОтветитьУдалить
  5. >Откуда следует, что тот, кто следующим захочет себе в кеш копию, будет ближе к тому, у кого F?

    Честно говоря, я уже не помню. Само утверждение я встретил где-то в описании MESIF, деталей там не было. Когда я писал, у меня в голове были какие-то примеры ситуаций, где это работает, но дописывать еще пару абзацев с эвристиками сил уже не было :)

    Ну идея такая, что если твой код вообще NUMA-aware, то ты будешь стараться группировать коммуницирующие потоки на топологически близких ядрах. И это автоматически улучшит работу MESIF. Ну, скажем, NUMA thread scheduler будет стараться потоки одного процесса раскидывать по ядрам поближе друг к другу.

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

    >И да, не хватает разъяснений про Store Buffers, Invalidate Queue и т.п.

    Во-первых маловато пока информации, а во-вторых кажется, что это менее важно с тз производительности. Т.е. memory-aware код даст тебе в среднем гораздо больший буст, чем store buffers aware. Поэтому пока что мне память интереснее деталей store buffers

    ОтветитьУдалить
  6. Спрошу глупость :) - а для чего тогда нужен volatile? Ведь получается, если взять, к примеру, MESIF, что при чтении значения переменной другим потоком нам в любом случае ответит либо основная память, либо кэш, у которого эта запись в состоняи Forwarded. Что я упускаю?

    ОтветитьУдалить
  7. @igor

    Вы упускаете то, что

    а) далеко не все архитектуры процессоров/памяти реализуют аппаратную кэш-когерентность.

    б) даже на кэш-когерентной архитектуре вам может "ответить" регистр процессора

    ОтветитьУдалить
  8. Спасибо, теперь все встало на свои места... почти

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

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

    Для чтения мембар получается тогда не нужен?

    ОтветитьУдалить
  9. Барьеры памяти и когерентность -- они просто про разные аспекты. Барьер памяти (их много может быть разных) задает упорядочивание между инструкциями обращения к памяти. Вы просто говорите системе: (компилятору, процессору, контроллеру памяти) "я хочу, чтобы действие А ни в коем случае не возымело эффект раньше, чем действие Б". Как именно система будет это выполнять -- вас не волнует. Очевидная реализация -- да, на уровне компилятора сбросить/перечитать регистры, на уровне процессора зафлешить store buffer, на уровне контроллера памяти -- синхронизировать кэшлайн. Но в каких-то случаях можно что-то более умное реализовать, для вас это будет прозрачно.

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

    Для чтения мембар тоже нужен. В частности, чтобы компилятор-таки перечитал значение из памяти.

    ОтветитьУдалить
  10. Про чтение все-таки не понял почему нужен мембар.

    Компилятор вставляет инструкцию:

    mov ax, [x]

    Разве этого не достаточно, для того чтобы всегда перечитывать свежее значение?

    ОтветитьУдалить
  11. А компилятор прямо-таки всегда будет вставлять такую инструкцию? А если, скажем, 5 инструкций назад он уже зачитал эту ячейку памяти в регистр -- тоже перечитывать будет?

    Кроме того, mov ax, [x] не обязательно даст значение из памяти. Если вы недавно записали значение в [x], и запись еще висит в store buffer -- чтение может быть удовлетворено прямо оттуда, это быстрее.

    ОтветитьУдалить
  12. Я соственно и имел ввиду, что вставлять mov ax,[x] именно для того, чтобы обновить значение в регистре и только тогда, когда нам этого надо. Например для считывания volatile переменной.

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

    Насколько я понимаю, процессору все-равно откуда ему дадут значение.

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

    Нет, строго говоря mov ax, [x] не достаточно, чтобы получить "свежайшее" значение. Как я уже писал -- чтение процессор может удовлетворить из своего store buffer-а -- не спуская его контроллеру памяти вообще.

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

    Кроме того, volatile -- это не про "свежесть" значения, а про порядок.

    Но, по некоторым причинам, на x86 для чтения volatile барьер на уровне процессора в самом деле не нужен -- только на уровне компилятора. Не нужен он, в частности потому, что volatile read это не чтение "свежайшего" значения -- это просто строго упорядоченное чтение.

    ОтветитьУдалить
  14. Да, я именно хотел пока разобраться в частном случае, где реализована аппаратная кэш-когерентность.

    Тогда чтобы как-то резюмировать: volatile дает нам гарантию, что компилятор не переставит операцию чтения с другими инструкциями, но для того, чтобы считать именно "свежее" значение все-равно нужен барьер, который заполнит store buffer новыми данными перед их считыванием?

    У Martin Thompson в статье рассказывается про store buffer и load buffer. И получается, что одна и та же ячека памяти может быть как в store buffer (в случае ее модификации), так и в load buffer.
    Тогда при чтении, необходимо проверить store buffer (вдруг мы ее уже изменили) и, если не нашли, ищем в load buffer.

    Так ли это?

    Сорри за флуд, но тема действительно очень интересная, а Ваш блог очень хороший источник информации :)

    ОтветитьУдалить
  15. volatile и барьеры находятся на разных уровнях абстракции -- это разные способы формализовывать модель памяти. Можно формулировать модель памяти в нотации ребер HB, можно в нотации барьеров.

    Ограничения, накладываемые volatile на конкретной архитектуре реализуются расстановкой каких-то барьеров. Барьеры, в свою очередь, абстрагируют вас от совсем низкоуровневых деталей реализации -- типа тех же самых store/load буферов. Но при этом нотация барьеров тоже не имеет дело с понятием "свежайшего" значения -- барьеры тоже задают только _порядок_ выполнения -- запрещают какие-то перестановки.

    Конечно, конкретный барьер на конкретной архитектуре может иметь implementation note: forces store buffer flush, но это именно implementation note.

    Статью Мартина я, похоже, не читал -- дайте ссылку пожалуйста.

    ОтветитьУдалить
  16. http://mechanical-sympathy.blogspot.com/2011/07/memory-barriersfences.html

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

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

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

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

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

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

    Да, это та вещь, которую мало кто замечает: модель памяти ничего не говорит о времени, она говорит только о порядке. Модель памяти не запрещает процессору хоть на час отложить запись нового значения в память -- до тех пор, пока он придерживает и те записи, которые "упорядочены после" этой.

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

    >Я вот теперь запутался :)

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

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

    ОтветитьУдалить
  19. Вот еще неплохая ссылка, может кому пригодится: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.152.5245&rep=rep1&type=pdf

    ОтветитьУдалить
  20. Разобраться хочется именно на низком уровне - на уровне ассемблера возможно с деталями реализации на конкретной архитектуре - x86.

    ОтветитьУдалить
  21. Ну уровне ассемблера для x86 все как раз просто. Там только один нетривиальный барьер -- storeload=lock xadd ax,0. Все остальные барьеры noop

    ОтветитьУдалить
  22. А есть ссылка где утверждается, что "Ну уровне ассемблера для x86 все как раз просто. Там только один нетривиальный барьер -- storeload=lock xadd ax,0. Все остальные барьеры noop" ?

    Известно на x86_64, что MFENCE это LFENCE+SFENCE. И что конкретно вы имеете ввиду, что MFENCE = LFENCE = SFENCE = storeload=lock xadd ax,0 ?
    Или что LFENCE = nope?

    Но если LFENCE на x86 не имеет значения, то зачем тогда все, в том числе и Herb Sutter для Sequential Consistency использует MFENCE (т.е. получается nope+SFENCE, а значит можно было бы вместо MFENCE использовать всегда SFENCE)?

    Herb Sutter в выступлении на 00:33:07: http://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-2-of-2
    или на слайде на странице 34: https://skydrive.live.com/view.aspx?resid=4E86B0CF20EF15AD!24884&app=WordPdf&wdo=2&authkey=!AMtj_EflYn2507c

    Помимо этого, краткое описание: http://peeterjoot.wordpress.com/2009/12/04/intel-memory-ordering-fence-instructions-and-atomic-operations/
    И цитата отсюда (Intel® 64 and IA-32 Architectures Developer's Manual: Vol. 2A), заметьте не Itanium: http://www.intel.com/content/www/us/en/architecture-and-technology/64-ia-32-architectures-software-developer-vol-2a-manual.html
    Performs a serializing operation on all load-from-memory instructions that were issued prior the LFENCE instruction. This serializing operation guarantees that every load instruction that precedes in program order the LFENCE instruction is globally visible before any load instruction that follows the LFENCE instruction is globally visible.


    Мало того, есть целых 4 подхода в достижении максимальной гарантии через семантику Sequential Consistency на x86/x86_64:
    1. LOAD(without fence) and STORE+MFENCE
    2. LOAD(without fence) and LOCK XCHG
    3. MFENCE+LOAD and STORE(without fence)
    4. LOCK XADD(0) and STORE(without fence)
    http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html

    ОтветитьУдалить
  23. Информация эта из JMM cookbook -- ближе к концу приведена таблица базовых мэппингов для основных архитектур. Возможно, она специфична для JMM, где есть только два memory_order -- SC и relaxed. Возможно, если вводить acquire/release/consume придется играться тоньше. Хотя lazySet (ака mo_release) в JVM тоже реализован простым store, без барьеров. Вообще, я не видел в явовском дизасме ничего кроме lock xadd.

    Я почитаю ваши ссылки попозже, спасибо за них. Но даже в последней из них, которую вы сами цитируете -- вы сами приводите пример 4-х вариантов обеспечения SC -- и ни в одном из них LFENCE не фигурирует. И в полной версии этой таблицы даже для release/acquire/consume тоже LFENCE нет. Похоже, LFENCE нужен в каких-то краевых случаях, без которых кодогенераторы JVM/C0x могут обойтись?

    ОтветитьУдалить
  24. На x86 гарантия Release-Acquire обеспечивается автоматически: http://peeterjoot.wordpress.com/2009/12/04/intel-memory-ordering-fence-instructions-and-atomic-operations/
    "On strongly-ordered systems (x86, SPARC, IBM mainframe), release-acquire ordering is automatic for the majority of operations."

    Так же известно, что MFENCE = LFENCE + SFENCE. Т.е. подход 3 можно переписать так:
    3. (LFENCE+SFENCE) + LOAD and STORE(without fence)

    Отсюда: http://peeterjoot.wordpress.com/2009/12/04/intel-memory-ordering-fence-instructions-and-atomic-operations/
    "SFENCE ... does not affect load operations." - т.е. можно переписать теперь так:
    3. LFENCE + LOAD and STORE(without fence) - получается LFENCE здесь единственно, что обеспечивает гарантию SC.

    Почему так не пишут - не знаю. Узнаете - скажите :)


    P.S.
    У Herb Sutter'а тоже достаточно конкретно написано, что на x86: LFENCE, SFENCE и MFENCE - это разные процессорные инструкции с разными гарантиями, на странице 34: https://skydrive.live.com/view.aspx?resid=4E86B0CF20EF15AD!24884&app=WordPdf&wdo=2&authkey=!AMtj_EflYn2507c

    ОтветитьУдалить
    Ответы
    1. Я не могу дать строгий ответ на ваши вопросы, но могу указать на несколько тонкостей:

      1. release-acquire ordering это не то же самое, что total sync order, который требуется в яве для volatile.

      2. "SFENCE ... does not affect load operations." - т.е. можно переписать теперь так: LFENCE + LOAD and STORE(without fence) - получается LFENCE здесь единственно, что обеспечивает гарантию SC.

      Это вот очень типичная ошибка: то, что store mbar не влияет на load не означает, что его можно выкинуть. Дело в том, что ваш код исполняется в каком-то контексте -- есть еще код вокруг этих трех инструкций. И этот "соседний" код взаимодействует с вашими инструкциями -- использует результат load, делает какие-то другие store...

      У Hans Boehm была где-то специальная даже статья на тему "почему только барьеров чтения/записи не достаточно" -- я не помню ссылку, но краткий смысл именно в том, что всегда есть контекст. Например, практически всегда значение, полученное load-ом используется чтобы потом на нем сделать какой-то бранч, и в разных ветках уже сделать какой-то store. И вот если вы используете только lfence, то load действительно нельзя будет переставить до этого lfence -- но никто же не мешает спекулятивно выполнить раньше зависимый от него store! Вы получаете потенциально совершенно мистические ошибки. Есть некое небольшое множество случаев, где можно обойтись только l-bar или только s-bar, но оно очень небольшое.

      Поэтому, собственно, редко кто использует sfence/lfence -- не только в JIT, но и в gcc -- потому что сложно описать множество случаев, где это допустимо. Необходимо анализировать широкий контекст кода, а компиляторы не особо сильны в глобальном анализе. Причем известно, что таких случаев немного, и выгоды там не велики. Разве что в каких-то hand-optimized asm-вставках. В остальных местах компиляторы консервативно ставят более сильные барьеры "чтобы уж наверняка".

      Почему в JIT используется lock xadd вместо mfence: когда-то в древности (2005 год, кажется) было обнаружено, что mfence на некоторых моделях процессоров (AMD) работал медленнее, чем lock. При этом на остальных моделях lock работал так же хорошо, как mfence -- выбор инженеров очевиден :)

      Как ни странно, похоже, что сейчас картина не изменилась -- lock по прежнему как минимум не медленнее mfence. Можно предположить, что intel оптимизируют прежде всего то, что чаще используется, а lock-ed инструкции используются многократно чаще mfence. Типичная картина предвзятости первого выбора.

      Удалить