Równoległe pętle OpenMP z niewielkim wzrostem wydajności

Question

Jestem w trakcie uczenia się, jak korzystać z OpenMP w C, a jako ćwiczenie HelloWorld piszę program do liczenia liczb pierwszych. I wtedy parallelise to w następujący sposób:

int numprimes = 0; 
#pragma omp parallel for reduction (+:numprimes) 
for (i = 1; i <= n; i++) 
{ 
    if (is_prime(i) == true) 
     numprimes ++; 
} 

skompilować ten kod przy użyciu gcc -g -Wall -fopenmp -o primes primes.c -lm (-lm dla math.h funkcji używam). Następnie uruchamiam ten kod na Intel® Core™2 Duo CPU E8400 @ 3.00GHz × 2 i zgodnie z oczekiwaniami wydajność jest lepsza niż w przypadku programu szeregowego.

Problem pojawia się jednak, gdy próbuję uruchomić to na znacznie potężniejszym komputerze. (Próbowałem również ręcznie ustawić liczbę wątków do korzystania z num_threads, ale to niczego nie zmienia.) Licząc wszystkie liczby pierwsze do 10 000 000 daje mi następujących godzinach (przy użyciu time): maszynę

8-core :

real 0m8.230s 
user 0m50.425s 
sys  0m0.004s 

maszyna dwurdzeniowy:

real 0m10.846s 
user 0m17.233s 
sys  0m0.004s 

a ten wzór trwa liczenie kolejne liczby pierwsze urządzenie z większą liczbą rdzeni pokazuje niewielki wzrost wydajności, ale nie tyle, ile by się spodziewać havin g więcej dostępnych rdzeni. (Spodziewam się 4 razy więcej rdzeni sugerować prawie 4 razy mniej czasu pracy?)

Zliczanie liczb pierwszych do 50 000 000:

8-rdzeń maszyna:

real 1m29.056s 
user 8m11.695s 
sys  0m0.017s 

dwurdzeniowy maszyny:

real 1m51.119s 
user 2m50.519s 
sys  0m0.060s 

Jeśli ktoś może to dla mnie wyjaśnić, byłoby to bardzo cenne.

EDIT

To jest moja funkcja prime-checking.

static int is_prime(int n) 
{ 
    /* handle special cases */ 
    if  (n == 0) return 0; 
    else if (n == 1) return 0; 
    else if (n == 2) return 1; 

    int i; 
    for(i=2;i<=(int)(sqrt((double) n));i++) 
    if (n%i==0) return 0; 

    return 1; 
} 

Answer 1

Spektakl dzieje, ponieważ:

1. is_prime(i) trwa dłużej tym większe i pobiera i
2. Implementacja OpenMP używa statycznego szeregowania domyślnie parallel for konstruktami bez klauzuli schedule, czyli kotlety pętla for w równe wielkości ciągłe fragmenty.

Innymi słowy, wątek o najwyższym numerze wykonuje wszystkie najcięższe operacje.

Jawnie wybierając bardziej odpowiedni typ planowania z klauzulą ​​schedule, można uczciwie dzielić pracę między wątkami.

Ta wersja będzie podzielić prace lepiej:

int numprimes = 0; 
#pragma omp parallel for schedule(dynamic, 1) reduction(+:numprimes) 
for (i = 1; i <= n; i++) 
{ 
    if (is_prime(i) == true) 
     numprimes ++; 
} 

Informacje na temat składni harmonogram jest dostępny poprzez MSDN i Wikipedia.

schedule(dynamic, 1) może nie być optymalny, jak zauważa w swojej odpowiedzi. Istnieje bardziej szczegółowa dyskusja na temat granulacji planowania w tym OpenMP wihtepaper.

Podziękowania także dla Jens Gustedt i Mahmoud Fayez za wniesienie wkładu w tę odpowiedź.

Answer 2

Myślę, że trzeba użyć kod dynamiczny więc nici każdy może zajmować różną liczbę powtórzeń jak twoi iteracje mają różne obciążenia pracą tak aktualny kod jest zrównoważony, który nie pomoże w Twoim przypadku to wypróbować proszę:

int numprimes = 0; 
#pragma omp parallel for reduction (+:numprimes) schedule(dynamic,1) 
for (i = 1; i <= n; i++){ 
    if (is_prime(i) == true) 
    ++numprimes; 
} 

Answer 3

Przyczyną pozornie słabego skalowania programu jest, jak zasugerował @naroom, zmienność w czasie wykonywania każdego połączenia z funkcją is_prime. Czas działania nie zwiększa się po prostu wartością i. Twój kod pokazuje, że test kończy się tak szybko, jak pierwszy czynnik i zostanie znaleziony, więc najdłuższy czas działania będzie dla liczb z kilkoma (i dużymi) czynnikami, włączając w to same liczby pierwsze.

Jak już powiedziano, domyślny harmonogram równoległości spowoduje odtworzenie iteracji głównej pętli na raz do dostępnych wątków. Dla twojego przypadku z 5*10^7 liczb całkowitych do przetestowania i 8 rdzeni do użycia, pierwszy wątek otrzyma liczby całkowite 1..6250000 do przetestowania, drugi otrzyma 6250001..12500000 i tak dalej. Doprowadzi to do znacznego niezrównoważonego obciążenia wątków, ponieważ, oczywiście, liczby pierwsze nie są równomiernie rozłożone.

Zamiast używać domyślnego harmonogramu, należy eksperymentować z dynamicznym szeregowaniem. Poniższe oświadczenie informuje okresie czasu Parcel się iteracje swojej pętli głównej m iteracje w czasie do wątków w Twojej obliczeń:

#pragma omp parallel for schedule(dynamic,m) 

Po wątek zakończył swoje m iteracji zostanie podana m więcej pracować nad. Sztuką dla Ciebie jest znalezienie sweet spot dla m. Zbyt małe i twoje obliczenia będą zdominowane przez pracę, którą wykonuje czas wykonywania w powtarzaniu iteracji, za duże i twoje obliczenia powrócą do niezrównoważonych ładunków, które już widziałeś.

Weź jednak pod uwagę, poznasz kilka przydatnych lekcji na temat kosztów i korzyści związanych z obliczaniem równoległym, wykonując wszystkie te czynności.