Polytopní model - Polytope model

The polyedrický model (nazývané také metoda mnohostěnů) je matematický rámec pro programy, které provádějí velké množství operací - příliš velké na to, aby byly explicitně vyjmenovány - a proto vyžadují kompaktní zastoupení. Vnořené smyčkové programy jsou typickým, ale ne jediným příkladem a nejběžnější použití modelu je pro optimalizace smyčkového hnízda v optimalizace programu. Metoda mnohostěnu zachází s každou iterací smyčky ve vnořených smyčkách jako mřížové body uvnitř matematických objektů zvaných mnohostěn, vystupuje afinní transformace nebo obecnější non-afinní transformace, jako je obklady na polytopech a poté převede transformované polytopy na ekvivalentní, ale optimalizované (v závislosti na cílovém cíli optimalizace), hnízdí smyčky skrz polyedrické skenování.

Jednoduchý příklad

Zvažte následující příklad napsaný v C:

  konst int n = 100;  int i, j, A[n][n];  pro (i = 1; i < n; i++) {    pro (j = 1; j < (i + 2) && j < n; j++) {      A[i][j] = A[i - 1][j] + A[i][j - 1];    }  }

Základní problém s tímto kódem spočívá v tom, že každá iterace vnitřní smyčky je zapnuta a [i] [j] vyžaduje, aby výsledek předchozí iterace, a [i] [j - 1], již k dispozici. Proto tento kód nelze paralelizovat nebo pipeline jak je aktuálně napsáno.

Aplikace modelu polytopu s afinní transformací ${displaystyle (i ',, j') = (i + j ,, j)}$ a příslušná změna hranic, transformuje vnořené smyčky výše na:

      A[i - j][j] = A[i - j - 1][j] + A[i - j][j - 1];

V tomto případě žádná iterace vnitřní smyčky nezávisí na výsledcích předchozí iterace; celá vnitřní smyčka může být provedena paralelně. (Každá iterace vnější smyčky však závisí na předchozích iteracích.)

Podrobný příklad

Závislosti src, před zkosení smyčky. Červená tečka odpovídá src [1] [0]; růžová tečka odpovídá src [2] [2].

Následující C kód implementuje formu distribuce chyb dithering podobný Floyd – Steinberg dithering, ale upraveno z pedagogických důvodů. Dvourozměrné pole src obsahuje h řádky w pixely, přičemž každý pixel má a stupně šedi hodnota mezi 0 a 255 včetně. Po dokončení rutiny výstupní pole dst bude obsahovat pouze pixely s hodnotou 0 nebo hodnotou 255. Během výpočtu se chyba rozkladu každého pixelu shromáždí přidáním zpět do src pole. (Všimněte si toho src a dst jsou během výpočtu čteny i zapisovány; src není jen pro čtení a dst není jen pro zápis.)

Každá iterace vnitřní smyčka upravuje hodnoty v src [i] [j] na základě hodnot src [i-1] [j], src [i] [j-1], a src [i + 1] [j-1]. (Stejné závislosti platí pro dst [i] [j]. Pro účely zkosení smyčky, můžeme myslet src [i] [j] a dst [i] [j] jako stejný prvek.) Můžeme ilustrovat závislosti src [i] [j] graficky, jako na obrázku vpravo.

#define ERR (x, y) (dst [x] [y] - src [x] [y])prázdnota váhat(nepodepsaný char** src, nepodepsaný char** dst, int w, int h){    int i, j;    pro (j = 0; j < h; ++j) {        pro (i = 0; i < w; ++i) {            int proti = src[i][j];            -li (i > 0)                proti -= CHYBOVAT(i - 1, j) / 2;            -li (j > 0) {                proti -= CHYBOVAT(i, j - 1) / 4;                -li (i < w - 1)                    proti -= CHYBOVAT(i + 1, j - 1) / 4;            }            dst[i][j] = (proti < 128) ? 0 : 255;            src[i][j] = (proti < 0) ? 0 : (proti < 255) ? proti : 255;        }    }}

Závislosti src, po zkosení smyčky. Prvky pole budou zpracovány v pořadí šedá, červená, zelená, modrá, žlutá ...

Provádění afinní transformace ${displaystyle (p ,, t) = (i ,, 2j + i)}$ na původním diagramu závislostí nám dává nový diagram, který je zobrazen na dalším obrázku. Poté můžeme přepsat kód, do kterého se smyčka přepne str a t namísto i a j, získání následující "zkosené" rutiny.

 prázdnota dither_skewed(nepodepsaný char **src, nepodepsaný char **dst, int w, int h)   {     int t, str;     pro (t = 0; t < (w + (2 * h)); ++t) {         int pmin = max(t % 2, t - (2 * h) + 2);         int pmax = min(t, w - 1);         pro (str = pmin; str <= pmax; str += 2) {             int i = str;             int j = (t - str) / 2;             int proti = src[i][j];             -li (i > 0)               proti -= CHYBOVAT(i - 1, j) / 2;             -li (j > 0)               proti -= CHYBOVAT(i, j - 1) / 4;             -li (j > 0 && i < w - 1)               proti -= CHYBOVAT(i + 1, j - 1) / 4;             dst[i][j] = (proti < 128) ? 0 : 255;             src[i][j] = (proti < 0) ? 0 : (proti < 255) ? proti : 255;         }     } }

Viz také

Externí odkazy a reference

"Základní metoda mnohostěnů", tutoriál Martina Griebla obsahující diagramy výše uvedeného příkladu pseudokódu
"Generování kódu v modelu Polytope" (1998). Martin Griebl, Christian Lengauer a Sabine Wetzel
„Generátor mnohostěnných kódů CLooG“
"CodeGen +: Z-mnohostěn skenování"^{[trvalý mrtvý odkaz ]}
PoCC: Polyhedral Compiler Collection
PLUTO - automatický paralelizátor a optimalizátor lokality pro hnízda afinních smyček
- Bondhugula, Uday; Hartono, Albert; Ramanujam, J .; Sadayappan, P. (01.01.2008). Praktický automatický mnohostěnný paralelizátor a optimalizátor lokality. Sborník 29. konference ACM SIGPLAN o návrhu a implementaci programovacího jazyka. PLDI '08. New York, NY, USA: ACM. 101–113. doi:10.1145/1375581.1375595. ISBN 9781595938602.
polyhedral.info - Web, který shromažďuje informace o mnohostěnné kompilaci
Polly - Rámec LLVM pro optimalizaci smyčky na vysoké úrovni a optimalizace datových lokalit
MIT Tiramisu mnohostěn Rámec.