緩存的編碼和算法的命中率

-1

我知道命中率是在緩存中找到的數據的百分比。但我不知道如何找到算法的命中。我在想，對於代碼1，我將有11塊，每塊有4個元素，對於代碼2，我將有4塊，每塊有11個元素，每次我看到4個元素錯過。不知道這是否有意義。任何的建議是歡迎緩存的編碼和算法的命中率

由4列假設有11個行的2維陣列A，存儲在存儲器中這樣[0][0], [0][1], [0][2], [0][3], [1][0], [1][1], …[10][2], [10][3]

還假設的10個存儲塊全關聯單級高速緩存，其中每個存儲器塊保持4個字節，以及FIFO替換策略。

每行準確地放入一個緩存塊中，而不幸的是整個數組無法放入緩存中。緩存是一個行過小...

現在給出2個以下代碼， 1-如何計算的命中率 2 - 考慮到緩存訪問時間爲5ns和內存訪問時間爲70ns，並且假定重疊訪問內存和緩存，我如何計算每個代碼的EAT？

代碼1：

for (int row = 0; row < 11; row ++) 
{ 
    for (int column = 0; column < 4; column ++) 
    { 
     myByte = A [ row, column ]; 
    } 
}

代碼2：

for (int column = 0; column < 4; column ++) 
    { 
    for (int row = 0; row < 11; row ++) 
    { 
     myByte = A [ row, column ]; 
    } 
}

任何幫助理解。謝謝

來源

2013-03-26 dddx

我聞到功課。高速緩存命中率取決於實現。嘗試'valgrind' – phoeagon 2013-03-26 08:41:26

那麼我們不計算算法的命中率。我們用這種方式編寫算法，即利用緩存的概念即獲得最大命中率。你的問題實際上屬於計算機組織和架構。

無論如何，你的2D數組以主要的順序存儲在內存中。因此，對於代碼1，帶有第一個內部for循環塊將從包含四個元素的內存中獲取，因爲在緩存中找不到任何內容（因爲它是未命中）（即內存訪問時間爲70ns）。現在，隨後的三個元素[ 0] [1]，[0] [2]，[0] [3]將從cahce（即3 * 5 = 15ns）即訪問前四個元素的總時間= 70 + 3 * 5 = 85ns獲取。

上述過程將重複您的數組w.r.t 10個緩存塊的十行。但對於使用FIFO概念的最後一個塊將會進行塊交換，但時間將保持相同。所以總時間= 85 * 11 = 935ns

對於代碼2，

用於內部for循環每次迭代的塊將被獲取。所以，每次你訪問內存，在這種情況下，你都沒有利用緩存的概念，即它是一段糟糕的代碼。如果您的數組按主要順序存儲在內存中，則代碼2將工作得最好。

來源

2013-03-26 06:55:40

緩存的編碼和算法的命中率

回答

相關問題