There will be a quiz in this recitation.
It will be a closed book exam. You may not use a computer.
You may bring a calculator that can do add, subtract, multiply, divide, powers (y^x), and logs.
The quiz will consist of three questions and each problem is worth 3 points:

• 1 point for turning in the paper
• 2 points for showing some reasonable work
• 3 points for showing work and getting the correct answer

The quiz this week will cover memory hierarchy.
The material will be taken from Section 1 of Appendix B.
The first question will ask you explain one or more of the following terms:

• direct mapped cache
• n-way set associative cache
• cache hit rate
• cache miss rate
• cache miss penalty

The second will be like the example on page B.5.
The third will be about the fields of a memory address.
You will be given some information about the size of a memory address and about the cache and you will determine the format of the address with a picture similar to the upper left corner of Figure B.5.
After turning in the quiz, start on the problems below.

1. Assume we have the standard 5-stage pipeline with a CPI of 1 when there are no cache misses and that we have separate caches for instructions and data.
   Assume a miss penalty of 10 cycles and 30% of instructions are loads and stores. What is the CPI if:
   1. the instruction cache hit ratio is 100%, and the data cache hit ratio is 75%
   2. the instruction cache hit ratio is 90%, and the data cache hit ratio is 100%
   3. the instruction cache hit ratio is 90%, and the data cache hit ratio is 75%
2. Given the assumptions of the previous problem, assume the instruction cache hit ratio is 90% and the data cache hit ratio is 75%.
   Which is better, to improve the instruction cache hit ratio to 95% or to improve the data cache hit ratio to 85%?
3. A memory system uses a 50-bit address with a 32K cache having a block size of 128 bytes. Find the number of bits in the tag, index, and block offset if the cache is:
   1. direct mapped
   2. 2-way set associative
   3. 4-way set associative
   4. fully associative
   The remaining problems will be discussed in the next recitation.
4. Redo the above problem for a block size of 256 bytes.
5. Suppose you have a 32KB direct mapped cache with a 32-byte block.
   1. How many bits of an address are used for the block offset?
   2. How many bits of an address are used for the index?
   3. How many bits of an address are used for the tag?
6. Repeat the above problem for a 2-way set associative cache.
7. Repeat the above problem for a 4-way set associative cache.
8. Repeat the above problem for a fully associative cache.