Önbellek Bellek Optimizasyonu Dizisi Transpoze: 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]; 
     } 
    } 
} 

src dizisi adres 0'da başlar ve dst dizisi 0x10 adresinde başlar.

L1 veri önbellek, doğrudan harita, yazma-ayırma, 8 bayt blok boyutu.

Önbellek toplam boyutu 16 veri bayttır.

src ve dst dizisinin her girdisinde isabet veya hanımefendi nedir?

cevabı: önbellek toplam boyut 32 veri bayt

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 

varsa, cevap:

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 

ben hem sonuçların emin değilim. Konsepti ve önbelleğe alma konseptini gerçekten anlamıyorum.

Answer 1

Yani, ilk örnekte, her biri 16 bayt olmak üzere 8 baytlık iki önbellek hattınız var. 4 baytlık bir int veri boyutu alacağım.

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 

Sonra her bellek adresi program tarafından ziyaret edilmektedir erişimin sırasını bilmek gerekir: C Dizilerin yerleştirme ve bu sağladık uzaklıklar Verilen önbelleğe alınabilir bellek çizgilerdir. Derleyici tarafından yeniden sıralamaya neden olabilecek hiçbir optimizasyon kabul ediyorum.

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 

Bu, sanırım ikinci cevabınıza uyuyor. Daha sonra, tüm diğer faktörler varsayılarak 32 bayt (4 hat), bir önbellek boyutu ile sabittir:

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 

Bunlar özdeştir. Tek fark, tekrar transjen olursanız olurdu. 1. durumda tam olarak aynı davranışı elde edersiniz (iyi, tüm yanlış şeylerle dolu önbellekle başlayacaksınız, bu yüzden boş olabilir). Daha büyük önbellek durumunda, ikinci arama için ihtiyacınız olan her şey önbelleğe alınmış durumdadır, bu nedenle önbellek kayıpları olmayacaktır.

Yanıtlarım ile sizinki arasındaki fark büyük olasılıkla, döngü sayıcınız için derleyicinin davranışı hakkındaki varsayımlarımıza bağlıdır (i ve j). Her ikisi de yazmaçlarda saklandıklarını (ve böylece veri önbelleğini etkilemeyeceğini) varsayardım. Beklenen sonuçları almak için bir yerde bellekte olduğunu (ve bu nedenle önbellekle etkileşimde bulunduklarını) varsaymanız gerekebilir.