Miejscowość odniesienia - Locality of reference

W informatyce , miejscowości odniesienia , znany również jako zasadę lokalności , jest tendencja procesor dostęp do tego samego zestawu miejscach pamięci powtarzalnie w krótkim okresie czasu. Istnieją dwa podstawowe typy lokalizacji referencyjnej – lokalizacja czasowa i przestrzenna. Lokalizacja czasowa odnosi się do ponownego wykorzystania określonych danych i/lub zasobów w stosunkowo krótkim czasie. Lokalizacja przestrzenna (nazywana również lokalizacją danych ) odnosi się do wykorzystania elementów danych w stosunkowo bliskich lokalizacjach przechowywania. Lokalizacja sekwencyjna, szczególny przypadek lokalizacji przestrzennej, występuje, gdy elementy danych są rozmieszczone i dostępne liniowo, np. przemierzając elementy w jednowymiarowej tablicy .

Lokalność to rodzaj przewidywalnego zachowania, które występuje w systemach komputerowych. Systemy, które wykazują silną lokalizację odniesienia, są świetnymi kandydatami do optymalizacji wydajności poprzez wykorzystanie technik, takich jak buforowanie , wstępne pobieranie pamięci i zaawansowane predyktory rozgałęzień na etapie potokowania rdzenia procesora.

Rodzaje miejscowości

Istnieje kilka różnych typów lokalizacji odniesienia:

  • Lokalizacja czasowa : Jeśli w pewnym momencie nastąpi odwołanie do określonej lokalizacji w pamięci, prawdopodobnie w najbliższej przyszłości nastąpi odwołanie do tej samej lokalizacji. Istnieje czasowa bliskość między sąsiednimi odniesieniami do tej samej lokalizacji pamięci. W takim przypadku często podejmuje się wysiłki w celu przechowywania kopii danych odniesienia w szybszym przechowywaniu w pamięci, aby zmniejszyć opóźnienie kolejnych odwołań. Lokalizacja czasowa jest szczególnym przypadkiem lokalizacji przestrzennej (patrz niżej), a mianowicie, gdy lokalizacja potencjalna jest identyczna z lokalizacją obecną.
  • Lokalizacja przestrzenna : Jeśli dana lokalizacja pamięci jest przywoływana w określonym czasie, prawdopodobne jest, że w najbliższej przyszłości nastąpi odwołanie do pobliskich lokalizacji pamięci. W takim przypadku często próbuje się odgadnąć wielkość i kształt obszaru wokół aktualnego odniesienia, dla którego warto przygotować szybszy dostęp do późniejszego odniesienia.
    • Lokalizacja pamięci (lub lokalizacja danych ): Lokalizacja przestrzenna wyraźnie odnosząca się do pamięci .
  • Oddział lokalizację : Jeśli istnieje tylko kilka możliwych alternatyw dla przyszłego część ścieżki w przestrzenno-czasowe współrzędnych przestrzeni. Dzieje się tak, gdy pętla instrukcji ma prostą strukturę lub możliwy wynik małego systemu warunkowych instrukcji rozgałęziających jest ograniczony do niewielkiego zestawu możliwości. Lokalizacja oddziału zazwyczaj nie jest lokalizacją przestrzenną, ponieważ kilka możliwości może znajdować się daleko od siebie.
  • Równoodległa lokalizacja : w połowie drogi między lokalizacją przestrzenną a lokalizacją branżową. Rozważmy pętlę uzyskującą dostęp do lokalizacji we wzorcu równoodległym, tj. ścieżka w przestrzenno-czasowej przestrzeni współrzędnych jest linią przerywaną. W takim przypadku prosta funkcja liniowa może przewidzieć, która lokalizacja będzie dostępna w najbliższej przyszłości.

Aby skorzystać z często występującej lokalizacji czasowej i przestrzennej, większość systemów przechowywania informacji jest hierarchiczna . Równoodległa lokalizacja jest zwykle obsługiwana przez różne nietrywialne instrukcje przyrostowe procesora. W przypadku lokalizacji rozgałęzień współczesne procesory mają wyrafinowane predyktory rozgałęzień i na podstawie tej prognozy menedżer pamięci procesora próbuje zebrać i wstępnie przetworzyć dane prawdopodobnych alternatyw.

Stosowność

Istnieje kilka powodów lokalizacji. Te powody to albo cele do osiągnięcia, albo okoliczności do zaakceptowania, w zależności od aspektu. Poniższe powody nie są rozłączne ; w rzeczywistości poniższa lista przechodzi od najbardziej ogólnego przypadku do przypadków szczególnych:

  • Przewidywalność : Lokalność to tylko jeden rodzaj przewidywalnego zachowania w systemach komputerowych.
  • Struktura programu : Lokalizacja występuje często ze względu na sposób, w jaki tworzone są programy komputerowe do rozwiązywania problemów rozstrzygalnych. Zasadniczo powiązane dane są przechowywane w pobliskich lokalizacjach w pamięci masowej. Jeden wspólny wzorzec w informatyce obejmuje przetwarzanie kilku elementów, po jednym na raz. Oznacza to, że jeśli wykonywanych jest dużo przetwarzania, pojedynczy element będzie dostępny więcej niż jeden raz, co prowadzi do czasowej lokalizacji odniesienia. Co więcej, przejście do następnej pozycji oznacza, że ​​odczytana zostanie następna pozycja, stąd przestrzenna lokalizacja odniesienia, ponieważ lokalizacje pamięci są zwykle odczytywane partiami.
  • Liniowe struktury danych : lokalność często występuje, ponieważ kod zawiera pętle, które mają tendencję do odwoływania się do tablic lub innych struktur danych za pomocą indeksów. Lokalizacja sekwencyjna, szczególny przypadek lokalizacji przestrzennej, występuje, gdy odpowiednie elementy danych są uporządkowane i dostępne liniowo. Na przykład proste przechodzenie elementów w jednowymiarowej tablicy, od adresu podstawowego do najwyższego elementu, wykorzystałoby sekwencyjną lokalizację tablicy w pamięci. Równoodległa lokalizacja występuje, gdy przejście liniowe odbywa się na dłuższym obszarze sąsiednich struktur danych o identycznej strukturze i rozmiarze, uzyskując dostęp do odpowiadających sobie elementów każdej struktury, a nie do każdej całej struktury. Dzieje się tak, gdy macierz jest reprezentowana jako sekwencyjna macierz wierszy i wymagany jest dostęp do pojedynczej kolumny macierzy.
  • Efektywność wykorzystania hierarchii pamięci : Chociaż pamięć o dostępie swobodnym daje programiście możliwość odczytu lub zapisu w dowolnym miejscu i czasie, w praktyce na opóźnienia i przepustowość wpływa wydajność pamięci podręcznej , która jest poprawiana poprzez zwiększenie lokalizacji odniesienia. Słaba lokalizacja odniesienia skutkuje thrashingiem pamięci podręcznej i zanieczyszczeniem pamięci podręcznej i aby tego uniknąć, elementy danych o słabej lokalizacji mogą być pomijane z pamięci podręcznej.

Ogólne zastosowanie

Jeśli przez większość czasu znaczna część odwołań agreguje się w klastry i jeśli kształt tego systemu klastrów można dobrze przewidzieć, można go wykorzystać do optymalizacji wydajności. Istnieje kilka sposobów na skorzystanie z lokalizacji za pomocą technik optymalizacji . Popularne techniki to:

  • Zwiększenie lokalizacji referencji (ogólnie po stronie oprogramowania)
  • Wykorzystywanie lokalizacji odniesień: Ogólnie osiągane po stronie sprzętu, lokalizacja czasowa i przestrzenna może być kapitalizowana przez hierarchiczny sprzęt pamięci masowej. Równoodległa lokalizacja może być wykorzystana przez odpowiednio wyspecjalizowane instrukcje procesorów, za tę możliwość odpowiada nie tylko sprzęt, ale również oprogramowanie, czy jego struktura nadaje się do kompilacji programu binarnego, który wywołuje odpowiednie instrukcje specjalistyczne. Lokalizacja oddziału jest możliwością bardziej rozbudowaną, stąd potrzebny jest większy wysiłek rozwojowy, ale w takim miejscu jest znacznie większa rezerwa na przyszłe eksploracje niż we wszystkich pozostałych.

Wykorzystanie lokalizacji przestrzennej i czasowej

Pamięć hierarchiczna

Główny artykuł: Hierarchia pamięci

Pamięć hierarchiczna to optymalizacja sprzętowa, która wykorzystuje zalety lokalizacji przestrzennej i czasowej i może być używana na kilku poziomach hierarchii pamięci. Stronicowanie w oczywisty sposób korzysta z lokalizacji czasowej i przestrzennej. Pamięć podręczna jest prostym przykładem wykorzystania lokalizacji czasowej, ponieważ jest specjalnie zaprojektowanym, szybszym, ale mniejszym obszarem pamięci, zwykle używanym do przechowywania danych, do których ostatnio się odwołują, oraz danych w pobliżu tych, do których się odwołuje, co może prowadzić do potencjalnego wzrostu wydajności.

Elementy danych w pamięci podręcznej niekoniecznie odpowiadają elementom danych, które są blisko przestrzennie w pamięci głównej; jednak elementy danych są umieszczane w pamięci podręcznej po jednym wierszu pamięci podręcznej na raz. Oznacza to, że ponownie ważna jest lokalizacja przestrzenna: jeśli odwołujemy się do jednego elementu, kilka sąsiednich elementów również zostanie przeniesionych do pamięci podręcznej. Wreszcie, lokalizacja czasowa odgrywa rolę na najniższym poziomie, ponieważ wyniki, do których odwołuje się bardzo blisko siebie, mogą być przechowywane w rejestrach maszyny . Niektóre języki programowania (takie jak C ) pozwalają programiście sugerować, że pewne zmienne powinny być trzymane w rejestrach.

Lokalizacja danych jest typową cechą odniesienia do pamięci w zwykłych programach (chociaż istnieje wiele nieregularnych wzorców dostępu do pamięci). Dzięki temu hierarchiczny układ pamięci jest opłacalny. W komputerach pamięć jest podzielona hierarchicznie w celu przyspieszenia dostępu do danych. Niższe poziomy hierarchii pamięci są zwykle wolniejsze, ale większe. W ten sposób program osiągnie większą wydajność, jeśli użyje pamięci, gdy jest przechowywana w pamięci podręcznej na wyższych poziomach hierarchii pamięci i unika wprowadzania innych danych na wyższe poziomy hierarchii, które zastąpią dane, które będą używane wkrótce w przyszłości. To jest ideał, a czasem nie da się go osiągnąć.

Typowa hierarchia pamięci (czasy dostępu i rozmiary pamięci podręcznej są przybliżeniami typowych wartości używanych do celów dyskusji w 2013 r.; rzeczywiste wartości i rzeczywista liczba poziomów w hierarchii różnią się):

  • Rejestry procesora (8–256 rejestrów) – dostęp natychmiastowy, z szybkością najgłębszego rdzenia procesora
  • Pamięć podręczna L1 CPU (32 kB do 512  kB ) – szybki dostęp, z szybkością najbardziej wewnętrznej magistrali pamięci należącej wyłącznie do każdego rdzenia
  • Pamięć podręczna L2 CPU (128 KB do 24  MB ) – nieco wolniejszy dostęp, z szybkością magistrali pamięci dzielonej między bliźniacze rdzenie
  • Pamięć podręczna L3 CPU (2 MB do 32  MB ) – jeszcze wolniejszy dostęp, przy szybkości magistrali pamięci współdzielonej przez jeszcze więcej rdzeni tego samego procesora
  • Główna pamięć fizyczna ( RAM ) (256 MB do 64  GB ) – wolny dostęp, którego prędkość jest ograniczona odległościami przestrzennymi i ogólnymi interfejsami sprzętowymi między procesorem a modułami pamięci na płycie głównej
  • Dysk ( pamięć wirtualna , system plików ) (1 GB do 256  TB ) – bardzo wolny, ze względu na węższy (w bitach), fizycznie znacznie dłuższy kanał danych między płytą główną komputera a urządzeniami dyskowymi oraz ze względu na dodatkowy protokół oprogramowania potrzebny na wierzchu wolnego interfejsu sprzętowego
  • Pamięć zdalna (inne komputery lub chmura) (praktycznie nieograniczona) – szybkość waha się od bardzo wolnego do bardzo wolnego

Nowoczesne maszyny mają tendencję do odczytywania bloków niższej pamięci na następny poziom hierarchii pamięci. Jeśli spowoduje to przesunięcie używanej pamięci, system operacyjny próbuje przewidzieć, które dane będą dostępne najrzadziej (lub najnowsze) i przenieść je w dół hierarchii pamięci. Algorytmy predykcyjne wydają się być proste, aby zmniejszyć złożoność sprzętu, chociaż stają się nieco bardziej skomplikowane.

Mnożenie macierzy

Typowym przykładem jest mnożenie macierzy : 

for i in 0..n
  for j in 0..m
    for k in 0..p
      C[i][j] = C[i][j] + A[i][k] * B[k][j];

Zmieniając kolejność pętli na ji k, przyspieszenie w mnożeniu dużych macierzy staje się dramatyczne, przynajmniej w przypadku języków, które umieszczają ciągłe elementy tablicy w ostatnim wymiarze. Nie zmieni to wyniku matematycznego, ale poprawi wydajność. W tym przypadku „duża” oznacza w przybliżeniu ponad 100 000 elementów w każdej macierzy lub wystarczającą ilość pamięci adresowalnej, aby macierze nie mieściły się w pamięciach podręcznych L1 i L2. 

for i in 0..n
  for k in 0..p
    for j in 0..m
      C[i][j] = C[i][j] + A[i][k] * B[k][j];

Powodem tego przyspieszenia jest to, że w pierwszym przypadku odczyty z A[i][k]są w pamięci podręcznej (ponieważ kindeks jest ciągłym, ostatnim wymiarem), ale B[k][j]tak nie jest, więc istnieje kara za brak pamięci podręcznej na B[k][j]. C[i][j]Jest bez znaczenia, ponieważ może być podniesiona z wewnętrznej pętli - zmiennej sterującej istnieje k. 

for i in 0..n
  for j in 0..m
    temp = C[i][j]
    for k in 0..p
      temp = temp + A[i][k] * B[k][j];
    C[i][j] = temp

W drugim przypadku zarówno odczyty, jak i zapisy C[i][j]znajdują się w pamięci podręcznej, odczyty B[k][j]są w pamięci podręcznej, a odczyt A[i][k]można wyciągnąć z wewnętrznej pętli. 

for i in 0..n
  for k in 0..p
    temp = A[i][k]
    for j in 0..m
      C[i][j] = C[i][j] + temp * B[k][j];

Zatem drugi przykład nie ma kary za brak pamięci podręcznej w wewnętrznej pętli, podczas gdy pierwszy przykład ma karę za brak pamięci podręcznej.

Na procesorze z roku 2014 drugi przypadek jest około pięć razy szybszy niż pierwszy przypadek napisany w C i skompilowany za pomocą gcc -O3. (Dokładne badanie zdeasemblowanego kodu pokazuje, że w pierwszym przypadku GCC używa instrukcji SIMD, a w drugim nie, ale kara pamięci podręcznej jest znacznie gorsza niż zysk SIMD.)

Lokalizację czasową można również poprawić w powyższym przykładzie, stosując technikę zwaną blokowaniem . Większą macierz można podzielić na macierze podrzędne o równych rozmiarach, dzięki czemu do mniejszych bloków można się odwoływać (mnożyć) kilka razy w pamięci. Zauważ, że ten przykład działa dla macierzy kwadratowych o wymiarach ROZMIAR x ROZMIAR, ale można go łatwo rozszerzyć na dowolne macierze, zastępując w razie potrzeby SIZE_I, SIZE_J i SIZE_K. 

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE)
  for (kk = 0; kk < SIZE; kk += BLOCK_SIZE)
    for (jj = 0; jj < SIZE; jj += BLOCK_SIZE)
      maxi = min(ii + BLOCK_SIZE, SIZE);
      for (i = ii; i < maxi; i++)
        maxk = min(kk + BLOCK_SIZE, SIZE);
        for (k = kk; k < maxk; k++)
          maxj = min(jj + BLOCK_SIZE, SIZE);
          for (j = jj; j < maxj; j++)
            C[i][j] = C[i][j] + A[i][k] * B[k][j];

Lokalizacja czasowa powyższego rozwiązania jest zapewniona, ponieważ blok może być użyty kilka razy przed przejściem dalej, dzięki czemu rzadziej jest przenoszony do i z pamięci. Lokalność przestrzenna jest ulepszona, ponieważ elementy z kolejnymi adresami pamięci mają tendencję do wciągania razem hierarchii pamięci.

Zobacz też

Bibliografia

Bibliografia