For this project, you will be building a small single-cycle CPU. When complete, your CPU will be capable of running real programs (with conditionals, function calls, etc) and outputting numbers. You know, kind of like a real computer!

You will be implementing an ISA called cpu2241. This is a 16-bit architecture with some similarities to MIPS. Your implementation of it will be a single-cycle Harvard architecture.

You can get partial credit for broken instructions, or for pieces of circuitry for an instruction that isn’t implemented. However, a terrible strategy is to “try to get a little of everything done.” This strategy can work on exams, but works really badly when you build things. It’s much better to understand 70% of the project well than to understand all of it poorly.

Importantly, the way we test your project is by running programs on it. If no programs can be run on your project, the best you can get is a 30%. So do not put off running the test programs when you get to that part of the project.

Grading Rubric

Style: although there is no point category for style, the graders may take off up to 10 points if your circuit is very hard to understand. You can lose points for things like:

You can help the grader by doing these (but they’re not required):

The points break down as follows:

Stuff to download and pages to keep open

  1. Download this file, and unzip it (i.e. “decompress” it) into a new folder.
    • If you don’t know how to do that, get help.
    • No seriously. Get help. Don’t you DARE try to do the project WITHOUT THE FILES.
  2. Rename the abc123_proj2.circ file to your username.
    • Cmon, do it now. Why does everyone wait until the last minute to do this? If you don’t rename it, it makes it super confusing when four students send me abc123_proj2.circ and I don’t know which belongs to who.
  3. Open that file in Logisim.

Finally, this is the ISA reference - open it in a new tab and keep it open alongside this page.

How to approach this

You may use any built-in Logisim component to build your CPU! You don’t have to build the ALU out of 500 gates or the registers out of flip flops. You may also use anything you’ve made in the labs, like the ALU and Register File lab. Finally, you may use any examples on the Materials page, like pc_fsm.circ.

Just don’t use any circuits someone else made, because that’s cheating, duh.

Go in order. The project is going to consist of a few “phases:”

  1. First you will be creating some of the basic components (or reusing them from the lab).
    • You will test each of the components in isolation. (This is called “unit testing.”)
  2. Then I will walk you through the process of setting up the interconnect and starting the control.
    • This is where you will start running programs on your CPU.
    • (This is called “integration testing,” because you are integrating multiple parts together.)
  3. Then you will be left to do the rest of the project on your own.
    • You’ll implement the control and interconnect needed for some instruction(s)…
    • Then run the test(s) to make sure they work.
    • You’ll repeat that until you get all the tests working!

Try to get through the first two phases (creating the components and doing the control and interconnect tutorial) by the end of the first week. That will leave the second week for just implementing the rest of the instructions. (Or, if you do the first two phases during Thanksgiving break, then you’ll have TWO weeks to implement the other instructions!)

Getting familiar with what you’ve been given

When you open the project circuit, you’ll see this.

Eventually you will connect the rest of the CPU to these things through wires and tunnels.

The Instruction and Data memories

The Instruction Memory is a Memory > ROM component. ROM stands for read-only memory.

The ROM is super simple to use: put instruction address (i.e. the value of the PC register) into the left side, get instructions out the right side. I’ve also attached a probe to the A input so that you can see what the current PC is… once you build that. That will be very helpful in running the tests.

The Data Memory is a Memory > RAM component. The address and data to store go in the left side, the clock in the bottom (the triangle), and the data that is loaded comes out the right side.

The str input is the memory’s write enable signal. Most instructions don’t write to the memory, so you’ll have to hook something up to it. Ignore the sel, ld, and clr inputs! You will never need them!

Also, both memories are word-addressed. What that means is that each memory address refers to an entire word (16-bit value) rather than a byte. This is a simpler arrangement than byte-addressable machines, but it’s something to keep in mind.

Phase 1: making pieces

1. The ALU

The ALU is a combinational circuit. Remember, you’re allowed to use any of the built-in Logisim components - adders, subtractors, shifters, bit extenders etc.

The ALU is almost exactly the same as what you made in lab 7, except 16 bits instead of 8. If you finished that lab, you can reuse your work like so:

  1. In your project, double-click the ALU component on the left side to edit it.
  2. Open your lab 7 (yes you can have multiple things open in Logisim at the same time)
  3. Go into your lab 7’s ALU component, Ctrl/⌘A to select all, and Ctrl/⌘C to copy
  4. Use the Window menu to go back to your project
  5. Use Ctrl/⌘V to paste that stuff into your project’s ALU circuit
  6. Change the “Data Bits” of the inputs and output from 8 to 16…
    • then follow the orange wires and change everything else from 8 to 16 bits as needed.
    • (the shifters will use the lower 4 bits of B, instead of the lower 3 like on the lab.)

Do NOT use the Project > Load Library menu in Logisim. It’s neat, but makes it MUCH harder for us to grade, because now your project is split across multiple files. Please copy and paste as described above.

If you didn’t do the lab, there are more detailed instructions on how to build this in the lab 7 instructions.

The ALU component works like this:

Notes:

2. The register file

Again, this register file is almost exactly what you made in lab 7, but 16 bits instead of 8. If you did that lab, you can do the same thing as you did with the ALU and copy it into your project’s Register File component. If you didn’t do that lab, well, you have to go do it now, because I’m not going to repeat the directions here.

I showed how to make the register file in class, and you presumably did it on the lab too. Details:

3. The PC FSM

The PC is a register which holds the address of the current instruction. Since your instruction memory uses 16-bit addresses, what size should the PC register be? 😉

Remember from class that the PC can move ahead by 1 instruction, or jump to other places, or conditionally branch. That’s what this component is for. There is also an example PC FSM on the Materials page whose structure you can base yours on. But this time, don’t just copy and paste the circuitry; replicate it yourself. There are enough differences from the example that copying and pasting won’t really save you much time anyway.

It will have:

Like we said in class, how the branch conditions are checked are not really the responsibility of this component! That is explained later and done elsewhere.

Phase 2: the control and interconnect

Now What?

From here, things get a little weird. You have two more important things to make: the interconnect (connecting all the components together) and the control (tells all the components and the interconnect what to do for each instruction).

However, you can’t really make one without knowing something about the other. It’s technically possible to do all the interconnect before moving onto the control, but most people aren’t familiar enough with how the CPU works yet to be able to do that easily! So I will ease you into it for the first few instructions.

How the control and interconnect work together

Remember from the interconnect lecture that each instruction can make use of multiple components of the CPU. For example, a load instruction might:

The interconnect is all of the wires and multiplexers that connect the various CPU components together so that they can send the data to each other. However, none of these components can read instructions, and cannot do any work without being told what to do.

The control is what reads the instructions and tells all the CPU components - and the interconnect - what to do to implement each instruction. Remember: the control is the brain, and all the other parts of the CPU are the body.

“Where does the instruction’s work happen? In the control?”

No. The control doesn’t do any work itself. It isn’t adding numbers or loading values or anything. It just tells all the other parts of the CPU what to do, and when.

“Does the control need to take the registers/ALU output/loaded memory/etc. as inputs?”

No. Again, the control isn’t responsible for doing any work. It does not work on values. The only input to the control is the instruction coming out of the instruction memory (ROM).

“How does an instruction description like REG[rd] <- REG[rs] + REG[rt] get implemented?”

Well it’s good to keep in mind:

It’s hard to explain an exact process for turning an instruction description into something the CPU can do, but that’s what the rest of this tutorial will try to do!

4.1 - Starting the control

If you did lab 8, this should be familiar to you now. If you didn’t… well, have fun!

Please go review the Control lecture slides. There is also a decoding.circ example on the Materials page that shows many of the concepts in practice, but for a small subset of MIPS, not this project’s ISA. Lab 8 also had its own instruction set.

  1. Edit the Control component. Inside, its only input is the 16-bit instruction.
    • (It does not have a clock input as it is a combinational circuit.)
  2. Split up the instruction input.
    • The instruction formats are documented on the ISA page.
    • Use splitters to split the instruction into all possible unique fields.
      • The “fan out” is how many pieces to split the value into.
      • You will have like, 4 splitters to get out all the fields you need.
    • After splitting you should have one of each of these:
      • opcode (5 bits) - you do not need 4 copies of it
      • rd_field, rs_field, and rt_field (all 3 bits)
        • I recommend you name them like this for Reasons that will Become Apparent Later.
      • imm5 (5 bits)
      • imm8 (8 bits)
      • target (11 bits)
  3. Decode the opcodes.
    • Just like the slides, decoding.circ, and lab 8, you’ll use a decoder. 5-bit opcode into a 5-bit decoder.
    • Create all the instruction signal tunnels connected to the outputs of the decoder. Look at the ISA to see which opcodes correspond to which instructions. It lists them all in numerical order (so, the same order as the decoder outputs). Name the tunnels coming out of the decoder like so: hlt, put, li, etc.
      • Don’t waste space naming them add rd, rs, rt or whatever!
      • And definitely DO NOT name them 00000, 00001, etc. YOU ARE NOT A COMPUTER!!
  4. Output the register indexes.
    • Create 3 3-bit outputs named rd, rs, and rt.
    • Connect the rd_field, rs_field, and rt_field outputs to them… for now.
      • We’ll come back to them later.

4.2 The interconnect

The interconnect is not another component. It exists on the main circuit, connecting all the components of the CPU together.

So go to the main circuit, and you can start connecting them up. Here are the broad strokes:

Some more tips:

You should now have something like this on your main circuit. However, I customized the appearances of some of my components to make it easier to hook things up. You don’t have to, but it can make it look nicer.

4.3 The first instruction: hlt

Try ticking the clock right now by using the hand tool to click the clock button. The PC moves ahead. This is wrong.

See, the ROM is full of instructions that are all 0s, which is the hlt instruction. This instruction should halt the CPU, which means the PC should stop changing.

If you don’t believe me that this is a hlt instruction, use the hand tool to double-click the control in the circuit, and look at the decoder. Mine looks like the image to the right. Things to note:

Alright, let’s make the halt instruction work. It has two effects:

So do this:

  1. In the control:
    1. Add a 1-bit output to the control named “halt”.
    2. Duplicate the hlt tunnel from the decoder, and attach it to that output.
  2. On the main circuit:
    1. Duplicate the “Halt” tunnel that’s connected to the Halt LED already, and connect it to the Control’s halt output.
    2. Duplicate that tunnel and connect it to the PC FSM’s “halt” input.

Like this. See how the LED is lit up?

Now reset, and tick the clock. The PC should now stay at 0! You just implemented the hlt instruction!

4.4 The next instructions: li and put

The first real test program is the one that tests these instructions. Let’s actually do put first cause it’s simpler, but we won’t be able to test it until we implement li.

Implementing put

The put description says display <- REG[rs]. This is telling us two things:

So here’s what to do:

  1. Connect the REG[rs] output of the Register File to the “Data” input of the Display.
    • Use a dang tunnel named REG[rs].
    • You’ll be copying and pasting that tunnel multiple times throughout the project!
  2. You need a new control signal.
    • In the control:
      • Make a 1-bit Display WE output
      • Duplicate and connect the put tunnel to it
    • On the main circuit:
      • make a Display WE tunnel
      • use it to connect the control’s Display WE output to the Display’s WE input

That’s it! But here’s an important warning: hlt and put are extremely simple instructions, and you cannot just make an output for every instruction like this. These instructions are the exception, not the norm. The control circuitry for subsequent instructions is going to get more complex!

Implementing li

Finally, a non-trivial instruction. It says REG[rd] <- sxt_16(imm8). What does that mean?

So here’s what you’ll do:

  1. Add a 16-bit imm output to your control. For now, sign-extend the imm8 field to 16 bits, and connect that to the imm output. (We’ll revisit this.)
  2. On the main circuit, connect the control’s imm output to the register file’s REG[rd] input.
    • (This will change soon, but for now it’s all you need.)

  3. In the control, make a new control signal output, Reg WE.
    • Normally for a 1-bit control signal, you’d OR together all the instructions for which that signal needs to be 1. But actually a majority of the instructions (24 out of 32) need to write to the register file.
    • So instead, we’ll OR together the instructions that don’t write to the register file, and then NOT that. Lol.
    • If you look at the ISA page, you can find those instructions - basically, anything that doesn’t have REG[x] on the left side of a <-.
    • Duplicate the tunnels for those 8 instructions from the decoder and make them face right.
    • Make an 8-input NOR gate and connect its output to the Reg WE output.
    • Connect all of those 8 instruction tunnels to the OR gate’s inputs.
    • See image on right!
    • Essentially this is saying, “if we are not executing any of these instructions, then turn on the register file’s write enable.
  4. On the main circuit, connect the control’s Reg WE output to the Register File’s WE input.

Whew! This is how your main circuit should look at this point.

Wait. Look at the instruction input to the control.

What?

It got disconnected from the control!

So here’s a really really annoying feature of Logisim. Because we added more outputs to the control, it got taller, which made the instruction input move down, making it get disconnected from the instruction memory.

This drives me nuts. There are two ways to solve this:

  1. Every time you add more outputs to the control, you have to check on the main circuit to see if it came undone and reconnect it to the ROM. This is annoying.
  2. Go into your Control circuit, then Project > Edit Circuit Appearance. See the blue square on the left? Drag it up by 2 dots.
    • Now go back to main and make sure it’s reconnected to the instruction tunnel.
    • Once it is, you never have to do this again. Once you have edited the control’s appearance, the input will never move! And you can also edit its appearance to e.g. space out the outputs more so you can connect tunnels to it more easily.
    • The only downside is, the rectangle won’t automatically get any bigger from now on, so you’ll have to edit the control’s appearance to make it taller.

Testing the li and put instructions

Okay. Now that that’s dealt with, you can test it out by doing this:

If all goes well, after a few cycles you should see ffc3 on the display! One more cycle should show 0029, and it halts. (That test description also explains what could go wrong if you implemented things incorrectly.)

Hey, guess what, you now have a 40% on the project, and it (mostly) gets easier from here, honestly!

Intermission: testing registers

The next test tests that all the registers are working properly. That test should work correctly now, unless there is something wrong with your register file.

4.5 Implementing lui, I-type instructions, and the RegDataSrc mux

Then comes the test for the lui instruction, which you haven’t implemented yet. If you run the test now, you’ll see FFEF (which is right), then FFBE (which is wrong).

lui stands for “load upper immediate” - it loads the 8-bit immediate into the upper 8 bits of the given register. This way, you can do an li followed by a lui to load a 16-bit value into a register. If this sounds weird, this instruction is borrowed from MIPS!

There are two issues that need to be resolved to get this working:

  1. We need to control the register file’s rs input differently for I-type instructions; and
  2. We need to choose which value goes into the register file.

Let’s tackle the first one.

I-type instructions’ rs input

I-type instructions only have one register field, rd. But many I-type instructions need to read a register too. The solution to this is to use the instruction’s rd field as both the rd and rs inputs to the register file. (If that sounds weird, real MIPS has something similar - some I-type instructions use rt as the destination, and others use it as the source. The book explains it in more detail.)

Importantly, we don’t have to change the register file to implement this at all. Remember, it’s the control’s responsibility to tell all the other parts what to do. So go into your control.

  1. Right now, you have rs_field connected to the rs output. Disconnect it.
  2. You need to make a circuit that does this:
    • If the current instruction is I-type, output rd_field to the rs output.
    • Else, output rs_field to the rs output.

So that’s a MUX, right? The inputs to the MUX will be rs_field on input 0 and rd_field on input 1, and the output goes to the rs output. The trickier part is the MUX’s select. “If the current instruction is I-type”… that means you need to OR together all the I-type instruction signals (there are 12). The OR’s output is the MUX’s select input.

The RegDataSrc mux

Back on the main circuit, you need to set up a MUX on the register file’s input like the image on the right. Details:

Keep the order of the values on the inputs in mind as we talk about how to implement the RegDataSrc control signal in the control:

Finally on the main circuit, hook the RegDataSrc signal up. Don’t forget to do this!

Now the lui test should work: it shows FFEF, then BEEF. (If it shows EFBE for the second value, you have the inputs to that lui splitter mess swapped.) Notice that on each instruction when the register file’s WE is 1, RegDataSrc is set to a value that chooses the appropriate MUX input. Nice!

Now would be a good time to go back to make sure 01_li_put still works, too.

Okay!

It takes a good bit of work to get here, but you actually have pretty much all the skills you need to finish the project, as well as a good bit of the interconnect complete.

Proceed through the tests in the order they’re given, implementing the needed instructions as you go. Sometimes this will require you to change some circuitry you already built (like when we had to add the RegDataSrc MUX earlier). That’s okay. It’s okay to change your work.

Phase 3: the test programs

Each test assumes the previous tests work properly. If you can’t get one test working, don’t waste your time trying later ones, because they will probably break too. So, do them in order, and get the earlier tests done first. Ask for help if you are stuck. Correct implementation of a few instructions is worth more points than partial implementation of several instructions.

To run the tests:

  1. In your main circuit, right click your program ROM component and choose “Load Image”
  2. Open the .rom file you want to run, which should be in the same folder if you followed the directions above.
  3. Reset, save, and run it.
    • The shorter programs are easier to test by single-stepping the clock, instead of having the clock tick automatically.

Finally, these rom files are just text files - you can open them in a text editor to see the source code on the right, as well as the PC for each instruction (in decimal), so you can figure out which instructions are tripping up your CPU.

0. The hlt instruction (00_halt.rom)

The simplest program ever: this should halt immediately. (It really is all 00000 instructions.)

The PC should not increment, and the HALT LED should turn on.

If the PC is changing (going 0, 1, 2, 3): your control unit should be sending a halt signal to the PC FSM, and the PC FSM should prevent the PC from changing (i.e. disable it) when the halt signal is 1.

1. PLEASE GET THESE WORKING: li and put (01_li_put.rom)

This is a very short program, so it’s easiest to see if it’s working right by resetting, then ticking the clock manually (ctrl+T or ⌘T, or clicking the button you have ORed with the clock signal).

The output should start at 0000 (it always does), then show ffc3, then 0029 and halt.

In more detail, this program does the following:

If the PC goes directly from 0 to 4, causing it to never display anything other than 0000, you’re not supposed to add 4 to the PC on each tick!!!!!!

If it displays 00c3 instead, you probably have your zero- and sign-extension circuitry in the control swapped somehow.

If it skips ffc3 and only displays 0029, you probably demultiplexed the data in the reg file instead of the write enable, which is wrong. See lecture 19 slides 12 and 13.

If it otherwise never displays anything, check:

2. ALSO IMPORTANT: Checking the register file (02_allregs.rom)

This checks to see if all 8 registers can be written to and read from.

It will also “load” the immediate 0xFF into r0, which should do nothing.

This should appear to do nothing for several instructions, and then display the numbers 0011, 0022, 0033... up to 0077, then halt. Unlike the first test, the display does not go back to 0000 at the end. That is normal. It’s fine. Calm down.

If you see 00FF as the first value, you implemented r0 wrong. It’s a constant 0, not a register.

If you only see 0077 at the very end, your write enable circuitry is messed up. Don’t use a demux for the data, use it for the write enable signal.

If there are missing numbers, or they come out in a weird order, step through and see what’s going into the registers after each li instruction. Be sure to double click on the component in the main circuit and not the name on the left side. Sometimes it’s easy to forget to connect one register’s write enable or data in the reg file component.

3. lui (03_lui.rom)

lui works like lui in MIPS: it loads the 8-bit immediate into the upper 8 bits of the given register, and it does that by also reading that register. But the tutorial explains that.

Here’s what it does:

If it only shows 0000 for the whole test, there are some possibilities:

Note: using priority encoders the right way

You’re about to make the control logic for the ALUOp control signal, which is 3 bits. That means you need a priority encoder with 3 Select Bits.

People often get confused about how to use priority encoders the right way, so start with the thing on the right. You always need to put a constant 1 into the 0 input to avoid blue wires.

But that constant 1 automatically handles ALUOp 0, which if you did your ALU like was specified in lab 7, is the addition operation. That means you do not need to do anything to make the instructions that add (e.g. add, adi, ld, st) work properly. They’re done.

Input 1 of the priority encoder is for ALUOp 1, which again if you followed the lab, is subtraction. So you will OR together all the instructions that need to perform subtraction. Then input 2 is for ALUOp 2, etc.

Last, there’s one more thing I see people do sometimes, and that is to use a 1-bit priority encoder. If you set them up with a constant 1 as input 0, these basically do nothing. They’re a really complicated wire. So you can just delete them and use whatever is going into input 1 directly (see below).

Control and Interconnect Intermission 1: the ALU

You are about to implement the ALU instructions. So go look at them on the ISA reference. You already built the ALU to perform all these operations. So, what are the inputs to the ALU going to be? Go look at the interconnect lecture slides too. It’s gonna be veeeery similar. Like…………………. the same. It’s the same okay

That ALUBSrc MUX needs to be controlled. It’s just a 1-bit control signal, so you know what to do there.

As for RegDataSrc, as long as you followed my advice and used the ALU output as input 0 to that mux, then you’re already done. If you didn’t, well, have fun ORing together all the ALU instructions in the control to pick the ALU’s output for RegDataSrc :)

4. Basic ALU: add, sub, and, or, xor, not, shl, shr (04_alu_basic.rom)

This program is a bit longer, and will display 8 different numbers. They will appear in this order (the things in the parentheses are what produced that value):

If it just displays 0000 until it halts, did you actually do the interconnect to the ALU like I told you in the previous section? If nothing is going into the ALU, it’s just gonna output 0s. The other possibility is that your RegWE signal is wrong and not being turned on for them.

If all you see is 0000 and 0078, look for blue wires on your main circuit. If you don’t actually tell a mux what to select, it will output blue. Fix that.

If several or all the answers are wrong, maybe there’s something up with the way you come up with the ALU Operation control signal.

If only one is wrong, maybe that part of your ALU needs a look. Remember, you can see what instruction is at each PC by looking inside the control unit and seeing what the decoder says it is.

Control and Interconnect Intermission 2: handling the immediates

Your control is just outputting sxt_16(imm8) for the immediate, which has worked fine for all the I-type instructions you’ve implemented so far. But that’s about to change. Some of the I-type instructions use a zero-extended version of the 8-bit immediate. Then there are L-type instructions, which use the 5-bit immediate; and J-type which use the 11-bit target!

All of this can be handled in the control, just like you did with the rs weirdness. The rest of the CPU doesn’t have to know that imm is just “whatever it needs to be for this instruction.” That’s the control’s job.

So in the control, here’s the logic for the imm output:

if(opcode is "j" or "jal") {
    imm is zxt_16(target)
} else {
    if(opcode is "ld" or "st") {
        imm is sxt_16(imm5)
    } else {
        if(opcode is "ani" or "ori" or "xri") {
            imm is zxt_16(imm8)
        } else {
            imm is sxt_16(imm8)
        }
    }
}

Remember from the PC FSM slides that an if-else if-else if is represented by muxes-after-muxes. So yeah, it’s gonna be three chained muxes.

To test: poke the instruction input to your control to the given bit pattern (if it asks about “tied to supercircuit’s state”, say yes), then look at the imm output. Test cases:

5. Immediate ALU: adi, sbi, ani, ori, xri, sli, sri (05_alu_imm.rom)

Again, this will display several numbers:

If they all fail, maybe your data going into the ALU’s “B” input is wrong. It should be choosing the immediate value, not the register value.

Pay attention to whether the immediate should be sign- or zero-extended! This is important for adi, sbi, ani, ori, and xri. (sli and sri don’t care, because they only look at the least significant bits of it anyway.)

Control and Interconnect Intermission 3: the data memory and rt

The next test is the load and store instructions for accessing data memory. Once again, go look at the ISA for these two instructions, and revisit the last interconnect slide. It’s gonna be the same as that, again. The ALU produces the address for the memory, and REG[rt] goes into the D input on the left side.

RegDataSrc definitely needs to be updated, since the D output on the right side of the data memory needs to go into the register file. Remember that not every instruction writes to the register file, so not every instruction must choose something for RegDataSrc. (To put it another way, it’s okay if RegDataSrc is 0 for st, because st doesn’t put anything in the register file, so the value going through the MUX will just be ignored.)

You may have to update your ALUBSrc control to include ld and st, since these also perform “register + immediate.”

You shouldn’t have to update ALUOp since, again, the constant 1 handles addition for you.

Finally, the data memory needs a write enable signal (MemWE). That goes into the str (“store”) input of the data memory. Hey - DOES ld WRITE INTO MEMORY? DOES IT???? HUH???????? NO!!!!!!!! AAAAAAAAAAAAAHHHHHHHHH!!!!!!!!!!!!!!!!!!!!! (can you tell I’ve answered this question eighty thousand times?)

Do not use the RAM’s ld input for the ld instruction. I know. It’s tempting. Just don’t. Never connect anything to the RAM’s ld, sel, or clr.

Finally there is one more complication - st and only st uses the rd field as the second register to read from the register file. So you need to change how your control handles the rt output like how you did for rs. The logic is:

if(opcode is "st") {
    rt is rd_field
} else {
    rt is rt_field
}

That is, you output rd_field for rt for st, and rt_field for every other instruction.

6. RAM: ld and st (06_ld_st.rom)

Let’s see if the RAM works. The display should stay 0 for a while, then display 0005, 0006, 0007, then halt.

At the end of the program, use the hand tool to click the address column on the RAM (the grey numbers on the left) and type 0000. It should look like this:

If you only see 0001 and 0002 at the end, there are a few possibilities:

If nothing is displayed (just 0000 the whole time),: at the end of the program click the address column and type 0004. If you see this (0001 and 0002 in RAM at addresses 0006 and 0007):

Then you swapped the address and data inputs to the Data Memory (RAM). The ALU output is the address.

If instead you see this in RAM:

Then your ALU is doing REG[rs] + REG[rt] when it should be doing REG[rs] + imm. make sure the second input to the ALU is the immediate for both ld and st, just like all the immediate ALU instructions.

If all the RAM values are 0000 instead, you probably aren’t turning on the RAM’s write enable (the str input) for st.

If your RAM looks correct, but it displayed all 0000, look in your register file after the program halts. r4, r5, and r6 should hold 5, 6, and 7. If they don’t, your ld is wrong. Chances are, you forgot to turn on the register file’s write enable for ld.

7. More tests of ld and st (07_ld_st_2.rom)

This one tests the address calculation of these instructions. Basically it does:

If the addresses are REALLY off and it’s accessing some address other than 0x0001 at PC = 4, you are probably zero-extending the 5-bit immediate instead of sign-extending it.

Control and Interconnect Intermission 4: jumps and the return address

Look at the jump instructions in the ISA. There are 4, but they are kind of all related to each other j and jal both use target as the target; jr and jlr use REG[rs] as the target. j and jr simply jump; jal and jlr also link (put the return address in r7).

Your control needs to output a couple things for these to work:

Then for the interconnect, you need to connect that Jump signal to the PC FSM, and then make a circuit to choose what the PC FSM’s Target input should be.

You also need to connect the PC FSM’s PC+offs output to the RegDataSrc mux, which means you need to update its control. Both jal and jlr use that output, so you can OR them together.

Finally, there is one more piece of register decoding to deal with in the control.

if(opcode is "jal" or opcode is "jlr") {
    rd is 7 // like, a constant 7.
} else {
    rd is rd_field
}

Yeah, now all three register index outputs can be different fields depending on which instruction it is! This is pretty normal stuff in instruction decoding. Packing all the information into a small number of bits usually means you have to do some work to unpack it all in the control.

8. j (infinite loop) (08_j.rom)

This should loop infinitely, displaying an increasing count on the display (0001, 0002, 0003, 0004 etc.). Try doing Simulation > Enable Ticks and turn up the tick frequency… wheeee!!!

The PC (that is, the probe on the address going into the instruction memory!) should go 0, 1, 2, 3, 1, 2, 3, 1, 2, 3...

The j is at PC = 3. At PC = 3, your PC FSM inputs should be:

If it halts, then your PC FSM probably isn’t being told that j is a jump.

If it loops, but just shows 0001 forever, and the PC goes back to 0 after 3, then the PC FSM’s jump target is probably wrong. It’s supposed to be the immediate.

9. jr (09_jr.rom)

The jr instruction works just like j, except instead of using the immediate as the jump target, it uses REG[rs] as the jump target.

This is a very short program. The jr is located at PC = 1, and it will try to jump to address 5.

On success, it will output 0001 and halt. (The PC will go “0, 1, 5, 6, 7” in that case.)

If it outputs FFFF instead, that means your jr didn’t jump. Your PC FSM’s “jump” control signal should be 1 if you are executing any of the jump instructions (j, jr, jal, or jlr).

If it loops infinitely with the PC going 0, 1, 0, 1, 0, 1…, that means your jr is using the wrong target. It’s probably using the immedate, when it should be using the value of REG[rs]. j and jal use the immediate as the target; jr uses REG[rs] as the target. CHOOSE.

10. jal (10_jal.rom)

jal works similarly to MIPS’s jal. It puts the return address into register 7.

This is another very short program. The jal is located at PC = 1, and it will try to jump to address 5, putting the return address (2) into register 7.

On success, it will output 0002 and halt. (The PC will go “0, 1, 5, 6” in that case.)

11. jlr (11_jlr.rom)

jlr puts the return address in r7 like jal, but uses REG[rs] as the jump target like jr.

This is another very short program. The jlr is located at PC = 2, and it will try to jump to address 6, putting the return address (3) into register 7.

On success, it will output 0003 and halt. (The PC will go “0, 1, 2, 6, 7” in that case.)

If it outputs 0006, it means that your RegDataSrc control is wrong. Either jal or jlr should choose PC+offs as the value to go into the reg file.

Otherwise, the same outputs/issues apply for this instruction as for jal. So scroll up.

12. jal and jr together (12_jal_jr.rom)

This program should output 0001, 0000, 0002, 0000, 0003 and then halt. It does the equivalent of:

f1();
put(1);
f1();
put(2);
f2();
put(3);
halt;

void f2() { f1() }
void f1() { put(0); }

The PC should go in this sequence (this is in decimal):

0, 1, 2, 3, 16, 17, 4, 5, 16, 17, 6, 7, 10, 11, 12, 16, 17, 13, 14, 15, 8, 9 (halt)

If it goes like 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and displays 0001, 0002, 0003, then jal isn’t actually jumping anywhere. The first jal is at PC = 3. Investigate!

If it goes like 0, 1, 2, 3, 16, 17, 0, 1, 2, 3, 16, 17, ... in an infinite loop, there are a few possibilities:

If it goes like 0, 1, 2, 3, 16, 17, 3, 16, 17, 3, 16, 17, ... in an infinite loop, you forgot to use PC + 1 as the return address (i.e. the value coming from the PC into the register file).

If it does something else… I dunno!! Go back to the earlier jr and jal tests!

Control and Interconnect Intermission 5: Comparison instructions

The next group of instructions is the comparison instructions (slt, sle, seq) and the branch instructions (bez and bnz). We didn’t talk about this, but this is actually how MIPS does conditional branching - try using blt t0, 10, _loop in MARS and look at what it assembles into.

The comparison instructions stand for “set if less than,” “set if less than or equal”, and “set if equal.” What they essentially do is put a boolean in the destination register - 1 if the condition is satisfied, and 0 if not. Then, the branch instructions test for 0 or not-0, which matches that behavior nicely. This way, we can get all six comparisons with just three comparison instructions; and since testing for 0 and not-0 is so common, some branches can be done without a comparison at all.

To implement the comparison instructions:

Then you need to make a Thing. This Thing can be on the main circuit, or you can make a new component for it. This Thing will:

Finally, for the interconnect, you need to connect the output of that Thing to the RegDataSrc MUX on the right input, connect the output of the ALU to the input of that Thing, and connect the control signal for it.

13. Comparisons: slt, sle, seq (13_set.rom)

This program puts the numbers 3 and 5 into r1 and r2 respectively, then compares them. It does this:

It then combines the outputs of those three instructions into a single number by doing

and outputs that number.

Done correctly, this test outputs 0006. 6 is binary 110, which is the three comparison results in order.

If it outputs FFFE instead, you might be sending the ALU’s output into the reg file for the set instructions. That’s wrong. It should be the output of the Thing explained in the previous section.

If it outputs 0000 or 0007: it might be using the same condition for all three set instructions. Each one tests a different condition.

If it outputs something else:

If they’re all broken, uhhh get help?

14. Signed comparisons (14_sign_cmp.rom)

This checks that your comparison instructions are performing signed comparisons instead of unsigned ones.

It does something very similar to the previous test, but compares -3 to 5 instead. It also does a bitwise NOT on the final result before displaying it so that you can tell that this test is different from the previous one.

Done correctly, it will display FFF9 at the end.

If it displays FFFF, it means your comparison Thing is using a comparator set to do unsigned comparison. Change it to 2’s complement.

Control and Interconnect Intermission 6: Branches

There are only two branch instructions, and they behave very similarly: they both compare REG[rs] to 0. (Yes, REG[rs]; the instruction description says REG[rd] because they’re I-type, but you already handled that complication.)

Your PC FSM handles changing the PC already. If its Branch input is 1, it will add the offset to the PC, otherwise it adds 1 to it. What you have to implement is the logic that comes up with the PC FSM’s Branch input, and connect the immediate to the branch offset input. (Again, you handled the immediates in the control already.)

Here are some common questions and answers:

15. bez (15_bez.rom)

This tests that bez (“branch if equal to zero”) branches when it should, and doesn’t branch when it shouldn’t. The bez instructions are at PC=1 and PC=5.

Done correctly, this outputs 0005. The PC goes 0, 1, 4, 5, 6, 7, 8 in that case.

If it outputs FFFB and the PC goes 0, 1, 2, 3, it means that it didn’t branch when it should have. Investigate!

If it outputs FFFA and the PC goes 0, 1, 4, 5, 9, 10, it means that it did branch when it should not have. The second bez at PC=5 should not branch. Chances are, you are just turning on the PC FSM’s Branch input if the current instruction is a branch. No! Look at the previous section (“the branch should happen only when…”)

16. bnz (16_bnz.rom)

This tests that bnz (“branch if not equal to zero”) branches when it should, and doesn’t branch when it shouldn’t. The bnz instructions are at PC=1 and PC=3.

Done correctly, this outputs 0008. The PC goes 0, 1, 2, 3, 6, 7, 8 in that case.

If it outputs FFFC, it means that it didn’t branch when it should have.

If it outputs FFFD, it means that it did branch when it should not have. The second bnz at PC=3 should not branch.

17. Finding primes (17_primes.rom)

Finally, a real program. This is a prime-number-finder. It runs forever, and will output the sequence of prime numbers: 0002, 0003, 0005, 0007, 000b, 000d, 0011, 0013, 0017… well, it’s in hex, so they’ll look a little funny, but hey.

This is a very slow program, so turn on ticks (Simulate > Ticks Enabled) and set the Simulate > Tick Frequency to a large value. The first few numbers will be found very quickly. But the bigger the numbers get, the longer it will take to find them. Even at 4KHz, it will take several seconds for each.

If you’re curious, the algorithm this uses is incredibly stupid. It does something like this (but written in a very weird way):

18. Recursive function (18_sum.rom)

A real program with a recursive function and a call stack! If everything else worked until now, this should work. This program uses most of the kinds of instructions your CPU can run - output, loading immediates, arithmetic, loads, stores, calls, returns, and branches - so it’s a good test of everything up to this point.

It will push a bunch of things “on the stack” (starting at address 0 in memory), then pop them, and then it should output 0037 and halt.

This program will take a while to run, so set the tick frequency higher and let it run on its own. When run at maximum speed (4KHz), this should finish within a second or two. If it’s going for several seconds at max speed, maybe it’s going into an infinite loop…

It does something like:

put(sum(10));
halt;

int sum(int x) {
    if(x == 1)
        return 1;
    else
        return x + sum(x - 1);
}

sum is a recursive function that calculates the sum of integers from 1 to n. So, sum(10) should give 55, or 0x37 in hex.

It uses r6 as the stack pointer, and initializes it to 0 at the beginning of the program. The stack grows upwards in this program, so each time it pushes something, it will appear at successive memory addresses (0, 1, 2, 3…). This makes it easier to see those values.

If you’re having problems with it, you can right-click the RAM component, click “Edit Contents”, and view the contents of the stack that way. It should look something like (starting at address 0 and moving right) 0003, 000a, 000e, 0009, 000e, 0008, 000e, 0007, ....

Control and Interconnect Intermission 7: Multiplication

Right now, assuming all tests work correctly, you have an A- (92%). But if you want to go for the 100%, there are the multiplication instructions, mul and mfp. You don’t actually have to do very much much work for these, so you can think of them as a “victory lap” ;)

The control is super simple: you just need two 1-bit signals, one for “is this mul” and one for “is this mfp”. The “is this mul” signal goes to the Multiplier’s Start input. The other one, well…

You need to add a Pause input to the PC FSM, which works like this: if either Halt or Pause is 1, disable the PC. (So you’re just ORing it with Halt.)

Then, in the interconnect, the PC FSM’s Pause signal is:

Pause = isMFP & ~multiplier.Done;

That is, if the current instruction is mfp (move from product), and the multiplier’s is not done (its Done output is 0), then pause the PC FSM.

Finally, I’ll leave it up to you to figure out the data interconnect - what has to connect to the Multiplier’s A and B inputs, and how to split up and connect its PROD output to the register file. The ISA descriptions of mul and mfp tell you everything you need to know for this.

19. mul and mfp (19_mul_mfp.rom)

This program loads 0xBEEF into r1 and 0xC0DE into r2. It then multiplies them together with mul, and then immediately uses mfp (at PC=5) to get the lower part of PROD. Because of this, the CPU should actually pause at PC=5 for several cycles until continuing to PC=6.

Done correctly, it pauses at PC=5 for several cycles and outputs d342 then 8fd8.

If it doesn’t pause at PC=5 and outputs 7dde then 0016, that means the Pause signal is wrong - it’s getting a half-baked product and printing that out.

If it pauses at PC=5 but outputs 8fd8 then d342 (the numbers are swapped), then you just swapped which part of PROD goes into the reg file for mfp.

20. Recursive factorial function (20_fact.rom)

The final test. This is similar to 18_sum but does a factorial instead. It also takes advantage of the fact that the multiplication proceeds in the background to run other instructions while it’s multiplying, so that it never has to pause to wait for the product.

Like that program, it runs for a while before displaying the answer. It calculates 8! and displays 9d80 (43,020 in decimal).

It’s actually kind of fun to watch it at a slower speed like 32 Hz. Try going inside the multiplier while it runs too. zoooooom

Here’s the source code for the curious:

    li  r6, 0    # r6 is the data stack pointer, grows upwards from 0
    li  r1, 8    # r1 is the argument to fact()
    jal fact
    put r1
    hlt

fact:
# push r7
st  r7, [r6]
adi r6, 1

    # r1 != 1?
    li  r2, 1
    seq r2, r1, r2
    bnz r2, _base_case
        # push r1
        st  r1, [r6]
        adi r6, 1

        # r1 = fact(r1 - 1)
        sbi r1, 1
        jal fact

        # pop r2
        sbi r6, 1
        ld  r2, [r6]

        # r1 * r2...
        mul r1, r2

        # pop r7
        sbi r6, 1
        ld  r7, [r6]

        # ...r1 = r1 * r2
        mfp r1, 0
    jr  r7

    _base_case:
        # return 1
        li r1, 1

        # pop r7
        sbi r6, 1
        ld  r7, [r6]

    jr  r7

And that’s it! That’s all the tests!

When you’re done with the last test, re-run all the tests, to make sure you didn’t break anything along the way!

Submission

Be sure to review the grading rubric before submitting.

To submit:

  1. On Canvas, go to “Assignments” and click this project.
  2. Click “Start Assignment.”
  3. Under “File Upload,” click the “Browse” button and choose your _proj2.circ file.
    • You named it with your username, right?
    • Do not include any other files.
  4. Click “Submit Assignment.”

If you need to resubmit, that’s fine, just click “New Attempt” on the assignment page and upload it again. The last thing you submit is what we grade. If you resubmit, Canvas may change your filename to have a -1 or -2 etc. appended to it. This is normal and not a problem.

It is okay to submit on/before the normal due date, and then resubmit on the late due date. You will get the late penalty, but if you turn in a 60 on time and a 100 late, that 100 becomes a 90, and it’s a net win anyway!

Reminder that if you submit a file that cannot be opened (e.g. you used Logisim’s “Project > Load Library” feature) and we have to ask you for a fixed version, that is a 20 point penalty. That penalty is in addition to the late penalty.