CSE 378 Homework #5: SMOKin' again

Due: 5/15/2002

Assignment Goals

In this assignment, you'll develop a single-cycle implementation of a subset of the MIPS ISA. We won't be providing you with a test oracle that will tell you if your machine is correct or not. 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.

Administrivia

You may (and are encouraged to) work with a partner on this assignment. You'll make one turnin, and get the same grade. Remember that your relationship with your partner should be one of equals -- you should both share in the work and understanding required to get the job done.

The 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.)

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

The datapath is just the one we developed in class, plus a few details related to the control units and branch instructions that you will have to figure out.

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. 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 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 and check out the online SMOK Component documentation 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. You'll have to add/widen control lines beyond the ones we talked about in class.

(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/ANDI: 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.

Solution Path

Below are some hints 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. Make sure you download the most recent version of SMOK!
  5. 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.
  6. Build a test program. First, I'd recommend testing the R-type instructions. Just write a little assembly program that exercises all of them.
  7. Test a few more instructions, like memory access (LW, SW, etc).
  8. Finally, start worrying about the control instructions. Take them one at a time, in the context of small assembly programs.
  9. Finally, build a real test program in C--. (Your quicksort program (modified), might be a good final test, but before that, I'd recomment simple programs that test specific elements, such as procedure call...)

A Word About Testing

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 below code 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!). Then you can convert your a.out into a smokmem file by using the following command: java util.Exe --smokmem a.out > a.smokmem. This should create a text file called a.smokmem, which you can load into a SMOK memory component.

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.)

A Word about I/O

So far, we've simulated input and output system calls inside of the Cebollita simulator. We don't have this luxury in the SMOK world, so we'll have to do it in a more realistic manner. Real machines (MIPS included) use Memory Mapped IO, which just means that certain memory addresses are reserved and mapped to registers/devices that actually control an I/O device. In this assignment, we give you a small container that simulates a memory mapped character device. Basically, you'll just have to wire this device into your SMOK model in the correct manner, and output should work as expected. If you add a component from a file, you can select a container to load. Double click on the container, and then check out the properties, and you'll find some basic instructions for wiring it into your model. We also provide you with C-- code that implements functions like printString, readString, printInt, etc using memory-mapped I/O. (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:
  1. prologue-smok.s: a prologue for building SMOK-compatable executables.
  2. prologue.s: a prologue for building a standard Cebollita executables.
  3. iolib.c: a library of C-- code that used memory-mapped addresses to perform I/O. Warning: This file does I/O differently than we've been doing it in Cebollita. It do I/O correctly in Cebollita -- just use the standard, simulated syscalls if you build a Cebollita executab.e...
SMOK-related files:
  1. mips.smok: the basic datapath as we developed it in class.
  2. chario.smokcont: a SMOK container that implements memory mapped output.

Deliverables

Stay tuned for the real scoop, 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.

Extra Credit

Stay tuned -- obviously there are a ton of different things you could do. The main interesting option might include modiying/extending the character device to handle input as well. Adding new instructions might be interesting too, but it would mean also modifying the compiler to take advantage of the new instructions. (This might be an assignment on its own later in the quarter!)
dugan@cs.washington.edu