Homework Problems

Since we want you guys to focus on the third project, we're trying to keep the homework pretty simple for this final assignment. We want you guys to complete the following problems from P&H (THESE ARE BASED ON THE FOURTH EDITION, WE HAVE NOT CONFIRMED WHETHER THE PROBLEMS ARE THE SAME IN THE THIRD EDITION. Expect an update later with the problems copied onto this page for those of you who can not get access to the book) and put your answers in a plaintext file named README. Below are the problems we want you to complete:

• Exercise 5.4 (do the problems for both rows of the table)
• Exercise 5.8 parts 1 through 3
• Exercise 5.10 part 4
• Exercise 5.12 parts 1 through 5

Below are the questions copied verbatim from the book:

• 5.4 For a direct-mapped cache design with 32-bit address, the following bits of the address are used to access the cache.

  	Tag	Index	Offset
  a.	31-10	9-4	3-0
  b.	31-12	11-5	4-0

  • What is the cache line size (in words)? (cache line is another term for cache block)
  • How many entries does the cache have?
  • What is the ratio between the total bits required for such a cache implementation over the data storage bits?

  Starting from power on, the following byte-addressed cache references are recorded.

  Address

  0

  4

  16

  132

  232

  160

  1024

  30

  140

  3100

  180

  2180

  • How many blocks are replaced?
  • What is the hit ratio?
  • List the final state of the cache, with each valid entry represented as a record of <index, tag, data>.

• 5.8 (This exercise is supposed to be done assuming the addresses you're given are word addresses!) This exercise examines the impact of different cache designs, specifically comparing associative caches to the direct-mapped caches from section 5.2. For these exercises, refer to the table of address streams shown in Exercise 5.3 (I'm reincluding them below - Tom).

  a.	1,134,212,1,135,213,162,161,2,44,41,221
  b.	6,214,175,214,6,84,65,174,64,105,85,215

  • Using the references from Exercise 5.3, show the final cache contents for a three-way set-associative cache with two-word blocks and a total size of 24 words. Use LRU replacement. For each reference identify the index bits, the tag bits, the block offset bits, and if it is a hit or a miss.
  • Using the references from Exercise 5.3, show the final cache contents for a fully associative cache with one-word blocks and a total size of eight words. Use LRU replacement. For each reference identify the index bits, the tag bits, the block offset bits, and if it is a hit or a miss.
  • Using the references from Exercise 5.3, what is the miss rate for a fully associative cache with two-word blocks and a total size of eight words, using LRU replacement? What is the miss rate using MRU (most recently used) replacement? finally what is the best possible miss rate for this cache, given any replacement policy?

• 5.10.4

  	Virtual Address Size	Page Size	Page Table Entry Size
  a.	32 Bits	4 KB	4 bytes
  b.	64 Bits	16 KB	8 bytes

  Given the parameters in the table above, calculate the total page table size for a system running five applications that utilize half of the memory available

• 5.12.1-5 In this exercise, we will examine how replacement policies impact miss rate. Assume a two-way set-associative cache with four blocks. You may find it helpful to draw a table like those found on page 483 to solve the problems in this exercise, as demonstrated below on the address sequence "0,1,2,3,4".

  Address of Memory Block Accessed	Hit or Miss	Evicted Block	Set 0	Set 0	Set 1	Set 1
  0	Miss		Mem[0]
  1	Miss		Mem[0]		Mem[1]
  2	Miss		Mem[0]	Mem[2]	Mem[1]
  3	Miss		Mem[0]	Mem[2]	Mem[1]	Mem[3]
  4	Miss	0	Mem[4]	Mem[2]	Mem[1]	Mem[3]
  ...	Miss

  The following table shows address sequences

  a.	0,2,4,0,2,4,0,2,4
  b.	0,2,4,2,0,2,4,0,2

  • Assuming an LRU replacement policy, how many hits does this address sequence exhibit?
  • Assuming an MRU (Most Recently Used) replacement policy, how many hits does this address sequence exhibit?
  • Simulate a random replacement policy by flipping a coin. For example, "heads" means to evict the first block in a set and "tails" means to evict the second block in a set. How many hits does this address sequence exhibit?
  • Which address should be evicted at each replacement to maximize the number of hits? How many hits does this address sequence exhibit if you follow this "optimal" policy?
  • Describe why it is difficult to implement a cache replacement policy that is optimal for all address sequences.