Стоимость атомной операции

Question

Какова стоимость атомарной операции (любая из операций сравнения и замены или атомарного добавления / уменьшения)? Сколько циклов он потребляет? Это приостановит другие процессоры на SMP или NUMA, или это заблокирует доступ к памяти? Будет ли он очищать буфер переупорядочения в неработающем процессоре?

Какие эффекты будут на кеше?

Я заинтересован в современных популярных процессорах: x86, x86_64, PowerPC, SPARC, Itanium.

Answer 1

Я искал фактические данные за прошедшие дни и ничего не нашел. Тем не менее, я провел некоторое исследование, которое сравнивает стоимость атомарных операций с затратами на кэширование.

Стоимость префикса x86 LOCK, или CAS, до PentiumPro (как описано в документе) - это доступ к памяти (например, потеря кэша), + остановка операций с памятью другими процессорами, + любой конфликт с другими процессорами, пытающимися заблокировать автобус. Однако, поскольку PentiumPro, для обратной записи (т.е. кешируемой) памяти (со всей памятью, с которой работает приложение, если вы не общаетесь напрямую с аппаратным обеспечением), вместо блокировки всех операций с памятью блокируется только соответствующая кешлайн (на основе ссылки, размещенной выше).

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

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

Он объясняет, что загрузка + CAS в одном месте может стоить два промаха в кэше, например Load-Linked/Store-Conditional (см. Там о последнем). Его объяснение основано на знании протокола согласованности кэша MESI. Он использует 4 состояния для кэширования: M(одифицированный), E(xclusive), S(hared), I(nvalid) (и, следовательно, он называется MESI), объясненный ниже при необходимости. Сценарий, объясненный, следующий:

• ЗАГРУЗКА вызывает пропадание кеша - соответствующая кешлайн загружается из памяти в состоянии Shared (т. е. другим процессорам все еще разрешается хранить эту кешлинку в памяти; в этом состоянии изменения не допускаются). Если место находится в памяти, эта ошибка кэша пропускается. Возможная стоимость: 1 промах кеша. (пропускается, если строка кэша находится в состоянии Shared, Exclusive или Modified, т.е. данные находятся в кэше L1 этого ЦП).
• программа рассчитывает новые значения для хранения,
• и он запускает атомарную инструкцию CAS.
  • Он должен избегать одновременной модификации, поэтому он должен удалять копии строки кэша из кэша других процессоров, чтобы переместить строку кэширования в состояние "Эксклюзив". Возможная стоимость: 1 промах кеша. В этом нет необходимости, если он уже находится в исключительной собственности, то есть в состоянии "Исключено" или "Изменено". В обоих состояниях никакие другие процессоры не поддерживают кэш-строку, но в состоянии "Исключительно" она не была изменена (пока).
  • После этой связи переменная изменяется в локальном кеше нашего ЦП, и в этот момент она видна всем другим ЦП в глобальном масштабе (потому что их кеши согласованы с нашими). В конечном итоге он будет записан в основную память в соответствии с обычными алгоритмами.
  • Другие процессоры, пытающиеся прочитать или изменить эту переменную, сначала должны получить эту строку кэширования в режиме совместного использования или в эксклюзивном режиме, и для этого они свяжутся с этим процессором и получат обновленную версию строки кэша. Вместо этого операция LOCKed может стоить только промаха кэша (потому что линия кэширования будет запрашиваться непосредственно в исключительном состоянии).

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

Answer 2

Я выполнил некоторое профилирование со следующей настройкой: Тестовый компьютер (AMD Athlon64 x2 3800+) был загружен, переключен в длинный режим (прерывания отключены), и интересующая инструкция была выполнена в цикле, развернутых 100 итераций и 1000 циклов цикла. Тело цикла было выровнено до 16 байтов. Время измерялось с помощью инструкции rdtsc до и после цикла. Кроме того, был выполнен фиктивный цикл без какой-либо инструкции (который измерял 2 цикла на итерацию цикла и 14 циклов для остальных), и результат был вычтен из результата времени профилирования команды.

Следующие инструкции были измерены:

• "lock cmpxchg [rsp - 8], rdx"(как при сравнении, так и при несовпадении),
• "lock xadd [rsp - 8], rdx",
• "lock bts qword ptr [rsp - 8], 1"

Во всех случаях измеренное время составляло около 310 циклов, ошибка составляла около +/- 8 циклов.

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

Чтобы оценить стоимость заблокированной инструкции по отсутствию кэша, я добавил wbinvld инструкция перед заблокированной инструкцией и положить wbinvld плюс add [rsp - 8], rax в цикл сравнения. В обоих случаях стоимость составляла около 80 000 циклов на пару инструкций! В случае блокировки bts разница во времени составляла около 180 циклов на инструкцию.

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

Вывод: заблокированная операция тяжелая, но потеря кеша может быть намного тяжелее. Также: заблокированная операция не приводит к отсутствию кэша. Это может вызвать только трафик синхронизации кеша, когда кешлайн не принадлежит исключительно.

Для загрузки машины я использовал версию FreeLdr x64 из проекта ReactOS. Вот исходный код asm:

#define LOOP_COUNT 1000
#define UNROLLED_COUNT 100

PUBLIC ProfileDummy
ProfileDummy:

    cli

    // Get current TSC value into r8
    rdtsc
    mov r8, rdx
    shl r8, 32
    or r8, rax

    mov rcx, LOOP_COUNT
    jmp looper1

.align 16
looper1:

REPEAT UNROLLED_COUNT
    // nothing, or add something to compare against
ENDR

    dec rcx
    jnz looper1

    // Put new TSC minus old TSC into rax
    rdtsc
    shl rdx, 32
    or rax, rdx
    sub rax, r8

    ret

PUBLIC ProfileFunction
ProfileFunction:

    cli

    rdtsc
    mov r8, rdx
    shl r8, 32
    or r8, rax
    mov rcx, LOOP_COUNT

    jmp looper2

.align 16
looper2:

REPEAT UNROLLED_COUNT
    // Put here the code you want to profile
    // make sure it doesn't mess up non-volatiles or r8
    lock bts qword ptr [rsp - 8], 1
ENDR

    dec rcx
    jnz looper2

    rdtsc
    shl rdx, 32
    or rax, rdx
    sub rax, r8

    ret

Answer 3

На основе SMP на основе шины, атомный префикс LOCK утверждает (включает) сигнал проводной шины LOCK#, Это запретит другим процессорам / устройствам на шине использовать его.

Книга Ppro & P2 http://books.google.com/books?id=3gDmyIYvFH4C&pg=PA245&dq=lock+instruction+pentium&lr=&ei=_E61S5ehLI78zQSzrqwI&cd=1

Заблокированные инструкции - это сериализация, синхронизация операций... /about Out-of-order/ заблокированный RMW/read-modify-write = atomic самой / инструкция гарантирует, что процессор выполнит все инструкции до заблокированной инструкции до ее выполнения. / о еще не очищенных записях / заставляет все записанные записи в процессоре быть сброшенными во внешнюю память перед выполнением следующей инструкции.

/ о SMP/ семафор находится в кеше в состоянии S... выдает транзакцию чтения и аннулирования для 0 байтов даты (это уничтожение / общих копий строки кэша в соседних процессорах /)