Optymalizacja gniazda pętli

W informatyce, a zwłaszcza w projektowaniu kompilatorów , optymalizacja gniazda pętli (LNO) to technika optymalizacji, która stosuje zestaw transformacji pętli w celu optymalizacji lokalności lub równoległości lub innej redukcji narzutu pętli w gniazdach pętli. ( Pętle zagnieżdżone występują, gdy jedna pętla znajduje się wewnątrz innej pętli). Jednym z klasycznych zastosowań jest zmniejszenie opóźnienia dostępu do pamięci lub przepustowości pamięci podręcznej niezbędnej ze względu na ponowne użycie pamięci podręcznej dla niektórych popularnych algorytmów algebry liniowej .

Technika stosowana do tworzenia tej optymalizacji nazywana jest pętlą , zwaną również blokowaniem pętli lub minami odkrywkowymi i wymianą .

Przegląd

Kafelkowanie pętli dzieli przestrzeń iteracji pętli na mniejsze fragmenty lub bloki, aby zapewnić, że dane używane w pętli pozostaną w pamięci podręcznej, dopóki nie zostaną ponownie użyte. Podział przestrzeni iteracji pętli prowadzi do podziału dużej tablicy na mniejsze bloki, dopasowując w ten sposób dostępne elementy tablicy do rozmiaru pamięci podręcznej, zwiększając ponowne wykorzystanie pamięci podręcznej i eliminując wymagania dotyczące rozmiaru pamięci podręcznej.

Zwykła pętla

 0   
  
 dla  (  ja  =  ;  ja  <  N  ;  ++  ja  )  {  ...  }

można zablokować blokiem o rozmiarze B, zastępując go blokiem

 0   
       
    
  
 dla  (  jot  =  ;  jot  <  N  ;  jot  +=  b  )  {  dla  (  ja  =  jot  ;  ja  <  min  (  N  ,  j  +  b  );  ++  ja  )  {  ....  }  }

gdzie min() jest funkcją zwracającą minimum swoich argumentów.

Przykład: mnożenie macierz-wektor

Poniżej znajduje się przykład mnożenia wektorów macierzowych. Istnieją trzy tablice, każda po 100 elementów. Kod nie dzieli tablic na mniejsze rozmiary.

       
     
     0     
      0
       0    int  ja  ,  j  ,  za  [  100  ][  100  ],  b  [  100  ],  c  [  100  ];  int  n  =  100  ;  dla  (  ja  =  ;  ja  <  n  ;  ja  ++  )  {  do  [  ja  ]  =  ;  dla  (  j  =  ;  j  <  n   
            
    
   ;  jot  ++  )  {  do  [  ja  ]  =  do  [  ja  ]  +  za  [  ja  ][  jot  ]  *  b  [  jot  ];  }  }

Po zastosowaniu kafelkowania pętli przy użyciu bloków 2 * 2 kod wygląda następująco:

         
     
     0       
      0
      int  ja  ,  j  ,  x  ,  y  ,  za  [  100  ][  100  ],  b  [  100  ],  do  [  100  ];  int  n  =  100  ;  dla  (  ja  =  ;  ja  <  n  ;  ja  +=  2  )  {  do  [  ja  ]  =  ;  c  [  ja  +    0
       0       
                 
                 1  ]  =  ;  dla  (  jot  =  ;  jot  <  n  ;  jot  +=  2  )  {  dla  (  x  =  ja  ;  x  <  min  (  ja  +  2  ,  n  );  x  ++  )  {  dla  (  y  =  j  ;  y  <  min  (  jot  +  2  ,    
                
        
      
     n  );  y  ++  )  {  do  [  x  ]  =  do  [  x  ]  +  za  [  x  ][  y  ]  *  b  [  y  ];  }  }  }  }

Oryginalna przestrzeń iteracji pętli to n na n . Dostępny fragment tablicy a[i, j] jest również n by n . Gdy n jest zbyt duże, a rozmiar pamięci podręcznej maszyny jest zbyt mały, elementy tablicy, do których uzyskano dostęp w jednej iteracji pętli (na przykład i = 1 , j = 1 do n ) mogą przekraczać linie pamięci podręcznej, powodując chybienia w pamięci podręcznej.

Rozmiar płytek

Nie zawsze łatwo jest zdecydować, jaka wartość rozmiaru kafelków jest optymalna dla jednej pętli, ponieważ wymaga to dokładnego oszacowania dostępnych regionów tablicy w pętli oraz rozmiaru pamięci podręcznej maszyny docelowej. Kolejność zagnieżdżeń pętli ( wymiana pętli ) również odgrywa ważną rolę w osiąganiu lepszej wydajności pamięci podręcznej. Jawne blokowanie wymaga wybrania rozmiaru kafelka na podstawie tych czynników. Natomiast algorytmy nieświadome pamięci podręcznej są zaprojektowane tak, aby efektywnie wykorzystywać pamięć podręczną bez jawnego blokowania.

Przykład: mnożenie macierzy

Wiele dużych operacji matematycznych na komputerach kończy się spędzaniem dużej części czasu na mnożeniu macierzy . Operacja to:

C = A×B

gdzie A, B i C to tablice N × N. Indeksy dolne dla poniższego opisu mają postać C[wiersz][kolumna] .

Podstawowa pętla to:

   

   0    

       0    
    
          0

           0     int  ja  ,  j  ,  k  ;  dla  (  ja  =  ;  ja  <  N  ;  ++  ja  )  {  dla  (  jot  =  ;  jot  <  N  ;  ++  jot  )  {  do  [  ja  ][  jot  ]  =  ;  dla  (  k  =  ;  k  <  N  ;  ++  k 
                
    
 )  do  [  ja  ][  j  ]  +=  ZA  [  ja  ][  k  ]  *  B  [  k  ][  j  ];  }  }

Do rozwiązania są trzy problemy:

  • Dodawanie zmiennoprzecinkowe zajmuje pewną liczbę cykli. Aby sumator z opóźnieniem wielu cykli był zajęty, kod musi aktualizować wiele akumulatorów równolegle.
  • Maszyny mogą zazwyczaj wykonać tylko jedną operację pamięci na multi-add , więc załadowane wartości muszą być ponownie użyte co najmniej dwa razy.
  • Typowe systemy pamięci komputerów PC mogą obsłużyć tylko jedno 8-bajtowe podwójne słowo na 10–30 wielokrotnych dodań podwójnej precyzji, więc wartości ładowane do pamięci podręcznej muszą być wielokrotnie używane.

Oryginalna pętla oblicza wynik dla jednego wpisu w macierzy wyników naraz. Dzięki równoczesnemu obliczeniu małego bloku wpisów następująca pętla ponownie wykorzystuje każdą załadowaną wartość dwukrotnie, tak że wewnętrzna pętla ma cztery ładunki i cztery wielokrotne dodania, rozwiązując w ten sposób problem nr 2. Przenosząc cztery akumulatory jednocześnie, ten kod może prawie cały czas utrzymywać zajęty pojedynczy sumator zmiennoprzecinkowy z opóźnieniem 4 (problem nr 1). Jednak kod nie rozwiązuje trzeciego problemu. (Nie odnosi się też do niezbędnych prac porządkowych, gdy N jest nieparzyste. Takie szczegóły zostaną pominięte w dalszej dyskusji).

   0      

       0      
    
                0
           0    
         dla  (  ja  =  ;  ja  <  N  ;  ja  +=  2  )  {  dla  (  jot  =  ;  jot  <  N  ;  jot  +=  2  )  {  acc00  =  acc01  =  acc10  =  acc11  =  ;  dla  (  k  =  ;  k  <  N  ;  k  ++  )  { 
                0    0
                    0
                0     acc00  +=  B  [  k  ][  j  +  ]  *  ZA  [  ja  +  ][  k  ];  acc01  +=  B  [  k  ][  j  +  1  ]  *  ZA  [  ja  +  ][  k  ];  acc10  +=  B  [  k  ][  j  +  ]  *  ZA  [  ja  +  1  ][  k 
                    
        
          0  0  
          0    
            ];  acc11  +=  B  [  k  ][  j  +  1  ]  *  ZA  [  ja  +  1  ][  k  ];  }  C  [  ja  +  ][  j  +  ]  =  acc00  ;  do  [  ja  +  ][  jot  +  1  ]  =  acc01  ;  do  [  ja  +  1  ][  j  +  0  
              
    
 ]  =  acc10  ;  do  [  ja  +  1  ][  jot  +  1  ]  =  acc11  ;  }  }

i, jak i j zostały zablokowane dwukrotnie, a wynikowe wewnętrzne pętle dwóch iteracji zostały całkowicie rozwinięte.

Ten kod działałby całkiem zadowalająco na Cray Y-MP (zbudowanym na początku lat 80.), który może wytrzymać mnożenie 0,8 na operację pamięci w pamięci głównej. Maszyna taka jak Pentium 4 2,8 GHz, zbudowana w 2003 r., ma nieco mniejszą przepustowość pamięci i znacznie lepszą liczbę zmiennoprzecinkową, dzięki czemu może wytrzymać 16,5 mnożenia na operację pamięci. W rezultacie powyższy kod będzie działał wolniej na Pentium 4 2,8 GHz niż na Y-MP 166 MHz!

Maszyna z dłuższym opóźnieniem dodawania zmiennoprzecinkowego lub z wieloma sumatorami wymagałaby większej liczby akumulatorów do równoległego działania. Łatwo jest zmienić powyższą pętlę, aby obliczyć blok 3x3 zamiast bloku 2x2, ale wynikowy kod nie zawsze jest szybszy. Pętla wymaga rejestrów do przechowywania zarówno akumulatorów, jak i załadowanych i ponownie użytych wartości A i B. Blok 2x2 wymaga 7 rejestrów. Blok 3x3 wymaga 13, co nie będzie działać na maszynie z zaledwie 8 rejestrami zmiennoprzecinkowymi w ISA . Jeśli procesor nie ma wystarczającej liczby rejestrów, kompilator zaplanuje dodatkowe ładowanie i przechowywanie w celu rozlania rejestrów na gniazda stosu, co spowoduje, że pętla będzie działać wolniej niż mniejsza zablokowana pętla.

Mnożenie macierzy jest podobne do wielu innych kodów, ponieważ może być ograniczone przepustowością pamięci, a więcej rejestrów może pomóc kompilatorowi i programiście zmniejszyć zapotrzebowanie na przepustowość pamięci. Ta presja na rejestry jest powodem, dla którego dostawcy procesorów RISC , którzy zamierzali budować maszyny bardziej równoległe niż procesory ogólnego przeznaczenia x86 i 68000 , przyjęli 32-wejściowe pliki rejestrów zmiennoprzecinkowych .

Powyższy kod nie wykorzystuje zbyt dobrze pamięci podręcznej. Podczas obliczania wyniku poziomego paska C ładowany jest jeden poziomy pasek A i cała macierz B. Dla całego obliczenia C jest przechowywane raz (to dobrze), A jest ładowane do pamięci podręcznej raz (zakładając, że pasek A mieści się w pamięci podręcznej z paskiem B), ale B jest ładowany N/ib razy, gdzie ib to rozmiar paska w macierzy C, w sumie N 3 /ib podwójnych słów załadowanych z pamięci głównej. W powyższym kodzie ib wynosi 2.

Następnym krokiem w celu zmniejszenia ruchu w pamięci jest uczynienie ib tak dużym, jak to tylko możliwe. Musi być większy niż numer „salda” zgłaszany przez strumienie. W przypadku jednego konkretnego systemu Pentium 4 2,8 GHz użytego w tym przykładzie liczba bilansowa wynosi 16,5. Drugi przykład kodu powyżej nie może zostać rozszerzony bezpośrednio, ponieważ wymagałoby to znacznie większej liczby rejestrów akumulatorów. Zamiast tego pętla jest blokowana przez i. (Technicznie rzecz biorąc, jest to właściwie drugi raz, kiedy i jest zablokowany, ponieważ pierwszy raz był współczynnikiem 2.) 

   0      

       0      
    
                   
        
                  dla  (  ii  =  ;  ii  <  N  ;  ii  +=  ib  )  {  za  (  jot  =  ;  jot  <  N  ;  jot  +=  2  )  {  za  (  ja  =  ii  ;  ja  <  ii  +  ib  ;  ja  +=  2  )  {  acc00  =  acc01  =  acc10  =    0
               0    
            
                    0    0
                        0 acc11  =  ;  dla  (  k  =  ;  k  <  N  ;  k  ++  )  {  acc00  +=  B  [  k  ][  j  +  ]  *  ZA  [  ja  +  ][  k  ];  acc01  +=  B  [  k  ][  j  +  1  ]  *  ZA  [  ja  +  ][  k  ]; 
                    0    
                        
            
              0  0  
             acc10  +=  B  [  k  ][  j  +  ]  *  ZA  [  ja  +  1  ][  k  ];  acc11  +=  B  [  k  ][  j  +  1  ]  *  ZA  [  ja  +  1  ][  k  ];  }  C  [  ja  +  ][  j  +  ]  =  acc00  ;  C  [  ja   0    
                0  
                  
        
    
 +  ][  j  +  1  ]  =  acc01  ;  do  [  ja  +  1  ][  jot  +  ]  =  acc10  ;  do  [  ja  +  1  ][  jot  +  1  ]  =  acc11  ;  }  }  }

Za pomocą tego kodu ib można ustawić na dowolny żądany parametr, a liczba obciążeń macierzy B zostanie zmniejszona o ten współczynnik. Ta swoboda ma swoją cenę: N×ib wycinków macierzy A jest przechowywanych w pamięci podręcznej. Dopóki to pasuje, ten kod nie będzie ograniczony przez system pamięci.

Więc jaki rozmiar matrycy pasuje? Przykładowy system, Pentium 4 2,8 GHz, ma podstawową pamięć podręczną danych o wielkości 16 KB. Przy ib=20 wycinek macierzy A w tym kodzie będzie większy niż podstawowa pamięć podręczna, gdy N > 100. W przypadku większych problemów potrzebna jest inna sztuczka.

Ta sztuczka polega na zmniejszeniu rozmiaru paska macierzy B poprzez zablokowanie pętli k, tak aby pasek miał rozmiar ib × kb. Zablokowanie k w sumie transfery B jest nadal przenoszone N / IB razy, dla transferów Tak długo aż

2*N/kb + N/ib < N/bilans

system pamięci maszyny nadąży za jednostką zmiennoprzecinkową, a kod będzie działał z maksymalną wydajnością. Pamięć podręczna Pentium 4 o pojemności 16 KB nie jest wystarczająco duża: gdyby zamiast tego wybrano ib=24 i kb=64, użyto by 12 KB pamięci podręcznej — unikając całkowitego jej zapełnienia, co jest pożądane, dlatego macierze C i B muszą mieć trochę miejsca do przepłynięcia. Liczby te mieszczą się w granicach 20% szczytowej prędkości zmiennoprzecinkowej procesora.

Oto kod z zablokowaną pętlą k . 

   0      

       0      
    
         0      
        
                   dla  (  ii  =  ;  ii  <  N  ;  ii  +=  ib  )  {  za  (  kk  =  ;  kk  <  N  ;  kk  +=  kb  )  {  za  (  jot  =  ;  jot  <  N  ;  jot  +=  2  )  {  za  (  ja  =  ii  ;  i  <  ii      
            
                   0
                            0
                
                
                        0  0
                        0  
                       +  ib  ;  ja  +=  2  )  {  gdyby  (  kk  ==  )  acc00  =  acc01  =  acc10  =  acc11  =  ;  else  {  acc00  =  C  [  i  +  ][  j  +  ];  acc01  =  do  [  ja  +  ][  j  +  1  ];  acc10  =  C  [  ja     0
                          
                
                         
                
                        0    0 +  1  ][  j  +  ];  acc11  =  do  [  ja  +  1  ][  j  +  1  ];  }  dla  (  k  =  kk  ;  k  <  kk  +  kb  ;  k  ++  )  {  acc00  +=  B  [  k  ][  j  +  ]  *  ZA  [  ja  +  ][  k 
	                        0
	                    0    
	                        ];  acc01  +=  B  [  k  ][  j  +  1  ]  *  ZA  [  ja  +  ][  k  ];  acc10  +=  B  [  k  ][  j  +  ]  *  ZA  [  ja  +  1  ][  k  ];  acc11  +=  b  [  k  ][  j  +  1  ]  *  ZA  [  ja  +  
                
                  0  0  
                  0    
                    0  
                       1  ][  k  ];  }  C  [  ja  +  ][  j  +  ]  =  acc00  ;  do  [  ja  +  ][  jot  +  1  ]  =  acc01  ;  do  [  ja  +  1  ][  jot  +  ]  =  acc10  ;  do  [  ja  +  1  ][  jot  +  1  ]  =  acc11 
            
        
     ;  }  }  }  }

Powyższe przykłady kodu nie pokazują szczegółów postępowania z wartościami N, które nie są wielokrotnościami czynników blokujących. Kompilatory, które optymalizują zagnieżdżanie pętli, emitują kod w celu oczyszczenia krawędzi obliczeń. Na przykład większość kompilatorów LNO prawdopodobnie oddzieliłaby iterację kk == 0 od pozostałych iteracji kk , aby usunąć instrukcję if z pętli i . Jest to jedna z zalet takiego kompilatora: chociaż kodowanie prostych przypadków tej optymalizacji jest proste, utrzymywanie poprawności wszystkich szczegółów podczas replikacji i przekształcania kodu jest procesem podatnym na błędy.

Powyższa pętla osiągnie tylko 80% szczytowych flopów w przykładowym systemie, gdy zostanie zablokowana dla rozmiaru pamięci podręcznej L1 o wielkości 16 KB. Będzie gorzej w systemach z jeszcze bardziej niezrównoważonymi systemami pamięci. Na szczęście Pentium 4 ma 256 KB (lub więcej, w zależności od modelu) wysokoprzepustową pamięć podręczną poziomu 2 oraz pamięć podręczną poziomu 1. Jest wybór:

  • Dostosuj rozmiary bloków dla pamięci podręcznej poziomu 2. To obciąży zdolność procesora do jednoczesnego utrzymywania wielu instrukcji w locie i istnieje duża szansa, że ​​nie będzie w stanie osiągnąć pełnej przepustowości z pamięci podręcznej poziomu 2.
  • Ponownie zablokuj pętle, ponownie dla rozmiarów pamięci podręcznej poziomu 2. Dzięki łącznie trzem poziomom blokowania (dla pliku rejestru, dla pamięci podręcznej L1 i pamięci podręcznej L2) kod zminimalizuje wymaganą przepustowość na każdym poziomie hierarchii pamięci . Niestety, dodatkowe poziomy blokowania pociągną za sobą jeszcze większe obciążenie pętli, co w przypadku niektórych rozmiarów problemów na niektórych urządzeniach może być bardziej czasochłonne niż jakiekolwiek niedociągnięcia w możliwości sprzętu do strumieniowego przesyłania danych z pamięci podręcznej L2.

Zamiast specjalnie dostrajać się do jednego określonego rozmiaru pamięci podręcznej, jak w pierwszym przykładzie, algorytm nieświadomy pamięci podręcznej ma na celu wykorzystanie dowolnej dostępnej pamięci podręcznej, bez względu na jej rozmiar. To automatycznie wykorzystuje dwa lub więcej poziomów hierarchii pamięci, jeśli są dostępne. Znane są algorytmy nieświadome pamięci podręcznej do mnożenia macierzy .

Zobacz też

Dalsza lektura

  1. Wolfe, M. Więcej Kafelkowanie przestrzeni iteracji . Superkomputery'89, strony 655–664, 1989.
  2. Wolf, ME i Lam, M. Algorytm optymalizacji lokalizacji danych . PLDI '91, strony 30–44, 1991.
  3. Irigoin, F. i Triolet, R. Partycjonowanie Supernode . POPL '88, strony 319–329, 1988.
  4. Xue, J. Płytki pętli dla równoległości . Wydawnictwa Naukowe Kluwer. 2000.
  5. MS Lam, EE Rothberg i ME Wolf. Wydajność pamięci podręcznej i optymalizacje zablokowanych algorytmów . W Proceedings of the 4th International Conference on Architectural Support for Programming Languages ​​and Operating Systems, strony 63–74, kwiecień 1991.

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Loop_nest_optimization&oldid=1019845219 ”