GATE CSE
First time here? Checkout the FAQ!
x
+6 votes
429 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 (64.6k points)   | 429 views

1 Answer

+15 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 = 8KB/16B = 512. Number of cache blocks needed for the array = 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 0x00000000 = 0b0000..0 (32 0's). Ending address is 0x00001FFF = 0b0000..0111111111111 (4*2048 = 8192 location).

Here, the last 4 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 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 => for 2048 accesses we will have 512 cache misses. (This would be same even if we access array in forward order).

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

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...!!



Top Users Sep 2017
  1. Habibkhan

    7166 Points

  2. Warrior

    2640 Points

  3. Arjun

    2574 Points

  4. rishu_darkshadow

    2520 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,144 questions
33,726 answers
79,957 comments
31,116 users