CSE 378 Homework #4: Single-cycle Cebollita Machine

Due: Monday, 5/4/2009, 11:00PM

Assignment Steps

  1. Read through this assignment.

  2. You can work on this and the next assignment either alone or with a partner. We'd like the common cases to be either working alone on both or working with the same partner on both, but you're free to follow another path. If you work with a partner and want shared file space, it will take a while (up to a day) to make that availablle to you.

    If you want to work with a partner AND want shared file space, try to find your partner quickly and then send mail to the course staff (all of us) with the names of the people on your team. We'll get back to you with a Unix group name and a path to your shared file space. (The group name is probably irrelevant to you, but the group is needed to give you access to the space.)

  3. Individually, decide where you want to do your work, and make sure the tools you need are set up there. The tools are Cebollita and SMOK. SMOK is a native Windows (and so Windows-only) application. It is already installed on all the lab desktops, as well as on aria.cs.washington.edu (a windows terminal server, allowing remote logins). You can also download and install it on your personal Windows machine.

  4. Read through the assignment again, and experiment with the skeletal processor implementation.

  5. Implement and test your processor.

  6. Turnin your assignment.

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.) You can build test cases in assembler, just as you have been, or in C--, Cebollita's implementation of a very pared down C language. (The C-- compiler produces assembler files, which you then assemble and link using the techniques you're accustomed to.)

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. (As emitted by the compiler, 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 in Cebollita 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. Be careful to use the Cebollita documentation as the definitive statement for both the encoding and operation of each instruction. You can looks at text, and the MIPS documentation, as well for clarification, but if there are disagreements, Cebollita wins.

Is this Cebollita subset enough to get anything interesting done? Yes. In fact, the Cebollita C-- 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.

The SMOK input file defining this initial model 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 D 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 with Cebollita in the .../cebollita/apps/... directory).

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:
These files are also available from your Cebollita distribution, in directory .../cebollita/apps/prologues/.
  1. prologue-standalone.s: explained in the section on building applications above. 
    # The null prologue, which leaves the user-written code at PC=0
# but satisifies the linker by having a __start: symbol
.text
	.global __start
__start:
  2. prologue-noos.s: explained in the section on building applications above. 
    # The Cebollita ISA simulator's loader has set things up so that on entry:
#	$gp = size of text segment
#	$sp = text size + data size + heap size + stack size - 4
#	$pc = entry point (presumably __start here!)
.text
	.global __start
__start: jal	main
	halt
  3. prologue-os.s: requires a system that is running the Cebollita OS: 
    # The Cebollita ISA simulator's loader has set things up so that on entry:
#	$gp = size of text segment
#	$sp = text size + data size + heap size + stack size - 4
#	$pc = entry point (presumably __start here!)
.text
	.global __start
__start: jal	main
	ori	$v0, $0, 10             # exit
	syscall

Test Suite
  1. testSuite.jar: save to disk and then expand using jar xf testSuite.jar.
    These are really just files of consecutive instructions, i.e., they don't do anything coherent. They're just ways to test out individual instructions. Each includes the symbol __start, so they do not need to be linked with a prologue. (We do that so you don't have to have jalworking to use these test programs.)

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 using SMOK.
  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, 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

Turn-in is online.

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). PDF is nice.

Turnin

Turnin is online.