1 Możliwości automatycznego zrównoleglania kodu w kompilatorze języka C Piotr Błaszyński Katedra Inżynierii Oprogramowania

2 Szybkie programy Prawa ograniczające:  prawo Moore'a (jego granice),  prawo Gatesa,  prawo Amdahla,  prawo Gustafsona.

3 Problemy i rozwiązania Programiści nie znają wszystkich metod uzyskiwania wyższej wydajności, Pracując z istniejącym kodem muszą go dobrze zrozumieć przed dokonaniem zmian. Automatyczne wyszukiwanie najlepszego kodu  sekwencyjnego,  równoległego.

4 Problemy i inne rozwiązania  LLVM  Profiler guided  HotSpot i JIT (dlaczego muszą być rozpędzone i czy zużywają zasoby)  Architektury się jednak zmieniają

5 Kompilacja iteracyjna  Przy pomocy modelu statycznego dokonuje się wyboru metod optymalizacji kodu wynikowego jak w tradycyjnym kompilatorze,  Wybierane są parametry dla wybranych optymalizacji,  Generowany jest tymczasowy kod wynikowy z wybranymi wcześniej parametrami,  Testowana jest wydajność kodu wynikowego, informacje te są zwrotnie przekazywane do kompilatora

6 Kompilacja iteracyjna  Na podstawie powyższych informacji zmieniane są parametry i następuje kolejna kompilacja,  W przypadku jeśli wydajność jest na wystarczającym poziomie, przygotowywana jest wersja ostateczna kodu wynikowego.

7 Model kompilatora Kod źródłowy Kompilator (analiza statyczna) Ostateczny kod wynikowy Tymczasowy kod wynikowy Profilowanie / symulacja (analiza dynamiczna) System ekspercki Analiza empiryczna Algorytmy ewolucyjne Sprzężenie zwrotne Wyniki empiryczne Pula transformacji

8 Metody testowania 1.Przygotowanie eksperymentów i na ich podstawie opracowanie części wiedzy 2.Opracowanie modelu Dane wejściowe: Program źródłowy, architektura, rozmiar problemu, zbiór parametrów. Dane wejściowe przekształcane przy pomocy opracowanego modelu. Na wyjściu otrzymujemy wybrane/zaproponowane parametry (zestaw parametrów) dla zadanego kryterium (czas, pamięć, energia). Dodatkowo elementem danych wejściowych dla opracowanego modelu jest wiedza pochodząca z eksperymentów.

9 Stosowane narzędzia MiiBench + Własny zestaw testowy GCC Własny frontend kompilatora (ANSI C) przygotowanie do analizy zależności

10 Prosty przykład - loop unrolling Loop Unrolling Żeby można było zmieniać kolejność kodu, w większości przypadku należy zwracać uwagę na granice pojedynczej iteracji pętli (występuje tam przede wszystkim zmiana przepływu sterowania przez instrukcje skoku). Efektywną techniką pozwalającą rozwiązać ten problem jest rozwijanie pętli. Zalecane są niewielkie rozmiary rozwinięć. Dzięki rozwinięciom możliwe jest łatwiejsze, o ile nie ma zależności, znalezienie możliwości zrównoleglenia.

11 Prosty przykład - loop unrolling Pętla for for (i=0; i

12 Prosty przykład - loop unrolling wszystkie testy z MiiBench, wielkość rozwinięć większa od przyjętej standardowo, własny frontend kompilatora (ANSI C) - modyfikacja źródeł.

13 Prosty przykład - loop unrolling Przykładowy program w wersji oryginalnej, for (i = 1; i > 8; j = 1 + (j / 2); weight[i] = j

14 Prosty przykład - loop unrolling Przykładowy program w wersji rozwiniętej 4 razy, for (i = 1; i + 4 > 8; j = 1 + (j / 2); weight[i] = j > 8; j = 1 + (j / 2); weight[i+1] = j > 8; j = 1 + (j / 2); weight[i+2] = j > 8; j = 1 + (j / 2); weight[i+3] = j > 8; j = 1 + (j / 2); weight[i] = j

15 Prosty przykład - loop unrolling Przykładowe wyniki: Przed: ubuntu@ubuntu-desktop:~/src/cbench/bzip2d/src$./__run 8 10 Found dataset: 8 Command line: -z -k -f -c../../consumer_data/2.wav > ftmp_out Loop wrap: 10 real 0m31.143s user 0m30.422s sys 0m0.648s Po: ubuntu@ubuntu-desktop:~/src/cbench/bzip2d/src$./__run 8 10 Found dataset: 8 Command line: -z -k -f -c../../consumer_data/2.wav > ftmp_out Loop wrap: 10 real 0m29.050s user 0m28.526s sys 0m0.416s

16 Prosty przykład - loop unrolling Dobór do kompilacji statycznej na danej architekturze: Wychodzi, że dla większości programów wartości dające efekty na architekturze 2-rdzeniowej, procesor E8400, _sensowne zmiany dają wartości loop_unroll z przedziału Należy pamiętać o kosztach zmian: ubuntu@ubuntu-desktop:~/src/cbench/bzip2d/src$ ll a.out4 -rwxr-xr-x 1 ubuntu ubuntu 107726 2009-11-16 03:40 a.out4 ubuntu@ubuntu-desktop:~/src/cbench/bzip2d/src$ ll a.out8 -rwxr-xr-x 1 ubuntu ubuntu 111822 2009-11-16 03:46 a.out8

17 Zadania - analiza zależności konieczność przetestowania dla dużej liczby przypadków testowych (różne kody źródłowe) dla uzyskania jakości przemysłowej - w przypadku ręcznej ekstrakcji pętli jest niemożliwe do wykonania, własny frontend kompilatora (ANSI C), przygotowanie do analizy zależności, możliwość analizy przy pomocy różnych narzędzi (Petit, Loopo, Candl) o różnych formatach wejściowych, potrzebna również przy rozwijaniu pętli.

18 Reprezentacja kodu żródłowego Formy pośrednie reprezentacji kodu źródłowego  Gcc  Vhdl2bool  Stepson

19 Reprezentacja kodu żródłowego Gcc Inne formy przejściowe  Gcc – SSA, GIMPLE  @3013 tree_list valu: @83 chan: @3017  @3014 tree_list valu: @86 chan: @3018  @3015 identifier_node strg: __divdc3 lngt: 8  @3016 function_decl name: @3019 type: @3020 srcp: :0  chan: @3021 body: undefined  link: extern  @3017 tree_list valu: @83 chan: @128  @3018 tree_list valu: @86 chan: @3022  @3019 identifier_node strg: __mulxc3 lngt: 8  @3020 function_type size: @12 algn: 8 retn: @112

20 Reprezentacja kodu żródłowego Gcc Inne formy przejściowe  Gcc Zalety:  Gotowy kompilator,  Standardowy, istnieje wiele rozwiązań opartych o tą formę. Wady:  Skomplikowanie,  Zbyt „odległy” od kodu źródłowego,  Trudny w odczycie przez człowieka

21 Reprezentacja kodu żródłowego VHDL2BOOL Inne formy przejściowe  Vhdl2bool Drzewo katalogów  Zalety: trywialna obsługa przestrzeni nazw, możliwość zajmowania się tylko fragmentem kodu.  Wady: Konieczność ustalania formatu, Trudności w manipulacji, Problemy z przekształcaniem plików.

22 Reprezentacja kodu żródłowego Stepson (1):for(i=0 ; i

23 Reprezentacja kodu żródłowego Stepson ParseTree1 (1) (for(i=0 ; i

24 Transformacja pętli while Metoda transformacji  Wyszukanie zmiennej, po której iterujemy,  Wyszukanie wszystkich miejsc jej użycia,  Określenie warunku zakończenia pętli

25 Transformacja pętli while Przekształcenie powyższej pętli: i=0 while (i

26 Transformacja pętli while Inne tranformacje i istotne ograniczenia a=otherList.head() t=list.head();a=otherList.head() while (t!=NULL)for (t=list.head() ; t!=NULL ; t++){ *a = *t + sVal; a++; t++;}

27 Podsumowanie Cele i osiągnięcia najbliższe  Rozwój bazy testów,  Analiza zależności,  Konwersja while na for,  Zależności i przestrzeń iteracji jako polyhedra (wielościan),  wskaźniki,  Implementacja prostych transformacji. Cele strategiczne:  Kompilacja iteracyjna (również ekstracja wiedzy),  Automatyczne zrównoleglanie dużego zbioru testowego (z naciskiem na wybraną klasę algorytmów),  Większy niż w innych rozwiązaniach podzbiór języka C (w przyszłości również C++, kompilacja kodu zarządzanego)

28 Dziękuję za uwagę