Глобально невидимые инструкции загрузки
Могут ли некоторые инструкции загрузки никогда не быть глобально видимыми из-за пересылки нагрузки хранилища ? Другими словами, если инструкция load получает свое значение из буфера хранилища, она никогда не должна считываться из кэша.
Поскольку обычно утверждается, что загрузка глобально видна, когда она читает из кэша L1D, те, которые не читают из L1D, должны сделать ее глобально невидимой.
3 ответа:
Концепция глобальной видимости для нагрузок сложна, потому что нагрузка не изменяет глобальное состояние памяти, и другие потоки не могут непосредственно наблюдать его.
Но как только пыль осядет после выполнения out-of-order / speculative, мы сможем сказать, какое значение получила нагрузка, если поток хранит ее где-то или ветвится на ее основе. Это наблюдаемое поведение нити-вот что важно. (Или мы могли бы наблюдать это с отладчиком, и / или просто рассуждать о том, какие значения имеет нагрузка можно было бы посмотреть, если эксперимент труден.)
По крайней мере, на сильно упорядоченных процессорах, таких как x86, все процессоры могут договориться о том, чтобы общий порядок хранилищ стал глобально видимым, обновляя единственное когерентное+согласованное состояние кэша+памяти. На x86, were StoreStore переупорядочивание не допускается, это TSO (Total Store Order) согласуется с программным порядком каждого потока. (Т. е. общий порядок-это некоторое чередование порядка программы из каждого потока). SPARC TSO также это строго приказано.
(для хранилищ, обходящих кэш, глобальная видимость - это когда они сбрасываются из некогерентных буферов, объединяющих запись,в DRAM.)
На слабо упорядоченном ISA потоки A и B могут не согласовывать порядок хранения X и Y, выполняемых потоками C и D, Даже если потоки чтения используют acquire-loads, чтобы убедиться, что их собственные загрузки не переупорядочены. то есть не может быть глобального порядка магазинов вообще, не говоря уже о том, чтобы он не был таким же, как программа порядок.
IBM POWER ISA настолько слаба, как и модель памяти C++11 ( будут ли две атомарные записи в разные места в разных потоках всегда рассматриваться другими потоками в одном и том же порядке?). Это, по-видимому, противоречит модели хранилищ, которые становятся глобально видимыми, когда они фиксируются из буфера хранилища в кэш L1d. Но @BeeOnRope говорит в комментариях, что кэш действительно когерентен и позволяет восстанавливать последовательную последовательность с барьерами. Эти эффекты множественного порядка происходят только из-за SMT (нескольких логических процессоров на одном физическом процессоре), вызывающих сверхъестественное локальное переупорядочение.(Одним из возможных механизмов было бы позволить другим логическим потокам вынюхивать не спекулятивные хранилища из буфера хранилища даже до того, как они зафиксируют L1D, только сохраняя еще не удаленные хранилища закрытыми для логического потока. Это может немного уменьшить задержку между потоками. x86 не может этого сделать, потому что это нарушило бы модель сильной памяти; HT Intel статически разбивает буфер хранилища на разделы, когда на ядре активны два потока. Но, как отмечает @BeeOnRope, абстрактная модель того, какие переупорядочения допускаются, вероятно, является лучшим подходом для рассуждений о правильности. Просто потому, что вы не можете придумать механизм HW, чтобы вызвать изменение порядка, не означает, что это не может произойти.)
Слабо упорядоченные Isa, которые не так слабы, как POWER, все еще выполняют переупорядочивание в локальном буфере хранилища каждого ядра, если барьеры или магазины релизов не используются. На для многих процессоров существует глобальный порядок для всех магазинов, но это не какое-то чередование порядка программ. Процессоры OoO должны отслеживать порядок памяти, поэтому одному потоку не нужны барьеры, чтобы видеть свои собственные магазины в порядке, но разрешение магазинам фиксироваться из буфера магазина в L1d вне порядка программы, безусловно, может улучшить пропускную способность (особенно если есть несколько магазинов, ожидающих для одной и той же строки, но порядок программы выселит строку из набора-ассоциативного кэша между каждым магазином. например, противный гистограмма паттерна доступа.)
Давайте проведем мысленный эксперимент о том, откуда берутся данные загрузки
Вышесказанное по-прежнему касается только видимости магазина, а не нагрузок. можем ли мы объяснить значение, рассматриваемое каждой нагрузкой как считываемое из глобальной памяти / кэша в какой-то момент (игнорируя любые правила упорядочения нагрузки)?
Если это так, то все результаты загрузки можно объяснить, поместив все хранилища и нагрузки всеми потоками в некоторый комбинированный порядок, читая и записывая a когерентное глобальное состояние памяти.
Оказывается, что Нет, мы не можем, буфер хранилища нарушает это : частичная переадресация хранилища на загрузку дает нам встречный пример (на x86, например). Узкое хранилище, за которым следует широкая загрузка, может объединить данные из буфера хранилища с данными из кэша L1d до того, как хранилище станет глобально видимым. Реальные процессоры x86 действительно делают это, и у нас есть реальные эксперименты, чтобы доказать это.
Если вы только посмотрите на полную переадресацию магазина, если загрузка берет данные только из одного хранилища в буфере хранилища, можно утверждать, что загрузка задерживается буфером хранилища. то есть, что нагрузка появляется в глобальном заказе total load-store сразу после магазина, который делает это значение глобально видимым.
(этот глобальный общий порядок хранения нагрузки не является попыткой создать альтернативную модель упорядочения памяти; он не может описать фактические правила упорядочения нагрузки x86.)
Частичная переадресация хранилища показывает, что данные о загрузке не всегда поступают из глобального когерентного домена кэша.
Если хранилище из другого ядра изменяет окружающие байты, атомарная широкая нагрузка может прочитать значение, которое никогда не существовало и никогда не будет существовать в глобальном когерентном состоянии.
Смотрите мой ответ на Может ли x86 переупорядочить узкий магазин с более широкой загрузкой, которая полностью его содержит?, и ответ Алекса на экспериментальное доказательство того, что такое переупорядочение может произойти, делая предложенную схему блокировки в этот вопрос недействителен. хранилище, а затем перезагрузка с одного и того же адреса не являются барьером для загрузки хранилища .
Некоторые люди(например, Линус Торвальдс) описывают это, говоря, что буфер хранилища не когерентен . (Лайнус отвечал кому-то другому, кто самостоятельно изобрел ту же самую идею с недействительным замком.)
Еще один вопрос, касающийся буфера хранения и когерентности: Как эффективно устанавливать биты битового вектора параллельно?. Вы можете сделать некоторые неатомные ORs чтобы установить биты, затем вернитесь и проверьте наличие пропущенных обновлений из-за конфликтов с другими потоками. Но вам нужен барьер загрузки хранилища (например, x86
lock or), чтобы убедиться, что вы не просто видите свои собственные магазины при перезагрузке.
Нагрузка становится глобально видимой, когда она считывает свои данные. Обычно от L1d, но буфер хранить или оно или некэшируемых памяти и другие возможные источники.
Это определение согласуется с руководствами x86, в которых говорится, что нагрузки не переупорядочиваются с другими нагрузками. т. е. они загружаются (в программном порядке) из представления памяти локального ядра.
Сама загрузка может стать глобально видимой независимо от того, сможет ли какой-либо другой поток загрузить это значение с этого адреса.
Я не уверен, что глобальная видимость является интересной концепцией для операций загрузки (уточнение запрошено ), но если вы хотите использовать ее для разрешения некоторого семантического аргумента, то вам придется зависеть от определений. Если, например, ваше определение global visibility для loads является моментом, когда оно загружает значение из кэша L1, и не допускает возможности пересылки хранилища, то ответ будет либо "оно никогда не становится видимым", либо "ваше определение является дефектный".
На практике, однако, можно думать о нагрузках , получающих свое значение из некоторого конкретного хранилища в системе. Таким образом, мы можем говорить о глобальной видимости для магазинов (и, возможно, частичный или полный порядок на этих магазинах), а затем обсудить, какие грузы могут получать свое значение из каких магазинов. Таким образом, ряд значений, полученных различными нагрузками, помещает их в тип глобального времени (хотя, возможно, только частично упорядоченный, если магазины заказываются только частично).В этой модели нагрузки обычно получают свое значение из некоторого глобально видимого хранилища, но в частном случае пересылки хранилища нагрузка получает свое значение из хранилища , которое еще не является глобально видимым! На практике хранилище (или последующее хранилище, которое перезаписывает его) либо (а) станет глобально видимым в какой-то момент, поскольку оно записывается в L1 из буфера хранилища, либо (Б) будет отброшено из-за какого-то события, такого как предположение сбой, прерывание, исключение и т. д. В случае, когда хранилище отбрасывается, нам не нужно беспокоиться: загрузка только берет свое значение из более раннего хранилища в программном порядке, поэтому, когда хранилище отбрасывается, все более поздние инструкции в программном порядке также отбрасываются, включая загрузку.
В случае, если связанное хранилище в конечном итоге становится глобально видимым, вы получаете интересный эффект типа путешествия во времени: нагрузка на локальный процессор потенциально видела хранилище намного раньше, чем другие процессоры, и в частности, возможно, он видит его не в порядке по отношению к другим хранилищам в системе. Этот эффект является одной из причин, почему системы с переадресацией хранилища обычно имеют переупорядочивание, связанное с этим - например, на сильной модели памяти x86, разрешенные переупорядочивания являются именно теми, которые вызваны буферизацией хранилища и переадресацией хранилища.
Позвольте мне немного расширить вопрос и обсудить аспект корректности реализации переадресации загрузки хранилища. (Вторая половина ответа Питера прямо отвечает на вопрос, который я думаю).
Переадресация хранилища-нагрузки изменяет задержку загрузки, а не ее видимость. Если только он не был смыт из-за какой-то ошибки, магазин в конечном счете станет глобально видимым в любом случае. Без переадресации загрузки хранилища загрузка должна ждать, пока все конфликтующие хранилища не удалятся. А потом ... загрузка может получить данные в обычном режиме.
(точное определение конфликтующего хранилища зависит от модели упорядочения памяти ISA. В x86, предполагая тип памяти WB, который позволяет пересылать данные из хранилища в хранилище, любое хранилище, находящееся ранее в программном порядке и целевое расположение физической памяти которого перекрывает расположение нагрузки, является конфликтующим хранилищем).
Хотя при наличии любого параллельного конфликтующего хранилища от другого агента в системе это может фактически изменить загруженное значение потому что иностранный магазин может вступить в силу после локального магазина, но до локальной загрузки. Как правило, буфер хранилища не находится в области когерентности, и поэтому переадресация загрузки хранилища может уменьшить вероятность того, что произойдет нечто подобное. Это зависит от ограничений реализации переадресации нагрузки хранилища; обычно нет никаких гарантий, что переадресация произойдет для каких-либо конкретных операций загрузки и хранения.
Переадресация загрузки хранилища также может привести к глобальным заказам памяти. без него это было бы невозможно. Например, в сильной модели x86 переупорядочивание нагрузки хранилища разрешено и вместе с переадресацией нагрузки хранилища может позволить каждому агенту в системе просматривать все операции памяти в различных порядках.
В общем случае рассмотрим систему с общей памятью, состоящую ровно из двух агентов. Пусть S1 (A, B) - множество возможных глобальных порядков памяти для последовательностей A и B с переадресацией нагрузки на хранилище, а S2(A, B)-множество возможных глобальных порядков памяти. для последовательностей A и B без пересылки загрузки хранилища. И S1(A, B), и S2(A, B) являются подмножествами множества всех законных глобальных порядков памяти S3 (A, B). Перенаправление нагрузки хранилища может сделать S1(A, B) не подмножеством S2 (A, B). Это означает, что если S2(A, B) = S3 (A, B), то переадресация загрузки хранилища будет незаконной оптимизацией.
Переадресация нагрузки хранилища может изменить вероятность возникновения каждого глобального порядка памяти, поскольку это уменьшает задержку нагрузки.