koszt operacji atomowych

Jaki jest koszt operacji atomowej (dowolnej z opcji porównania i zamiany lub atomowego dodawania / zmniejszania)? Ile cykli zużywa? Czy wstrzyma inne procesory na SMP lub NUMA, czy też zablokuje dostęp do pamięci? Czy opróżni bufor zmiany kolejności w niesprawnym procesorze?

Jakie efekty pojawią się w pamięci podręcznej?

Interesują mnie nowoczesne, popularne procesory: x86, x86_64, PowerPC, SPARC, Itanium.

Szukałem rzeczywistych danych z ostatnich dni i nic nie znalazłem. Jednak przeprowadziłem pewne badania, w których porównuje się koszt atomowych operacji z kosztami błędów pamięci podręcznej.

Koszt prefiksu x86 LOCK (w tym lock cmpxchgatomowego CAS) przed PentiumPro (zgodnie z opisem w dokumentacji) to dostęp do pamięci (jak brak pamięci podręcznej), + zatrzymanie operacji pamięciowych przez inne procesory, + dowolna rywalizacja z innymi procesorami próbuje ZABLOKOWAĆ autobus. Jednak od PentiumPro, dla normalnej pamięci podręcznej z zapisem zwrotnym (cała pamięć, z którą działa aplikacja, chyba że rozmawiasz bezpośrednio ze sprzętem), zamiast blokować wszystkie operacje pamięci, tylko odpowiednia linia pamięci podręcznej jest blokowana (na podstawie linku w odpowiedzi @ osgx ) .

tj. rdzeń opóźnia odpowiadanie na żądania współdzielenia MESI i RFO dla linii aż do zakończenia części lockskładowej rzeczywistej operacji ed. Nazywa się to „blokadą pamięci podręcznej” i dotyczy tylko tej jednej linii pamięci podręcznej. Inne rdzenie mogą jednocześnie ładować / przechowywać lub nawet obsługiwać inne linie.

W rzeczywistości sprawa CAS może być bardziej skomplikowana, jak wyjaśniono na tej stronie , bez czasu, ale wnikliwy opis przez godnego zaufania inżyniera. (Przynajmniej dla normalnego przypadku użycia, w którym wykonujesz czysty ładunek przed faktycznym CAS).

Zanim przejdę do zbyt wielu szczegółów, powiem, że operacja ZABLOKOWANA kosztuje jedną chybienie w pamięci podręcznej + możliwą rywalizację z innym procesorem w tej samej linii pamięci podręcznej, podczas gdy CAS + poprzednie obciążenie (co jest prawie zawsze wymagane z wyjątkiem muteksów, gdzie zawsze CAS 0 i 1) może kosztować dwa chybienia w pamięci podręcznej.

Wyjaśnia, że ​​ładowanie + CAS w jednej lokalizacji może w rzeczywistości kosztować dwa chybienia w pamięci podręcznej, jak Load-Linked / Store-Conditional (zobacz tam, gdzie jest to drugie). Jego wyjaśnienie opiera się na znajomości protokołu koherencji pamięci podręcznej MESI . Używa 4 stanów dla cacheline: M (odified), E (xclusive), S (hared), I (nvalid) (i dlatego nazywa się MESI), wyjaśnione poniżej w razie potrzeby. Scenariusz, wyjaśniony, jest następujący:

• LOAD powoduje brak pamięci podręcznej - odpowiednia linia pamięci podręcznej jest ładowana z pamięci w stanie współdzielonym (tj. inne procesory mogą nadal utrzymywać tę linię pamięci podręcznej w pamięci; w tym stanie nie są dozwolone żadne zmiany). Jeśli lokalizacja jest w pamięci, to brak pamięci podręcznej jest pomijany. Możliwy koszt: 1 brak pamięci podręcznej. (pomijane, jeśli cacheline jest w stanie Shared, Exclusive lub Modified, tj. dane są w pamięci podręcznej L1 tego procesora).
• program oblicza nowe wartości do zapamiętania,
• i uruchamia atomową instrukcję CAS.
  • Musi unikać jednoczesnych modyfikacji, więc musi usunąć kopie pamięci podręcznej z pamięci podręcznej innych procesorów, aby przenieść linię pamięci podręcznej do stanu wyłączności. Możliwy koszt: 1 brak pamięci podręcznej. Nie jest to konieczne, jeśli jest już wyłącznym właścicielem, tj. W stanie wyłącznym lub zmodyfikowanym. W obu stanach żadne inne procesory nie utrzymują linii pamięci podręcznej, ale w stanie wyłącznym nie została ona (jeszcze) zmodyfikowana.
  • Po tej komunikacji zmienna jest modyfikowana w lokalnej pamięci podręcznej naszego procesora, w którym to momencie jest globalnie widoczna dla wszystkich innych procesorów (ponieważ ich pamięci podręczne są spójne z naszymi). Ostatecznie zostanie zapisany w pamięci głównej zgodnie ze zwykłymi algorytmami.
  • Inne procesory próbujące odczytać lub zmodyfikować tę zmienną będą najpierw musiały uzyskać tę linię pamięci podręcznej w trybie współdzielonym lub wyłącznym, a aby to zrobić, skontaktują się z tym procesorem i otrzymają zaktualizowaną wersję tej zmiennej. Zamiast tego operacja ZABLOKOWANA może kosztować jedynie brak pamięci podręcznej (ponieważ linia pamięci podręcznej będzie żądana bezpośrednio w stanie wyłączności).

We wszystkich przypadkach żądanie linii pamięci podręcznej może zostać wstrzymane przez inne procesory, które już modyfikują dane.

Zrobiłem pewne profilowanie z następującą konfiguracją: Maszyna testowa (AMD Athlon64 x2 3800+) została uruchomiona, przełączona w tryb długi (przerwania wyłączone) i instrukcja będąca przedmiotem zainteresowania została wykonana w pętli, 100 iteracji rozwiniętych i 1000 cykli pętli. Treść pętli została wyrównana do 16 bajtów. Czas mierzono instrukcją rdtsc przed i po pętli. Dodatkowo wykonano pozorowaną pętlę bez żadnej instrukcji (która mierzyła 2 cykle na iterację pętli i 14 cykli dla pozostałych), a wynik odjęto od wyniku czasu profilowania instrukcji.

Mierzono następujące instrukcje:

• „ lock cmpxchg [rsp - 8], rdx” (zarówno z dopasowaniem porównawczym, jak i niezgodnością),
• „ lock xadd [rsp - 8], rdx”,
• „ lock bts qword ptr [rsp - 8], 1”

We wszystkich przypadkach zmierzony czas wyniósł około 310 cykli, błąd około +/- 8 cykli

Jest to wartość dla wielokrotnego wykonywania w tej samej (buforowanej) pamięci. Przy dodatkowym braku pamięci podręcznej czasy są znacznie dłuższe. Dokonano tego również z aktywnym tylko jednym z dwóch rdzeni, więc pamięć podręczna była wyłączną własnością i nie była wymagana synchronizacja pamięci podręcznej.

Aby ocenić koszt zablokowanej instrukcji w przypadku chybienia w pamięci podręcznej, dodałem wbinvldinstrukcję przed zablokowaną instrukcją i umieściłem wbinvldplus add [rsp - 8], raxw pętli porównania. W obu przypadkach koszt wyniósł około 80 000 cykli na parę instrukcji! W przypadku blokady bts różnica czasu wynosiła około 180 cykli na instrukcję.

Należy zauważyć, że jest to wzajemna przepustowość, ale ponieważ zablokowane operacje są operacjami serializacji, prawdopodobnie nie ma różnicy w opóźnieniu.

Wniosek: zablokowana operacja jest ciężka, ale brak pamięci podręcznej może być znacznie większy. Ponadto: zablokowana operacja nie powoduje błędów w pamięci podręcznej. Może powodować ruch synchronizacji pamięci podręcznej tylko wtedy, gdy linia pamięci podręcznej nie jest wyłączną własnością.

Aby uruchomić maszynę, użyłem wersji x64 FreeLdr z projektu ReactOS. Oto kod źródłowy 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

W przypadku SMP opartego na magistrali, atomowy prefiks LOCKzapewnia (włącza) sygnał przewodu magistrali LOCK#. Zabroni używania go innym procesorom / urządzeniom na magistrali.

Ppro & książka P2 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 strony 244-246

Zablokowane instrukcje są serializujące, synchronizują operacje .... / o Nieuporządkowany / zablokowany RMW / odczyt-zmodyfikuj-zapis = sam atomowy / instrukcja zapewnia, że ​​procesor wykona wszystkie instrukcje przed zablokowaną instrukcją przed jej wykonaniem. / o jeszcze nie opróżnionych zapisach / wymusza opróżnienie wszystkich wysłanych zapisów w procesorze do pamięci zewnętrznej przed wykonaniem następnej instrukcji.

/ o SMP / semafor jest w pamięci podręcznej w stanie S ... wydaje transakcję odczytu i unieważnienia dla 0 bajtów daty (to jest zabicie / współdzielonych kopii linii pamięci podręcznej w sąsiednich procesorach /)