edited by
6,064 views
34 votes
34 votes

In a C program, an array is declared as $\text{float} \ A[2048]$. Each array element is $4 \ \text{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  \ \text{Kbytes}$, with block (line) size of $16 \ \text{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.
edited by

1 Answer

Best answer
52 votes
52 votes
  1. Data cache size $= 8 \ KB.$

    Block line size $= 16 \ B.$

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

    Number of cache blocks $=\dfrac{8 \ KB}{16 \ B}= 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 01111111111111 (4\times 2048
    = 8192 \text{ locations), $0 - 8191$}$.

    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.
     
  2. 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).
edited by

Related questions

23 votes
23 votes
4 answers
1
Kathleen asked Sep 15, 2014
9,820 views
A device employing INTR line for device interrupt puts the CALL instruction on the data bus while:$\overline{INTA}$ is activeHOLD is activeREADY is inactiveNone of the ab...
2 votes
2 votes
1 answer
2
Kathleen asked Sep 15, 2014
1,455 views
In 8085 which of the following modifies the program counterOnly PCHL instructionOnly ADD instructionsOnly JMP and CALL instructionsAll instructions