Jaka jest różnica między atomową a krytyczną w OpenMP?

111

Jaka jest różnica między atomową a krytyczną w OpenMP?

mogę to zrobić

#pragma omp atomic
g_qCount++;

ale to nie to samo co

#pragma omp critical
g_qCount++;

?

codereviewanskquestions
źródło

Odpowiedzi:

173

Wpływ na g_qCount jest taki sam, ale to, co zostało zrobione, jest inne.

Sekcja krytyczna OpenMP jest całkowicie ogólna - może otaczać dowolny blok kodu. Płacisz jednak za tę ogólność, ponosząc znaczny narzut za każdym razem, gdy wątek wchodzi i wychodzi z sekcji krytycznej (oprócz nieodłącznego kosztu serializacji).

(Ponadto w OpenMP wszystkie nienazwane sekcje krytyczne są uważane za identyczne (jeśli wolisz, jest tylko jedna blokada dla wszystkich nienazwanych sekcji krytycznych), więc jeśli jeden wątek znajduje się w jednej [nienazwanej] sekcji krytycznej, jak powyżej, żaden wątek nie może wejść do żadnego [nienazwana] sekcja krytyczna. Jak możesz się domyślić, możesz obejść ten problem, używając nazwanych sekcji krytycznych).

Operacja atomowa ma znacznie niższe koszty ogólne. Tam, gdzie to możliwe, wykorzystuje sprzęt zapewniający (powiedzmy) atomową operację inkrementacji; w takim przypadku nie ma potrzeby blokowania / odblokowywania przy wchodzeniu / wychodzeniu z wiersza kodu, po prostu wykonuje atomowy przyrost, o którym sprzęt mówi, że nie można w niego ingerować.

Zaletą jest to, że narzut jest znacznie niższy, a jeden wątek będący w operacji atomowej nie blokuje żadnych (różnych) operacji atomowych, które mają się wydarzyć. Wadą jest ograniczony zestaw operacji obsługiwanych przez atomic.

Oczywiście w każdym przypadku ponosisz koszty serializacji.

Jonathan Dursi
źródło
5
„możesz stracić przenośność” - nie jestem pewien, czy to prawda. W standardzie (wersja 2.0) określa, które są dozwolone operacje atomowe (zasadniczo takie rzeczy jak ++i *=), a jeśli nie są one wspierane sprzętowo, mogą one zostać zastąpione przez criticalsekcje.
Dan R
@DanRoche: Tak, masz rację. Nie sądzę, żeby to stwierdzenie było kiedykolwiek poprawne, poprawię je teraz.
Jonathan Dursi
Kilka dni temu skorzystałem z samouczka OpenMP i, o ile zrozumiałem, istnieje różnica w dwóch różnych kodzie. To jest wynik może się różnić, ponieważ sekcja krytyczna zapewnia, że ​​instrukcja jest wykonywana przez wątek w czasie, jednak możliwe jest, że instrukcja: g_qCount = g_qCount + 1; dla wątku 1 po prostu przechowuje wynik g_qCount tylko w buforze zapisu, a nie w pamięci RAM, a gdy wątek 2 pobiera wartość g_qCount, po prostu odczytuje wynik w pamięci RAM, a nie w buforze zapisu. Instrukcja atomowa zapewnia, że ​​instrukcja
wyczyściła
31

W OpenMP wszystkie nienazwane sekcje krytyczne wzajemnie się wykluczają.

Najważniejszą różnicą między krytycznym a atomowym jest to, że atomic może chronić tylko jedno przypisanie i możesz go używać z określonymi operatorami.

Michael
źródło
13
Byłby to lepszy komentarz (lub zmiana) do poprzedniej odpowiedzi.
kynan
20

Krytyczny fragment:

  • Zapewnia serializację bloków kodu.
  • Można rozszerzyć o serializację grup bloków z odpowiednim użyciem tagu „nazwa”.

  • Wolniej!

Operacja atomowa:

  • Jest dużo szybszy!

  • Zapewnia tylko serializację określonej operacji.

efarsarakis
źródło
9
Ale ta odpowiedź jest bardzo czytelna i byłaby świetnym podsumowaniem pierwszej odpowiedzi
Michał Miszczyszyn
7

Najszybszy sposób nie jest ani krytyczny, ani atomowy. W przybliżeniu dodawanie z sekcją krytyczną jest 200 razy droższe niż zwykłe dodawanie, dodawanie atomów jest 25 razy droższe niż proste dodawanie.

Najszybszą opcją (nie zawsze stosowaną) jest przypisanie każdemu wątkowi własnego licznika i ograniczenie operacji, gdy potrzebna jest całkowita suma.

Andrii
źródło
2
Nie zgadzam się ze wszystkimi liczbami, które wymieniłeś w swoim wyjaśnieniu. Zakładając x86_64, operacja atomowa będzie miała narzut kilku cykli (synchronizacja linii pamięci podręcznej) kosztem mniej więcej jednego cyklu. Jeśli w przeciwnym razie miałbyś koszt `` prawdziwego dzielenia się '', narzut jest nihil. Część krytyczna wiąże się z kosztem zamka. W zależności od tego, czy blokada jest już zajęta, czy nie, narzut to około 2 instrukcje atomowe LUB dwa uruchomienia harmonogramu i czas uśpienia - zwykle jest to znacznie więcej niż 200x.
Klaas van Gend
6

Ograniczenia atomicsą ważne. Powinny być szczegółowo opisane w specyfikacji OpenMP . MSDN oferuje szybką ściągawkę, ponieważ nie zdziwiłbym się, gdyby to się nie zmieniło. (Visual Studio 2012 ma implementację OpenMP od marca 2002). Aby zacytować MSDN:

Wyrażenie musi mieć jedną z następujących form:

xbinop =expr

x++

++x

x--

--x

W poprzednich wyrażeniach: xjest lvaluewyrażeniem o typie skalarnym. exprjest wyrażeniem typu skalarnego i nie odwołuje się do obiektu wyznaczonego przez x. binop jest operator przeciążony i jeden +, *, -, /, &, ^, |, <<, i >>.

Zalecam używać, atomickiedy możesz, i nazwać sekcje krytyczne w inny sposób. Nazwanie ich jest ważne; w ten sposób unikniesz debugowania problemów.

darda
źródło
1
To nie wszystko, mamy inne zaawansowane dyrektywy atomowe, takie jak: #pragma omp aromic update (lub read, upate, write, capture), więc pozwala nam to mieć inne korzystne stwierdzenie
pooria
1

Już świetne wyjaśnienia tutaj. Możemy jednak zanurkować nieco głębiej. Aby zrozumieć podstawową różnicę między koncepcjami sekcji atomowej i krytycznej w OpenMP, musimy najpierw zrozumieć koncepcję blokady . Przyjrzyjmy się, dlaczego musimy używać blokad .

Program równoległy jest wykonywany przez wiele wątków. Rezultaty deterministyczne będą miały miejsce wtedy i tylko wtedy, gdy przeprowadzimy synchronizację między tymi wątkami. Oczywiście synchronizacja między wątkami nie zawsze jest wymagana. Odnosimy się do tych przypadków, w których synchronizacja jest konieczna.

Aby zsynchronizować wątki w programie wielowątkowym, użyjemy blokady . Gdy dostęp ma być ograniczony tylko przez jeden wątek na raz, w grę wchodzą blokady . Blokada realizacja koncepcji może się różnić od procesora do procesora. Zobaczmy, jak prosta blokada może działać z algorytmicznego punktu widzenia.

1. Define a variable called lock.
2. For each thread:
   2.1. Read the lock.
   2.2. If lock == 0, lock = 1 and goto 3    // Try to grab the lock
       Else goto 2.1    // Wait until the lock is released
3. Do something...
4. lock = 0    // Release the lock

Podany algorytm można zaimplementować w języku sprzętowym w następujący sposób. Przyjmiemy jeden procesor i przeanalizujemy zachowanie blokad w tym. W tym celu przyjmijmy jeden z następujących procesorów: MIPS , Alpha , ARM lub Power .

try:    LW R1, lock
        BNEZ R1, try
        ADDI R1, R1, #1
        SW R1, lock

Ten program wydaje się być w porządku, ale tak nie jest. Powyższy kod ma poprzedni problem; synchronizacja . Znajdźmy problem. Załóżmy, że początkowa wartość blokady wynosi zero. Jeśli dwa wątki uruchamiają ten kod, jeden może dotrzeć do SW R1, zablokować, zanim drugi odczyta zmienną lock . Dlatego oboje uważają, że zamek jest bezpłatny. Aby rozwiązać ten problem, podano inną instrukcję zamiast prostej LW i SW . Nazywa się to instrukcją odczytu, modyfikacji i zapisu . Jest to złożona instrukcja (składająca się z podinstrukcji), która zapewnia jednoczesne uzyskanie blokady procedurę wykonuje tylko jedenwątku na raz. Różnica między odczytem, ​​modyfikacją i zapisem ww porównaniu z prostymi instrukcjami odczytu i zapisu jest to inny sposób ładowania i przechowywania . Używa LL (Load Linked) do ładowania zmiennej blokady i SC (Store Conditional) do zapisywania w zmiennej lock. Dodatkowy rejestr linków służy do zapewnienia, że ​​procedura pozyskiwania blokady jest wykonywana przez pojedynczy wątek. Algorytm podano poniżej.

1. Define a variable called lock.
2. For each thread:
   2.1. Read the lock and put the address of lock variable inside the Link Register.
   2.2. If (lock == 0) and (&lock == Link Register), lock = 1 and reset the Link Register then goto 3    // Try to grab the lock
       Else goto 2.1    // Wait until the lock is released
3. Do something...
4. lock = 0    // Release the lock

Gdy rejestr łącza zostanie zresetowany, jeśli inny wątek założył, że blokada jest wolna, nie będzie mógł ponownie zapisać zwiększonej wartości do blokady. Zatem współbieżność dostępu do zamka zmiennej .

Podstawowa różnica między krytycznym a atomowym wynika z pomysłu, że:

Po co używać blokad (nowej zmiennej), skoro możemy używać rzeczywistej zmiennej (którą wykonujemy na niej operację) jako zmiennej blokującej?

Użycie nowej zmiennej dla blokad doprowadzi do sekcji krytycznej , podczas gdy użycie rzeczywistej zmiennej jako blokady doprowadzi do koncepcji atomowej . Sekcja krytyczna jest przydatna, gdy wykonujemy wiele obliczeń (więcej niż jeden wiersz) na rzeczywistej zmiennej. Dzieje się tak, ponieważ jeśli wynik tych obliczeń nie zostanie zapisany na rzeczywistej zmiennej, całą procedurę należy powtórzyć, aby obliczyć wyniki. Może to prowadzić do słabej wydajności w porównaniu z oczekiwaniem na zwolnienie blokady przed wejściem do obszaru wymagającego dużej mocy obliczeniowej. Dlatego zaleca się użycie dyrektywy atomic, gdy chcesz wykonać pojedyncze obliczenia (x ++, x--, ++ x, --x itp.) I użyć dyrektywy krytycznej, gdy sekcja intensywna zajmuje się bardziej złożonym obliczeniowo regionem.

hexpheus
źródło
-5

atomic jest stosunkowo wydajne, gdy trzeba włączyć wzajemne wykluczanie tylko dla jednej instrukcji, podobnie nie jest prawdą w przypadku omp krytycznego.

Mahesh
źródło
13
To nic innego jak źle sformułowane powtórzenie zaakceptowanej odpowiedzi bez wyjaśnienia.
Znak wysokiej wydajności
-5

atomic to pojedyncza instrukcja Sekcja krytyczna, tzn. blokujesz wykonanie jednej instrukcji

sekcja krytyczna to blokada na bloku kodu

Dobry kompilator przetłumaczy twój drugi kod w taki sam sposób jak pierwszy

Wissam Y. Khalil
źródło
Po prostu źle. Proszę, nie mów o rzeczach, których nie rozumiesz.
jcsahnwaldt Przywróć Monikę