CSE 378 Homework #6: Single-cycle Cebollita Machine

Due: 2/21/2003
Work in pairs or individually

Updates will be posted here:

2/11/03: You must use V5.x of SMOK, and V1.4 of Cebollita. These have been installed for the lab machines. Report problems to zahorjan@cs.
2/13/03: The memory mapped I/O portion of the assignment is now in place.

Assignment Goals

In this assignment, you'll develop a single-cycle implementation of a subset of the Cebollita ISA, itself (almost) a subset of the MIPS ISA. We'll provide you with a datapath; you'll build various aspects of control:
• The main control for the datapath. We suggest using a PLA.
• A separate ALU control.
• A memory mapped character I/O subsystem. We suggesting placing this in a Container component.

When you're done, you'll have a processor that is capable of executing the kinds of Cebollita programs we've built so far. You can use Cebollita to generate complicated test cases, in fact. (Part of this assignment (and all real-world projects) is convincing yourself that your implementation works. You'll do that through a combination of testing and reasoning.)

The Cebollita/MIPS Subset

Fortunately, you won't have to design a machine that implement the whole MIPS ISA. Here's the subset:

Arithmetic

ADD, ADDI, SUB, MULT*, DIV*, SLT

Logic

OR, ORI, AND, XOR, SRAV, SLLV

Memory

LW, SW, LB, SB

Control

J, JAL, JR, BEQ, BNE

(* Remember that MULT/DIV have been simplified to look like regular R-type instructions.) The instruction encodings are given in the relevant Cebollita documentation. Note that you have to build only a subset of the instructions listed there for this assignment.

Is this subset enough to get anything interesting done? Yes. In fact, the Cebollita compiler limits itself to this subset as well, so you will be able to use it to build real benchmarks and test programs for your machine.

The Datapath

A picture is here. The datapath as a SMOK input file is linked near the end of this assignment.

ALU Control

The ALU control unit needs to tell the ALU what operation to perform on each cycle. The ALU control decides how to do this based on two inputs. The first comes from the main control unit, the second comes from the FUNC field of the instruction. Why two inputs? Because sometimes the main control unit has enough information to determine exactly what operation the ALU should perform. For instance, on a LW, the main control unit knows that the ALU should do an addition (since it's used to compute the effective address). We'll use a scheme similar to the one in the book, but extend it a bit. ALUop 0 means ADD, ALUop 1 means subtract, ALUop 2 means OR, ALUop 3 means that the decision should be based on the contents of the FUNC field.

For R-type instructions, the FUNC field needs to be inspected. While there is no obvious and direct mapping from the MIPS func field to ALU control signals, it can be done with a minimum of bit-twiddling and logic. (HINT: exploit the fact that you can edit meanings of the ALU ops in SMOK.)

Main Control Unit

The main control unit takes the OPCODE and FUNC field as input, and needs to output control signals to the register file, memory interface, and a variety of multiplexors. Implementing this function in basic logic elements is a painful and error prone process. To make your lives easier, we've provided you with a PLA component, that essentially lets you express the truth table for the logic function your control unit implements. Your job, then, is to carefully determine the truth table and then wire the outputs of the PLA to the correct destinations.

Read the relevant section of Appendix B and C to learn more about PLAs. Check out the online SMOK Component documentation, and look at the examples for the stack machine in this class handout, to figure out how to specify the operation of your PLA.

Control & Immediate Instructions

Branches and Jumps: By far the most difficult element of the assignment will be getting branches (BEQ and BNE) and the three jump instructions working correctly. Rememember, JAL needs to dump the PC+4 into register 31. (Meaning that the RegDst mux will have an additional input, as will the Data2Reg mux.) JR needs to set the next PC to be the contents of register RS. This is the part of the assignment where you (and your partner) will have to do some thinking and sketching before implementing it in SMOK.

(HINT: For handling jumps, it's easiest (probably) to add a 2-bit control line to a 3-way MUX. This mux selects between the value produced by the branch logic (00); a value from the register file (for JR, 01); and a value taken from the instruction itself (for JAL and J, 10).

ORI/ADDI: It seems redundant to have both of these instructions; however, ORI has the nice quality that it does NOT sign-extend its immediate operand. This makes it useful/convenient for generating large constant values. The upshot of its inclusion is that the ALUSrc MUX will now take 3 inputs: a register value (for R-types), a sign-extended immediate (for memory ops and ADDI), and a non-sign-extended immediate (for ORI). Again, the inclusion of this instruction will impact your control equation.

Memory Mapped I/O

This is described in a separate page.

Solution Path

Below are recommendations to get you towards a solution. Your main strategy should be to understand the issues on paper (and in your brain) before you start SMOKing.
1. (On paper) draw the extended datapath and muxes for all of the instructions. Pay special attention to the control instructions (BEQ, BNE, J, etc.). Simulate them in your head and by hand to see if the datapath makes sense.
2. (On paper) work out the truth table for the main control unit.
3. (On paper) design the ALU control. Look at the different FUNC fields and thing about how you can map them to ALU operations. If you do it right, your ALU control will be pretty tidy.
4. Check your work with your partner, and then implement your design in SMOK -- this should be a really mechanical process if you've done your thinking ahead of time. Connect all of your wires and you should be ready to go.
5. Build a test program. First, I'd recommend testing the R-type instructions. Just write a little assembly program that exercises all of them.
6. Test a few more instructions, like memory access (LW, SW, etc).
7. Start worrying about the control instructions. Take them one at a time, in the context of small assembly programs.
8. Build a real test program in C--.
9. Finally, build your memory mapped character IO device. Test it using either some simple .s file that reads/writes to the mapped locations, or use SMOK DebugInput components to provide inputs for testing. When it seems to work, write a C-- program that does IO to verify on more complex cases.

Running Test Programs

Initially, you'll want to build very simple assembly programs that just test the set of instructions you're interested in. You can use the code below as a template for testing your instructions. (The first line, which sets the global pointer is important, for reasons that will become clear later. The upshot of this restriction is that ORI is probably the first instruction you'll want to get working...).

.text
__start:   ori  $gp, $0, 0
           addi $t0, $0, 10
           add  $t1, $t0, $t1

You can assemble and link the above program in the usual manner (no other .o files are necessary, it's a standalone program that does nothing!).

Once you have built the a.out file, you can load it directly into the SMOK memory componentSMOK memory component in the usual way (i.e., through the properties dialog). Note that you may have to change the file extension filter on the open file dialog to find your executable.

Later, you'll want to build "real" programs that test the whole machine. To build a test program of this kind, you should be able to use the Cebollita tools, with a few minor changes.

1. You'll want to use a different prologue (a small series of instructions that kicks off your main function) -- why? Because we want prologue code that will set the global pointer as above.
2. You'll link your program in the standard manner, but against the modified prologue, like so: java asm.Linker prologue-smok.o yourfile.o etc.o.
3. After you've built an a.out, you need to turn it (which is in binary format) into a text file. Use util.Exe (as above) to do this. (The --smokmem flag is important; it causes the utility to patch the first instruction in the prologue, which sets up the global pointer.)
4. If you want to test your test program in the Cebollita simulator, you'll need to use the "standard" prologue that we've used in past assignments. (See below for a link to the code.)

The Files

We provide you with a bunch of files to get you started:

Cebollita-related files when running on a machine built in SMOK:

1. prologue-smok.s: a prologue for building SMOK-compatable executables.
2. iolib.c: the I/O library (that implements readString(), readInt(), printString(), and the like).

Cebollita-related files when running on Cebollita's own simulator:

1. prologue.s: a prologue for building SMOK-compatable executables.
2. iolib.c: the same IO library as with SMOK

SMOK-related files:

1. mips.smok: the basic datapath

Deliverables

As usual, we'll announce details later. But, you can guess that we'll want you to turn in your SMOK model, as well (possibly) as benchmark/test programs you tested your model on. We'll also ask you to turn in a short writeup telling us (specifically) how you tested the various aspects of your design, and how much of the instruction set you implemented successfully.