Skalowalna lokalizacja

oprogramowanie komputerowe wykazuje skalowalność lokalną, jeśli może nadal wykorzystywać procesory , które wyprzedzają ich systemy pamięci , do rozwiązywania coraz większych problemów. Termin ten jest odpowiednikiem wysokowydajnego jednoprocesorowego zastosowania skalowalnej równoległości w odniesieniu do oprogramowania , w którym można zastosować coraz większą liczbę procesorów do większych problemów.

Przegląd

Rozważ wzorce użycia pamięci w następującym gnieździe pętli (iteracyjne dwuwymiarowe obliczenia wzorcowe ):

   0   
          
              
                   dla  t  :=  do  T  zrób  dla  i  :=  1  do  N  -  1  zrób  dla  j  :=  1  do  N  -  1  zrób  nowy  (  i  ,  j  )  :=  (  A  (  i  -  1  ,  j  )  +  A  (  ja  ,  j )  -  1  )  +  ZA  (       
        
    

          
         ja  ,  jot  )  +  ZA  (  ja  ,  jot  +  1  )  +  ZA  (  ja  +  1  ,  jot  ))  *  .  2  koniec  koniec  dla  i  :=  1  do  N  -  1  do  j  :=  1  do  N  -  1  do  A  (  i  ,  j  )  :  =       
              
        
     nowy  (  i  ,  j  )  koniec  koniec  koniec 

Całe gniazdo pętli dotyka około 2*N**2 elementów tablicy i wykonuje około 5*T*N**2 operacji zmiennoprzecinkowych. Zatem ogólny bilans obliczeniowy (stosunek obliczeń zmiennoprzecinkowych do użytych komórek pamięci zmiennoprzecinkowej) całego tego gniazda pętli wynosi około 5T/2. Kiedy bilans obliczeniowy jest funkcją rozmiaru problemu, tak jak tutaj, mówi się, że kod ma skalowalny bilans obliczeniowy . Tutaj moglibyśmy osiągnąć dowolną równowagę obliczeniową, po prostu wybierając wystarczająco duży T .

Jednak gdy N jest duże, ten kod nadal nie będzie wykazywać dobrego ponownego wykorzystania pamięci podręcznej ze względu na słabą lokalizację odniesienia : do czasu, gdy new(1,1) będzie potrzebny w drugim zadaniu lub w drugim kroku wykonywania pierwszego zadania , linia pamięci podręcznej zawierająca new(1,1) zostanie nadpisana inną częścią jednej z tablic.

Kafelkowanie pierwszego gniazda pętli i/j może poprawić wydajność pamięci podręcznej, ale tylko w ograniczonym stopniu, ponieważ to gniazdo ma równowagę obliczeniową około 5/2. Aby uzyskać bardzo wysoki stopień lokalności, na przykład 500 (aby wydajnie uruchomić ten kod z tablicą, która nie mieści się w pamięci RAM i jest przeniesiona do pamięci wirtualnej), musimy ponownie wykorzystać wartości w różnych krokach czasowych.

Optymalizacja w różnych krokach czasowych została zbadana w wielu kompilatorach badawczych; patrz praca Wonnacotta, Songa i Li lub Sadayappana i in. aby uzyskać szczegółowe informacje na temat niektórych podejść do układania w czasie . Wonnacott wykazał, że układanie w czasie można wykorzystać do optymalizacji zestawów danych poza rdzeniem; w zasadzie każde z tych podejść powinno być w stanie osiągnąć dowolnie wysoką lokalizację pamięci bez wymagania, aby cała tablica mieściła się w pamięci podręcznej (wymagania dotyczące pamięci podręcznej rosną jednak wraz z wymaganą lokalizacją). Cytowane powyżej techniki wieloprocesorowe powinny w zasadzie jednocześnie generować skalowalną lokalność i skalowalną równoległość .