Jak dobrać stopień zrównoleglenia?

Zrównoleglenie danego algorytmu to jeszcze nie koniec wyzwań. Pytanie jakie należy postawić, to jak wiele stworzyć wątków? Musimy wziąć pod uwagę synchronizacje i problemy z tym związane.

Jeśli mamy tylko 4 procesory, wtedy tworzenie więcej niż 4 wątków nie przyśpieszy obliczeń, jeśli wszystkie one zawsze będą zajęte. Tworzenie większej liczy wątków niż CPU, ma sens wyłącznie jak część z nich musi czekać na jakieś dane i tym samym, nie wykorzystują one w pełni cykli CPU.

Liczba wątków, zależy od tego jak zaprojektowaliśmy nasz algorytm. Jeśli mamy do dyspozycji komputer z 20 procesorami, nie znaczy to, że 20 wątków zawsze warto tworzyć. W jednym, z ostatnich wpisów pokazałem jakiego typu optymalizacje można osiągnąć. Wniosek był taki, że najczęściej jest to poziom subliniowy. Innymi słowy, jeśli praca na jednym CPU zajęła 10 sekund, to na 5 osiągniemy wynik >2s. Bardzo często jakaś część algorytmu będzie wykonywana równolegle. Oznacza to, że dodając nowe wątki, przyśpieszamy wyłącznie pracę wykonywaną równolegle. Jeśli  10 sekund zajmuje algorytm sekwencyjny, a operacje, które muszą zostać wykonane liniowo zajmują 4 sekundy, to mowa jest tylko o przyśpieszeniu pozostałych operacji, które zajmują 6s.

Prowadzi to do wniosku, że w pewnym momencie, dodawanie nowych rdzeni traci sens, ponieważ wyłącznie sekcja krytyczna będzie wąskim gardłem algorytmu.

Przyśpieszenie algorytmu można wyliczyć za pomocą następującego wzoru:  1 / (S+ (1-S)/P).

S to procent operacji wykonywanych sekwencyjnie (sekcja krytyczna), a 1-S to pozostały procent, przeznaczony na operacje, które mogą zostać wykonane równolegle. P to liczba wątków, czyli stopień zrównoleglenia. Jeśli S=1 to algorytm jest typowo sekwencyjny i nie ważne jak wiele wątków użyjemy, wynik będzie taki sam. Jeśli z kolei 1-S równa się zero, to tworząc 5 nowych wątków, przyśpieszymy algorytm 5-krotnie.

Spójrzmy na przykład. Zakładamy, że 90% operacji muszą zostać wykonane sekwencyjnie. Podstawiając do wzoru, otrzymamy następujące rezultaty:

P

Przyśpieszenie

1 1
2

1.052631579

3

1.071428571

4

1.081081081

5

1.086956522

Jak widać, dodawanie kolejnych rdzeni nie ma zbytniego sensu. Należy jednak pamiętać, że jest to wielkie przybliżenie. W praktyce mamy do czynienia z dodatkowymi czynnikami. Każdy nowy rdzeń to nie tylko dodatkowe cykle, ale również pamięć podręczna. Nie wzięliśmy również pod uwagę, że część kodu może zostać wykonywana dłużej niż inna. Nie da się tego tak łatwo opisać, że 80% kodu można zrównoleglić. Co jeśli czas algorytmu zależy od danych wejściowych? Ma na myśli sytuacje, gdzie np. przetworzenie pierwszej części tablicy zajmuje więcej niż drugiej?

Wzór to wyłącznie przybliżenie ale daje nam konkretną informację na temat korzyści płynących z zrównoleglenia danego algorytmu.

2 thoughts on “Jak dobrać stopień zrównoleglenia?”

Leave a Reply

Your email address will not be published.