Consult the Wiki page for a FAQ on this assignment.
Cebollita
, and
SMOK
, a native Windows (and so Windows-only) application.
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:
- The main control for the datapath, as a PLA.
- A separate ALU control (also a PLA).
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.)
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.
- Any instruction not listed above.
- Any ability to do IO.
- Any ability to actually do a system call (SYSCALL).
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.
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.
You need to implement control, which you do by editing the filesceb_centralcontrol.smokpla
andceb_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).
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.
SMOK
can loadCebollita
executable files (.exe
's), and will properly initialize$gp
and$sp
when thememory
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 CebollitaC--
compiler to generate much larger test programs (including using the ones that come in thecebollita/apps/...
distribution).More information on building applications for this homework can be found here.
You need to install SMOK, and to upgrade to the latest version of Cebollita. Details are here.
We provide you with a bunch of files to get you started:
- SMOK-related files:
- ceb-initial.smok: the SMOK model file
- ceb_centralControl.smokpla: skeletal central control PLA data
- ceb_ALUControl.smokpla: skeletal ALU PLA data
- Cebollita-related files:
- prologue-noos.s: explained in the section on building applications above.
- prologue-noos.s: explained in the section on building applications above.
- prologue-noos.s: does a
jal
tomain
and then anexit syscall
.
- Test Suite
- testSuite.jar: save to disk and then expand using
jar xf testSuite.jar
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.
- 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.
- (On paper) work out the truth table for the main control unit.
- (On paper) design the ALU control.
- Check your work as a team, and then implement your design: edit the skeletal
.smokpla
files to specify your control.- 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.)
- Test a few more instructions, like memory access (LW, SW, etc), and maybe the immediate format ones.
- Start worrying about the control instructions. Take them one at a time, in the context of small assembly programs.
- Build a real test program in C--. The largest ones supplied by us in the Cebollita distribution are in
cebollita\apps\quicksort
andcebollita\apps\towers
. They do IO (so issue syscall instructions).
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:
- the names of the team members, and the team name (letter)
- IF you know your machine isn't working, what you know isn't working and what your guess is about why not
- otherwise, what you've done to convince yourself the machine actually works.
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
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