The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
807 views

In a C program, an array is declared as float A[2048]. Each array element is 4 Bytes in size, and the starting address of the array is 0x00000000. This program is run on a computer that has a direct mapped data cache of size 8 Kbytes, with block (line) size of 16 Bytes.

  1. Which elements of the array conflict with element A[0] in the data cache? Justify your answer briefly.
  2. If the program accesses the elements of this array one by one in reverse order i.e., starting with the last element and ending with the first element,  how many data cache misses would occur? Justify your answer briefly. Assume that the data cache is initially empty and that no other data or instruction accesses are to be considered.
asked in CO & Architecture by Veteran (59.4k points)
retagged by | 807 views
0

Suppose the question mentioned array having 4096 elements.Then the  2049th element would conflict $A[0]$ right?

1 Answer

+26 votes
Best answer

(a)
Data cache size $= 8KB.$

Block line size $= 16B.$

Since each array element occupies $4B,$ four consecutive array elements occupy
a block line (elements are aligned as starting address is $0$ )

Number of cache blocks $=\dfrac{8KB}{16B}= 512.$
Number of cache blocks needed for the array $=\dfrac{2048}{4}=512.$
So, all the array elements has its own cache block and there is no collision.

We can also explain this with respect to array address.
Starting address is $\text{0x00000000} = 0_b0000\ldots0 \text{(32 0's)}.$
Ending address is $\text{0x00001FFF} = 0_b0000\ldots 0111111111111 (4\times 2048
= 8192 \text{ locations)}$.

Here, the last $4\text{ bits}$ are used as OFFSET bits and the next $9$ bits are
used as SET bits. So, since the ending address is not extending beyond these
$9\text{ bits},$ all cache accesses are to diff sets.

(b)
If the last element is accessed first, its cache block is fetched. (which should
contain the previous $3$ elements of the array also since each cache block
hold $4$ elements of array and $2048$ is and exact multiple of $4$ ). Thus,
for every $4$ accesses, we will have a cache miss $\Rightarrow$ for $2048$
accesses we will have $512$ cache misses. (This would be same even if we
access array in forward order).

answered by Veteran (339k points)
edited by
+1
Ending address is 0x00001000 ?​
0
corrected :)
0

part (a) -  although we have 512 cache blocks to store the array (4 contiguous elements in 1 cache block )
but since it is DIRECT MAPPED cache so we will apply { K mod c = i  ; where K is main memory block no  , c is no. of cache blocks , i is cache block no.} then there will be so many locations which will be mapped to same cache block line and hence misses will occur as a result of which A[0] data will get conflict........plz correct if i am wrong...!!

0
For each block mapping block will be different try this.
+1
@Arjun sir, It might be a silly doubt but still please help... Isn't the whole array being stored in the 8KB cache itself? If yes then there shouldn't be any miss at all, isn't it?
0
same doubt
+1
The cache initially is empty so to fetch the array elements misses will occur.

for ( int i = 0; i < 2048; i++)

      printf("%d ",arr[ i ]);

So to loop over the whole array once compulsory misses will occur. But if again I loop over the array then there would be 0 misses since the whole array can get fit perfectly in the cache.
0

 

If the last element is accessed first, its cache block is fetched. (which should
contain the previous 33 elements of the array also since each cache block
hold 44 elements of array and 2048 is and exact multiple of 44 ). Thus,
for every 44 accesses, we will have a cache miss ⇒⇒ for 2048
accesses we will have 512 cache misses. (This would be same even if we
access array in forward order).

@Tuhin Dutta Iam not able to relate this with the above explanation given by arjun Sir. please help  



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

34,943 questions
41,958 answers
119,194 comments
41,472 users