CS270 Recitation 22: The eLC-3 (Even Littler Computer 3)

What to turn in

Goals

1. To practice implementing a finite state machine controller.
2. To understand the basics of how data moves in a processor.

The Assignment

Start from the following files that provide a partial implementation of eLC-3 that you will complete. Read this entire document before panicking.

• eLC-3.circ contains the skeleton implementation you must complete
• truthtable.xlsx shows a partial truth table for the implementation
• elc3statediagrampartial.png provides a partial state diagram
• elc3statediagrampartial.html provides a partial state diagram that you can save and open with http://draw.io
• test.asm is a simple assembler program you can execute after implementing NOT.
• test.hex is assembled object code you can load after implementing NOT.

You will complete the design and implementation of the eLC-3. The eLC-3 only supports the following instructions:

• NOT
• ADD (both in register and immediate mode)
• AND (both in register and immediate mode)
• BR (both conditional and unconditional)
• LD
• ST

Grading

There is one submission for this assignment:

1. R22 is a complete submission via Checkin that must pass final testing. It should implement all of the instructions. There is no preliminary testing.

This assignment will be auto-graded. Don't change anything on the eLC-3 datapath circuits. Don't change the input or output sections on the eLC-3 controller. You should only change the logic circuits on the eLC-3 controller to support instruction fetch and decode, state transitions, and control signals generated. Pay attention to the notes inside the input, output, and reserved sections.

eLC-3 Datapath

Here's the datapath for the eLC-3. The ADDR1MUX, ADDR2MUX, MARMUX, and GateMARMUX logic have been replaced by GateOFFSET and GateREG.

In the skeleton file, you'll find two circuits: eLC-3 and Controller. The eLC-3 circuit is just the Logisim implementation of the datapath shown above. You don't have to (and must not) do anything to this circuit, so don't be intimidated by it. Initially, you will see a lot of blue and red wires. That's because you must complete the Controller circuit. Notice the FSM chip next to the clock? This is an instance of the Controller circuit. This circuit is the state machine that controls the movement of information in the datapath. You will be completing the implementation of the FSM circuit.

In the previous assignment, you dealt with state machines with one bit for the input and one bit for the output. The state machine in this assignment is richer. The inputs are the IR and the CC. The outputs are the control signals. You must complete the state machine:

• The fetch stage for all instructions must take exactly 3 cycles.
• The ADD (both modes), AND (both modes), NOT, and BR(hit) instructions must finish in exactly 1 additional cycle. How many additional cycles are necessary if the branch is not hit?
• The LD and ST instructions must finish in exactly 3 additional cycles.

The state machine is a Mealy machine: the output is simply a function (implemented using combinational logic) of the current state and the input. The solution only requires 7 states, so it's not a gigantic state machine. The 3 state bits provided in the controller are sufficient for your implementation. You should complete the truth table before implementing the circuit. Once the truth table is complete the circuit can be implemented in a very mechanical way we have use to implement smaller FSM. Refer to the LC-3 visualization or state diagram for details about the LC-3.

Do not introduce a clock in your state machine. Instead, use the CLOCK input as the clock. This input is connected to the clock in the datapath. Also, use only elements from the Wiring and Gates libraries.

As intimidating as it looks, the layout of the Logisim datapath is very close to the picture above. Here are some details that you need to know about the datapath:

• Notice that your state machine doesn't have to take care of SR1, SR2, and DR. We handle these signals for you in the datapath. If you really want to know, SR1 is IR[11:9] for the ST instruction and IR[8:6] for the other instructions. SR2 is IR[2:0] for all instructions (of course it's only relevant for ADD and AND). DR is IR[11:9] for all instructions (it's only relevant for the arithmetic instructions and for LD).
• Here's the reference for some control signals that may not be obvious:
  • ALUK: 00 for +, 01 for &, and 10 for ~
  • MEM.RW: 0 for reading and 1 for writing
  • MIO.EN: 0 if what's going to be loaded into the MDR comes from the bus. 1 if it comes from memory.
  • PCMUX: 0 if what's going to be loaded into the PC comes from the PC offset adder. 1 if it comes from the PC incrementer.
  • SR2MUX: 0 if the second operand for the ALU comes from SR2. 1 if it comes from SEXT(IR[4:0]).

Testing

We will test your submission by loading a program in memory, running it, and inspecting the result. You can do the same. Suppose you wanted to test the following program, test.asm, after you have completed the instruction fetch and NOT instruction:

.ORIG x0000
NOT R2, R1
.END

First, notice that I'm using x0000 instead of the usual x3000 for the .ORIG. This is because it's not easy to load the program in a location other than x0000 in the eLC-3.

Let's assemble this into a format that Logisim can understand. Use the following command (you may need to adapt it to your environment):

~cs270/lc3tools/lc3as -hex test.asm && sed -i "1s/.*/v2.0 raw/" test.hex

This generates the following file, test.hex:

v2.0 raw
947f

Notice that 947f is just the hexadecimal translation of NOT R2, R1. Now, go to the eLC-3 circuit in Logisim. Right click on the memory element and select Load Image. Select the test.hex file. This populates memory with your program.

Now click on the CC register and change its value to 2. For this program, this is not needed. However, if the first thing in your program is an unconditional BR instruction, it is necessary for the CC to be set to something that is not 0 so that it actually branches.

You may also want to change the value of R1 so that you can check that R2 eventually becomes ~R1.

When you're ready to run your program, click on the clock twice. This makes the clock go high and then low. This is one cycle. Check if the expected register transfers occurred. Keep repeating until the program is completed and check that the registers end up with the right values. You can always check the value present on a wire by clicking on it with the hand tool.

Now that you read the entire document, you may panic at will. :-)

Submitting the Assignment

When finished, submit your eLC-3.circ file to the R22 box in the Checkin tab.

R22 will be worth 120 points and counted as an assignment