Ciekawe, ilu z nas ma wciąż jeszcze do czynienia z jednordzeniowym procesorem? Po krótkim wywiadzie okazało się, że w moim otoczeniu tylko ja używam jeszcze czasami (za to z wielkim sentymentem) starego dobrego IBMa z P4 1.8GHz na pokładzie. Wszędzie dookoła panują komputery z n-rdzeniowymi procesorami (gdzie n=2 nawet w najprostszych konfiguracjach, nikogo nie dziwią przypadki n=4, a Intel zapowiedział właśnie wprowadzenie na wiosnę tego roku Xeonów, w których n=10 !).
Pytanie tylko, co z tego wynika dla nas-użytkowników oraz czy my-programiści jesteśmy w stanie z tego skorzystać w praktyce ?

Teoria przydzielania czasu procesora (tym samym jego mocy obliczeniowej) poszczególnym programom jest złożona. Na szczęście nie musimy sobie nią zawracać głowy - ten ciężar spoczywa na twórcach systemu operacyjnego, a jak się z tego wywiązują postanowiłem sprawdzić na przykładzie dwóch aplikacji: Excela 2007 oraz Mathematica 8.
W przypadku Excela użyłem znalezionego w sieci arkusza mocno obciążającego obliczeniami, zaś w Mathematice kazałem wykonać (dla zainteresowanych - ma to coś wspólnego z liczbami Mersenne'a) :

min = 1000; max = 5000; step = 500;
Table[{i,AbsoluteTiming[Select[ Range[i], PrimeQ[2^# - 1] &]]}, {i,min, max, step}]; 

Oto wyniki z menadżera zadań:

1) Excel

2) Mathematica

Jak widać system rozkłada moc dość nierównomiernie, zauważalnie silniej obciążając jeden z rdzeni. Gdyby więc zależało nam na jak najszybszym wykonaniu obliczeń, to moglibyśmy chcieć pełniej wykorzystać moc CPU. Z drugiej strony - pozostała moc gwarantuje dobrą 'reagowalność' (responsywność) systemu, dzięki czemu można w tym samym czasie spokojnie pracować z innymi aplikacjami.

Sprawdziliśmy zachowanie potężnych aplikacji komercyjnych, a co z aplikacjami będącymi efektami naszego skromnego kodowania w C# ?
Doświadczenia przeprowadzimy na pewnym zwierzątku - uprzedzając zarzuty ze strony obrońców praw zwierząt - dodam szybko, że znosi ono dobrze wszelkie eksperymenty, bowiem żyje w świecie urojonym (zespolonym).
Mowa o żuku Mandelbrota - jednym z najsłynniejszych przedstawicieli fraktali.

Napisałem w tym celu prostą aplikację wizualizującą ten zbiór - zmieniając parametr 'Ilość iteracji' decydujemy o dokładności odwzorowania zbioru Mandelbrota - tym samym o ilości obliczeń (która rośnie wraz ze zwiększaniem wartości parametru). Dodatkowo mamy 3-pozycyjny przełącznik: single, parallel oraz 2xparallel.
Pracy tutaj dla procesora jest aż nadto - zasadnicza część algorytmu ma postać:

 
for (int xs = 0; xs < imageWidth; xs++)
            {
                for (int ys = 0; ys < imageHeight; ys++)
                {
                    while (...)
                    {
                        ...
                    }
                    ...
                }
            ...
            }

Oto efekt uruchomienia tego programu ze standardowymi ustawieniami początkowymi:

A tutaj obciążenie generowane przez niego:

Pewnie byśmy nie odróżnili pracy tych trzech programów...

"Niech moc będzie z nami"

Przyjmijmy teraz postawę 'chcę więcej i szybciej' - chcemy wycisnąć, ile się da mocy procesora dla naszych obliczeń.
Jak to zrobić w Excelu - nie wiem, natomiast Mathematica (jak przystało na nowoczesny program) pozwala bardzo prosto osiągnąć taki efekt. Wystarczy nieco zmodyfikować poprzednie polecenie poprzez dodanie słówka 'Parallelize' :
Table[{i,AbsoluteTiming[Parallelize[Select[ Range[i], PrimeQ[2^# - 1] &]]]}, {i, min, max, step}];

Tym razem menadżer zadań pokazał coś takiego:
Znacznie lepsze wykorzystanie mocy i idące za tym znaczne skrócenie czasu wykonywania.

Pytanie teraz, czy programista też może osiągnąć takie zrównoleglenie w razie potrzeby? Najlepiej bez tego całego tworzenia wątków, odpowiedniego podziału pracy, synchronizowania wyników itp. ...

W tym momencie z pomocą przychodzi nam nowość w .NET Framework 4 - tytułowe Parallel.For dostępne w System.Threading.Tasks .

Dzięki tej metodzie zamienienie klasycznej sekwencyjnej pętli

for(int i=0;i{
  ciało_pętli_zależne_od_i
}

Parallel.For(0,max,(i)=>
    {
         ciało_pętli_zależne_od_i
    }
)

W przypadku, gdy ciało pętli nie zależy od indeksu napiszemy tak:

Parallel.For(0,max,()=>
    {
        ciało_pętli_niezależne_od_i
    }
)

(iterowany w pętli argument)=>{ ciało pętli zależne od tego argumentu} 

Jeśli się temu przyjrzeć, to wygląda to jak zapis funkcji: x->f(x). Jeśli ciało pętli nie zależy od zmiennej, po której przebiega pętla, to można zapisać:

()=>{ ciało pętli } 

Trzeba wiedzieć (i pamiętać), że Parallel.For(min,max,...) przebiega po wartościach od min włącznie do max-1, zatem równoległa postać pętli 

for(int i=0;i<=max;i++) {...}

 
Parallel.For(0,max+1,...)

Sprawdźmy zatem, jak to działa w praktyce.
Przełączenie programu na 'Parallel' powoduje, że zasadniczy fragment algorytmu wygląda tak:

 
Parallel.For(0, imageWidth, (xs)=>
            {
                for (int ys = 0; ys < imageHeight; ys++)
                {
                    while (...)
                    {
                        ...
                    }
                    ...
                }          
            )

i obciąża CPU praktycznie w 100% :

Efekt? - około dwukrotne przyspieszenie obliczeń (w przypadku mojego 2-rdzeniowego procesora).
Koszt? - raptem 'kosmetyczna' zmiana w kodzie.

Czy to już wszystko? Czy udało się zamknąć całą skomplikowaną teorię programowania równoległego w jednym poleceniu Parallel.For? Niestety tak nie jest. Programując równolegle możemy sporo zyskać na wydajności, ale też musimy uważać na nowe problemy i zjawiska.

Polecam lekturę strony MSDN na ten temat. Oto niektóre z przedstawionych tam problemów.

1. Nie zawsze równoległy znaczy szybszy

Sprawdziłem to tym razem w Mathematice - oto kilka wyników (pozioma oś odmierza wielkość danych, a pionowa czas wykonywania).
 
Natomiast dla większych danych przewaga skorzystania z procesów równoległych staje się bardzo widoczna:

Dla małych danych może się okazać, że koszty poniesione na rozdzielenie zadania na równoległe wątki oraz ich synchronizację są większe niż zysk z prędkości. 
Podobnie możemy nie osiągnąć spodziewanych rezultatów w przypadku zrównoleglania zagnieżdżonych pętli. Efekt takiego zabiegu zależy od stopnia komplikacji obliczeń prowadzonych na każdym poziomie pętli oraz od dostępnych zasobów sprzętowych (rdzeni). Takie podwójne zrównoleglenie w moim programie wywoływane jest przez wybranie opcji 'parallelx2'. 
Podczas testów zdarzały się sytuacje, że to ustawienie dawało dużo gorsze wyniki do zwykłego 'parallel'. Chociaż już uruchomienie programu na 4-rdzeniowych Xeonie dało faktycznie prawie 4-krotne przyspieszenie! 

2. Problem dostępu do zasobów programu (race condition)

Sytuacja taka ma miejsce, gdy wykonujące się obok siebie zadania korzystają np. z tej samej zmiennej. Wówczas jeden wątek może 'popsuć' wartości, z których korzysta inny. Może też nastąpić konflikt dostępu - kiedy wątek czeka usiłuje się dostać do obiektu blokowanego przez inny.
Obie te sytuacje możemy przetrenować na przykładzie naszego programu.
Zaznaczenie 'parallel' zamiast 'single' oznacza przejście z

Color color;
 double x0, y0, x, y, xtemp;
 int iteration;     
 for (int xs = 0; xs < imageWidth; xs++)
 {
 for (int ys = 0; ys < imageHeight; ys++)

na

 
Parallel.For(0,imageWidth,xs=>
 {
 int iteration;
 double x0;
 double y0;
 double x;       
 double y;       
 double xtemp;
 Color color;
 for (int ys = 0; ys < imageHeight; ys++)
 {

Warto zwrócić uwagę na miejsce deklaracji zmiennych - na zewnątrz pętli w piewszym przypadku, a wewnątrz w drugim. Posiadającym dostęp do VS2010 proponuję przeprowadzenie eksperymentu na źródłach: wystarczy w drugim przypadku pozostawić deklaracje na zewnątrz - zupełnie jak w wersji 'single'. Oto efekt takiego zabiegu u mnie:

No cóż - prawie dobrze... Rysunek da się jeszcze rozpoznać, ale nie chciałbym być naświetlany w aparacie rentgenowskim sterowanym takim 'prawie dobrze' działającym programem.

Aby wywołać konfilt dostępu do zasobów, wystarczy zauważyć, że w kodzie źródłowym każdej z równoległych metod jest zakomentowana linijka

bmp.SetPixel(xs, ys, color);

lock (bmp)
{
  bmp.SetPixel(xs, ys, color);
}

3. Nie każdy problem da się zrównogleglić

Tutaj najbardziej narzucającym się przykładem może być rekurencja. Jeżeli obliczenia zależą od jakichś wartości z poprzednich iteracji, to prawie na pewno zrównoleglenie będzie niemożliwe albo obciążone pojawieniem się błędów.
Zrównoleglanie obliczania fraktala daje tak dobre wyniki, ponieważ wartości poszczególnych pikseli nie zależą od innych. 

Parallel.For jest w stanie dać nam wiele, o ile wcześniej dokładnie przemyślimy problem. Zwykłe wrzucenie kodu do tej pętli może okrutnie się na nas zemścić - w naszym doświadczalnym projekcie problemy były widoczne 'na oko'. Gorzej, gdy program nie zgłosi żadnych błędów, a po cichu generowane będą niepoprawne dane - o wiele trudniej jest zdiagnozować taki problem w wersji równoległej.
Mimo to, a może dzięki tym wyzwaniom, myślę, że warto poznać opisane tu zagadnienia dokładniej i mam nadzieję, że Czytelnik podczas lektury nabrał podobnego przekonania. 

Dodaj komentarz:
Autor:*

WWW:

Treść:*

Wprowadź kod zabezpieczający*:


        * - pola wymagane

• Atraktor Lorenza
• O związku motyli z pogodą...
• Nie taki dialog straszny, czyli kilka słów o okienkach dialogowych
• Android - dostosowanie paska tytułowego
• Równoległy może więcej(?) - czyli kilka słów o Parallel.For

• 2012-01-02 09:38:09
  Szanowny Anonimie - może jakieś uzasadnienie? W tym mini-arcie chodziło tylko o zabawę. Nie ukrywam, że nie ja wymyśliłem IFS, a i współczynniki są dostępne powszechnie. Pozdrawiam kuba@leniwce.com
• 2011-12-21 15:01:26
  Jest mi bardzo przkro , gdyz jest to PIRACTWO....
• 2011-11-01 22:30:51
  :)
• 2011-09-27 12:00:59
  Wspomniane w tym artykule zjawisko nowi nazwę "Efekt motyla" i jest ściśle związane z teorią chaosu ;) Według niej, niektórych rzeczy nigdy nie będzie w stanie przewidzieć - niezależnie od szybkości procesorów i technologii :)
• 2011-08-27 15:55:20
  Zgadzam się. Wyraźnie tego nie napisałem, ale przedstawione działanie excela jest w tym sensie jak najbardziej poprawne, i nie może być mowy o błędnym działaniu. Inną kwestią jest świadomość użytkownika, skąd biorą się takie, a nie inne wyniki obliczeń. Artykułem chciałem właśnie zwrócić uwagę na to, że kłopoty z numerycznymi prognozami biorą się z niejako naturalnych zjawisk (punkty 1-3).