[Solved] CS2100-Tutorial 11 Cache

D1. ]

A machine with a word size of 16 bits and address width of 32 bits has a directmapped cache with 16 blocks and a block size of 2 words, initially empty.

• Given a sequence of memory references as shown below, where each reference is given as a byte address in both decimal and hexadecimal forms, indicate whether the reference is a hit (H) or a miss (M).

• Given the above sequence of memory references, fill in the final contents of the cache. Use the notation M[i] to denote the word starting at memory address i, where i is in hexadecimal. If a block is replaced, cross out the content in the cache and write the new content over it.

Tutorial Questions

1. Here is a series of address references in decimal: 4, 16, 32, 20, 80, 68, 76, 224, 36, 44, 16, 172, 20, 24, 36, and 68 in a MIPS machine. Assuming a direct-mapped cache with 16 one-word blocks that is initially empty, label each address reference as a hit or miss and show the content of the cache.

You may write the data word starting at memory address X as M[X]. (For example, data word starting at memory address 12 is written as M[12]. This implies that the word includes the 4 bytes of data at addresses 12, 13, 14 and 15.) You may write the tag values as decimal numbers. If a block is replaced in the cache, cross out the corresponding content in the cache, and write the new content over it.

2. Use the series of references given in question 1 above: 4, 16, 32, 20, 80, 68, 76, 224, 36, 44, 16, 172, 20, 24, 36, and 68 in a MIPS machine. Assuming a two-way set-associative cache with two-word blocks and a total size of 16 words that is initially empty, label each address reference as a hit or miss and show the content of the cache. Assume LRU replacement policy.

You may write the data word starting at memory address X as M[X]. (For example, data word starting at memory address 12 is written as M[12]. This implies that the word includes the 4 bytes of data at addresses 12, 13, 14 and 15.) You may write the tag values as decimal numbers. If a block is replaced in the cache, cross out the corresponding content in the cache, and write the new content over it.

3. Although we use only data memory as example in the cache lecture, the principle covered is equally applicable to the instruction memory. This question takes a look at both the instruction cache and data cache.

The code below is from Tutorial 3 Question 1 (palindrome checking) with the following variable mappings:

low $s0, high $s1, matched $s3, base of string[] $s4, size $s5

Parts (a) to (d) assume that instruction i0 is stored at memory address 0x0.

• Instruction cache: Direct mapped with 2 blocks of 16 bytes each (i.e. each block can hold 4 consecutive instructions).

Starting with an empty cache, the fetching of instruction i1 will cause a cache miss. After the cache miss is resolved, we now have the following instructions in the instruction cache:

Fetching of i2 and i3 are all cache hits as they can be found in the cache.

Assuming the string being checked is a palindrome. Show the instruction cache block content at the end of the 1^st iteration (i.e. up to instruction i16).

• If the loop is executed for a total of 10 iterations, what is the total number of cache hits (i.e. after the 10^th j loop is fetched)?

• Suppose we change the instruction cache to:
• Direct mapped with 4 blocks of 8 bytes each (i.e. each block can hold 2 consecutive instructions).

Assuming the string being checked is a palindrome. Show the instruction cache block content at the end of the 1^st iteration (i.e. up to instruction i16).

• If the loop is executed for a total of 10 iterations, what is the total number of cache hits (i.e. after the 10^th j loop is fetched)?

Let us now turn to the study of data cache. We will assume the following scenario for parts (e) to (g):

• The string being checked is 64-character long. The first character is located at location 0x1000.
• The string is a palindrome (i.e. it will go through 32 iterations of the code).

• Given a direct mapped data cache with 2 cache blocks, each block is 8 bytes, what is the final content of the data cache at the end of the code execution (after the code failed the beq at i5)? Use s[X..Y] to indicate the data string[X] to string[Y].

• What is the hit rate of (e)? Give your answer in a fraction or a percentage correct to two decimal places.

• Suppose the string is now 72-character long, the first character is still located at location 0x1000 and the string is still a palindrome, what is the hit rate at the end of the execution?