CSE 378 Homework #4: Single-cycle Cebollita Machine

Due: Thursday, 2/9/2006

Consult the Wiki page for a FAQ on this assignment.

Assignment Steps

  1. Read through this assignment.
  2. Decide if you want to work with one or more partners. (Teams of up to three are fine, but my feeling is that a team of two will be less work than a team of three.) If you do, arrange your team and then send mail to the course staff (all of us) with the names of the people on your team.
  3. Individually, set up the tools you'll need: a new version of Cebollita, and SMOK, a native Windows (and so Windows-only) application.
  4. Read through the assignment again, and experiment with the skeletal processor implementation.
  5. Implement and test your processor.

Assignment Overview

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 complete datapath; you'll build the control:

When you're done, you'll have a processor that is capable of executing some of the kinds of Cebollita programs we've built so far -- your processor won't be able to do I/O, because your machine has no I/O devices (and there's no operating system running on it), but everything else will run. This means that you can use Cebollita to generate complicated test cases. (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 entire MIPS ISA, nor even the entire Cebollita ISA. Instead, you need to implement only this subset of the Cebollita instruction set:
Arithmetic
ADD, SUB, MULT*, DIV*, SLT
ADDI, SLTI
Logic
AND, OR, XOR, SLLV, SRLV, SRAV
ORI
Memory
LW, SW, LB, SB
Control
J, JAL, JR, BEQ, BNE
Special
HALT, BREAK, SYSCALL, SLL

For the instructions in blue, your implementation must "do no harm." SLL can be implemented as a no-op -- the compiler uses it only for the nop instruction. (It is naturally a no-op, with no work on your part, because it's (a) an R-type instruction, and (b) specifies $0 as the destination register.) BREAK and SYSCALL can either be implemented as no-ops, or can halt the machine, depending on what method you use for debugging (see Tool Setup and Use below).

(* Remember that MULT/DIV have been simplified to look like regular R-type instructions. Other changes from the Mips are noted in the Cebollita documentation.) The Cebollita instruction encodings are given in the relevant Cebollita documentation.

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.

What You Are Not Implementing

Despite this, there is a way to see IO happen (it's just that your processor won't be doing it). The Tool Setup and Use section tells you more.

What You Start With

We're providing a SMOK model that has a complete data path, including all connections among data path components and to the two control PLAs. Additionally, control, in the form of definition of the function of the PLAs, is there in a skeletal form.

The data path is "complete" in the sense that it has been used to build a completely functional processor. That's a demonstration that you do not need to change it to get a working processor. You are free to do so, though, if the existing data path dosn't make sense to you or you simply prefer another way of doing things.

Initial SMOK Model: The Datapath

The initial SMOK model has six "containers", but components only in four of them. The other two are there as placeholders for the next assignment. (You can safely delete the empty containers now if they annoy you.) A picture is here.

One SMOK container holds the main datapath elements. Another contains the PC and the components required to update the PC. A third holds the PLAs, as well as a Stop component (used to implement, for example, the Halt instruction). The final one holds some constant registers.

SMOK containers are not functional elements; they are simply a way to help organize the components of the machine visually, and to deal with limited screen real estate. Double-clicking on the background within a container expands it, making it easier to work on. The large up arrow in the toolbar at the top gets you back to the main screen (as does Ctrl-u). A picture of the expanded data path container is here. A picture of the expanded PC control container is here. The connections in red are control connections, eminating from the PLAs.

This initial model, as a SMOK input file, is linked near the end of this assignment.

Initial SMOK Model: 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 low order bits of the instruction (the FUNC field, if it's an R-type instruction).

Why two inputs? You clearly need the FUNC field of (most) R-type instructions, because it, not the opcode alone, determines what ALU operation to perform. On the other hand, you also need to know that the instruction is one for which the FUNC field is meaningful, something determined by the other control PLA.

Note that, if convenient to your implementation, you can modify the ALU component to alter which Op control line values correspond to which ALU operations: right-click on the ALU and choose Edit ALU Ops.

Initial SMOK Model: Main Control Unit

The skeletal control unit takes simply the OPCODE instruction field as input. That (plus use of the ALU PLA) is enough to implement all the instructions. However, if you want to provide additional inputs to your PLA, go ahead and do so.

(Read the relevant section of Appendix B and C to learn more about PLAs, if you'd like. There is more information in the online SMOK Component documentation, and an example using PLAs (to build a "stack machine") on this page.)

Initial SMOK Model: R0 == 0

The Cebollita ISA (like the MIPS) says that R0 is 0 even if an instruction is executed that tries to write to it (e.g., ori $0,$0,1). SMOK provides a simple way to guarantee this - the RegisterFile component can be set to enforce this behavior. The RegisterFile in the inital model distribution has this behavior set.

What You'll Do

You need to implement control, which you do by editing the files ceb_centralcontrol.smokpla and ceb_ALUControl.smokpla. The SMOK PLA component, and more information on the format of the .smokpla file, can be found on the SMOK component reference guide page for the PLA, as well as on this page.

More general information about control and PLAs can be found in Appendix C of the text (which, unfortuantely, is on CD).

Implementing Control & Immediate Instructions

Branches and Jumps: Perhaps 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 put PC+4 into register 31. JR needs to set the next PC to be the contents of register RS.

ORI/ADDI: It may seem redundant to have both of these instructions in the instruction set; 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 takes three inputs: a register value (for R-types), a sign-extended immediate (for memory ops and ADDI), and a non-sign-extended immediate (for ORI).

SRLV/SRAV: One sign extends, one doesn't. Shifting is done by the ALU. It has a right shift operation ('>>'). Whether or not to sign extend is controlled by the IsL ("is logical") input: 0 for sign-extend, 1 for 0 insertion.

Building (Compiling/Assembling/Linking) Test Programs

SMOK can load Cebollita executable files (.exe's), and will properly initialize $gp and $sp when the memory component (re)loads the associated contents file. (To load a .exe into memory, right-click on the memory component, then Properties, then the ellipsis to the right of the Loaded From File textbox.) That means you can, and should, use the Cebollita assembler at first to create simple test cases for your processor, and then, once you think all instructions are working, use the Cebollita C-- compiler to generate much larger test programs (including using the ones that come in the cebollita/apps/... distribution).

More information on building applications for this homework can be found here.

Tool Setup and Use

You need to install SMOK, and to upgrade to the latest version of Cebollita. Details are here.

The Files

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

SMOK-related files:
  1. ceb-initial.smok: the SMOK model file
  2. ceb_centralControl.smokpla: skeletal central control PLA data
  3. ceb_ALUControl.smokpla: skeletal ALU PLA data

Cebollita-related files:
  1. prologue-noos.s: explained in the section on building applications above.
  2. prologue-noos.s: explained in the section on building applications above.
  3. prologue-noos.s: does a jal to main and then an exit syscall.

Test Suite
  1. testSuite.jar: save to disk and then expand using jar xf testSuite.jar

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. Start by making sure you understand the data path: what are the components used for, for each instruction type? what are the control lines, and why are they needed? Pay special attention to the control flow 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.
  4. Check your work as a team, and then implement your design: edit the skeletal .smokpla files to specify your control.
  5. Build an initial test program in assembly. I recommend starting with just one or two R-type instructions. Make sure they work. (We provide some test programs you can use if you like. We don't guarantee that executing them correctly means your processor is 100% bug free, however.)
  6. Test a few more instructions, like memory access (LW, SW, etc), and maybe the immediate format ones.
  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--. The largest ones supplied by us in the Cebollita distribution are in cebollita\apps\quicksort and cebollita\apps\towers. They do IO (so issue syscall instructions).

Deliverables

We'll use the turn-in program (really!).

We'd like your SMOK model and PLA files, as well as whatever test programs you tested your model on.

We also would like a file containing:


Plus put the writeup in some format we can easily read (of which text is the least likely to be portable): Word, PDF, or text if necessary.

Please submit files in a tar file hw4.tar. To make this file, enter cygwin, navigate to the directory with your files and use the following command:
   
    tar cvzf hw4.tar.gz  <space separated list of files to include>

for example:
    
    tar cvzf hw4.tar.gz  *.smok *.smokpla *.c *.s mywriteup.pdf

Turnin

To turnin your solutions, please login to attu, navigate to the folder containing your hw4.tar.gz file and type:
    
    turnin -c cse378 -p hw4 hw4.tar.gz