Submitting your Solutions

Problems

1. (P&H 3rd edition Exercise 7.9)

Here is a series of address references given as word addresses: 2, 3, 11, 16, 21, 11, 3, 22, 27, 6, and 11. Assuming a direct-mapped cache with 16 one-word blocks that is initially empty, label each reference in the list as a hit or a miss and show the final contents of the cache.

2.

Repeat Problem 1 (Exercise 7.9) for a fully associative cache with 16 one-word blocks.

3.

Repeat Problem 1 (Exercise 7.9) for a 4-way set associative cache.

4. (P&H 3rd edition Exercise 7.10)

Using the series of references given in Problem 1 (Exercise 7.9), show the hits and misses and the final cache contents for a direct-mapped cache with four-word blocks and a total size of 16 words.

5. (P&H 3rd edition Exercise 7.17)

Find the AMAT (Average Memory Access Time = Time for a hit + Miss rate * Miss penalty) for a processor with a 2 ns clock, a miss penalty of 20 clock cycles, a miss rate of 0.05 misses per instruction, and a cache access time (including hit detection) of 1 clock cycle. Assume that the read and write miss penalties are the same and ignore other write stalls. Also, assume that we are dealing with a single-cycle processor and not a pipelined processor. Please show your work.

6. (P&H 3rd edition Exercise 7.29)

Suppose a computer's address size is k bits (using byte addressing), the cache size is S bytes, the block size is B bytes, and the cache is A-way set-associative. Assume that B is a power of two, so B = 2^b. Figure out what the following quantities are in terms of S, B, A, b, and k: the number of sets in the cache, the number of index bits in the address, and the number of bits needed to implement the cache (see Exercise 7.12 in P&H 3rd edition). Please explain your reasoning.

7. (P&H 3rd edition Exercise 7.35)

The following C program is run (with no optimizations) on a processor with a cache that has eight-word (32-byte) blocks and holds 256 bytes of data:

int i,j,c,stride,array[512]
...
for (i=0; i<10000; i++) 
   for (j=0; j<512; j=j+stride)  
	c = array[j] + 17;
}

If we consider only the cache activity generated by references to the array and we assume that integers are words, what is the expected miss rate (ignoring compulsory misses) when the cache is direct mapped and stride = 256? How about if stride = 255? Would either of these change if the cache were two-way set associative? Please explain your reasoning for each part.

8. (P&H 3rd edition Exercise 7.39)

Consider a virtual memory system with the following properties: