Optymalizacja pamięci podręcznej Transpozycja macierzy: C

Question

typedef int array[2][2]; 

void transpose(array dst, array src) { 
    int i, j; 
    for (j = 0; j < 2; j++) { 
     for (i = 0; i < 2; i++) { 
      dst[i][j] = src[j][i]; 
     } 
    } 
} 

tablica src zaczyna się od adresu 0, a tablica dst zaczyna się od adresu 0x10.

Pamięć podręczna danych L1, bezpośrednia mapa, przypisanie przydziału do zapisu, rozmiar bloku 8 bajtów.

Łączny rozmiar pamięci podręcznej wynosi 16 bajtów danych.

Co jest hitem na każdym wpisie tablicy src i dst?

Odpowiedź brzmi:

src: 
[0][0] -> miss, 
[0][1] -> miss, 
[1][0] -> miss, 
[1][1] -> hit 

dst: 
[0][0] -> miss, 
[0][1] -> miss, 
[1][0] -> miss, 
[1][1] -> miss 

Jeśli bufor powierzchnia wynosi 32 bajtów danych, odpowiedź brzmi:

src: 
[0][0] -> miss, 
[0][1] -> hit, 
[1][0] -> miss, 
[1][1] -> hit 

dst: 
[0][0] -> miss, 
[0][1] -> hit, 
[1][0] -> miss, 
[1][1] -> hit 

jestem pewien obu wyników. Naprawdę nie rozumiem pojęcia z tablicami i buforowaniem.

Answer 1

Tak więc, w pierwszej kolejności masz dwie linie pamięci podręcznej po 8 bajtów każda, łącznie 16 bajtów. Zakładam rozmiar danych int 4 bajty. Biorąc pod uwagę rozmieszczenie tablic w C i przesunięcia już przewidziane są to linie pamięci, które mogą być buforowane:

Cacheable lines: 
#A: &src[0][0] = 0x00, &src[0][1] = 0x04 
#B: &src[1][0] = 0x08, &src[1][1] = 0x0C 
#C: &dst[0][0] = 0x10, &dst[0][1] = 0x14 
#D: &dst[1][0] = 0x18, &dst[1][1] = 0x1C 

Następnie musimy znać kolejność dostępu, każdy adres pamięci jest odwiedzana przez program. Zakładam, że nie ma optymalizacji, które mogłyby spowodować ponowne zamawianie przez kompilator.

Access order and cache behavior (assuming initially empty): 
#1: load src[0][0] --> Miss line A = cache slot 1 
#2: save dst[0][0] --> Miss line C = cache slot 2 
#3: load src[0][1] --> Hit line A = cache slot 1 
#4: save dst[0][1] --> Hit line C = cache slot 2 
#5: load src[1][0] --> Miss line B = cache slot 1 (LRU, replaces line A) 
#6: save dst[1][0] --> Miss line D = cache slot 2 (LRU, replaces line C) 
#7: load src[1][1] --> Hit line B = cache slot 1 
#8: save dst[1][1] --> Hit line D = cache slot 2 

Co, jak sądzę, pasuje do drugiej odpowiedzi. Następnie o wielkości 32 bajtów pamięci podręcznej (4 linie), przyjmując wszystkie inne czynniki są stałe:

Access order and cache behavior (assuming initially empty): 
#1: load src[0][0] --> Miss line A = cache slot 1 
#2: save dst[0][0] --> Miss line C = cache slot 2 
#3: load src[0][1] --> Hit line A = cache slot 1 
#4: save dst[0][1] --> Hit line C = cache slot 2 
#5: load src[1][0] --> Miss line B = cache slot 3 
#6: save dst[1][0] --> Miss line D = cache slot 4 
#7: load src[1][1] --> Hit line B = cache slot 3 
#8: save dst[1][1] --> Hit line D = cache slot 4 

Są identyczne. Jedyna różnica polegałaby na ponownym transponowaniu. W przypadku 1 otrzymasz dokładnie to samo zachowanie (cóż, zaczniesz od pamięci podręcznej pełnej wszystkich złych rzeczy, więc równie dobrze może być pusta). Jednak w przypadku większej pamięci podręcznej wszystko, czego potrzebujesz do drugiego połączenia, jest już buforowane, więc nie będzie żadnych błędów w pamięci podręcznej.

Różnica między moimi odpowiedziami a twoją jest najprawdopodobniej wynikająca z naszych założeń dotyczących zachowania kompilatora dla rejestrów zliczających pętle (i i j). Zakładam, że oba są przechowywane w rejestrach (i tak nie wpłynęłoby to na pamięć podręczną danych). Być może będziesz musiał założyć, że są gdzieś w pamięci (i dlatego wchodzą w interakcję z pamięcią podręczną), aby uzyskać oczekiwane rezultaty.