No. of Misses

Question

Assume that we have a two dimensional array of 60 × 60. Each element is of 4 bytes and array is stored in row major order. RAM is 2 MB and cache is 8 KB with each block of 16 bytes.

In case of direct mapped cache, the number of cache misses are _______ (Assume that cache is empty initially).

Ans. 1288

Answer 1

for L1:-

Array size=60 x 60=3600 bytes

Block size=16 bytes

Element size=4 bytes

Number of elements in one block=4 bytes

When first element A[0][0]  is referred, we bring block number 0 of main memory to line number 0.We not only bring  A[0][0]  element but also 2² - 1 elements(as we bring the whole block).So, when first element is referred, gives a miss. Next 2²-1 elements gives hit.

Miss rate= 1/4

No. of misses= 1/4 x number of references.

No. of misses= 1/4  x 60 x 60 =900.

for L2:-

No. of Blocks in cache  = 512.

The elements are already present in the cache, so no miss operation will takes place for this 512 blocks.

Number of misses=900-512=388

Total Number of misses in cache=900+388=1288

Comments

Please Elaborate the L2 miss part again ?

---

Because there are only 512 blocks in cache memory, in order to fill in 900 blocks we initially put the First 512 data blocks in cache. Later we replace the top 388 blocks.

SO now the situation of cache blocks is as follows:

Top 388 blocks of cache contain the last 388 blocks of data (i.e.. from 513 to 900) and the remaining cache blocks (i.e.. from 389 to 512) are filled with 389 to 512 data blocks.

so the missing data blocks are from 0 to 387.

hence add 388 to 900.