D. Klauzula schedule
Region równoległy ma co najmniej jedną barierę na końcu i może mieć w nim dodatkowe bariery. Przy każdej barierze inni członkowie zespołu muszą czekać na przybycie ostatniego wątku. Aby zminimalizować ten czas oczekiwania, wspólna praca powinna być dystrybuowana tak, aby wszystkie wątki docierały do bariery mniej więcej w tym samym czasie. Jeśli część tej udostępnionej pracy znajduje się w for konstrukcjach, klauzula schedule może być używana w tym celu.
W przypadku powtarzających się odwołań do tych samych obiektów wybór harmonogramu for konstrukcji może być określany przede wszystkim przez cechy systemu pamięci, takie jak obecność i rozmiar pamięci podręcznej oraz czy czasy dostępu do pamięci są jednolite lub niezgodne. Takie zagadnienia mogą sprawić, że lepiej, aby każdy wątek konsekwentnie odnosił się do tego samego zestawu elementów tablicy w serii pętli, nawet jeśli niektóre wątki są przypisane stosunkowo mniej pracy w niektórych pętlach. Tę konfigurację można wykonać przy użyciu static harmonogramu z tymi samymi granicami dla wszystkich pętli. W poniższym przykładzie zero jest używane jako dolna granica w drugiej pętli, mimo że k byłoby bardziej naturalne, gdyby harmonogram nie był ważny.
#pragma omp parallel
{
#pragma omp for schedule(static)
for(i=0; i<n; i++)
a[i] = work1(i);
#pragma omp for schedule(static)
for(i=0; i<n; i++)
if(i>=k) a[i] += work2(i);
}
W pozostałych przykładach zakłada się, że dostęp do pamięci nie jest dominującym zagadnieniem. O ile nie określono inaczej, zakłada się, że wszystkie wątki otrzymują porównywalne zasoby obliczeniowe. W takich przypadkach wybór harmonogramu for konstrukcji zależy od wszystkich wspólnych prac, które mają być wykonywane między najbliższą wcześniejszą barierą a domniemaną barierą zamykającą lub najbliższą nadchodzącą barierą, jeśli istnieje klauzula nowait . W przypadku każdego rodzaju harmonogramu krótki przykład pokazuje, jak ten rodzaj harmonogramu może być najlepszym wyborem. Krótka dyskusja jest następstwem każdego przykładu.
Harmonogram static jest również odpowiedni dla najprostszego przypadku, regionu równoległego zawierającego jedną for konstrukcję, z każdą iterację wymagającą tej samej ilości pracy.
#pragma omp parallel for schedule(static)
for(i=0; i<n; i++) {
invariant_amount_of_work(i);
}
Harmonogram static charakteryzuje się właściwościami, które każdy wątek otrzymuje w przybliżeniu taką samą liczbę iteracji, jak każdy inny wątek, a każdy wątek może niezależnie określić przypisane iteracji. W związku z tym żadna synchronizacja nie jest wymagana do dystrybucji pracy, a przy założeniu, że każda iteracja wymaga tej samej ilości pracy, wszystkie wątki powinny zostać zakończone w mniej więcej tym samym czasie.
Dla zespołu wątków p , let ceiling(n/p) być liczbą całkowitą q, która spełnia n = p*q - r z 0 <= r < p. Jedna implementacja harmonogramu dla tego przykładu static spowoduje przypisanie iteracji q do pierwszych wątków p-1 i iteracji q-r do ostatniego wątku. Kolejna akceptowalna implementacja przypisze iteracji q do pierwszych wątków p-r i iteracji q-1 do pozostałych wątków języka r. W tym przykładzie pokazano, dlaczego program nie powinien polegać na szczegółach określonej implementacji.
Harmonogram dynamic jest odpowiedni dla przypadku for konstrukcji z iteracjami wymagającymi różnych, a nawet nieprzewidywalnych ilości pracy.
#pragma omp parallel for schedule(dynamic)
for(i=0; i<n; i++) {
unpredictable_amount_of_work(i);
}
Harmonogram dynamic charakteryzuje się właściwością, że żaden wątek nie czeka na barierę dłużej niż potrzeba innego wątku do wykonania ostatniej iteracji. To wymaganie oznacza, że iteracji muszą być przypisywane pojedynczo do wątków, gdy staną się dostępne, z synchronizacją dla każdego przypisania. Obciążenie synchronizacji można zmniejszyć, określając minimalny rozmiar fragmentu k większy niż 1, dzięki czemu wątki są przypisywane k w czasie do mniej niż k pozostałych. Gwarantuje to, że żaden wątek nie czeka na barierę dłużej niż potrzeba innego wątku do wykonania końcowego fragmentu (w większości) iteracji k .
Harmonogram dynamic może być przydatny, jeśli wątki otrzymują różne zasoby obliczeniowe, co ma znacznie taki sam efekt, jak różne ilości pracy dla każdej iteracji. Podobnie harmonogram dynamiczny może być również przydatny, jeśli wątki docierają do for konstrukcji w różnym czasie, choć w niektórych z tych przypadków guided harmonogram może być preferowany.
Harmonogram guided jest odpowiedni dla przypadku, w którym wątki mogą pojawiać się w różnym czasie w for konstrukcji z każdą iterację wymagającą mniej więcej takiej samej ilości pracy. Taka sytuacja może wystąpić, jeśli na przykład for konstrukcja jest poprzedzona co najmniej jedną sekcją lub for konstrukcją z klauzulami nowait .
#pragma omp parallel
{
#pragma omp sections nowait
{
// ...
}
#pragma omp for schedule(guided)
for(i=0; i<n; i++) {
invariant_amount_of_work(i);
}
}
Podobnie jak dynamic, guided harmonogram gwarantuje, że żaden wątek nie czeka na barierę dłużej niż inny wątek, aby wykonać jego ostateczną iterację, lub końcowe iteracji k , jeśli określono rozmiar fragmentu k . Wśród takich harmonogramów guided harmonogram charakteryzuje się właściwością, która wymaga najmniejszych synchronizacji. W przypadku rozmiaru fragmentu k typowa implementacja przypisze iterację q = ceiling(n/p) do pierwszego dostępnego wątku, ustaw n na większą liczbę n-q i p*k, a następnie powtarza do momentu przypisania wszystkich iteracji.
Jeśli wybór optymalnego harmonogramu nie jest tak jasny, jak w przypadku tych przykładów, runtime harmonogram jest wygodny do eksperymentowania z różnymi harmonogramami i rozmiarami fragmentów bez konieczności modyfikowania i ponownego kompilowania programu. Może to być również przydatne, gdy optymalny harmonogram zależy (w jakiś przewidywalny sposób) od danych wejściowych, do których jest stosowany program.
Aby zobaczyć przykład kompromisów między różnymi harmonogramami, rozważ udostępnienie 1000 iteracji wśród ośmiu wątków. Załóżmy, że istnieje niezmienna ilość pracy w każdej iteracji i użyj jej jako jednostki czasu.
Jeśli wszystkie wątki zaczynają się jednocześnie, static harmonogram spowoduje wykonanie konstrukcji w 125 jednostkach bez synchronizacji. Załóżmy jednak, że jeden wątek to 100 jednostek późno przybywających. Następnie pozostałe siedem wątków czeka na 100 jednostek w barierze, a czas wykonywania całej konstrukcji wzrasta do 225.
Ponieważ zarówno dynamic harmonogramy, jak i guided zapewniają, że żaden wątek nie czeka na więcej niż jedną jednostkę w barierze, opóźniony wątek powoduje, że ich czas wykonywania konstrukcji zwiększa się tylko do 138 jednostek, prawdopodobnie zwiększa się o opóźnienia synchronizacji. Jeśli takie opóźnienia nie są niewielkie, ważne jest, aby liczba synchronizacji wynosiła 1000, dynamic ale tylko 41 dla guidedparametru , przy założeniu domyślnego rozmiaru fragmentu jednego. W przypadku rozmiaru fragmentu 25 i dynamic guided obu zakończeń w 150 jednostkach oraz wszelkich opóźnień z wymaganych synchronizacji, które teraz mają tylko 40 i 20, odpowiednio.