Jaka jest różnica między harmonogramem "statycznym" a "dynamicznym" W OpenMP?

Inni od tego czasu odpowiedzieli na większość pytania, ale chciałbym wskazać pewne konkretne przypadki, w których konkretny typ harmonogramu jest bardziej odpowiedni niż inne. Schedule kontroluje podział iteracji pętli pomiędzy wątki. Wybór odpowiedniego harmonogramu może mieć duży wpływ na szybkość aplikacji.

static harmonogram oznacza, że bloki iteracji są mapowane statycznie do wątków wykonawczych w sposób round-robin. Ładną rzeczą w planowaniu statycznym jest to, że OpenMP run-time gwarantuje, że jeśli masz dwie oddzielne pętle z tą samą liczbą iteracji i wykonasz je z tą samą liczbą wątków używając statycznego planowania, wtedy każdy wątek otrzyma dokładnie ten sam zakres iteracji w obu równoległych regionach. Jest to dość ważne w systemach NUMA: jeśli dotkniesz pamięci w pierwszej pętli, będzie ona znajdować się na węźle NUMA, w którym znajdował się wątek wykonujący. Następnie w drugiej pętli ten sam wątek mógł szybciej uzyskać dostęp do tego samego miejsca pamięci ponieważ będzie znajdować się na tym samym węźle NUMA.

Wyobraź sobie, że istnieją dwa węzły NUMA: węzeł 0 i węzeł 1, np. dwugniazdowa Płyta Intel Nehalem z 4-rdzeniowymi procesorami w obu gniazdach. Następnie wątki 0, 1, 2 i 3 będą znajdować się na węźle 0, a wątki 4, 5, 6 i 7 będą znajdować się na węźle 1:

|             | core 0 | thread 0 |
| socket 0    | core 1 | thread 1 |
| NUMA node 0 | core 2 | thread 2 |
|             | core 3 | thread 3 |

|             | core 4 | thread 4 |
| socket 1    | core 5 | thread 5 |
| NUMA node 1 | core 6 | thread 6 |
|             | core 7 | thread 7 |

char *a = (char *)malloc(8*4096);

#pragma omp parallel for schedule(static,1) num_threads(8)
for (int i = 0; i < 8; i++)
   memset(&a[i*4096], 0, 4096);

4096 bajtów w ten przypadek jest standardowym rozmiarem jednej strony pamięci w Linuksie na x86, jeśli ogromne strony nie są używane. Ten kod spowoduje zerowanie całej tablicy 32 KiB a. Wywołanie malloc() rezerwuje wirtualną przestrzeń adresową, ale w rzeczywistości nie "dotyka" pamięci fizycznej (jest to domyślne zachowanie, chyba że używana jest inna wersja malloc, np. taka, która zeruje pamięć tak, jak robi to calloc()). Teraz ta tablica jest ciągła, ale tylko w pamięci wirtualnej. W pamięci fizycznej połowa leżałaby w pamięci dołączonej do Gniazdo 0 i pół w pamięci dołączonej do gniazda 1. Dzieje się tak, ponieważ różne części są zerowane przez różne wątki i te wątki znajdują się na różnych rdzeniach i istnieje coś o nazwie first touch NUMA policy, co oznacza, że strony pamięci są przydzielane na węźle NUMA, na którym znajduje się wątek, który pierwszy "dotknął" strony pamięci.

|             | core 0 | thread 0 | a[0]     ... a[4095]
| socket 0    | core 1 | thread 1 | a[4096]  ... a[8191]
| NUMA node 0 | core 2 | thread 2 | a[8192]  ... a[12287]
|             | core 3 | thread 3 | a[12288] ... a[16383]

|             | core 4 | thread 4 | a[16384] ... a[20479]
| socket 1    | core 5 | thread 5 | a[20480] ... a[24575]
| NUMA node 1 | core 6 | thread 6 | a[24576] ... a[28671]
|             | core 7 | thread 7 | a[28672] ... a[32768]

Teraz uruchom kolejną pętlę w ten sposób:

#pragma omp parallel for schedule(static,1) num_threads(8)
for (i = 0; i < 8; i++)
   memset(&a[i*4096], 1, 4096);

Każdy wątek uzyska dostęp do już zmapowanej pamięci fizycznej i będzie miał takie samo mapowanie wątku do regionu pamięci, jak podczas pierwszej pętli. Oznacza to, że wątki będą miały dostęp tylko do pamięci znajdującej się w ich blokach pamięci lokalnej, co będzie szybkie.

Teraz wyobraź sobie, że dla drugiej pętli używany jest inny schemat planowania: schedule(static,2). Spowoduje to "posiekanie" przestrzeni iteracji na bloki dwóch iteracji, a w sumie będą 4 takie bloki. Co się stanie, że będziemy mieli następujący wątek do mapowania lokalizacji pamięci (poprzez numer iteracji):

|             | core 0 | thread 0 | a[0]     ... a[8191]  <- OK, same memory node
| socket 0    | core 1 | thread 1 | a[8192]  ... a[16383] <- OK, same memory node
| NUMA node 0 | core 2 | thread 2 | a[16384] ... a[24575] <- Not OK, remote memory
|             | core 3 | thread 3 | a[24576] ... a[32768] <- Not OK, remote memory

|             | core 4 | thread 4 | <idle>
| socket 1    | core 5 | thread 5 | <idle>
| NUMA node 1 | core 6 | thread 6 | <idle>
|             | core 7 | thread 7 | <idle>

Dzieją się tu dwie złe rzeczy:

• wątki od 4 do 7 pozostają bezczynne, a połowa możliwości obliczeniowych zostaje utracona;
• wątki 2 i 3 uzyskują dostęp do pamięci nielokalnej, a ich ukończenie zajmie im około dwa razy więcej czasu, podczas którego wątki 0 i 1 pozostaną bezczynne.

Więc jedną z zalet korzystania z harmonogramowania statycznego jest to, że poprawia to dostęp do pamięci. Wadą jest zły dobór parametrów planowania może zrujnować występ.

dynamic planowanie działa na zasadzie "kto pierwszy, ten lepszy". Dwa biegi z tą samą liczbą wątków mogą (i najprawdopodobniej) wytworzyć zupełnie inne odwzorowania" przestrzeni iteracji "- > "wątków", co można łatwo zweryfikować: {]}

$ cat dyn.c
#include <stdio.h>
#include <omp.h>

int main (void)
{
  int i;

  #pragma omp parallel num_threads(8)
  {
    #pragma omp for schedule(dynamic,1)
    for (i = 0; i < 8; i++)
      printf("[1] iter %0d, tid %0d\n", i, omp_get_thread_num());

    #pragma omp for schedule(dynamic,1)
    for (i = 0; i < 8; i++)
      printf("[2] iter %0d, tid %0d\n", i, omp_get_thread_num());
  }

  return 0;
}

$ icc -openmp -o dyn.x dyn.c

$ OMP_NUM_THREADS=8 ./dyn.x | sort
[1] iter 0, tid 2
[1] iter 1, tid 0
[1] iter 2, tid 7
[1] iter 3, tid 3
[1] iter 4, tid 4
[1] iter 5, tid 1
[1] iter 6, tid 6
[1] iter 7, tid 5
[2] iter 0, tid 0
[2] iter 1, tid 2
[2] iter 2, tid 7
[2] iter 3, tid 3
[2] iter 4, tid 6
[2] iter 5, tid 1
[2] iter 6, tid 5
[2] iter 7, tid 4

(to samo zachowanie jest obserwowane, gdy gcc jest używany zamiast)

Jeśli przykładowy kod z sekcji static został uruchomiony z dynamic, zamiast tego będzie tylko 1/70 (1,4%) szansy, że oryginalny lokalizacja zostałaby zachowana i 69/70 (98,6%) szans na zdalny dostęp. Fakt ten jest często pomijany i dlatego osiąga się nieoptymalne wyniki.

Jest jeszcze jeden powód, aby wybrać pomiędzy static i dynamic harmonogramowanie - równoważenie obciążeń. Jeśli każda iteracja trwa znacznie różni się od średniego czasu do zakończenia, wówczas może wystąpić wysoka nierównowaga pracy w przypadku statycznym. Weźmy jako przykład przypadek, w którym czas na ukończenie iteracji rośnie liniowo wraz z iteracją numer. Jeśli przestrzeń iteracji jest podzielona statycznie między dwa wątki, drugi będzie miał trzy razy więcej pracy niż pierwszy i dlatego przez 2/3 czasu obliczeniowego pierwszy wątek będzie bezczynny. Dynamiczny harmonogram wprowadza pewne dodatkowe koszty, ale w tym konkretnym przypadku doprowadzi do znacznie lepszego rozkładu obciążenia. Szczególnym rodzajem planowania dynamic jest guided, gdzie do każdego zadania przydzielane są coraz mniejsze bloki iteracji w miarę postępu prac.

Od wstępnie skompilowany kod może być uruchamiany na różnych platformach byłoby miło, gdyby użytkownik końcowy mógł kontrolować planowanie. Dlatego OpenMP udostępnia specjalną klauzulę schedule(runtime). Z runtime scheduling typ jest pobierany z zawartości zmiennej środowiskowej OMP_SCHEDULE. Pozwala to na testowanie różnych typów harmonogramów bez rekompilacji aplikacji, a także pozwala użytkownikowi końcowemu dostroić się do swojej platformy.