Model Polytope

Aby zapoznać się z fizycznymi modelami wielościanów, zobacz Model wielościanu .

Model wielościenny (zwany także metodą polytope ) jest matematyczną ramą dla programów, które wykonują dużą liczbę operacji — zbyt dużą, aby można ją było wyraźnie wyliczyć — co wymaga zwartej reprezentacji . Programy z zagnieżdżonymi pętlami są typowym, ale nie jedynym przykładem, a najczęstszym zastosowaniem tego modelu jest optymalizacja zagnieżdżenia pętli w optymalizacji programu . Metoda wielościanów traktuje każdą iterację pętli w zagnieżdżonych pętlach jako punkty siatki wewnątrz obiektów matematycznych zwanych wielościanami , wykonuje transformacje afiniczne lub bardziej ogólne transformacje nieafiniczne, takie jak kafelkowanie na polytopach, a następnie konwertuje przekształcone polytopy na równoważne, ale zoptymalizowane (w zależności od docelowego celu optymalizacji), zagnieżdżenia pętli poprzez skanowanie wielościanów.

Prosty przykład

Rozważmy następujący przykład napisany w C :

    
   

        
                stała  int  n  =  100  ;  int  ja  ,  j  ,  za  [  n  ][  n  ];  dla  (  ja  =  1  ;  ja  <  n  ;  ja  ++  )  {  dla  (  jot  =  1  ;  jot  <  (  ja  +  2  )  &&  jot  <  n  ;  jot  ++  
            
  
 )  {  za  [  ja  ][  jot  ]  =  za  [  ja  -  1  ][  jot  ]  +  za  [  ja  ][  jot  -  1  ];  }  } 

Podstawowy problem z tym kodem polega na tym, że każda iteracja wewnętrznej pętli na a[i][j] wymaga, aby wynik poprzedniej iteracji, a[i][j - 1] , był już dostępny. W związku z tym tego kodu nie można zrównoleglać ani przesyłać potokowo, tak jak jest obecnie napisany.

Zastosowanie modelu polytope z transformacją afiniczną ${\ Displaystyle (i', \, j') = (i + j, \, j)}$ i odpowiednia zmiana granic przekształci powyższe zagnieżdżone pętle w:

               za  [  ja  -  jot  ][  jot  ]  =  za  [  ja  -  jot  -  1  ][  jot  ]  +  za  [  ja  -  jot  ][  jot  -  1  ]; 

W tym przypadku żadna iteracja pętli wewnętrznej nie zależy od wyników poprzedniej iteracji; cała wewnętrzna pętla może być wykonywana równolegle. (Jednak każda iteracja pętli zewnętrznej zależy od poprzednich iteracji).

Szczegółowy przykład

Zależności src przed pochyleniem pętli . Czerwona kropka odpowiada src[1][0] ; różowa kropka odpowiada src[2][2] .

Poniższy kod C implementuje formę ditheringu dystrybucji błędów podobną do ditheringu Floyda-Steinberga , ale zmodyfikowaną ze względów pedagogicznych. Dwuwymiarowa tablica src zawiera h wierszy po w pikseli, przy czym każdy piksel ma wartość w skali szarości z zakresu od 0 do 255 włącznie. Po zakończeniu procedury tablica wyjściowa dst będzie zawierać tylko piksele o wartości 0 lub 255. Podczas obliczeń błąd ditheringu każdego piksela jest zbierany przez dodanie go z powrotem do src szyk. (Zauważ, że src i dst są zarówno odczytywane, jak i zapisywane podczas obliczeń; src nie jest tylko do odczytu, a dst nie jest tylko do zapisu).

Każda iteracja pętli wewnętrznej modyfikuje wartości w src[i][j] na podstawie wartości src[i-1][j] , src[i][j-1] i src[i+1][ j-1] . (Te same zależności dotyczą dst[i][j] . Na potrzeby pochylenia pętli możemy myśleć o src[i][j] i dst[i][j] jako o tym samym elemencie). zależności src[i][j] graficznie, jak na diagramie po prawej stronie.

0 0 #define ERR(x, y) (dst[x][y] - src[x][y]) void dither ( unsigned char ** src , unsigned char ** dst , int w , int h ) { int i , j ; dla ( jot = ; jot < godz ; ++ jot ) { za ( ja = ; ja < 0 0 w ; ++ ja ) { int v = źródło [ ja ][ j ]; jeśli ( i > ) v -= BŁĄD ( i - 1 , j ) / 2 ; jeśli ( j > ) { v -= BŁĄD ( ja , j - 1 ) / 4 ; 0 0 jeśli ( i < w - 1 ) v -= BŁĄD ( i + 1 , j - 1 ) / 4 ; } dst [ ja ][ jot ] = ( v < 128 ) ? : 255 ; źródło [ ja ][ jot ] = ( v < ) ? 0 : ( v < 255 ) ? w : 255 ; } } }

Zależności src , po pochyleniu pętli. Elementy tablicy będą przetwarzane w kolejności : szary, czerwony, zielony, niebieski, żółty...

Wykonanie transformacji afinicznej ${\ Displaystyle (p, \, t) = (i, \, 2j + i)}$ na oryginalnym diagramie zależności daje nam nowy diagram co widać na kolejnym obrazku. Możemy następnie przepisać kod, aby zapętlił się na p i t zamiast i i j , uzyskując następującą „skośną” procedurę.

0 void dither_skewed ( unsigned char ** src , unsigned char ** dst , int w , int h ) { int t , p ; dla ( t = ; t < ( w + ( 2 * godz )); ++ t ) { int min = maks ( t % 2 , t- ( 2 * h ) + 2 ) ; int pmax = min ( t , w - 1 ); dla ( p = pmin ; p <= pmax ; p += 2 ) { int ja = p ; int j = ( t - 0 0 p ) / 2 ; int v = źródło [ i ][ j ]; jeśli ( i > ) v -= BŁĄD ( i - 1 , j ) / 2 ; jeśli ( j > ) v -= BŁĄD ( ja , j - 1 ) / 4 ; jeśli ( 0 0 0 j > && ja < w - 1 ) v -= BŁĄD ( ja + 1 , j - 1 ) / 4 ; dst [ ja ][ jot ] = ( v < 128 ) ? : 255 ; źródło [ ja ][ jot ] = ( v < ) 0 ? : ( v < 255 ) ? w : 255 ; } } }

Zobacz też

• Ramy wspierające model wielościenny
• Optymalizacja gniazda pętli
• Optymalizacja pętli
• Rozwijanie pętli
• Kafelkowanie w pętli

Zewnętrzne linki i odnośniki

• „Podstawowa metoda polytope” , samouczek Martina Griebla zawierający diagramy powyższego przykładu pseudokodu
• „Generowanie kodu w modelu Polytope” (1998). Martina Griebla, Christiana Lengauera i Sabine Wetzel
• „Generator kodu wielościennego CLooG”
• „CodeGen+: skanowanie wielościanów Z”
• PoCC: kolekcja kompilatorów wielościennych
• PLUTO - automatyczny równoległość i optymalizator lokalizacji dla gniazd pętli afinicznych
  •    Bondhugula, Uday; Hartono, Albert; Ramanujam, J.; Sadayappan, P. (2008-01-01). Praktyczny automatyczny paralelizator wielościenny i optymalizator lokalizacji . Materiały z 29. Konferencji ACM SIGPLAN na temat projektowania i wdrażania języka programowania . PLDI '08. Nowy Jork, NY, USA: ACM. s. 101–113. doi : 10.1145/1375581.1375595 . ISBN 9781595938602 . S2CID 7086982 .
• polyhedral.info - Strona internetowa zbierająca informacje o kompilacji wielościanów
• Polly — platforma LLVM do optymalizacji pętli wysokiego poziomu i lokalizacji danych
• MIT Tiramisu .