Какие архитектуры процессоров поддерживают сравнение и обмен (CAS)?

Question

просто интересно узнать, какие архитектуры процессоров поддерживают сравнение и замену атомарных примитивов?

Answer 1

Powerpc имеет более мощные доступные примитивы: "lwarx" и "stwcx"

lwarx загружает значение из памяти, но запоминает местоположение. Любой другой поток или процессор, который касается этого места, приведет к сбою "stwcx", инструкции условного хранения.

Таким образом, комбо lwarx / stwcx позволяет вам реализовывать атомарные инкременты / декременты, сравнивать и менять местами и более мощные атомарные операции, такие как «индекс циклического буфера атомных инкрементов»

Answer 2

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

Единственный, кого я знаю, это PARISC, в котором есть только атомарное ясное слово. Это может быть использовано для создания мьютекса (при условии, что слово выравнивается по 16-байтовой границе). В этой архитектуре нет CAS (в отличие от x86, ia64, ppc, sparc, mips, s390, ...)

Answer 3

Несколько человек прокомментировали / спросили, нужен ли префикс "lock" на x86 / x64 для cmpxchg. Ответ да для многоядерных машин. Инструкция полностью атомарна для одноядерных машин без блокировки.

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

Answer 4

Извините за большое количество писем. (

Почти все инструкции в x86 ISA (кроме так называемых строковых инструкций и, возможно, нескольких других), включая CMPXCHG, являются атомарными в контексте одноядерного ЦП. Это связано с тем, что в соответствии с архитектурой x86 ЦП проверяет поступившие прерывания после каждого выполнения инструкции, а не в середине. В результате запрос прерывания может быть обнаружен и его обработка может быть запущена только на границе между выполнением двух последовательных инструкций. В связи с этим все ссылки на память, используемые ЦП во время выполнения одной инструкции, изолированы и не могут быть чередованы никакими другими действиями. Такое поведение характерно для одноядерных и многоядерных процессоров. Но если в контексте одноядерного ЦП имеется только один блок системы, который осуществляет доступ к памяти, в контексте многоядерного ЦП имеется более одного блока системы, который одновременно осуществляет доступ к памяти. Изоляция инструкций недостаточна для согласованности в такой среде, поскольку доступ к памяти, осуществляемый разными процессорами в одно и то же время, может чередовать друг друга. Благодаря этому дополнительный уровень защиты должен применяться к протоколу изменения данных. Для x86 этот уровень является префиксом блокировки, который инициирует атомарную транзакцию на системной шине.

Резюме. Безопасно и дешевле использовать команды синхронизации, такие как CMPXCHG, XADD, BTS и т. Д., Без префикса блокировки, если вы уверены, что к данным, доступным по этой инструкции, может обращаться только одно ядро. Если вы не уверены в этом, примените префикс блокировки для обеспечения безопасности за счет снижения производительности.

Существует два основных подхода к поддержке аппаратной синхронизации ЦП:

1. На основе атомарной транзакции.
2. На основе протокола согласованности кэша.

Никто не является серебряной пулей. Оба подхода имеют свои преимущества и недостатки.

Подход, основанный на атомарных транзакциях, основан на поддержке специального типа транзакций на шине памяти. Во время такой транзакции только один агент (ядро ЦП), подключенное к шине, имеет право доступа к памяти. В результате, с одной стороны, все ссылки на память, сделанные владельцем шины во время атомарной транзакции, гарантированно будут выполнены как одна непрерывная транзакция. С другой стороны, все остальные агенты шины (ядра ЦП) будут вынуждены ждать завершения атомарной транзакции, чтобы получить возможность доступа к памяти. Неважно, к каким ячейкам памяти они хотят получить доступ, даже если они хотят получить доступ к области памяти, на которую не обращается владелец шины во время атомарной транзакции. В результате широкое использование инструкций с префиксом блокировки значительно замедлит работу системы. С другой стороны, из-за того, что арбитр шины предоставляет доступ к шине для каждого агента шины в соответствии с циклическим планированием, существует гарантия, что каждый агент шины будет иметь относительно справедливый доступ к памяти, и все агенты будут удалось добиться прогресса и сделал это с той же скоростью. Кроме того, проблема ABA вступает в игру в случае атомарных транзакций, потому что по своей природе атомарные транзакции очень короткие (несколько ссылок на память, сделанные одной инструкцией), и все действия, выполняемые с памятью во время транзакции, зависят только от значения области памяти. без учета того, что область памяти была доступна кому-то еще между двумя транзакциями. Хорошим примером поддержки синхронизации на основе атомарных транзакций является архитектура x86, в которой инструкции с префиксом блокировки заставляют ЦПУ выполнять их в атомарных транзакциях.

Подход, основанный на протоколе когерентности кэша, основан на том факте, что строка памяти может кэшироваться только в одном кэше L1 в один момент времени. Протокол доступа к памяти в системе когерентности кэша аналогичен следующей последовательности действий:

1. CPU A хранит строку памяти X в кеше L1. В то же время CPU B желает получить доступ к строке памяти X. (X -> CPU A L1)
2. ЦП B выдает строку памяти X транзакции доступа на шине. (X -> CPU A L1)
3. Все агенты шины (ядра ЦП) имеют так называемый агент отслеживания, который прослушивает все транзакции на шине и проверяет, хранится ли строка памяти, к которой запрашивалась транзакция, в кэш-памяти L1 ЦП своего владельца. Таким образом, CPU A snooping agent обнаруживает, что CPU A владеет строкой памяти, запрошенной CPU B. (X -> CPU A L1)
4. CPU A транзакция приостановки доступа к памяти, выданная CPU B. (X -> CPU A L1)
5. CPU A очищает строку памяти, запрошенную B, из своего кэша L1. (X -> память)
6. CPU Возобновление ранее приостановленной транзакции. (X -> память)
7. CPU B извлекает строку памяти X из памяти. (X -> CPU B L1)

Благодаря этому протоколу ядро ​​ЦП всегда получает доступ к актуальным данным в памяти, а доступ к памяти сериализуется в строгом порядке, один доступ во времени. Поддержка синхронизации на основе протокола когерентности кэша основана на том факте, что ЦП может легко обнаружить, что к определенной линии памяти обращались между двумя временными точками. Во время первого доступа к строке X, которая должна открыть транзакцию, CPU может пометить, что строка памяти в кэше L1 должна контролироваться агентом отслеживания. В свою очередь, отслеживающий агент может во время очистки строки кэша дополнительно выполнить проверку, чтобы определить, отмечена ли строка для контроля, и поднять внутренний флаг, если контролируемая строка очищена. В результате, если ЦП будет проверять внутренний флаг во время доступа к памяти, который закрывает транзакцию, он будет знать, что контролируемая строка памяти может быть изменена кем-то другим, и приходит к выводу, что транзакция должна быть выполнена успешно или должна рассматриваться как неудачная. Это способ реализации класса команд LL \ SC. Этот подход более простой, чем атомарные транзакции, и обеспечивает гораздо большую гибкость в синхронизации, поскольку на его основе может быть построено гораздо большее количество различных синхронизирующих примитивов по сравнению с подходом атомарных транзакций. Этот подход является более масштабируемым и эффективным, потому что он не блокирует доступ к памяти для всех других частей системы. И, как вы можете видеть, это решает проблему ABA, потому что основано на факте обнаружения доступа к области памяти, а не на значении обнаружения изменения области памяти. Любой доступ к области памяти, участвующей в текущей транзакции, будет рассматриваться как сбой транзакции. И это может быть хорошим и плохим одновременно, потому что конкретный алгоритм может интересоваться только значением области памяти и не принимает во внимание тот факт, что кто-то посередине получил доступ к местоположению, пока этот доступ не изменит память , В этом случае чтение значения памяти в середине приведет к ложному отрицательному сбою транзакции. Кроме того, такой подход может привести к значительному снижению производительности потоков управления, содержащихся в одной и той же строке памяти, поскольку они способны постоянно соединять линии памяти друг от друга и тем самым препятствовать успешному завершению транзакции друг друга. Это действительно серьезная проблема, потому что в терминальном случае это может превратить систему в живую блокировку. Поддержка синхронизации на основе протокола кэширования обычно используется в процессоре RISC из-за простоты и гибкости. Но следует отметить, что Intel решила поддержать такой подход для поддержки синхронизации и в архитектуре x86. В прошлом году Intel объявила о расширении Transactional Synchronization для архитектуры x86, которое будет реализовано в процессорах Intel Haswell поколения. В результате, похоже, x86 получит самую мощную поддержку синхронизации и позволит разработчикам систем использовать преимущества обоих подходов.

Answer 5

Начиная с архитектуры ARMv6, ARM имеет инструкции LDREX / STREX, которые можно использовать для реализации атомарной операции сравнения-обмена.

Answer 6

Intel x86 имеет эту поддержку. IBM в своем Руководстве по переносу с Solaris на Linux приводит следующий пример:

bool_t My_CompareAndSwap(IN int *ptr, IN int old, IN int new)
{
        unsigned char ret;

        /* Note that sete sets a 'byte' not the word */
        __asm__ __volatile__ (
                "  lock\n"
                "  cmpxchgl %2,%1\n"
                "  sete %0\n"
                : "=q" (ret), "=m" (*ptr)
                : "r" (new), "m" (*ptr), "a" (old)
                : "memory");

        return ret;
}

Answer 7

Просто для завершения списка, MIPS имеет инструкции Load Linked (ll) и Store Conditional (sc), которые загружают значение из памяти и позже условно сохраняют, если никакой другой ЦП не получил доступ к этому месту. Это правда, что вы можете использовать эти инструкции для выполнения операций подкачки, приращения и других операций. Однако недостатком является то, что при большом количестве процессоров, очень интенсивно выполняющих блокировки, вы попадаете в livelock: условное хранилище часто выходит из строя и требует повторного цикла, который завершится неудачей и т. Д.

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

Answer 8

Сравнение и замена были добавлены в мэйнфреймы IBM в 1973 году. Они (и сравнивают double и swap) все еще находятся в мэйнфреймах IBM (наряду с более поздними многопроцессорными функциями, такими как PLO - выполнение заблокированной операции).

Answer 9

x86 и Itanium имеют CMPXCHG (сравните и обменяйте)

Answer 10

Sparc v9 имеет инструкцию cas. В руководстве по архитектуре SPARC v9 обсуждается использование инструкции CAS в Приложении J, обратите особое внимание на примеры J.11 и J.12.

Я считаю, что название инструкции на самом деле "casa", потому что оно может получить доступ либо к текущему адресному пространству, либо к альтернативному. "cas" - это макрос ассемблера, который обращается к текущему ASI.

Есть также статья на developers.sun.com , в которой обсуждаются различные элементарные инструкции, которые процессоры Sparc реализовывали на протяжении многих лет, включая cas.