Some example cache questions follow. I've used associative mapped
cache as the default for these, but you can certainly insert direct
mapped cache (with the additional info where needed) for any of these
questions and expect it.

Quick questions:

How many words of main memory are accessible with a word addressable
machine and 8 bits?

Given an associative mapped cache with 4 bit tags and 8 words per
block, how many words of main memory are accessible in a word
addressable machine.

Given an associative mapped cache with 4-bit tags, and 8 words per
 block, how many bits are needed to specify a memory location in main
 memory.

Given an associative mapped cache of 32 words, a main memory with 128
words. When using 8 words per block, how many blocks are available in
cache? How many blocks are in main memory?

Given a cache that produces 20 misses out of 200 accesses, what is the
hit ratio? What does hit ratio measure?

What is the effective access time of a cache with 200 accesses, with
20 misses when an access on a cache miss requires 10 ms and a cache
hit takes 1 ms? Take a look at this final number and compare it to a
non-cache method that requires 9 ms for every access.


The longer question:

Given an associative mapped cache with 4 slots, 4-bit tags, and 16 words
 per block, show the cache at each time step of the following program
 using a LRU, LFU and FIFO policy. Produce hit ratios for
 each and rank them. 

The program requests the following address in main memory in this order:
0000 0000
1000 0000
1000 0001
1000 0010
0000 0000
0110 0000
0110 0001
0000 0000
0101 0000

0001 1110

0000 0001
1000 0001
1000 0010
1000 0011
0000 0001
0110 0001
0110 0010
0000 0001
0101 0001