стоимость атомной операции - PullRequest
77 голосов
/ 29 марта 2010

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

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

Меня интересуют современные популярные процессоры: x86, x86_64, PowerPC, SPARC, Itanium.

Ответы [ 3 ]

52 голосов
/ 06 мая 2010

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

Стоимость префикса 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), объясненный ниже, где это необходимо. Объясненный сценарий выглядит следующим образом:

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

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

33 голосов
/ 21 апреля 2013

Я выполнил некоторое профилирование со следующей настройкой: Тестовая машина (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
4 голосов
/ 02 апреля 2010

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

Ppro & P2 book http://books.google.com/books?id=3gDmyIYvFH4C&pg=PA245&dq=lock+instruction+pentium&lr=&ei=_E61S5ehLI78zQSzrqwI&cd=1#v=onepage&q=lock%20instruction%20pentium&f=false страницы 244-246

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...