Pamięć i pamięć podręczna
Jak działa hierarchia pamięci
- Celem hierarchii pamięci jest umożliwienie szybkiego dostępu do dużych ilości danych.
- Wykorzystuje ona zasady przestrzennej lokalności odwołań (po adresie x prawdopodobnie użyjemy adresów bliskich x)
oraz czasowej lokalności odwołań (dane niedawno użyte prawdopodobnie zostaną użyte ponownie).
Dane często używane przenosi się do szybszych podsystemów pamięci, a rzadko używane do wolniejszych.
- Procesor najczęściej korzysta z pamięci podręcznej L1. Jeżeli nie znajdzie tam szukanych danych (chybienie, cache miss),
przekazuje żądanie do L2, potem do L3, następnie do pamięci głównej, a na końcu do dysku (pamięć wirtualna).
Za obsługę pamięci wirtualnej odpowiada system operacyjny.
- Znalezienie danych to trafienie (cache hit). Średni czas dostępu = czas trafienia + współczynnik chybień x kara za chybienie.
Przy trafieniach w L1 równych 99% i karze 400 cykli średnio mamy 4 + 0,01 x 400 = 8 cykli, czyli dwa razy więcej niż sam L1.
// Lokalność przestrzenna: kolejne elementy leżą obok siebie - szybko
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
suma += a[i][j];
// Brak lokalności: skoki co n elementów - wiele chybień w pamięci podręcznej
for (j = 0; j < n; j++)
for (i = 0; i < n; i++)
suma += a[i][j];
Porównanie czasów obu pętli: patrz przykład cache.cpp.
Tomasz Kapela, Kraków 2011-2020