Pamięć hierarchicznaEdit

Pamięć hierarchiczna to optymalizacja sprzętowa, która czerpie korzyści z lokalności przestrzennej i czasowej i może być stosowana na kilku poziomach hierarchii pamięci. Stronicowanie oczywiście korzysta z czasowej i przestrzennej lokalności. Pamięć podręczna jest prostym przykładem wykorzystania lokalizacji czasowej, ponieważ jest to specjalnie zaprojektowany, szybszy, ale mniejszy obszar pamięci, zwykle używany do przechowywania ostatnio przywoływanych danych i danych w pobliżu ostatnio przywoływanych danych, co może prowadzić do potencjalnego wzrostu wydajności.

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

Lokalność danych jest typową cechą odwołań do pamięci w zwykłych programach (choć istnieje wiele nieregularnych wzorców dostępu do pamięci). To sprawia, że hierarchiczny układ pamięci jest opłacalny. W komputerach pamięć jest podzielona na hierarchię w celu przyspieszenia dostępu do danych. Niższe poziomy hierarchii pamięci są zwykle wolniejsze, ale większe. Tak więc program osiągnie większą wydajność, jeśli korzysta z pamięci, podczas gdy jest ona buforowana na wyższych poziomach hierarchii pamięci i unika wprowadzania innych danych na wyższe poziomy hierarchii, które będą wypierać dane, które będą używane krótko w przyszłości. Jest to ideał i czasami nie może być osiągnięty.

Typowa hierarchia pamięci (czasy dostępu i rozmiary pamięci podręcznej są przybliżeniami typowych wartości używanych od 2013 roku na potrzeby dyskusji; rzeczywiste wartości i rzeczywiste liczby poziomów w hierarchii różnią się):

• Rejestry procesora (8-256 rejestrów) – dostęp natychmiastowy, z prędkością najbardziej wewnętrznego rdzenia procesora
• L1 Cache procesora (od 32 KiB do 512 KiB) – dostęp szybki, z prędkością wewnętrznej magistrali pamięci posiadanej wyłącznie przez każdy rdzeń
• L2 Cache procesora (od 128 KiB do 24 MiB) – dostęp nieco wolniejszy, z prędkością magistrali pamięci współdzielonej pomiędzy bliźniakami rdzeni
• L3 cache CPU (2 MiB do 32 MiB) – jeszcze wolniejszy dostęp, z prędkością magistrali pamięci współdzielonej pomiędzy jeszcze większą liczbą rdzeni tego samego procesora
• Główna pamięć fizyczna (RAM) (256 MiB do 64 GiB) – wolny dostęp, którego szybkość jest ograniczona odległościami przestrzennymi i ogólnymi interfejsami sprzętowymi pomiędzy procesorem a modułami pamięci na płycie głównej
• Dysk (pamięć wirtualna, system plików) (1 GiB do 256 TiB) – bardzo wolny, ze względu na węższy (w szerokości bitów), fizycznie znacznie dłuższy kanał danych pomiędzy płytą główną komputera a urządzeniami dyskowymi, oraz ze względu na zbędny protokół programowy potrzebny na szczycie powolnego interfejsu sprzętowego
• Pamięć zdalna (inne komputery lub chmura) (praktycznie nieograniczona) – szybkość waha się od bardzo wolnej do ekstremalnie wolnej

Nowoczesne maszyny mają tendencję do odczytywania bloków niższej pamięci do następnego poziomu hierarchii pamięci. Jeśli to wypiera używaną pamięć, system operacyjny próbuje przewidzieć, które dane będą dostępne najmniej (lub najpóźniej) i przenieść je w dół hierarchii pamięci. Algorytmy przewidywania są zwykle proste, aby zmniejszyć złożoność sprzętową, choć stają się nieco bardziej skomplikowane.

Mnożenie macierzoweEdit

Powszechnym przykładem jest mnożenie macierzowe:

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

Przełączając kolejność pętli dla j i k, przyspieszenie w dużych mnożeniach macierzowych 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ży” oznacza, w przybliżeniu, więcej niż 100 000 elementów w każdej macierzy, lub wystarczająco dużo adresowalnej pamięci, aby macierze nie zmieściły się w pamięci podręcznej L1 i L2.

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

Powodem tego przyspieszenia jest to, że w pierwszym przypadku odczyty A są w pamięci podręcznej (ponieważ indeks k jest przylegającym, ostatnim wymiarem), ale B nie jest, więc istnieje kara za pominięcie pamięci podręcznej na B. C jest nieistotny, ponieważ może zostać wyciągnięty z wewnętrznej pętli — zmienną pętli jest tam k.

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

W drugim przypadku, odczyty i zapisy C są zarówno w pamięci podręcznej, odczyty B są w pamięci podręcznej, a odczyt A może zostać wyciągnięty z wewnętrznej pętli.

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

Tak więc, drugi przykład nie ma kary za miss pamięci podręcznej w wewnętrznej pętli, podczas gdy pierwszy przykład ma karę za pamięć podręczną.

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

Temporalna lokalność może być również poprawiona w powyższym przykładzie za pomocą techniki zwanej blokowaniem. Większa macierz może zostać podzielona na równej wielkości pod-macierze, dzięki czemu mniejsze bloki mogą być wielokrotnie referencjonowane (mnożone), gdy znajdują się w pamięci.

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 = C + A * B;

Lokalność czasowa powyższego rozwiązania jest zapewniona, ponieważ blok może być użyty kilka razy przed przejściem dalej, dzięki czemu jest rzadziej przenoszony do i z pamięci. Lokalność przestrzenna jest poprawiona, ponieważ elementy z kolejnymi adresami pamięci mają tendencję do wspólnego podciągania się w górę hierarchii pamięci.

.