Wskazówki planowania - Instruction scheduling

W informatyce , wskazówki planowania jest optymalizacja kompilatora wykorzystane do poprawy instrukcja poziomu równoległości , który poprawia wydajność na maszynach z rurociągów instrukcji . Mówiąc prościej, to stara się zrobić co następuje bez zmiany znaczenia kodu:

  • Unikać stragany rurociągów poprzez zmianę kolejności instrukcji.
  • Unikać nielegalnych lub semantycznie wieloznaczne operacji (zazwyczaj z udziałem subtelne kwestie czasowe rurociągów instrukcja lub zakaz sobą połączone zasobów).

Stragany rurociągów mogą być spowodowane przez zagrożeń strukturalnych (limit zasobów procesora), zagrożeń danych (wyjście z jednej instrukcji potrzebny innej instrukcji) i zagrożeń kontrolnych (rozgałęzienia).

zagrożenia dla danych

Szeregowanie instrukcja jest zazwyczaj odbywa się na jednym podstawowym blokiem . W celu ustalenia, czy rozmieszczanie instrukcje bloku w pewien sposób zachowuje zachowanie tego bloku, musimy pojęcie uzależnienia danych . Istnieją trzy rodzaje zależności, które również zdarzyć się trzy zagrożenia danych :

  1. Czytaj po write (RAW lub „true”): Szkolenie 1 zapisuje wartość używany później przez 2. Instrukcja obsługi 1 musi się najpierw, czy instrukcja 2 będzie czytać starą wartość zamiast nowego.
  2. Napisz po Read (WAR lub „anty”): Szkolenie 1 odczytuje lokalizację, która jest później zastąpione przez 2. Instrukcja obsługi 1 musi się najpierw, czy będzie to czytać nową wartość zamiast starego.
  3. Napisz po write (WAW lub „Wyjście”): Dwie instrukcje zarówno pisać tej samej lokalizacji. Muszą one występować w ich oryginalnej kolejności.

Technicznie rzecz biorąc, jest czwarty typ, Read po read (RAR lub „Wejście”): Obie instrukcje czytać tę samą lokalizację. Zależność wejście nie ogranicza kolejność wykonywania dwóch stwierdzeń, ale jest przydatny w skalarnego wymianą elementów tablicy.

Aby upewnić się, że przestrzega trzy rodzaje uzależnień, skonstruowano wykres zależności, która jest skierowana wykres gdzie każdy wierzchołek jest instrukcją, i nie ma krawędź z I 1 do I 2 , jeśli jeden musi się przed I 2 W wyniku zależność. Jeśli zależności z pętli wykonywane są pominięte, na wykresie zależność jest skierowany acykliczny wykres . Następnie każdy topologiczna porządek z tym wykresie jest poprawny harmonogram instrukcja. Krawędzie wykresu są zwykle znakowane opóźnienia w zależności. Jest to liczba cykli zegarowych, który musi upłynąć, zanim rurociąg może postępować z instrukcją docelowego bez zwłokę.

algorytmy

Najprostszy algorytm, aby znaleźć rodzaj topologii jest często stosowany i znany jest jako lista harmonogramów . Koncepcyjnie kilkakrotnie, wybiera się źródło na wykresie zależności, dodaje się z aktualnym instrukcji i usuwa go z wykresu. Może to powodować inne wierzchołki być źródła, które następnie również uznać za planowanie. Algorytm wykres kończy się, gdy jest pusta.

Aby osiągnąć dobry rozkład, Krzesło należy zapobiegać. To jest określona przez wybór następnej instrukcji być zaplanowane. Szereg heurystyki są w powszechnym użyciu:

  • Środki stosowane przez procesor już zaplanowanych instrukcji są rejestrowane. Jeśli kandydat korzysta z zasobu, który jest zajęty, jego priorytetem będzie spadać.
  • Jeśli kandydat jest zaplanowany bliżej swoich poprzedników niż powiązanej latencji jego priorytetem będzie spadać.
  • Jeśli kandydat leży na ścieżce krytycznej wykresu, jego priorytetem będzie rosnąć. Ten heurystyczny zapewnia jakąś formę antycypowana w skądinąd lokalnego procesu decyzyjnego.
  • W przypadku wyboru kandydata stworzy wiele nowych źródeł, jego priorytetem będzie rosnąć. Ten heurystyczny ma tendencję do generowania większej swobody dla harmonogramu.

Kolejność faz wykładowy harmonogramu

Szeregowanie instrukcja może być wykonane przed lub po alokacji rejestru lub zarówno przed, jak i po niej. Zaletą robi to przed przydziału rejestru jest to, że prowadzi to do maksymalnej równoległości. Wadą robi to przed przydziału rejestru jest to, że może to doprowadzić do rejestru podzielnik konieczności używania wielu rejestrów przekraczających te dostępne. Spowoduje to, że kod wyciek / fill zostać wprowadzone co zmniejszy wydajność sekcji kodu w pytaniu.

Jeśli architektura zaplanowano posiada sekwencje instrukcji, które mają potencjalnie nielegalnych kombinacji (z powodu braku blokad instrukcji) Instrukcje muszą być zaplanowane po alokacji rejestru. Ten drugi będzie również podanie harmonogramu poprawy umieszczenie kodu wyciek / wypełnienia.

Jeśli planowanie odbywa się dopiero po alokacji rejestru wtedy nie będzie fałszywe zależności wprowadzone przez przydziału rejestru, który będzie ograniczyć ilość ruchu instrukcji możliwe dzięki harmonogramu.

Rodzaje instrukcji planowania

Istnieje kilka typów instrukcji harmonogramu:

  1. Lokalny ( podstawowy blok ) szeregowanie : instrukcje nie mogą poruszać się po podstawowych granice bloków.
  2. Globalny harmonogram : instrukcje mogą poruszać się podstawowych granice bloków.
  3. Modulo szeregowania : algorytm do generowania rurociąg oprogramowania , co jest sposobem na zwiększenie poziomu obsługi równoległość przez przeplatanie różnych iteracji wewnętrznej pętli .
  4. Śledzenie harmonogramu : pierwsza praktyczne podejście do globalnego planowania, harmonogramowania ślad próbuje zoptymalizować drogę przepływu sterowania, który jest wykonywany najczęściej.
  5. Superblock szeregowania : uproszczona forma śladowych szeregowanie nie próbuje połączyć ścieżek kontroli przepływu w ścieżce „wejściach niepożądane”. Zamiast tego kodu mogą być realizowane przez więcej niż jednego schematu, znacznie upraszczając generator kodu.

Zobacz też

Referencje

Dalsza lektura