# Direct cache vs. associative cache

Trying to solve this problem where direct cache would outperform associative:

Propose you have a cache with a line size of L 32-bit words, S number of sets, W ways, and addresses are made up of A bits. Assume that the cache is word addressed, i.e., the low two bits of the address are always 0.

Come up with a sequence of addresses for a MIPS processor for which a direct-mapped cache of size 16 words, line size 4 words, outperforms a fully-associative cache with the same line size, using LRU replacement.

What I've gathered:

• Direct Mapped Cache means that a block of memory is mapped directly to line of cache
• MIPS uses Fetch, Decode, Execute, Encode, Memory (this might be irrelevant here)
• LRU replacement - Oldest Used is replaced
• Word are least significant bits which represent the address from main memory

Cache structure:
Tag   |   Line   |   Word

Word represents least significant bits
Tag represents the unique identifier for that
Size 16 words would be 2^4 bytes

number of lines would be cache capacity / line size =     ? / 2^4


I'm not sure how to draft this cache. If we have 16 words, 4 per line it would that would mean 4 total rows. I don't expect a full answer but an indication on how to draft the direct mapped cache and come up with a sequence would be greatly appreciated.

UPDATE:

I attached a picture with a cache that has 8 memory addresses mapped to 4 lines. . With this, a sequence of

  1234567824136857
direct mapped:  MMMMMMMMHHMMHHMM (4 Hits)
f. associative: MMMMMMMMMMMMMMMM (0 Hits)


However, I can't figure out how many lines there should be (16 words, line size 4 words). How many memory addresses will be mapped to how many lines in the cache? My image has 8 to 4. Do I need 16 addresses mapped to 4 lines in the cache?