Parrallel Extension, czyli programowanie równoległe, to nowość na platformie .NET 4.0. Platformie która swoje światło ujrzy dopiero w 2010 roku, za to już dziś możemy poznać jeden z jej kluczowych modułów. ParallelFX wprowadza nowy rodzaj programowania, oparty na równoległości, a nie współbieżności, wprowadza możliwości pełnego wykorzystania naszych wielordzeniowych procesorów, czyli jednym słowem, dodaje skrzydeł. Jeśli jesteś ciekawy jak to zrobiono i jak z tego korzystać, zapraszam do czytani
Kiedy kupowaliśmy nasze komputery, pierwszą rzeczą na jaką zwracaliśmy uwagę była częstotliwość procesora. Słusznie. Kiedy motoryzacyjny zapaleniec kupuje kolejne cacko do swojego garażu także patrzy na moc silnika. Więcej = Lepiej, proste. Jednak producenci procesorów (których w końcu nie jest tak wielu) nie mogli nas tak uszczęśliwiać w nieskończoność. Na drodze stanęła im matka natura, a jak wiadomo z kobietami nie jest już tak łatwo. Na pocieszenie dodam, że fascynacji 4 kółek są w o wiele gorszej sytuacji.
W latach 90 w półświatku informatyków dość głośno krążyło pewne prawo. Sformułował je nie byłe kto, bo założyciel firmy Intel, Gordon Moore. Mówiło one że Liczba tranzystorów w układzie elektrycznym podwaja się co 18-24 miesiące. I jak na tamte czasy pasowało idealnie. Postęp techniczny był niewyobrażalny. Coraz więcej tranzystorów potrafiliśmy wcisnąć w jeden wafel krzemu, a jak wiadomo ich liczba decyduje o częstotliwości pracy. Im więcej ich tam utkniemy tym szybciej zakręcimy naszą karuzelą. Lecz kiedy dotarliśmy do rozmiarów rzędu 0.45 nm., przestało już nam być do śmiechu. To bardzo blisko rozmiarów atomu, czy inżynierowie potrafią wetknąć tam coś więcej? Nie znam odpowiedzi na to pytanie. Faktem jest to, że szukano alternatywy, a poszukiwania nie trwały długo, bo odpowiedz wydawała się oczywista. Skoro nie możemy zwiększać prędkości procesorów, to może wpakujmy ich tam po prostu więcej. Stu procentowy przyrost, czyli dołożenie drugiego wydawało się strzałem w dziesiątkę. I tak powstała rodzina procesorów Core Duo. Dla ciekawostki podam, że funkcjonowała tez jednostka Core Solo, która tak naprawdę była Duo, tyle że pracował w niej tylko jeden rdzeń. Czemuż tak? Proces technologiczny w którym produkuje się procesory, nie należy do najłatwiejszych i często coś się po prostu psuje. Intel stwierdził że jeśli usterka nastąpi w jednym rdzeniu, to nie warto wyrzucać całej płytki do kosza. Sprzedawał to co miał, a publika kupowała. Kolejno pojawiły się także jednostki 4 rdzeniowe, a ostatnio nawet „prawie 8”. Prawie bo to ciągle 4 rdzenie, tyle że każdy w technologii HT, przez co system widzi 8 jednostek obliczeniowych. Menadżer zadań wygląda wtedy oszałamiająco.
Mamy więc procesory wielordzeniowe. Co zyskaliśmy? Aby odpowiedzieć zacytuję Dana Reeda z Microsoftu „Różnica jest taka jak między szybkim sportowym autem, a autobusem szkolnym. Pierwszy szybko przewiezie dwie osoby, a drugi, choć trochę wolniej – czterdzieści”. Zauważyć należy bowiem, że jednostki wielordzeniowe nie są tak samo szybkie jak te produkowane pojedynczo. Bo to ciągle jedna płytka i ciągle bardzo mało miejsca. A jaka nas czeka przyszłość? Analitycy z firmy Forrester Research przewidują, że już w 2012 roku rozbudowane procesory wyposażone w 64 rdzenie będą instalowane w komputerach domowych. Dużo? Nie wiem, zobaczymy dopiero w 2012. Dan Reed jednak nas ostrzega „Już niedługo zabraknie programistów z doświadczeniem w tworzeniu aplikacji wykorzystujących przetwarzanie równoległe. To już ostatni dzwonek, aby przekonać młodych programistów o wartości przetwarzania równoległego – dodaje.” Jeśli przebraliście te ogromne wprowadzenie, to bardzo się cieszę, bo pisze ten artykuł właśnie po to aby was o tej wartości przekonać.
Zanim przejdę dalej chciałbym wyjaśnić pewną kwestię. W tytule artykułu pojawia się pewna nierówność: równoległe != (różne od) współbieżne. Napisałem tak bo dla mnie to na prawdę dwie odrębne rzeczy. Czemu? Zastanówmy się. Kiedy wykorzystujemy współbieżność? Wtedy kiedy nie chcemy blokować wątku interfejsu użytkownika, gdy wykonujemy jakąś asynchroniczną operację, lub gdy manipulujemy I/O. A kiedy będziemy wykorzystywać równoległość? W tych samych przypadkach, lecz dodatkowo możemy o wiele bardziej zwiększyć wydajność naszych aplikacji, wykonując równolegle wiele dodatkowych rzeczy. Dokładniej mówiąc współbieżność odnosi się jedynie do pojedynczego rdzenia. To tam dzięki szeregowaniu dostajemy złudny obraz równoległego wykonywania wątków. Równoległość bowiem odnosi się do wielu rdzeni, bo tylko tam możemy niezależnie i fizycznie w tym samym czasie, równolegle wykonywać wątki, przez co znacząco zwiększamy wydajność naszych aplikacji. Zapamiętajmy tą różnicę.
Opisane na początku wydarzenia z rynku procesorów nie działy się przecież tak dawno, 3 może 4 lata wstecz. Już wtedy firma Microsoft wiedziała co z tego może wyniknąć. Jej oddział badawcza, znany także jako Microsoft Research, zaczął pracować nad czymś co pozwoliłoby developerem w łatwy i przyjemny sposób tworzyć aplikację wykorzystując możliwość równoległego wykonywania kodu. I tak powstała biblioteka TPL, czyli Task Parallel Library, która stanowi fundament Parallel Extension, lub jak kto woli ParallelFX i jest częścią nadchodzącej, kolejnej wersji, już 4.0 platformy .NET Framework.
Na samym początku chciałbym pokazać wam przykład jak praktycznie wykorzystać zalety przetwarzania równoległego. Do tego celu posłużę się aplikacją która była dostarczona wraz z wersją CDP (Community Technology Preview) tejże biblioteki. Link do biblioteki pod koniec artykułu. Aplikacja o której mowa zajmuje się generowaniem realistycznych scen 3D wykorzystując dosyć ciężką technikę śledzenia promieni, z ang. Ray Tracing.
Maszyna testowa to: Core Quad (4x 2.2Ghz), 1GB RAM, Windows Server 2008 na Hyper-V.
|
|
Ilość FPS |
Zużycie procesora |
|
Współbieżnie |
0,7 |
26 % |
|
Równolegle |
2,8 |
100% |
Przy pierwszym uruchomieniu, Menadżer zadań pokazał zużycie procesora w 26% co, jak na cztery rdzenie, świadczy o tym że wykorzystaliśmy tylko jeden z nich. Uruchomienie w trybie równoległym dało wzrost pracy do 100%, dzięki czemu wykorzystywaliśmy pełną moc naszej maszyny. Odświeżanie obrazu (FPS) było wtedy prawie 4 razy szybsze. Najciekawszy jest w tym wszystkim fakt, iż na poziomie kodu sposób równoległy od współbieżnego różni się jedynie kilkunastoma znakami. Tak mało za tak wiele, magia? Nie, to jedynie prawidłowe wykorzystanie drzemiącej w naszych komputerach wielordzeniowej mocy obliczeniowej.
Zastanawiacie się zatem jak to wszystko wygląda w kodzie. Aby Wam to przedstawić posłużę się kolejnym przykładem. Identycznym jak ten zaprezentowany przez Daniela Motha na konferencji PDC (Proffesiona Developer Conferension) w październiku 2008 roku.
Mamy sobie więc naszą mała aplikację i w niej metodę, której zadaniem jest wykonać pewne obliczenia na każdym węźle dostarczonego do niej drzewa binarnego. Ciało metody jest jak na razie psute, naszym zadaniem będzie napisanie tej metody w najlepszy możliwy sposób. Spójrzmy w kod:
|
[Kod C#]
using System;
using System.Diagnostics;
using System.Threading;
using System.Threading.Tasks;
namespace Tree
{
class Program
{
static void Main(string[] args)
{
TNode root = TNode.CreateTree(12, 1);
Stopwatch watch = Stopwatch.StartNew();
WalkTree(root);
Console.WriteLine(String.Format("Elapsed = {0}", watch.ElapsedMilliseconds));
}
public static void WalkTree(TNode node)
{
/* To co musimy zaimplementować. */
}
public static int ProcessItem(int value)
{
Thread.SpinWait(4000000);
return value;
}
}
class TNode
{
public TNode LeftNode { get; set; }
public TNode RightNode { get; set; }
public int Value { get; set; }
public static TNode CreateTree(int deep, int start)
{
TNode root = new TNode();
root.Value = start;
if (deep > 0)
{
root.LeftNode = CreateTree(deep - 1, start + 1);
root.RightNode = CreateTree(deep - 1, start + 1);
}
return root;
}
}
} |
Pierwszym pomysłem jaki powinien nam przyjść do głowy, to rekurencja. Tworzyliśmy drzewo w taki sposób wiec możemy tak samo po nim chodzić. Jak wyglądałaby nasza funkcja:
[Kod C#]
public static void WalkTree(TNode node)
{
if (node == null)
return;
WalkTree(node.LeftNode);
WalkTree(node.RightNode);
ProcessItem(node.Value);
} |
Ok. Krótka zgrabna, powinno być dobrze. Sprawdźmy zatem ile czasu zajmie nam taka operacja.
Maszyna testowa to: Core 2 Duo T7100 (2x1,8Ghz), 1GB RAM, Windows XP SP2
20389 ms. Miejcie ten wynik w pamięci. Ok. Ale naszemu przełożonemu nie spodobało się takie rozwiązanie. Zużycie procesora w tym teście to jedynie 50% (Tak pokazywał menadżer zadań). Czyli jak na dwa rdzenie, wykorzystywaliśmy tylko jeden z nich. Połowa mocy naszej maszyny została nie wykorzystana. Co z tym zrobić? Skoro mamy procesor wielordzeniowy, to spróbujmy wykorzystać wątki, wtedy bowiem powinniśmy ruszyć oba rdzenie do pracy. Jak wyglądałaby nasza funkcja kiedy byśmy zaimplementowali ją na wątkach. Spójrzmy:
[Kod C#]
public static void WalkTree(TNode node)
{
if (node == null)
return;
Thread left = new Thread((o) => WalkTree(node.LeftNode));
left.Start();
Thread right = new Thread((o) => WalkTree(node.RightNode));
right.Start();
left.Join();
right.Join();
ProcessItem(node.Value);
} |
Wykorzystano tu składnie Lambda, nowość w platformie .NET 3.5. Użyłem także metod join, aby rozwiązanie było funkcjonalnie porównywalne z rekurencją. Zobaczmy zatem jak czas osiągniemy. 11766 ms., czyli prawie dwa razy lepiej. Super! Podczas testowania miałem uruchomiony menadżer zadani, zrobiłem printscreen’a, spójrzcie:
W 100% wykorzystaliśmy moc naszego procesora. To o co nam chodziło! I gdyby nie jeden problem, rozwiązanie wydawałoby się ideale. W czym rzecz? Jak wygląda wykres zużycia pliku stronnicowego, czyli de facto pamięci? Podczas działania aplikacji, na wykresie powstał mały Mount Everest. Musieliśmy zadeklarować ponad 1GB pamięci. Dla każdego węzła tworzyliśmy wątek, węzłów w drzewie o wysokości 9 jest ponad tysiąc, a każdy wątek na zarządzanej platformie .NET to 1MB pamięci, stąd właśnie owy 1GB zajętości. Co by się stało gdybym zwiększył wysokość drzewa np. do 11? Oczywiście sprawdziłem. Pojawił się wyjątek znany, ale nie tak często spotykany. Out of memory exception, czyli brak pamięci. Jak widać rozwiązanie dobre dla małych zbiorów danych. Zauważmy dodatkowo że taka ilość wątków powodowała duży nakład związany z przełączania kontekstu. Wiele czasu traciliśmy właśnie w taki sposób. Podsumowując? Kiepsko. Jak można zrobić to lepiej? I tutaj z pomocą przychodzi nam Parallel Extension. Do takich celów właśnie to stworzono. Spójrzcie na listing:
[Kod C#]
public static void WalkTree(TNode node)
{
if (node == null)
return;
Task left = Task.Create((o) => WalkTree(node.LeftNode));
Task right = Task.Create((o) => WalkTree(node.RightNode));
left.Wait();
right.Wait();
ProcessItem(node.Value);
} |
Czy widzicie jakieś duże zmiany w porównaniu do wersji wielowątkowej? Nie. Słowo kluczowe Thread zastąpiono Task, a metodę Join w Wait i praktycznie to tyle. Spójrzmy na rezultat. Nasz wynik to 11573 ms, czyli jedynie pół sekundy szybciej, czy to dużo? Co zyskaliśmy? Odpowiedź: pamięć. Podczas działania naszej aplikacji, zarezerwowano jedynie 4 MB pamięci. I gdyby drzewo miało wysokość 11, czy 111, tyle samo pamięci byśmy zajęli. Wracając jednak do czasów. Należy pamiętać że do dyspozycji mam wersje CTP z czerwca 2008. Wiec jest to jeszcze naprawdę wczesna produkcja. Metoda fabrykująca zadania (Task) jest tutaj dość ciężka. Do programistów ParallelFx trafił dość duży feedback odnośnie tego problemu, naprawiono to, jednak nie wypuszczono kolejnej wersji CTP dodatku, wypuszczono bowiem VisualStudio 2010 oraz .NET 4.0 oczywiście wersji CTP w październiku 2008. Wyniki z tej wersji przedstawiam poniżej. Dane pobrane z prezentacji Daniela Motha.
|
|
.NET 4.0 CTP |
|
Rekurencja |
15022ms |
|
Wątki |
5801 ms |
|
Zadania |
3918 ms |
Do końca artykuły zaprezentowane testy będą wykonywane na wersji CTP z czerwca 2008.
Ok. Więc jak to wszystko działa. Dlaczego czasy są lepsze, a zajętość pamięci mniejsza? Czy to magia? Nie. Zajrzyjmy do wnętrza biblioteki TPL (Task Parallel Library) i zobaczmy to wszystko od kuchni. Podstawą kwestią jaką należy zrozumieć to sposób działania menadżera zadań, ale nie tego znanego z Windows, ale menadżera zadań parallel extension. Do artykuły będzie dołączona prezentacja Power Point, na której zasada działania tego moduł jest zaprezentowana w miły, ruszający się sposób, tutaj będzie mi trochę trudniej to zaprezentować.
Menadżer zadań można wyobrazić sobie w poniższy sposób. Jeśli mamy procesor o n rdzeniach, to dla każdego takiego rdzenia tworzona jest grupa robocza (work group) zaznaczona na rysunku zieloną kropą. Każda taka grupa robocza posiada jednego aktywnego workera. Worker to czerwona kropa na obręczy doczepionej do grupy roboczej. Workerów może być więcej, ale tylko jeden może być aktywny. Worker wykonuje zadania na rdzeniu, do którego przypisana jest grupa robocza. Każda grupa robocza posiada własną kolejkę zadań (tak, tych zadań które tworzyliśmy w kodzie). Dodatkowo istnieje także globalna kolejka zadań. Aha, tak naprawdę każda grupa robocza to jeden wątek, niezależnie od ilości workerów w niej egzystujących. Tak więc na każdym rdzeniu mam jeden wątek, skojarzony z naszą aplikacja. A teraz opis jak to wszystko działa.
Kiedy tworzymy nasze pierwsze zadania, trafiają one do globalnej kolejki zadań. Z tamtą zostają one rozdzielone do poszczególnych kolejek grup roboczych. Podział ten nie musi być sprawiedliwy i może zależeć od aktualnego obciążenia rdzeni. Kiedy pracownik (worker) nie wykonuje żadnych zadań zagląda do kolejki swojej grup roboczej i z tamtą pobiera kolejne zadania do wykonania. Załóżmy że w naszym przykładzie do każdej lokalnej kolejki trafiły jakieś zadania. Tak więc każdy pracownik bierze zadanie z kolejki i zaczyna je wykonywać. W tym momencie każdy rdzeń wykorzystywany jest w 100%. Czyli wykorzystujemy cały potencjał naszej maszyny. Super. Co jednak jeśli nasz pracownik skończył wykonywać swoje zadanie, a w kolejce jego grupy jest pusto? Pracownik, to nie student i bardzo chce coś w „życiu” robić. Tak więc zagląda do globalnej kolejki z nadzieją że może znajdą się tam jakieś zadania do wykonania. Jeśli tak, uradowany pobiera zadania i zajmuje się jego wykonywaniem. Co jednak jeśli tam również jest pusto? Czy nasz pracownik, czyli de facto rdzeń będzie siedział bezczynnie? Nie. Tu pojawia się mechanizm, z którego tak bardzo dumni są programiści i inżynierowie ParalleFX. Work Stealing, czyli kradzież pracy. Pracownik przegląda wszystkie lokalne kolejki sąsiednich grup roboczych i jeśli są tam zadania, kradnie je. Co oczywiście ma skutek w tym, że znów wszystkie rdzenie pracują pełna parą. Osiągnięto zatem równomierny rozkład pracy na wszystkie rdzenie procesora. Mechanizm jak najbardziej godny pochwały. W naszym przykładzie o drzewie, zadania tworzyły kolejne zadania do wykonywania. Jak to wszyto wygląda? Otóż, jeśli zadanie tworzy kolejne, to pracownik które wykonuje owo zadanie wrzuca je do lokalnej kolejki grupy roboczej. Czemu nie do globalnej? Bo to jest jego zadania, czemu miałby się dzielić. Wrzuca je do kolejki która funkcjonuje jako LIFO, czyli last in first out. Czemu tak? Zadania które zostało stworzone jako ostatnie, i będzie teraz wykonywane, bo znajduje się na pierwszym miejscu kolejki, z pewnością ma swoje dane jeszcze ciepłe w pamięci podręcznej rdzenia, wiec nie trzeba będzie ściągać ich z pamięci. Bardzo sprytnie. Co jednak z kolejnością zadań? Tu nie mamy praktycznie za dużej kontroli. Zadania jakie tworzymy powinny być od siebie niezależne, oczywiście mogą być, ale idea jest taka ażeby nie był. Więcej o tym pod koniec artykułu. Wracając jednak do naszego menadżera zadań. Jak wiemy pracownicy lubią kraść zadania innym. Jednak jak to robią? Kradną oni zadania ze szczytu kolejki, czyli nie z tego końca z którego pobiera je pracownik. Czemu tak? Skoro zadanie jest na końcu, to prawdopodobnie zostało stworzone dość dawno, a skoro tak, to dane dotyczące tego zadania nie znajdują się pewnie w cashu rdzenia na którym ustawiona jest grupa robocza od której kradniemy zadania. Tak więc nie trzeba będzie synchronizować się miedzy rdzeniami, znów bardzo zmyślne rozwiązanie, znacznie przyspieszające prace. Dla mnie bajka. Do omówienia został jeszcze jeden przypadek. W naszym przykładzie zadania blokowały się czekając aż wykonają się inne. Do tego celu służy metoda Wait. Jak to wygląda w menadżerze? Kiedy zadanie się blokuje, to pracownik który je wykonywał zamraża się, a grupa robocza tworzy kolejnego pracownika, który staje się tym aktywnym i wykonuje zadania znajdujące się w kolejce lub kradnie je innym. Należy wspomnieć że tworzenie nowego pracownika nie wiąże się z tworzeniem nowego wątku. Cała grupa robocza oraz wszyscy jej pracownicy wykonują się w tym samym wątku. Kiedy zadanie może być kontynuowane, to zamrożony pracownik oddaje je aktywnemu, lub inny pracownik z innej grup roboczej kradnie je i wykonuje dalej.
Uff… strasznie długo to opisywałem, ale mam nadzieję że wszystko wydaje się zrozumiałe.
Kolejna cześć artykułu już wkrótce. A w niej:
· Równoległe pętle for, foreach
· P/LINQ czyli Równoległy LINQ
· Mnóstwo ciekawych przykładów
Zapraszam do komentowania.
ParallelFX: http://msdn.microsoft.com/en-us/concurrency/default.aspx
Więcej literatury i więcej linków, w drugiej części artykułu.
Załączniki: