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.

(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).

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