Nowości w świecie kompilatorów.

 

 

Parallel compilers & parallel computing

 

Obliczenia równoległe jak wszyscy wiemy są jednym z bardziej popularnych sposobów na przyśpieszenie obliczeń. Duża liczba dużych problemów może być podzielona na mniejsze podproblemy, z których każdemu można przydzielić niezależny procesor z współdzielonymi lub niezależnymi zasobami.

 

 Poziom złożoności tego podejścia zależy od tego czy te procesory należą do jednej stacji roboczej (wieloprocesorowa maszyna), czy też są na różnych stacjach roboczych. Jeżeli mamy do czynienia z maszyną wieloprocesorową, to czy mają pamięć współdzieloną, czy też wyposażone są w niezależne jednostki pamięci z możliwą komunikacją pomiędzy procesorami. Z drugiej strony jeśli maszyny są rozproszone w sieci pojawia się problem z wydajnością komunikacji i wyższym prawdopodobieństwem utraty danych.

 

Program napisany w jakimkolwiek języku wysokiego poziomu (C, C++, Fortran) za pomocą kompilatorów czy interpreterów musi być przetłumaczony na kod maszynowy (zestaw instrukcji/rozkazów) zgodny z architekturą, na której będzie się wykonywał.

 

Istnieją trzy sposoby ulepszania kompilatora: preprocesor, prekompilator i kompilator równoległy.

Preprocesor używa sekwencyjnego kompilatora i biblioteki niskiego poziomu komputera docelowego do zaimplementowania konstrukcji równoległych wysokiego poziomu.

Wsparcie prekompilatora wymaga analiz przepływu programu, sprawdzenie zależności i ograniczonych optymalizacji w kierunku wykrycia równoległości.

Trzecia ścieżka wsparcia wymaga w pełni rozwiniętego kompilatora równoległego lub wektorowego, mogącego automatycznie wykrywać równoległość w kodzie źródłowym i przekształcać kody sekwencyjne w konstruktory równoległe.

 

Efektywność procesu bindowania zależy od efektywności preprocesora, prekompilatora, kompilatora równoległego, loadera, i wsparcis systemu operacyjnego. W związku z nieprzewidywalnym zachowaniem się programu, żaden z istniejących kompilatorów nie może być uznany za w pełni zautomatyzowany lub w pełni inteligentny w wykrywaniu wszelkich

typów równoległości. Bardzo często dyrektywy kompilatora wstawiane są w kod źródłowy programu w celu pomocy kompilatorowi z lepszym przeprowadzeniem postawionego przed nim zadania. Użytkownicy mogą współdziałać z kompilatorem w celu restrukturyzacji programu. Takie postępowanie zostało uznane za użyteczne w polepszaniu wydajności

komputerów równoległych.

 

Kompilatory równoległe to programy, które starają się „zrównoleglić” proces kompilacji programu. Są dwa podejścia do kompilacji równoległej:

 

Programowanie w istniejącym języku

Program piszemy w istniejącym języku i zoptymalizowany kompilator jest wykorzystywany, by wydobyć równoległość z programu i uzyskać istotny wzrost wydajności.

 

Rozwijanie języka programowania równoległego (Data parallel languages)

Rozwiązanie cechuje się posiadaniem wyraźnych konstruktorów wysokiego poziomu dla wyspecyfikowanego przetwarzania równoległego.

Data parallel languages ułatwiają programowanie równoległe eliminując problemy związane z współbieżnością, komunikacją i synchronizacją. Abstrakcja ta bazuje na strategii dzielenia dużych obliczeń na równoległe operacje na dużych strukturach danych (data parallelism). W rezultacie uzyskujemy przenośność, ale realizacja tego kosztuje. W szczególności wymaga to bardzo skomplikowanych i złożonych kompilatorów zdolnych do mapowania data-parallel programs na kod równoległy, który pasuje do komputerów równoległych i narzędzi programistycznych. Nowy język nie jest bowiem kompatybilny z poprzednikami. Koszt zbudowania tak złożonego kompilatora i narzędzi można usprawiedliwić, gdyż wspieranie abstrakcji na wysokim poziomie ułatwia programowanie równoległe i daje w efekcie bardziej przenośne programy. Jednak ze względu na koszty większość systemów omija to podejście szerokim łukiem.

 

 

Parallel-izing Compilers

 

Zadanie kompilatorów równoległych

 

Pewien program działa długo na pojedyńczym komputerze (serial computer). Załóżmy, że posiadamy komputer z wieloma procesorami, które mogą pracować równocześnie. Celem naszym jest skrócenie czasu działania programu dzieląc go na kawałki które mogą być wykonywane równolegle lub współbieżnie na jednostkach procesora.

Kompilator zajmuje się w pierwszej fazie wyszukiwaniem równoległości, a w drugiej stara się ją uporządkować w sposób dający poprawny wynik i większą wydajność.

Pytanie brzmi, na jakie kawałki program powinien zostać podzielony i jak te kawałki powinny być uporządkowane. A to wiąże się z:

 

  granularnością (granularity), stopniem równoległości

 

  analizą zależności między kandydatami do równoległego wykonywania

 

Kompilator najpierw rozpoznaje potencjalne równoległe jednostki w programie, a potem dokonuje na nich analizy zależności, aby się przekonać, które segmenty są niezależne od siebie i mogą być wykonywane współbieżnie. Często dokonuję się tego na poziomie instrukcji.

 

 

 

 

 

 

 

 

 

 

Vectorisers – vectorizing compilers

 

W świecie superkomputerów istnieją takie, które posiadają architekturę wektorową. Procesory wektorowe posiadają dodatkowe jednostki obliczeniowe i szybką pamięć. Dla porównania dodanie dwóch n-elementowych wektorów na zwykłym skalarnym procesorze będzie wykonywało jedną instrukcję w czasie.

 

DO 10 I = 1,N

A(I) = B(I) + C(I)

10 CONTINUE

 

Na procesorze wektorowym wszystkie n instrukcji może być wykonywanych na n osobnych procesorach, co redukuje całkowity czas wykonania. Będzie on n razy krótszy niż przy wykonywaniu pojedynczych dodawań. Tak zwane multi-media extensions (MMX), które pojawiły się w niektórych procesorach są także instrukcjami bazującymi na wektorach, które można poddać wektoryzacji.

Vectorizing compiler  rozpoznaje takie sekwencyjne operacje na wektorach i dokonuje ich translacji na instrukcje maszyny wektorowej. Aby tego dokonać muszą być spełnione pewne warunki: operandy źródłowe muszą być niezależne od operandów wyniku. Na przykład:

 

DO 20 I = 1,N

X(I) = B(I) + A(I) * X(I-1)

20 CONTINUE

 

W tym przykładzie X(I-1) musi być obliczone przed X(I). Ta pętla zawiera zależność, która uniemożliwia zastosowanie wektoryzacji. Ale w niektórych przypadkach jest możliwe zmodyfikowanie kodu w taki sposób, by wektoryzacja była możliwa. Na przykład:

 

DO 100 J = 1,N

DO 100 I = 1,N

DO 100 K = 1,N

C(I,J) = C(I,J) + A(I,K) * B(K,J)

100 CONTINUE

 

W tym przykładzie mnożenia macierzy w każdej iteracji C(I,J) jest obliczane wykorzystując wcześniejszą wartość C(I,J) wyznaczoną we wcześniejszej interacji, więc żadna wektoryzacja nie jest możliwa. Ale jeśli nasz kod zapiszemy tak:

 

DO 100 J = 1,N

DO 100 K = 1,N

DO 100 I = 1,N

C(I,J) = C(I,J) + A(I,K) * B(K,J)

100 CONTINUE

 

W tym przypadku wektoryzacja jest możliwa gdyż kolejne instrukcje obliczające C(I-1,J) i C(I,J) są niezależne od siebie i mogą być wykonywane współbieżnie na różnych procesorach.

Tak więc analiza zależności na poziomie instrukcji może nam pomóc rozpoznać poziom zależności operandów i zastosować odpowiednią optymalizację, która umożliwi wektoryzację.

 

 

 

Wykrywanie zależności

 

Program jest zbiorem wyrażeń, na których uporządkowanie i kolejność są nałożone pewne zalezności.

Zależności można podzielić na dwie kategorie:

 

1. Data Dependencies: kiedy wyrażenie dokonuje obliczeń na danych, wykorzystywanych przez innne wyrażenie

2. Control Dependencies: to te, które wynikają z narzuconej kolejności obliczeń w programie poprzez np. instrukcje sterujące

 

Graf zależności może być skonstruowany poprzez narysowanie krawędzi łączących zależne operacje. Zależności wykryte podczas analizy zależności wymuszają częściowe uporządkowanie operacji, które uniemożliwiają w pełni współbieżne wykonanie się programu.

 

Pomiędzy wyrażeniami i oraz j mogą istnieć cztery rodzaje zależności na pewnej ścieżce kontroli:

 

Figure 1 : Dependency types

 

1. Flow Dependence:  pomiędzy Sj oraz Si występuje, gdy wartość zmiennej a używana przez Sj została obliczona w Si

2. Antidependence: pomiędzy Sj oraz Si występuje, gdy wartość zmiennej a użyta przez Si jest ponownie obliczana przez Sj (w Sj następuje nowe przypisanie do zmiennej)

3. Output-Dependence: pomiędzy Sj oraz Si występuje, gdy oba wyrażenia obliczają tą samą zmienną i wartość tej zmiennej z Sj musi być przechowywana po tej z Si

4. Control-Dependence: Sj jest control-dependent z wyrażeniem warunkowym Si

jeżeli jego wykonanie następuje po Si i wybraniu ścieżki (Si musi się wykonać przed Sj)

 

 

Przykład analizy zależności (Dependency Analysis)

 

Na poniższym rysunku znajduje się kod programu napisany w Fortranie i analiza zależności bazująca na tym segmencie programu.

Zmienna A w wyrażeniu 1 i 3 jest przykładem flow dependence, w której zmienna jest zdefiniowana w jednym wyrażeniu i użyta w później występującym wyrażeniu.

Anti Dependence jest lustrzanym odbiciem flow dependence. Zachodzi ona, gdy zmienna jest używana we wcześniejszym wyrażeniu, a później jest ponownie przypisana w innym wyrażeniu. Przykładem jest zmienna A w wyrażeniu 3 i 6.

Output dependence pojawia się, gdy zmiennej jest przypisywana wartość co najmniej raz w różnych wyrażeniach, tak jak w wyrażeniu 1 i 6.

 

 

 

Figure 2: A Program in FORTRAN with corresponding dependency graph

 

 

Użycie analizy zależności (Dependency Analysis) w tworzeniu kompilatorów

 

Podstawową ideą wypływającą z grafów zależności jest umożliwienie kompilatorowi wykrycie różnych rodzajów zależności pomiędzy wyrażeniami, aby zapobiec ich wykonaniu w złej kolejności (w kolejności, która zmieni znaczenie programu, jego założenia, czy poprawność).

Pomaga to w identyfikowaniu różnych, dających się „zrównoleglić” komponentów programu i tych których nie wolno ruszać.

 

 

 

 

 

 

Parallel Compilers - Grain sizes

 

Aby koordynować pracę różnych procesorów nad tym samy problemem, wymagana jest raz na czas komunikacja między nimi. Liczbę obliczeń, które są wykonywane między zdarzeniami komunikacyjnymi i synchronizacyjnymi nazywamy granularnością. Czasem też stosunkiem liczby obliczeń do zdarzeń komunikacyjnych. Granularność ma bezpośredni wpływ na zrównoważenie obciążenia procesorów (load-balancing).

 

Fine Grain Parallelism

Wszystkie zadania wykonują małą liczbę instrukcji pomiędzy cyklami komunikacji

Mało obliczeń w stosunku do połączeń komunikacyjnych

Ułatwia równoważenie obciążenia

Powoduje większy narzut na komunikacje i mniejszy na wzrost wydajności

 

Jeżeli granularność jest zbyt drobna (fine) jest możliwe, że narzut związany z komunikacją i synchronizacją pomiędzy zadaniami zajmie więcej czasu niż same obliczenia.

 

Coarse grain parallelism

Długie obliczenia składające się z wielu instrukcji pomiędzy komunikacyjno-synchronizującymi punktami.

Dużo obliczeń w stosunku do komunikacji

Daje większe szanse na wzrost wydajności

Trudniej równoważyć obciążenia

 

W większości przypadków narzut związany z komunikacją i synchronizacją w dużej mierze wpływa na szybkość wykonywania, więc zaletą jest korzystanie z Coarse granularity.

 

Kompilatory urównoleglające najbardziej rozwinęły się przy Fortranie. Najpowszechniej wykorzystywaną formą równoległości jest ta związana z pętlami.  To dlatego, że Fortran operuje przeważnie na elementach tablicowych i wektorowych. Poziom równoległości (rodzaj, granularność i rozmiar) w całości zależy od języka i może mieć różną formę dla różnych języków.

 

Na przykład w języku takim jak Fortran równoległość może bazować na granularności na poziomie instrukcji, dla innych języków wysokiego poziomu może być to poziom procedur lub prostych bloków.

 

Każde równoległe obliczenie składa się z kilku prostych bloków. Kompilator musi rozpoznać zależności pomiędzy kandydatami do równoległego wykonania. Stopień analizy zależy od rozmiaru ziarenek i oczekiwanego stopnia równoległości.

            Jeśli analizuje tylko powiązania wewnątrz prostego bloku kodu, a nie wśród prostych bloków wtedy uzyskami raczej równoległość rodzaju fine grained.

Globalna analiza przepływu danych, w której sprawdzane są relacje pomiędzy prostymi blokami prowadzi do większej granularności.

Przykładem tego jest równoległość na poziomie pętli. Jest to równoległość pomiędzy iteracjami tej samej pętli. Wyrażenia wewnątrz pętli nie biorące udziału w cyklu zależności mogą zostać zwektoryzowane. Najbardziej ekstensywnym i trudnym typem analizy jest ta dotycząca całego programu, zwana interprocedural dataflow analysis. Analiza ta prowadzi do największej granularności. Rozmiar równoległości zależy więc od rozmiaru analizy.

 

 

 

Przykłady kompilatorów równoległych:

 

1  Parafrase Fortran reconstructing compiler: Parafrase jest optymalizującym preprocesorem kompilatora, który na wejście dostaje kod w Fortranie, dla którego tworzy graf zależności i przeprowadza serię kroków optymalizujących, które generują nową wersję oryginalnego programu i optymalizuje ją pod kątem architektur superkomputerowych.

 

2. Bulldog Fortran reassembling compiler: Kompilator Bulldog bazuje na parallelizacji na poziomie instrukcji. Jest skonstruowany tak, żeby wychwycić równoległości nie nadające się do wektoryzacji. Umożliwia równoległość wewnątrz bloków prostych.

 

3. Cilk2c compiler: this is a clone compiler which converts CILK (a C extension language for multithreaded parallel programming) source code to C source code.

 

4. F90 / High Performance Fortran (HPF) : High performance Fortran rozszerza

F90, aby wspierał data parallel programming. Dyrektywy kompilatora umożliwiają programiście specyfikacje dystrybucji i układu danych.