Ramy wspierające model wielościenny

Użycie modelu wielościennego (zwanego także modelem polytope ) w kompilatorze wymaga oprogramowania do reprezentowania obiektów tej struktury (zbiorów punktów o wartościach całkowitych w regionach różnych przestrzeni) i wykonywania na nich operacji (np. sprawdzanie, czy zbiór jest pusty).

Aby uzyskać więcej informacji na temat obiektów i operacji w tym modelu oraz przykład odnoszący model do kompilowanych programów, zobacz stronę modelu wielościennego.

Istnieje wiele ram wspierających model wielościenny . Niektóre z tych platform używają jednej lub więcej bibliotek do wykonywania operacji wielościennych. Inne, zwłaszcza Omega, łączą wszystko w jednym pakiecie. Niektóre powszechnie używane biblioteki to Omega Library (i nowszy fork), piplib, PolyLib, PPL, isl , generator kodu wielościennego Cloog i biblioteka barvinok do liczenia rozwiązań całkowitych. Spośród tych bibliotek PolyLib i PPL koncentrują się głównie na wartościach wymiernych, podczas gdy inne biblioteki koncentrują się na wartościach całkowitych. Struktura wielościenna gcc nazywa się Grafit. Polly zapewnia wielościenne optymalizacje dla LLVM , a R-Stream ma wielościenny mapper od ok. 2006.

Wspólne mocne strony

Ramy wielościenne są zaprojektowane do obsługi technik kompilatorów do analizy i transformacji kodów z zagnieżdżonymi pętlami, dając dokładne wyniki dla zagnieżdżeń pętli z afinicznymi ograniczeniami pętli i indeksami dolnymi („Static Control Parts” programów). Można ich używać do reprezentowania i wnioskowania o wykonaniach (iteracjach) instrukcji, zamiast traktowania instrukcji jako pojedynczego obiektu reprezentującego właściwości wszystkich wykonań tej instrukcji. Ramy wielościenne zazwyczaj pozwalają również na użycie wyrażeń symbolicznych.

Ramy wielościenne mogą być wykorzystywane do analizy zależności dla tablic, w tym zarówno tradycyjnej analizy aliasów, jak i bardziej zaawansowanych technik, takich jak analiza przepływu danych w tablicach czy identyfikacja zależności warunkowych. Mogą być również używane do reprezentowania transformacji kodu i udostępniania funkcji do generowania przekształconego kodu w języku wysokiego poziomu. Systemy transformacji i generowania mogą zazwyczaj obsługiwać pętle niedoskonale zagnieżdżone.

Przykład kontrastu wielościennych ram z wcześniejszymi pracami

Aby porównać model wielościenny oparty na ograniczeniach z wcześniejszymi podejściami, takimi jak transformacje pojedynczych pętli i podejście unimodularne , rozważ pytanie, czy możemy zrównoleglić (wykonać jednocześnie) iteracje następującej wymyślonej, ale prostej pętli:

 dla  i := 0  do  N  do  A(i) := (A(i) + A(Ni))/2

Podejścia, które nie mogą reprezentować warunków symbolicznych (takie jak niezmienna w pętli ilość N w pętli związanej i indeks dolny) nie mogą uzasadniać zależności w tej pętli. Albo konserwatywnie odmówią uruchomienia go równolegle, albo w niektórych przypadkach spekulacyjnie uruchomią go całkowicie równolegle, stwierdzą, że było to nieważne, i ponownie wykonają je sekwencyjnie.

Podejścia, które obsługują terminy symboliczne, ale reprezentują zależności za pomocą wektorów kierunkowych lub wektorów odległości, określą, że pętla i przenosi zależność (o nieznanej odległości), ponieważ na przykład, gdy N=10 iteracja 0 pętli zapisuje element tablicy (A(0) ), który zostanie odczytany w iteracji 10 (jako A(10-10)) i odczytuje element tablicy (A(10-0)), który zostanie później nadpisany w iteracji 10 (jako A(10)). Jeśli wszystko, co wiemy, to to, że pętla i zawiera zależność, po raz kolejny nie możemy bezpiecznie uruchomić jej równolegle.

W rzeczywistości istnieją tylko zależności od pierwszych N/2 iteracji do ostatnich N/2, więc możemy wykonać tę pętlę jako sekwencję dwóch w pełni równoległych pętli (od 0...N/2 i od N/2+ 1...N). Charakterystykę tej zależności, analizę równoległości i transformację kodu można przeprowadzić w kategoriach informacji o instancjach dostarczanych przez dowolną strukturę wielościenną.

Analiza i transformacja oparta na instancjach pozwala modelowi wielościennemu ujednolicić dodatkowe przekształcenia (takie jak dzielenie zestawu indeksów, usuwanie pętli, kafelkowanie, łączenie lub rozszczepianie pętli oraz transformacja niedoskonale zagnieżdżonych pętli) z tymi, które zostały już zunifikowane przez ramy jednomodułowe (takie jak pętla zamiana, pochylanie i odwracanie doskonale zagnieżdżonych pętli). Stymulowało to również rozwój nowych transformacji, takich jak krojenie przestrzeni iteracyjnej Pugha i Rossera (wersja dzielenia programu oparta na instancjach; zwróć uwagę, że kod nigdy nie został wydany z Biblioteką Omega).

Ciekawszy przykład

Autorzy struktur wielościennych zbadali proste 1-wymiarowe obliczenie szablonu równania ciepła z różnicą skończoną wyrażone następującym pseudokodem :

    
    
 dla  t := 0  do  T  wykonaj  dla  i := 1  do  N-1  wykonaj  nowy(i) := (A(i-1) + A(i) + A(i) + A(i+1)) * .25 // wyraźna różnica w przód z R = 0,25  koniec  dla  i := 1  do  N-1  do  A(i) := nowy(i)  koniec  koniec

Ten kod wprawia w zakłopotanie wiele systemów transformacji XX wieku ze względu na potrzebę optymalizacji niedoskonałego gniazda pętli. Ramy wielościenne mogą analizować przepływ informacji między różnymi wykonaniami instrukcji w gnieździe pętli i przekształcać ten kod, aby jednocześnie wykorzystywać skalowalną równoległość i skalowalną lokalność .

Przypomnienie tutaj dwóch podejść do tego przykładu może być miłe, ale na razie zobacz poszczególne artykuły Wonnacotta i Sadayappana et al. a także inni, którzy studiowali ten kod przy użyciu różnych platform, takich jak Song i Li.

Różnice w prezentacji lub słownictwie

Porównanie pracy przy użyciu różnych frameworków komplikują zarówno różnice techniczne (omówione później), jak i różnice w słownictwie i prezentacji. Przykłady podano poniżej, aby ułatwić tłumaczenie:

Klasyfikacja zależności

Ramy wielościenne obsługują analizę zależności na różne sposoby, pomagając uchwycić wpływ terminów symbolicznych, zidentyfikować zależności warunkowe i oddzielić efekty aliasingu pamięci. W szczególności efekty aliasingu pamięci zostały opisane na dwa sposoby: wielu autorów rozróżnia „prawdziwe” zależności danych (odpowiadające faktycznemu przepływowi informacji) od fałszywych zależności wynikających z aliasingu pamięci lub ograniczonej precyzji analizy zależności.

Publikacje Projektu Omega używają określonych terminów w celu określenia określonego wpływu na analizę. Zachowują tradycyjne rozróżnienie zależności przepływu, wyjścia i antyzależności, w oparciu o typy dostępu do tablicy (odpowiednio zapis do odczytu, zapis do zapisu lub odczyt do zapisu). Zależności można niezależnie sklasyfikować jako oparte na pamięci lub oparte na wartościach --- pierwsza odpowiada aliasingowi pamięci, a druga nie obejmuje zależności przerwanych przez interweniujące zapisy. Test zależności może generować informacje dokładne lub przybliżone, w zależności od charakteru analizowanego programu i algorytmów użytych w teście. Na koniec wyniki analizy zależności zostaną przedstawione w postaci abstrakcji zależności , która zapewnia pewien stopień precyzji.

Na przykład „relacje zależności” tworzone przez Test Omega oraz „quasty” generowane przez algorytmy Feautriera lub Maydana i Lama zawierają dokładne informacje (choć w różnych formach) o iteracjach pętli zaangażowanych w zależność. Wyniki obu testów można przekształcić w bardziej tradycyjną formę „wektora zależności”, ale ponieważ ta abstrakcja zapewnia mniejszą precyzję, wiele informacji o zależności zostanie utraconych. Obie techniki dają dokładne informacje dla programów ze sterowaniem afinicznym i wyrażeniami w indeksie dolnym i muszą być przybliżone dla wielu programów poza tą dziedziną (tj. w obecności indeksów dolnych innych niż afiniczne, takich jak tablice indeksów). Oryginalna praca Feautriera koncentrowała się na opisie prawdziwych zależności, które byłyby określane przez Projekt Omega jako dokładne zależności przepływu oparte na wartościach . Projekt Omega opisał również zastosowanie ich algorytmów do opartych na wartościach wyjściowych i antyzależności, chociaż quasts Feautriera można by przypuszczalnie łatwo dostosować również do tego.

Wizualizacja przekształceń i kafelkowania

Istnieje wiele sposobów na wizualne przedstawienie procesu przekształcania i układania przestrzeni iteracji. Niektórzy autorzy przedstawiają przekształcenia, zmieniając położenie punktów na stronie, zasadniczo wyrównując obraz z osiami współrzędnych przekształconej przestrzeni; na takich diagramach kafelki pojawiają się jako wyrównane do osi prostokąty / prostokątne bryły zawierające iteracje. Przykłady takiego podejścia można znaleźć w publikacjach i oprogramowaniu do wizualizacji transformacji autorstwa Michelle Mills Strout.

Inni autorzy przedstawiają różne transformacje jako różne czoła fali wykonania, które poruszają się w poprzek punktów pierwotnego układu współrzędnych pod różnymi kątami. Na takich diagramach kafelki pojawiają się jako równoległoboki / równoległoboki. Przykłady takiego podejścia można znaleźć w przekrzywionych czasowo publikacjach Davida G. Wonnacotta.

Różnice w podejściu lub statusie wdrożenia

Niektóre biblioteki były rozwijane na szerszą skalę niż Biblioteka Omega na początku 2000 roku, aw wielu miejscach mają znacznie bardziej wyrafinowane algorytmy. W szczególności użytkownicy zgłaszali dobre wyniki z generatorem kodu Cloog (zarówno pod względem generowanego kodu, jak i pod względem możliwości kontrolowania kompromisów podczas generowania kodu) oraz z algorytmami do liczenia rozwiązań całkowitoliczbowych (Alexander Barvinok , praca wymaga opisu wierzchołka polytope, który nie jest obsługiwany w bibliotece Omega).

Istnieje kilka innych punktów, w których ramy różnią się, w szczególności:

Precyzja i szybkość

Programowanie całkowitoliczbowe jest NP-zupełne , a Maydan wykazał, że problem sprawdzania aliasingu tablic w zagnieżdżonych pętlach z ograniczeniami afinicznymi i indeksami dolnymi jest równoważny programowaniu całkowitoliczbowemu; inne operacje, takie jak tablicowa analiza przepływu danych, są jeszcze bardziej złożone (algorytmy biblioteki Omega obsługują pełny język Presburger Arithmetic, czyli O(2^2^2^n)). Zatem oczekiwanie dokładnych i szybkich wyników dla dowolnych problemów związanych z aliasingiem tablicy lub przepływem danych przez tablicę, nawet w domenie afinicznej, jest wyraźnie nierealistyczne. Na szczęście wiele problemów mieści się w podzbiorze tej domeny, w którym ogólne algorytmy mogą dać dokładną odpowiedź w czasie wielomianowym.

Poza tą domeną Omega Library, piplib i isl kładą nacisk na uzyskanie dokładnego wyniku (z wyjątkiem przypadków niektórych zastosowań niezinterpretowanych symboli funkcyjnych w Omega), pomimo dużej złożoności. W niektórych przypadkach, takich jak eliminacja zmiennych („projekcja”), PolyLib i PPL używają głównie algorytmów dla domeny wymiernej, a tym samym tworzą przybliżenie wyniku dla zmiennych całkowitych. Może się zdarzyć, że zmniejszy to powszechne doświadczenie z Biblioteką Omega, w której niewielka zmiana jednego współczynnika może spowodować dramatyczną zmianę w odpowiedzi algorytmów biblioteki.

Polylib ma kilka operacji, które dają dokładne wyniki dla wielościanów Z (liczby całkowite ograniczone przez wielościany), ale w momencie pisania tego tekstu zgłoszono znaczące błędy. Zauważ, że błędy istnieją również w Bibliotece Omega, w tym poleganie na typach liczb całkowitych dostarczonych przez sprzęt i przypadkach pełnych algorytmów Presburger Arithmetic, które nie zostały zaimplementowane w bibliotece. Użytkownicy, którzy potrzebują dokładnych wyników dla zmiennych całkowitych, mogą być ostrożni w przypadku obu bibliotek.

Techniki Barvinoka do liczenia rozwiązań całkowitych wymagają opisu wierzchołków (i promieni ograniczających) wielościanu, ale dają dokładną odpowiedź w sposób, który może być znacznie bardziej wydajny niż techniki opisane przez Pugha. Algorytm Barvinoka jest zawsze wielomianowy w rozmiarze wejściowym, dla ustalonego wymiaru polytope i ustalonego stopnia wag, podczas gdy „odłamywanie” w algorytmie Pugha może rosnąć wraz z wartościami współczynników (a więc wykładniczo pod względem wielkości wejściowej, pomimo ustalonego wymiaru, chyba że istnieje jakiś limit wielkości współczynników).

Wyliczanie wierzchołków

Biblioteki wielościenne, takie jak PolyLib i PPL, wykorzystują podwójny opis wielościanów i dlatego naturalnie obsługują wyliczanie wierzchołków na (nieparametrycznych) polytopach. Biblioteka Omega wewnętrznie wykonuje wyliczanie wierzchołków podczas obliczania wypukłej otoczki. PolyLib i isl zapewniają wyliczanie wierzchołków na parametrycznych polytopach, co jest niezbędne do zastosowania algorytmu Barvinoka do parametrycznych polytopów.

Wskazanie przybliżonego wyniku

W niektórych częściach kompilatora przybliżony wynik jest akceptowalny w niektórych przypadkach. Na przykład, gdy analiza zależności jest używana do kierowania transformacją pętli, ogólnie dopuszczalne jest użycie nadzbioru prawdziwych zależności — może to uniemożliwić optymalizację, ale nie pozwoli na nielegalne transformacje kodu. Gdy Biblioteka Omega generuje przybliżoną odpowiedź, odpowiedź jest odpowiednio oznaczana jako górna granica (np. poprzez „i NIEZNANE”) lub dolna granica (np. poprzez „lub NIEZNANE”). Odpowiedzi nie oznaczone w ten sposób są dokładnymi opisami zestawów punktów o wartościach całkowitych (poza przypadkami błędów w oprogramowaniu).

Obsługa terminów nieliniowych

Gdy kod zawiera mieszaninę terminów afinicznych i nieafinicznych, biblioteki wielościenne mogą w zasadzie służyć do uzyskiwania przybliżonych wyników, na przykład po prostu pomijając takie terminy, gdy jest to bezpieczne. Oprócz zapewnienia sposobu oznaczania takich przybliżonych wyników, Biblioteka Omega pozwala na ograniczone użycie „niezinterpretowanych symboli funkcji” w celu zastąpienia dowolnego składnika nieliniowego, zapewniając system, który nieznacznie poprawia wynik analizy zależności i (prawdopodobnie bardziej znacząco) zapewnia język do komunikacji na temat tych terminów (w celu prowadzenia innej analizy lub komunikacji z programistą). Pugh i Wonnacott dyskutowali o nieco mniej ograniczonej domenie niż dozwolona w bibliotece, ale to nigdy nie zostało zaimplementowane (opis istnieje w rozprawie Wonnacotta).

Operacja domknięcia przechodniego

krojenie przestrzeni iteracyjnej Pugha i Rossera , można najłatwiej określić w kategoriach przechodniego domknięcia informacji o zależności. Zarówno Omega Library, jak i isl zapewniają przechodnią operację domknięcia, która jest dokładna w wielu przypadkach pojawiających się w programach z prostymi wzorcami zależności. W innych przypadkach Biblioteka Omega tworzy podzbiór domknięcia przechodniego, podczas gdy isl tworzy nadzbiór. W przypadku Biblioteki Omega sam podzbiór może być przybliżony, co skutkuje górną granicą (oznaczoną) dolnej granicy (nieoznaczoną) domknięcia przechodniego. Zauważ, że obliczenie dokładnego domknięcia przechodniego jest nierozstrzygalne.

Zobacz też

Optymalizacja gniazda pętli
Jean-Francois Collard, Reasoning About Program Transformations, opisuje niektóre ze wspólnej filozofii tych projektów.
Teza Cédrica Bastoula stanowi wprowadzenie do modelu wielościennego.
Wpis „Omega Test” w nadchodzącej Encyklopedii obliczeń równoległych Springera opisuje aplikacje i algorytmy Biblioteki Omega, wskazując główne publikacje Projektu Omega, w których można znaleźć dalsze szczegóły. Wcześniejszą wersję roboczą tej treści można znaleźć w formie raportu technicznego jako raport techniczny Haverford College Computer Science.
Linki do odpowiednich bibliotek typu open source podano w pierwszym akapicie tego artykułu.
Reservoir Labs zapewnia „Jolylib”, implementację Polylib w Javie itp., Która „zapewnia lepszą wydajność, stabilność i funkcje”. Jolylib jest dostępny do użytku komercyjnego i akademickiego.