Jak zoptymalizować swój kod pod pamięć podręczną procesora?

Z tego artykułu dowiesz się:

• Czym jest pamięć podręczna procesora.
• Jak optymalizować pod nią kod.
• Przeczytasz o zasadzie lokalności i jej rodzajach.
• Zobaczysz na przykładach, jak prawidłowo wykorzystać lokalność.

Spis treści

1. Pamięć podręczna procesora i jej warstwy
2. Rodzaje lokalności
3. Jak pisać kod przyjazny dla pamięci podręcznej
4. Jak lokalność wpływa na nasz kod
5. Podsumowując znaczenie pamięci podręcznej procesora

Współczesne procesory posiadają własne struktury pamięci. Najniższą są rejestry, które mogą przenosić dane w pojedynczych cyklach zegara. Ta najniższa struktura jest kosztowna w produkcji, przez co jest też najmniejsza, ale za to niezwykle szybka. Większość rdzeni komputera posiada jedynie kilkadziesiąt takich rejestrów.
Wziąwszy pod uwagę całą dostępną pamięć w komputerze, to na drugim końcu tego spektrum znajduje się pamięć RAM. Jest ona oczywiście wielokrotnie większa, tania w produkcji i wymaga setek cykli, aby przekazać do procesora te same dane.

Pamięć podręczna procesora i jej warstwy

Aby wypełnić lukę między szybką i drogą pamięcią a wolną i tanią istnieje tak zwana pamięć podręczna procesora, kolejno podzielona na trzy warstwy: L1, L2, L3.

• L1 to najszybsza dostępna pamięć podręczna. Jest znacznie szybsza niż inne warstwy pamięci podręcznej lub RAM. Jednakże jest również znacznie mniejsza w pojemności. W dzisiejszych czasach pamięć L1 waha się od 256 KB do nie więcej niż 1 MB, ale za to każdy rdzeń otrzymuje własną dedykowaną pamięć podręczną L1.
• Pojemność L2 jest kilka razy większa niż L1. Współczesne procesory posiadają pamięć L2 w rozmiarach około 6 MB do nawet 10 MB. L2 nie jest jednak tak szybka jak L1, znajduje się dalej od rdzeni i jest przez nie współdzielona.
• .L3 jest znacznie większa niż L1 i L2. W procesorach i9 Intela osiąga 16 MB, natomiast w niektórych procesorach AMD osiąga nawet 64 MB. Jest to jednak również najwolniejsza warstwa pamięci w procesorze.

Jeśli procesor nie może znaleźć danych w pamięci L1, to szuka ich w pamięci L2. Jeśli tam ich nie znajduje, to uderza do pamięci podręcznej L3, a jeśli tam również ich nie ma, to do pamięci głównej. Każde z chybionych przeszukań pamięci przedłuża czas operacji i przekłada się na zmniejszoną wydajność. Dodatkowo każdy kolejny poziom w hierarchii pamięci jest wolniejszy od poprzedniego, przez co także każde kolejne chybienie jest dodatkowo wolniejsze.

W dalszej części artykułu będziemy dość często odnosić się do takich wydarzeń używając właśnie pojęć „trafienie/chybienie”.

Odpowiednie buforowanie użytecznych danych pomaga zapobiec chybieniom. W tym celu należy wykorzystać pewną podstawową właściwość programów komputerowych.
Tą właściwością jest tak zwana zasada lokalności (ang. locality). Lokalność zakłada umieszczanie powiązanych danych w pamięci blisko siebie celem wydajniejszego buforowania. Programy z dobrą lokalnością będą skuteczniej uzyskiwać dostęp do tego samego zestawu danych z niższych poziomów hierarchii pamięci i dzięki temu będą działać szybciej. Wysoki poziom lokalności może oznaczać nawet dwudziestokrotnie szybsze obliczenia.

Rodzaje lokalności

Lokalność czasowa – (ang. temporal locality)

Czasowa lokalność oznacza natychmiastowe wykonywanie wszystkich operacji na załadowanych danych. Lokalność czasowa stanowi, że te same obiekty danych będą prawdopodobnie wielokrotnie wykorzystywane przez procesor podczas wykonywania określonego programu. Gdy obiekt danych zostanie zapisany w pamięci podręcznej po pierwszym chybieniu, możesz spodziewać się wielu kolejnych trafień na ten obiekt. Ponieważ pamięć podręczna jest szybsza niż pamięć na kolejnym wyższym poziomie, takim jak pamięć główna, te kolejne trafienia mogą być obsługiwane znacznie szybciej.

Lokalność przestrzenna – (ang. spatial locality)

Lokalność przestrzenna oznacza, że program uzyskuje dostęp do instrukcji, których adresy znajdują się blisko siebie. Jeśli obiekt danych zostanie raz przywołany, to istnieje duże prawdopodobieństwo, że sąsiadujące z nim obiekty danych również zostaną wkrótce przywołane. Bloki pamięci zazwyczaj zawierają wiele obiektów danych. Dzięki lokalności przestrzennej możesz oczekiwać, że koszt kopiowania bloku po chybieniu będzie zmniejszony przez kolejne odwołania do innych obiektów w obrębie tego bloku.

Jak pisać kod przyjazny dla pamięci podręcznej

Jednym z ważnych czynników do rozważenia podczas kodowania jest to, jak przyjazny będzie Twój kod dla pamięci podręcznej procesora.
Jeśli Twój kod często uzyskuje dostęp do tych samych danych, pomocna będzie optymalizacja kodu dla pamięci podręcznej poprzez strukturyzację danych w taki sposób, aby były one łatwe do przechowywania i pobierania przez tę pamięć. Programy z dobrą lokalnością działają szybciej, ponieważ mają niższy współczynnik chybień pamięci podręcznej w porównaniu do tych ze słabą lokalnością.

Jest kilka rzeczy, które możesz zrobić, aby Twój kod był bardziej przyjazny:

• Używanie ciągłych tablic danych zamiast połączonych list. Tablice są łatwiejsze do przechowywania i pobierania przez pamięć podręczną, ponieważ dane są przechowywane w jednym miejscu.
• Zapewnienie dostępu do danych w kolejności sekwencyjnej, kiedy tylko jest to możliwe. W ten sposób pamięć podręczna procesora może wykorzystać swoją lokalność przestrzenną poprzez przechowywanie danych, które są blisko siebie w pamięci.
• Minimalizacja liczby chybień w pamięci podręcznej. Do chybienia w pamięci dochodzi, gdy nie ma w niej potrzebnych danych, co powoduje opóźnienie podczas pobierania danych z pamięci głównej. Aby zminimalizować liczbę pominięć, musimy optymalizować kod tak, aby rzadziej uzyskiwał dostęp do mało używanych danych.

Jak lokalność wpływa na nasz kod

Aby zobaczyć przykład powyższych praktyk, rzuć okiem na prosty kawałek kodu w C opisujący dwuwymiarową tablicę. Rozważ funkcję sum_array(), która sumuje elementy tablicy dwuwymiarowej w kolejności wierszy:

Prosty kawałek kodu w C opisujący dwuwymiarową tablicę funkcją sum_arrayrows()

Wzór chybień i trafień dla dwuwymiarowej tablicy z funkcją sum_arrayrows() sumującej elementy tablicy dwuwymiarowej w kolejności wierszy

Blok zawierający od w[0] do w[3] jest ładowany do pamięci podręcznej i odwołanie do w[0] jest chybione, ale następne trzy odwołania są trafione. Odwołanie do w[4] powoduje kolejne chybienie, ponieważ do pamięci podręcznej ładowany jest nowy blok, następne trzy odwołania to trafienia. Ten schemat będzie się powtarzał z każdym blokiem. Oznacza to, że zawsze trzy z czterech odwołań będą trafione, co daje Ci najwydajniejszy wynik, na jaki możesz liczyć. Współczynnik trafień wynosi 3/4*100 = 75%.

Teraz zobacz, jak ten sam przykład wygląda w przypadku funkcji sum_array() sumującej elementy tablicy dwuwymiarowej ale w kolejności kolumn.

Prosty kawałek kodu w C opisujący dwuwymiarową tablicę z funkcją sum_array()

W tym wypadku wzór chybień i trafień będzie wyglądał następująco:

Wzór chybień i trafień dla dwuwymiarowej tablicy z funkcją  sum_array() sumującej elementy tablicy dwuwymiarowej w  kolejności kolumn.

C przechowuje tablice w kolejności wierszy, ale w tym przypadku dostęp do tablicy odbywa się w kolejności kolumn, więc lokalność się całkowicie rozlatuje. Odwołania będą wykonywane w kolejności: a[0][0], a[1][0], a[2][0] i tak dalej. Ponieważ rozmiar pamięci podręcznej jest mniejszy, każde odwołanie skończy się chybieniem z powodu słabej lokalności programu. Współczynnik trafień będzie wynosił 0. Słaby współczynnik trafień ostatecznie zmniejszy wydajność programu i doprowadzi do znacznie większego czasu oczekiwania.

Podsumowanie znaczenia pamięci podręcznej procesora

Mówiąc o rzeczywistych aplikacjach użytkowych i obszarach programowania, trzeba pamiętać, że zoptymalizowana wydajność pamięci podręcznej zapewnia znaczne przyspieszenie, nawet w przypadku skomplikowanych programów.
Dlatego pisanie kodu zoptymalizowanego pod pamięć podręczną procesora powinno być standardową praktyką w przypadku języków i sytuacji, które na to pozwalają. Choć podane przykłady są dość proste, to technikę lokalności można skalować i wykorzystać w znacznie bardziej skomplikowanych programach.