Consider the Code Snippet in Code Above. Suppose That It Is Executed on a System with A

Quiz 6

Assume the following 10-bit address sequence generated by the microprocessor: The cache uses 4 bytes per block. Assume a 2-way set associative cache design that uses the LRU algorithm (with a cache that can hold a total of 4 blocks). Assume that the cache is initially empty. Determine which memory accesses will result with a miss. TAG, SET, BYTE OFFSET fields in the table below are given for you to work on the answer. (4 wrong answers will cancel 1 right answer). (8pts)

int i;

int a[1024*1024];

int x=0;

for(i=0;i<1024;i++)

{

x+=a[i]+a[1024*i];

}

Consider the code snippet in code above. Suppose that it is executed on a system with a 2-way set

associative 16KB data cache with 32-byte blocks, 32-bit words, and an LRU replacement policy.

Assume that int is word-sized. Also assume that the address of a is 0x0, that i and x are in registers, and

that the cache is initially empty. How many data cache misses are there? How many hits are there?

The number of sets in the cache = (16 * 210) /(2*32) = 256

Since a word size is 4 bytes, int is word sized and the size of a cache block is 32 bytes, the number of

ints that would fit in a cache block is 8.

Therefore all the ints in a from a[0] to a[1023] map to the one of the cache lines of the sets 0 to 127,

while all the ints in a from a[1024] to a[1024*2 -1] map to the sets 128 to 255. Similarly the array

elements a[1024*2] to a[1024*3-1] map to cache lines of sets 0 to 127, a[1024*3] to a[1024*4 – 1] map

to cache lines 128 to 255 and so on.

In the loop, every time a[i] is accessed for i being a multiple of 8 would be a miss. There the number of

misses due to a[i] accesses inside the loop is 1024/8 = 128. The number of hits is 512.

Now all accesses to a[1024*i] within the loop are misses. This is because map alternately to sets 0 and

128 consecutively where there are cold misses the first time they are referenced.

The total number of misses = 1024 + 128 = 1062

The total number of hits = 512.

Consider the following cache:

·  block size: 64 Bytes

·  4-way set associative

·  256 blocks

·  Write Back with Dirty Bit

·  Valid Bit

·  Random Replacement strategy: A new block is always written to a random block position in the corresponding set.

·  32-bit address

·  32bit data

a) How many Tag comparisons are done for a cache access in a set? (4 points)

Solution: 4

b) Find the number of tag, index and offset bits. (4 points)

Solution: Offset: 6 Index: 6 Tag: 20

c) Find the total size of cache. Show your work. (4 points)

Solution: 64*4*(20+1+1+32)

d) How is the set number calculated for this cache configuration? (3 points)

Solution: Set number = block number modulo 64