koszt operacji atomowych

91

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.

performance  atomic  cpu-architecture  lock-free 
— osgx
źródło
@Jason S, Any. Różnica między cas i atomic inc / dec jest znikoma.
— osgx
2
Niepodzielne operacje na x86 stają się wolniejsze, gdy więcej rywalizacji jest umieszczanych na adresie pamięci. Uważam, że generalnie są one o rząd wielkości wolniejsze niż operacje niezablokowane, ale oczywiście będzie się to różnić w zależności od zastosowanych operacji, rywalizacji i barier pamięci.
— Stephen Nutt
hmmm. writes wydaje się być atomowy na x86. „Zrozumienie jądra Linuksa” -> spin_unlock
— osgx
Zapis 32-bitowy jest atomowy w Javie, tj. Jest przenośny atomowy (ale nie ma semantyki bariery pamięci, więc często jest to niewystarczające dla wskaźników). Dodanie 1 zwykle nie jest atomowe, chyba że dodasz przedrostek LOCK. O jądrze Linuksa, nie ma potrzeby zaglądania do spin_unlock. Zobacz, w aktualnych wersjach arch / x86 / include / asm / atomic_32.h (kiedyś było to include / asm-i386 / atomic.h).
— Blaisorblade
@Blaisorblade, JAvy tu nie ma. Jaki jest koszt operacji ZABLOKOWANYCH?
— osgx

Odpowiedzi:

60

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.

— Blaisorblade
źródło
dlaczego zmiana stanu na inne koszty procesora jako 1 brak pamięci podręcznej?
— osgx
1
Ponieważ jest to komunikacja poza procesorem, a zatem wolniejsza niż dostęp do pamięci podręcznej. Chociaż brak pamięci podręcznej i tak musi przejść od innych procesorów. Właściwie może się zdarzyć, że rozmowa z innym procesorem jest szybsza niż rozmowa z pamięcią, jeśli używane jest bezpośrednie połączenie, takie jak AMD Hypertransport (od bardzo dawna) lub Intel QuickPath Interconnect firmy Intel, na najnowszych procesorach Xeon na podstawie Nehalem. W przeciwnym razie komunikacja z innymi procesorami odbywa się na tej samej magistrali FSB, co pamięć. Wyszukaj HyperTransport i Front Side Bus w Wikipedii, aby uzyskać więcej informacji.
— Blaisorblade
Wow, nigdy nie myślałem, że jego jest tak drogi - brak pamięci podręcznej może wynosić kilka tysięcy cykli.
— Lothar
2
Naprawdę? Liczby, do których przywykłem, to: sto cykli chybionych pamięci podręcznej i tysiące cykli dla przełączników kontekstu / uprawnień (w tym wywołań systemowych).
— Blaisorblade
1
Brak pamięci podręcznej to nie kilka tysięcy cykli! To około 100ns, co zwykle wynosi 300-350 cykli procesora ...
— user997112
37

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
— Timo
źródło
Dzięki! Czy możesz samodzielnie opublikować kod testowy lub przetestować Core2 / Core i3 / i5 / i7? Czy w konfiguracji testowej zainicjowano wszystkie rdzenie?
— osgx
Dodałem kod źródłowy. Zainicjowano tylko jeden rdzeń. Chciałbym zobaczyć wyniki z innych maszyn.
— Timo
CLFLUSH powinien być znacznie lżejszym sposobem opróżnienia linii pamięci podręcznej niż WBINVD całej pamięci podręcznej. WBINVD również opróżni pamięci podręczne instrukcji, co prowadzi do dodatkowych błędów w pamięci podręcznej.
— Peter Cordes
Być może interesujące jest przetestowanie przypadku, gdy linia pamięci podręcznej jest gorąca w stanie współdzielonym. Możesz to zrobić, czytając go w innym wątku z czystym ładunkiem.
— Peter Cordes,
4

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 /)

— osgx
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.