0

I've given an assignment where I need to simulate an associative cache with Java. We're given a set of byte addresses, we need to find whether each address is a hit or a miss. The cache consists of 32 blocks and each block is 8 bytes

So the scheme is like the following:

  • Calculate the group address from the address (Group address is the address divided by the size of each block in the cache. For example group address for address 950 will be 950/8)
  • Use the entire group address as the tag
  • Scan the entire cache and see if the tag is already in the cache
  • If the tag is found, record a hit
  • If the tag is not found, record a miss, and store the tag in the first available block
  • If there are no spaces available, remove the LEAST recently used (LRU) block from the cache
  • Update the cache so the new tag is stored (if there was a miss) and remember this block is the MOST recently used.
  • Set valid bit to true, store tag in block, remember which address was used originally.

The problem I'm having is doing the Least Recently Used bit. The way we're asked to implement the LRU is by keeping the blocks in order from most recently used to least recently used, and when we need to replace a block we remove the old one from the end and add the new onto the beginning. Then when we get a hit we move the hit to the beginning of the cache.

Jacob Schoen
  • 14,034
  • 15
  • 82
  • 102
Kakalokia
  • 3,191
  • 3
  • 24
  • 42
  • What, specifically, is the question? – Oliver Charlesworth May 01 '12 at 00:30
  • How to implement a way that simulates the LRU scheme – Kakalokia May 01 '12 at 00:33
  • possible duplicate of [How would you implement an LRU cache in Java 6?](http://stackoverflow.com/questions/221525/how-would-you-implement-an-lru-cache-in-java-6) – Mike Samuel May 01 '12 at 00:35
  • You should go beyond what you have written here. How are you attempting to implement this? If you just can't get started, pick a smaller part of the problem and attempt to implement that. – Nathaniel Ford May 01 '12 at 00:36
  • I did start it and implemented the first bit but as I said I can't figure out to do the LRU bit. I've tried to do it but my hits are 53, when they should be 42 according to the specifications – Kakalokia May 01 '12 at 00:38
  • Well, I'm not very proficient with java, but the way i would solve this is by having a (double or single) linked list of cache-items. If you have a cache-hit you move the item you've found to the front of your list. On a miss you'll arrive at your least recently used item, which is the LAST filled item in the list. You can then just fill that item with the cache entry and move it to the front. For 32 blocks the linked list approach might even be fast than other solutions. – Nico Erfurth May 01 '12 at 00:39
  • 1
    @AliAlamiri If you found a solution, please post it as an answer instead of emptying the question. Even if you're answering your own question, it's sharing knowledge :) – Philipp Reichart May 02 '12 at 14:25
  • Could you have at least left the question here so the next guy who comes along, that has not solved the problem, could benefit? – Lawrence McAlpin May 02 '12 at 14:25

1 Answers1

0

You can achieve this with a linked-list. Of course, you will need to think of a way to perform quick lookup into the list...

Oliver Charlesworth
  • 267,707
  • 33
  • 569
  • 680