The Logisim Evolution

1. Use the Logisim Evolution. Other versions may not work correctly.
2. Do not rename the files you receive. If you do so you will automatically fail the tester when you submit.
3. Put your solution for each problem into implementation subcircuit
4. Do not rename the implementation subcircuit anything else. If you do so you will automatically fail the tester when you submit.
5. Do not change the appearance of the implementation subcircuit from what it is set as. Doing so will cause you to automatically fail the tester when you submit.
   1. That is this field right here
6. Do not move the pins inside of the implementation subcircuit as that affects the appearance of the circuit on the outside as you saw in discussion. Doing so will cause you to automatically fail the tester when you submit.
   1. If you want to “move the pins” instead connect tunnels to the pins and move the tunnels around.
7. Do not name any of the subcirucits in your solution main. Doing so will cause you to automatically fail the tester when you submit.
8. You can create as many other subcircuits as you want in your solution. Just make sure your solution ends up in the implementation subcircuit

Component Restrictions

For all problems in this homework, you may only use

• All of the components under Wiring
• All of the components under Gates EXCEPT for Controlled Buffer, Controlled Inverter, PLA
• All of the components under Plexers
• All of the components under Arithmetic
• All of the components under Memory EXCEPT for RAM, ROM, and Random Generator

Unless a problem specifies otherwise.

Problem Specification

Implement a Cache that meets the specifications below.

Cache Specifications

Inputs

All of the inputs will only be valid during the SINGLE clock cycle that your Cache says it is Ready. This means that you will have to save your inputs if you need them beyond that first clock cycle.

The only exception to this is LineFromMem. It will be valid as long as you say you want to read from memory. If you aren’t reading from memory LineFromMem will be EEE… and Red (an Error). Don’t worry about this it is normal behavior. As soon as your request to read from memory it will be the value at MemAddress.

Outputs

Why is MemAddress 8 bits instead of 10?

Our Memory is going to be Block Addressable instead of Byte Addressable. This means that each block has an address instead of each byte. This enables you to read a block from/write a block to memory in a single clock cycle which should help simplify your design a little. It should be pretty easy to figure out which bits to drop to form MemAddress. Hint: it is bits that help you pick out the byte within a block.

When are outputs checked?

• DidContain: At the end of every operation once your circuit becomes Ready.
• ByteRead: At the end of a read operation once your circuit becomes Ready.
• MemRead: Whenever you read from memory it increments the MissCounter.

Timing Restrictions

Your circuit must be able to complete a Read/Write request within 10 clock cycles. If you take longer than 10 clock cycles the tester will automatically advance to the next case. This will cause your Cache to start to “desync” from the tester and so will get everything wrong if you are taking too long. You can certainly finish in less than 10 clock cycles, I only took 7 but I’ve seen students get as low as 2.

Testing

1. Open the grading circuit
2. Click on the Cache folder and select reload library
   1. Double-check that your updates are visible inside of the grader. If your changes don’t show up, close your solution circuit and try reloading again. If the changes still fail to show up, close the grader and reopen it and then reload the library.
3. Open the subcircuit named CheckerCirc and
   1. Right-click the ROM inside of it
   2. Select Load Image
   3. Select one of the provided files that ends in _sol.txt.
      1. Eample: seq_read1_seq_mem_sol.txt
4. Open the subcircuit named InputGeneratorCirc and
   1. Right-click the ROM inside of it
   2. Select Load Image
   3. Select the corresponding input file that matches with the solution file. This will be the file that shares its name with the first part of the solution file.
      1. Example: seq_read1.txt
5. Go back to the main subcircuit
   1. Right-click the RAM
   2. Select Load Image
   3. Select the corresponding memory file that matches with the solution file. This will be the file that shares its name with the second part of the solution file.
      1. Example: seq_mem.txt

Anytime your reset a test case you must RELOAD the RAM! The RAM is the only one that has to be reloaded. The ROM’s will maintain the last value you put in them.

At the bottom of the the main circuit you will find probes that show your circuit’s inputs, outputs, answers, how many reads you got correct, how many times you said you hit, and how many misses(memory reads) you had. This is a good place to look when you are debugging to get a high level overview of what your cache is doing.

If you open the solution files in a text editor you will find what the correct values for all of the stats should be for that test case.

Testing Order

I recommend running the test cases in the following

1. seq_read1_seq_mem_sol.txt
2. seq_write1_seq_mem_sol.txt
3. set1_targeted_read_seq_mem_sol.txt
4. set0_targeted_write_seq_mem_sol.txt
5. random0_seq_mem_sol.txt
6. final_test_rand_mem_mem_sol.txt.

User Created Tests

If you want to make your own test, you can use cache_test_maker.py to create your own tests. It should be fairly easy to follow the documentation inside if you feel like using it.

Scoring

Your score is calculated as num_correct_read_values – abs(num_correct_read_value – number_of_reads_you_got_correct) + num_correct_hits – abs(num_correct_hits – your_number_of_hits) + num_correct_misses – abs(num_correct_misses – your_number_of_misses). Essentially you lose points for every value you are off from the right answers.

Debugging

This might be useful:

https://github.com/NoahRoseLedesma/CacheHitDetector .

What to Submit

A file named Cache.circ with your solution in the implementation subcircuit

Hints

• Before you start doing anything in Logisim make sure you really understand how the Cache should work on both a read and a write. Write out Psuedo Code detailing what should happen. This Psuedo Code should be so detailed that you could write a program that emulates a cache. You need that thorough of a plan to correctly implement your cache.
• Make subcircuits for Sets and Ways. Then for each Set or Way you need you can lay down an instance of that subcircuit.
• Speaking of Subcircuits, use lots of them to help keep your circuits neat.
• The bit finder can be a very useful tool in helping you to figure out which way within a set you should be working with.
• Do the data path first and then the control path. You won’t know what control signals you need until the data path is built so build that data path first. I ended having about 7 control signals. You may have more or less depending on your design.
• When it comes to data values, it is generally safe to pass the same data value to all of your Sets/Ways. Students are tempted to use Demuxes to “send” the data to the correct Set/Way. This is an incorrect way to think as the Sets/Ways that aren’t selected still get a value, it is just 0.
• For control signals, you may need to send them to only a single Set/Way by using a Demux or you may need to send the signal to all Sets/Ways. To figure this out simply, ask yourself, “Should all Sets/Ways do this or just one of them?” If it is just one, Demux the signal, if it is both don’t Demux it.
• Your circuit does not have to start out being ready. I needed an initialize state so that I could set the ages of the lines and as such I wasn’t ready to begin until after I had passed through that state.
• You can greatly simplify your logic by just thinking that you will get your value from a set or a line. Obviously you want to use the right one, but you can easily select among them by using muxes and make sure that right one gets the correct input by using dmuxes. This will save your from having to enumerate all the possibilities of where the element you are looking for could be.
• Here are some of the mistakes I made that I made solving the problem. Hopefully you can learn from them
  • Forgot to rename some labels
  • Needed to both add and remove states from my FSM
  • Mixed up the Id of a Way with its Age
  • Messed up on the aging of lines. I assumed that they would all start with unique values but of course they don’t.
    • The fix was to add an initialization state where I would set the ages of the lines to 0, 1, and 2.
  • Used the wrong Tag bits to when addressing memory on writes.
    • Fix. When writing to memory you should use the Tag bits found in the Line that you will be writing. When reading from memory you should use the Tag bits from the CpuAddress.