The Gateway to Computer Science Excellence
+5 votes
783 views

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 ?

in CO and Architecture by Boss (45.4k points)
retagged by | 783 views
+3

when i=0,j=0,  two elements will come into 0th block of cache. A[0][0] and A[1][0].(remember column major).

two access is there - 1. read A[0][0] which is a miss. And 2. Write A[0][0]- Hit.

Now when i=0, j=1,   read A[0][1] - miss  and write - hit.

Similarly for all elements - read will be miss and write will be hit.

so hit ratio = 50%.

1 Answer

+6 votes
Best answer

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!

by Boss (33k points)
selected by
0
@shiva is here no way to improve hit rate and still be in column major order .
0
@shekhar sir,

row major order is cache friendly code

we can use that to improve hit rate...
0

Sir,

I think in this code the column major order do not exploit locality of reference. So hit ratio cannot be improved by keeping column order I think.

Using better style of programming we can exploit locality of reference

  • Same item may be accessed more than once in a loop.
  • Related data are stored in consecutive locations in storage ARRAY, Store 2D array in row major order and access elements in row wise
  • Once a loop or subroutine is entered, there may be repeated references to a small set of instructions or data (cluster). 
0
@Shekhar ...  what is size of cache here ??
0
@vijay this is the all information i have which is mentioned in question ."32 bit word cache".
0
@kapil i read one of the articles in which they said if we interchange [i] with [j] it can be done ...i am confused with that part .
0

32 bit word cache - means word size is 32 bit = 4 byte rt ?

but with this info can we calculate how many cache blocks are there.

Ans for your 2nd question regarding improvement of hit ratio can be achieved if we increase cache size to more than 10 cache blocks. 

+1

@Vijay: Sir, I think cache size will not matter in this question I think..!! ,
because once in given code, an element is (eg A[0][0]) is used, it is never used in the code again!!

So cache size does not matter

NB:

  1.  If same element is used again and again, then in big sized cache, the element will not be replaced by other misses and total cache hit will be increased.
  2.  If same element is used again and again, then in small sized cache, the element will be replaced soon by other misses and total cache hit will be decreased. 3
  3.  If an element is not used again and again, total cache size has no effect
+1

@shekhar: Sir,

  • In given code you are reading elements in row wise A[0][0], A[0][1].....
  • Interchanging i and j means you are reading the elements in column wise ,not row wise.
  • ie A[0][0], A[1][0], A[2][0]...
  • In that case Cache hit will be increased to 75%
+2
@Shekhar ... yes .. if you interchange i and j in the above code then hit ratio would be 75% ...
+3

@shekhar sir,

just do this interchange...

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

Now, see the hit rate ,,, it will be 75%...

+1
@ kapil @vijay @shiva   thanks all...
0

@Shiva sir..see. if cache size is more than 10 blocks.

For i=0 , j=0 , a[0][0] and a[1][0]  come into first cache memory block.

 for i=0, j=1,   a[0][1] and a[1][1] come into 2nd cache memory block.

.

.

.

 for i=1, j=0 , a[1][0] - now it would not be miss any more, because this element has already come into 1st cache memory block, when i= 0, and j=0. 

so it may increase hit ratio ..

right ??

0

@vijay sir: I think you are talking about cache block size, not cache size. cache block size is alreday given as 8 words

The elements will be fetched in size of cache block size only.

Of course cache hit will be increased if cache block size is increased,

but total cache size is less relevant

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,367 answers
198,497 comments
105,266 users