retagged by
2,558 views
5 votes
5 votes

Consider an array has 100 elements and each element occupies 4 words .A 32 bit word cache is used and divided into a block of 8 words .What is the hit rate of this 
for(i=0; i<10; i++)
   for(j=0; j<10; j++);
         A[i][j] = A[i][j]+10;

Column major is used here.

How to improve Hit rate ?

retagged by

1 Answer

Best answer
6 votes
6 votes

Given that column major order is used:

  • Thus consecutive memory locations (words) store elements like this: A[0][0], a[1][0], A[2][0].......etc.

One element is of 4 words and one cache block is of 8 words size.

  • So whenever a cache miss occur, consecutive 8 words ,( ie 2 elements) are fetched and placed in cache.

In given code

for(i=0; i<10; i++)
   for(j=0; j<10; j++);
         A[i][j] = A[i][j]+10;

When i=0,j=0

  • In A[i][j] = A[i][j]+10; 
  • A[0][0] is miss -> A[0][0] is searched in memory and fetched consecutive 8 words,
  • ie, A[0][0] and A[1][0] is in memory.

Now while writing A[i][j] = A[i][j]+10; 

  • cache hit occurs because A[0][0] is already in cache

But next i=0 and j=1 and we need A[0][1].

  • But we have A[0][0] and A[1][0] in cache.
  • Again cache miss occur.

Thus while reading every new element cache miss occur. While writing back cache hit occur.

Each loop contain one read (always miss) and one write (always hit).

  • Total 10*10 =100 times loop works.
  • Thus 2*100=200 memory references and 100 reads and 100 writes

cache hit ratio = no of hits / total no of accesses. = no of writes/ no of accesses = 100/2*100 = 1/2

Cache hit ratio can be improved if ROW MAJOR order is used

Correct me if I am wrong!

selected by

Related questions

8 votes
8 votes
4 answers
1
4 votes
4 votes
3 answers
2
Parshu gate asked Nov 10, 2017
1,233 views
Consider an array A[200] and each element occupies 8-words. A 64-word cache is used and divided into 16-word blocks. What is the hit ratio for the following code segment:...
0 votes
0 votes
1 answer
3
nirupama thakur asked Mar 17, 2018
1,977 views
In some problems we multiply only with the second part of the equation with (1-H1) component and leave the first part. Whereas in other cases we multiply with cache hit a...