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:
- using few/no tunnels
- naming your tunnels stuff like
0
,1
,2
, or000
,001
,010
etc. - having very long wires with lots of bends in them
- having wires that cross over each other in confusing ways
- putting everything on the main circuit, instead of having components for the ALU, reg file etc.
- having a bunch of blue X wires or red error wires all over the place
You can help the grader by doing these (but they’re not required):
- using tunnels with good, descriptive names
- keeping your wires short and straight
- color-coding tunnels by similar purpose (e.g. blue for control signals, red for register values etc.)
- using the text tool to put “comments” in confusing places
The points break down as follows:
- [30 points] for building the CPU components other than the control
- [10] Register File
- [10] ALU
- [10] PC FSM
- [70 points] for implementing the control for each instruction. These are tested by running the programs on your computer. If we can’t run programs, you can only get a little partial credit.
- [2]
hlt
- [4]
put
- [4]
li
- [4]
lui
- [8]
add, sub, and, or, xor, not, shl, shr
- [6]
adi, sbi, ani, ori, xri, sli, sri
- [6]
ld, st
- Up to here is a 64
- [4]
j
- [4]
jr
- Up to here is a 72
- [4]
jal
- [4]
jlr
- Up to here is an 80
- [6]
slt, sle, seq
- [6]
bez, bnz
- Up to here is a 92
- [8]
mul, mfp
- [2]
Stuff to download and pages to keep open
- 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.
- 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.
- 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
- 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:”
- 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.”)
- 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.)
- 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.
- In the top-left is the clock, as always.
- Next to it is the display, same as it was on lab 8, but the register is in a component now.
- Next to that is the halt LED, which comes on when the programs end.
- In the top-right are the autograding outputs. Like it says, don’t change them or move them.
- To the left of those are the two memories: Instruction Memory (InstMem) and Data Memory (DataMem).
- Scattered around are the PC FSM, ALU, Reg File, and Control. These are the components you will fill in - they are all empty right now, but they are placed in vaguely good spots for them.
- At the bottom is the Multiplier unit, which I have given you.
- This is essentially the
slow_mult_4x4.circ
example, but changed to 16x16, and given the ability to load the registers with initial values. - …also it runs at double the clock speed of the rest of the CPU. lol.
- This is essentially the
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:
- In your project, double-click the ALU component on the left side to edit it.
- Open your lab 7 (yes you can have multiple things open in Logisim at the same time)
- Go into your lab 7’s ALU component, Ctrl/⌘A to select all, and Ctrl/⌘C to copy
- Use the Window menu to go back to your project
- Use Ctrl/⌘V to paste that stuff into your project’s ALU circuit
- 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:
- INPUTS:
- 16-bit
A
- 16-bit
B
- 3-bit
Operation
- 16-bit
- OUTPUTS:
- 16-bit
Result
- 16-bit
- BEHAVIOR:
- The
Result
output depends on whatOperation
is chosen:- if
Operation = 000
, then outputA + B
- if
Operation = 001
, then outputA - B
- if
Operation = 010
, then outputA & B
- if
Operation = 011
, then outputA | B
- if
Operation = 100
, then outputA ^ B
(that’s XOR) - if
Operation = 101
, then output~B
(A
is ignored) - if
Operation = 110
, then outputA << B[3:0]
(see below) - if
Operation = 111
, then outputA >>> B[3:0]
(logical, not arithmetic)
- if
- The
Notes:
- the syntax
B[3:0]
means “bits 3, 2, 1, and 0 of B”. It’s commonly used in hardware design.- So, you can use a splitter with a fan-out of 1, or a Bit Extender in this particular case.
- AND, OR, XOR, and NOT gates also have a “Data Bits” property.
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:
- 1 write port (3-bit
rd
to select the register, 16-bitREG[rd]
is the data input) - 2 read ports (3-bit
rs
andrt
to select the registers, 16-bitREG[rs]
andREG[rt]
are the data outputs) - one write enable input
- THIS is what you demultiplex, not
REG[rd]
- THIS is what you demultiplex, not
- one clock input
- 8 registers, 16 bits per register
- but register 0 is not a register - just a constant 0
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:
- INPUTS:
- 1-bit
Clock
- 16-bit
Offset
- 16-bit
Target
- 1-bit
Jump
- 1-bit
Branch
- 1-bit
Halt
- 1-bit
- OUTPUTS:
- 16-bit
PC Out
- 16-bit
PC+1 Out
(for thejal
instruction’s return address)
- 16-bit
- BEHAVIOR:
- If
Halt
is 1, the PC register is disabled. (This is backwards or inverted or negated from the normal behavior of the write enable input. HINT HINT.) - If
Jump
is 1,PC
will be set toTarget
.- Else if
Branch
is 1,PC
will be set toPC + Offset
. - Else,
PC
will be set toPC + 1
.
- Else if
PC+1 Out
should output whatever comes out of the adder.
- If
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:
- use the Register File to get the contents of one register
- use the ALU to add the contents of that register to the immediate, to calculate the address
- use the Data Memory (RAM) to load a value out of that address
- use the Register File again to put the loaded value into a register
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:
- what each part of your CPU is capable of doing, and
- how you tell it to do that (i.e. what inputs you have to give it).
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.
- 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.)
- 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 itrd_field
,rs_field
, andrt_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)
- 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!!
- Don’t waste space naming them
- Just like the slides,
- Output the register indexes.
- Create 3 3-bit outputs named
rd
,rs
, andrt
. - Connect the
rd_field
,rs_field
, andrt_field
outputs to them… for now.- We’ll come back to them later.
- Create 3 3-bit outputs named
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:
- The clock signal is needed by several components:
- The RAM (already hooked up)
- The Display unit
- The Register File
- The PC FSM
- The Multiplier (already hooked up)
- The PC FSM’s
PC Out
output goes into the ROM’sA
input.- That’s the one with the probe on it.
- The ROM’s
D
output goes into the Control’s instruction input.- Use a tunnel named
inst
or something short like that.
- Use a tunnel named
- The Control’s
rd
,rs
,rt
outputs go to the register file.- See, now the control is telling the register file which registers to access!
Some more tips:
- Use tunnels where they make sense. Tunnels let you name your wires and move the parts of your CPU around independently.
- Copy and paste tunnels when you need another of the same name. This avoids naming mistakes (e.g. naming one end
Inst
and the other endinst
, which are different names).
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:
- The bit numbers in my splitter match the bit numbers given in the ISA’s instruction format diagram. That’s really important.
- The
hlt
tunnel’s wire is lit up. That means the decoder is telling us, “this is ahlt
instruction.”- If you’re ever unsure of what the current instruction is, you can just look at this decoder’s output.
- I named my tunnels the names of the instructions.
- If you stagger the tunnels left and right like this, you can fit them in very compactly without needing lots of long wires.
Alright, let’s make the halt instruction work. It has two effects:
- the PC FSM should halt, and
- the HALT LED on the main circuit should light up.
So do this:
- In the control:
- Add a 1-bit output to the control named “halt”.
- Duplicate the
hlt
tunnel from the decoder, and attach it to that output.
- On the main circuit:
- Duplicate the “Halt” tunnel that’s connected to the Halt LED already, and connect it to the Control’s halt output.
- 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:
- How to connect the Display and the Register File together
- What should happen (the display should change)
So here’s what to do:
- 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!
- Use a dang tunnel named
- You need a new control signal.
- In the control:
- Make a 1-bit
Display WE
output - Duplicate and connect the
put
tunnel to it
- Make a 1-bit
- On the main circuit:
- make a
Display WE
tunnel - use it to connect the control’s
Display WE
output to the Display’sWE
input
- make a
- In the control:
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?
imm8
is the immediate, one of the fields of the encoded instruction. It’s one of the things coming out of the instruction splitter in your control.sxt_16(imm8)
means that immediate needs to get sign-extended to 16 bits.REG[rd] <- sxt_16(imm8)
is again telling us two things:- that immediate needs to go into the register file’s
REG[rd]
input; and - the register file’s write enable needs to be turned on for this instruction, so that the value will actually go into the register selected by
rd
.
- that immediate needs to go into the register file’s
So here’s what you’ll do:
- Add a 16-bit
imm
output to your control. For now, sign-extend theimm8
field to 16 bits, and connect that to theimm
output. (We’ll revisit this.) - On the main circuit, connect the control’s
imm
output to the register file’sREG[rd]
input.- (This will change soon, but for now it’s all you need.)
- 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.
- On the main circuit, connect the control’s
Reg WE
output to the Register File’sWE
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:
- 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.
- 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:
- load the test program into the instruction ROM
- reset (Ctrl+R or ⌘R)
- then tick the clock manually (click the button on the “clock ticker” thing)
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:
- We need to control the register file’s
rs
input differently for I-type instructions; and - 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.
- Right now, you have
rs_field
connected to thers
output. Disconnect it. - You need to make a circuit that does this:
- If the current instruction is I-type, output
rd_field
to thers
output. - Else, output
rs_field
to thers
output.
- If the current instruction is I-type, 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:
- Data bits: 16
- Select bits: 3
- First input should be the output of the ALU (trust me, this will make things much simpler later)
- Second input should be the immediate
- Third input should be… well, look on the right.
- Those are three splitters. Two have a fanout of 1 and output bits 0-7 of
REG[rs]
andimm
. The other has a fanout of 2 and combines them to produce thelui
tunnel which is used as the third input toRegDataSrc
.
- Those are three splitters. Two have a fanout of 1 and output bits 0-7 of
- Select is a 3-bit tunnel named
RegDataSrc
- Right now it’s not hooked up to anything but that will be the next thing you do.
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:
- Make a Plexers > Priority Encoder with 3 select bits
- Put a constant
1
into its first (top) input on the left- This will make the “default” data source the ALU, and trust me, that saves a lot of work when you get to the ALU instructions. (Otherwise, you would have to OR together alllllllll the ALU instructions…)
- Copy the
li
, andlui
tunnels, and hook them up as shown to the right. - Notice how the inputs to this encoder mirror the inputs to the
RegDataSrc
mux.- Input 0 (the constant
1
) makes the ALU output the “default” value to go into the reg file. - Input 1 (
li
) says “if we are executingli
, setRegDataSrc
to 1”, which causes input 1 (theimm
input) to be selected by the MUX! - Input 2 (
lui
) corresponds to the input of the MUX that combinesREG[rs]
andimm
.
- Input 0 (the constant
- The priority encoder’s output goes to a new 3-bit output named
RegDataSrc
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:
- In your main circuit, right click your program ROM component and choose “Load Image”
- Open the
.rom
file you want to run, which should be in the same folder if you followed the directions above. - 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:
- PC = 0 uses
li
to load the immediate0xC3
- which is sign-extended to0xFFC3
- intor1
- but remember that the effect of each instruction happens when you tick the clock; so this value will not actually be put into the register until you tick the clock and PC changes to 1.
- PC = 1 uses
li
to load0x29
- which is sign-extended to0x0029
- intor2
- PC = 2 displays
ffc3
on the numeric display by usingput r1
- again, you will not see the result of this
put
instruction until you tick the clock and PC becomes 3
- again, you will not see the result of this
- PC = 3 displays
0029
on the numeric display by usingput r2
- PC = 4 halts.
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:
- that register 1 holds
0xFFC3
when PC = 1- double click on the register file component on the main circuit and have a look (you should be seeing a yellow background)
- if it doesn’t,
li
is broken somehow. reset so that PC = 0 and make sure ALL of the following are true:- the register file’s write enable is turned on
- register 1 is being selected for writing (that is, the
rd
signal is001
) - the immediate value
0xFFC3
is being selected to go into the register file
- if
li
works, something’s wrong with the way the display works, or how things are connected to it.
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:
- It does
li r1, 0xEF
(which is sign-extended to0xFFEF
) - It does
put r1
(which showsFFEF
) - It does
lui r1, 0xBE
, which should cause the upper 8 bits ofr1
to change toBE
, and the lower 8 bits to stay the same -EF
- It does
put r1
(which showsBEEF
)
If it only shows 0000
for the whole test, there are some possibilities:
- The register file’s write enable is not on for the
lui
instruction - You are selecting the wrong data input for the
lui
instruction (theRegDataSrc
mux should be choosingREG[rs]
as the data input) - You are using the wrong reg file output (using
REG[rt]
instead ofREG[rs]
)
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):
0096
(add: 30 + 120
)005A
(sub: 120 - 30
)0018
(and: 30 & 120
)007E
(or: 30 | 120
)0066
(xor: 30 ^ 120
)FF87
(not: ~120
)01e0
(shl: 120 << 2
)001e
(shr: 120 >>> 2
)
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:
10101111 00001000
(this isj 0x708
) -imm
should be00000111 00001000
- if it’s
11111111 00001000
instead, you are sign-extendingtarget
. Should be 0.
- if it’s
10111111 00001000
(this isjal 0x708
) -imm
should be00000111 00001000
- same behavior as above.
10011000 00010000
(this isld r0, [r0-16]
) -imm
should be11111111 11110000
- if it’s
00000000 00010000
instead, you are 0-extendingimm5
. Should be sign.
- if it’s
10100000 00010000
(this isst r0, [r0-16]
) -imm
should be11111111 11110000
- same behavior as above.
01110000 11110000
(this isani r0, 0xF0
) -imm
should be00000000 11110000
- if… oh you get it by now.
01100000 11110000
(this isadi r0, 0xF0
) -imm
should be11111111 11110000
5. Immediate ALU: adi
, sbi
, ani
, ori
, xri
, sli
, sri
(05_alu_imm.rom
)
Again, this will display several numbers:
0050
(adi: 50 + 30
the output is hex, so decimal 80 is0x50
)0014
(adi: 50 + (-30)
)0050
(sbi: 50 - (-30)
)- If this is
004f
instead, your adder and subtractor are touching in your ALU. Separate them so thec out
of the adder is not connected to the subtractor’sb in
.
- If this is
0014
(sbi: 50 - 30
)00C0
(ani: 0xABCD & 0xF0
)- If this is
CDA0
instead, you didn’t handle the immediates as I explained above. - If this is
00A0
instead, yourlui
instruction is putting the immediate andREG[rs]
parts together in the wrong order. Swap em, and go back to thelui
test too.
- If this is
abff
(ori: 0xABCD | 0xFF
)ab32
(xri: 0xABCD ^ 0xFF
)bcd0
(sli: 0xABCD << 4
)0abc
(sri: 0xABCD >> 4
)
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.
- The first 3 instructions (PC = 0, 1, 2) load immediates into
r1, r2, r3
; - the next 3 (PC = 3, 4, 5) store into memory locations
0, 1, 2
; - the next 3 (PC = 6, 7, 8) load those values back into
r4, r5, r6
; - and the last 3 (PC = 9, 10, 11) display
r4, r5, r6
(which should show0005
,0006
,0007
).
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:
- You didn’t handle
rt
the way I said to in the previous section RegDataSrc
isn’t correctly picking the RAM output for theld
instruction
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:
- PC = 0
r1 = 8
- PC = 1
r2 = 9
- PC = 2
r3 = 2
- PC = 3
MEM[r3 + 1] = r1
address 0x03 should now hold 8 - PC = 4
MEM[r3 + -1] = r2
address 0x01 should now hold 9 - PC = 5
r3 = 3
- PC = 6
r4 = MEM[r3 + 0]
r4
should now hold 8 - PC = 7
r3 = 1
- PC = 8
r5 = MEM[r3 + 0]
r5
should now hold 9 - PC = 9 displays
r4
should show0008
- PC = 10 displays
r5
should show0009
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:
- the
Jump
control signal for the PC FSM - this should be 1 for any kind of jump - some signal saying which value to use for the jump target
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:
Jump = 1
(that is, “yes, we are jumping”)Jump Target = 0000 0000 0000 0001
(the immediate)
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.)
- If it outputs
FFFF
, that meansjal
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
, orjlr
).
- Your PC FSM’s “jump” control signal should be 1 if you are executing any of the jump instructions (
- If the PC goes “0, 1, 5, 6” but it outputs
FFFE
instead, that means yourjal
is jumping to the target correctly, it could be either:- you didn’t do the
rd
decoding right as explained in the previous control and interconnect intermission; or jal
not turning on the register file’s write enable. Time to update the control forRegWE
!
- you didn’t do the
- If the PC goes “0, 1, 5, 6” but it outputs
0000
, it could be that:- your
RegDataSrc
control isn’t choosing thePC+offs
output of the PC FSM. - that value just isn’t connected up on the main circuit.
- your
- If it loops infinitely with the PC going 0, 1, 0, 1, 0, 1…, that means your
jal
is using the wrong target. It’s probably usingREG[rs]
, when it should be using the immediate.j
andjal
use the immediate as the target;jr
usesREG[rs]
as the target. CHOOSE.
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:
- extremely common mistake: you are not write-enabling the register file for
jal
, so the return address is never saved into register 7. - if it is going into that register, then either:
jr
is not using the correct value for the jump target input to the PC FSM;- or the return address isn’t getting pushed or popped to the stack correctly. (did you break the
ld/st
instructions somehow? go back to the tests for those.)
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:
- you’ll need a new control signal that says which of the three conditions is being tested (
<
,<=
, or==
). Hmm… three possibilities… how many bits is this control signal going to be?- write down which comparison condition value means which operation so you don’t have to keep looking back at this!
- the
RegDataSrc
control needs to be updated to choose the next available input if the current instruction is any of the set instructions. (don’t use up the rest of theRegDataSrc
encoder inputs! you still need one more after this!) - the
ALUOp
control needs to be updated to do a COMPARISON for any of the set instructions.- COMPARISON!!!!!!!!!!
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:
- take the ALU’s output and the comparison condition control signal as inputs
- compare the ALU’s output to 0 (make sure that comparator is set to 2’s complement!!)
- if the comparison condition is satisfied, output a 16-bit constant 1, else output a 16-bit constant 0
- :)
- use your brain meats.
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:
r3 = 3 < 5
(slt
; this should setr3
to 1)r4 = 3 <= 5
(sle
; this should setr4
to 1)r5 = 3 == 5
(seq
; this should setr5
to 0)
It then combines the outputs of those three instructions into a single number by doing
r3 = (r3 << 2) | (r4 << 1) | r5
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:
- Reset, and tick until PC=5. Then look inside the register file by double-clicking it in the circuit.
r1
should contain0003
.r2
should contain0005
.r3
should contain0001
. If it doesn’t,slt
is broken.r4
should contain0001
. If it doesn’t,sle
is broken.r5
should contain0000
. If it doesn’t,seq
is broken.
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:
- Where do I check the branch condition? In the control? The PC FSM? The ALU?
- Definitely not in the control. Bad place for it!
- You could check the condition on the main circuit. The needed values are right there already.
- You could do it in the PC FSM too, but that might mean adding several more inputs to it, which might be ugly… but it’s your choice.
- What control signals do I need to do this…?
- Well, you need to know whether or not the current instruction is a branch (ANY branch), and then also which branch condition it is.
- There are only 2 branch conditions, so both of these signals are 1-bit. Easy.
- My branches are ALWAYS (or NEVER) branching!
- The branch should happen only when:
- The current instruction is a branch, AND (as in, use an AND gate lol) the branch’s condition is satisfied.
- It’s easy to only check for one of these and forget to check the other.
- The branch should happen only when:
- Logisim gives me an “Oscillation apparent” error and stops my simulation.
- You are doing Weird Shit ™️ with the
A
input to the instruction memory. Don’t. The current value of the PC is what goes into the instruction memory’sA
input. Yes, even for branches. You never have to change that part. Branch instructions change what the next PC is by turning on the PC FSM’sBranch
input.
- You are doing Weird Shit ™️ with the
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):
- It prints 2, since that’s the first prime
- Then, for each candidate prime starting at 3 (so every odd number lol):
- It tries dividing that candidate by every odd number less than it, using division by repeated subtraction, you know, the exponential time algorithm lmao
- If any of them divide evenly, it’s not prime and we skip to the next odd candidate
- If none of them divide evenly, it’s prime! So print it
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:
- On Canvas, go to “Assignments” and click this project.
- Click “Start Assignment.”
- 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.
- 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.