CSE 378 Homework #4: Single-cycle Cebollita Machine

Due: Wednesday, 2/9/2005

Updates will be posted here:

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 (also a PLA).
• Branch control, as logic.

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 -- you won't be able to do I/O, because your machine has no I/O devices, 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.) Those test cases will be useful in this assignment, and in future ones as we expand and reimplement the machine. Some information on how to build them is given below.

The Cebollita/MIPS Subset

Fortunately, you won't have to design a machine that implement the whole MIPS ISA, nor even the entire Cebollita ISA. Instead, you need to build only a subset:

Arithmetic

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

Logic

OR, ORI, AND, XOR, SLL, SRAV, SLLV

Memory

LW, SW, LB, SB

Control

J, JAL, JR, BEQ, BNE, HALT

SLL added 2/12/05, after the assignment was completed. Needed for NOP instruction.

(* 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 Start With

We're providing a skeletal SMOK model that has (most of) the components needed for the datapath already created, as well as many of the connections between them. Additionally, control, in the form of two PLA's, is there in a skeletal form. Because it's trivial, the skeletal control fully implements the Halt instruction. It also causes the machine to halt when a SYSCALL or BREAK instruction is encountered. Note that you are not building a machine capable of executing those two instructions in this assignment. We provided the infrastructure to halt the machine just in case you make a mistake linking your Cebollita programs (as explained in the section on building Cebollita apps) or want to manually insert a breakpoint instruction into the code in memory.

Initial SMOK Model: The Datapath

The initial SMOK model has been set up in a way that encourages you to confine your work to three SMOK Containers: one holding the datapath, one containing logic that handles the update of the PC, and one that is simply a place to put the control PLA's. You might also want to add some ConstantRegisters - there is a fourth container used simply to keep them out of the way (and small). A picture is here.

You'll notice that there are more than four containers (the large, light grey rectangles) in the model. The others are there just to indicate why you are using containers -- later assignments will require additional circuitry that we intend go in those "extra" containers. You can delete the extras for now if you want and your screen is large enough to make the connection points available when both Containers are "collapsed", but remember that (a) you'll need add many more components later, and (b) there is no simple way to move components from one container to another in SMOK (you basically have to delete them and create them anew, or else edit the .smok file).

Containers are not functional parts of the circuit, they're just ways of organizing the components on the screen. You can connect directly between components in different containers, if you want, or you can create input/output "passerelles" components that interface what's inside a container with everything outside. (The passerelles are simply connectable components large enough to click on when a container is not expanded, unlike the connection points on the other components within the container. When you run SMOK, you'll see what I mean.)

Double-clicking on the background within a container expands it, making it easier to work on. A picture of the expanded data path container is here. A picture of the expanded PC control container is here.

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 FUNC field of the 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. field.

Note that, if convenient to your implementation, you can edit the meanings of the ALU control lines in SMOK to alter which control line values correspond to which ALU operations.

Initial SMOK Model: Main Control Unit

The skeletal control unit takes simply the OPCODE instruction field as input. That (plus use of the ALU control) is enough for it to do the little bit that is implemented now -- halting the machine on HALT, SYSCALL, and BREAK instructions. Your full implementation of control will undoubtedly require additional field(s) from the instruction, as it will be doing more complicated things. For example, it will need to emit signals to control many of the MUXes, as well as we the write enable lines on RegisterFile and MemoryInterface.

Read the relevant section of Appendix B and C to learn more about PLAs. 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.

Implementing 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. JR needs to set the next PC to be the contents of register RS. This is the part of the assignment where your team will have to do some thinking and sketching before implementing it in SMOK.

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

What You Are Not Implementing

• Any instruction not listed in the table at the top of this writeup.
• Any ability to do IO.
• Any ability to do a system call (SYSCALL), an idea we won't even have talked about until about when this is due.

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. (You can draw all the components as in the pictures in the book, not worrying about the SMOK Containers.) 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 think 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 as a team, 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 an initial test program in assembly. I recommend starting with just one or two R-type instructions. Make sure they work.
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. Aim to end up with an assembly language test program that tests all instructions types and opcodes, so long as "most instructions are working". As explained next, you won't actually be able to run that full-blown test program until late in this assignment, but it will be useful in the next three assignments (making sure you haven't broken anything).
9. Build a real test program in C--. The largest one supplied by us in the Cebollita distribution is in cebollita\apps\quicksort. However, it does IO.

The Test Program/Suite

Ideally, your exhaustive test program can issue an instruction, then check to make sure it got the right result, and halt if not. By looking at the PC when the machine halts you can tell if your processor implementation passed the test (because it halted at the end). If not, which Halt it stopped on will tell you which test it failed.

There is a little glitch in that plan, though. If no instructions are known to execute correctly, how can you rely on the test program working? The answer is, you can't. You'll have to start with assembler programs consisting on only a couple of instructions and verify by stepping through your program that those instructions work. The test program I described above can't be used until at least some kind of conditional branch works. Because those are among the hardest things to get right, you might start with straightline code that tests a number of instructions, putting the result of each in a different register, and then halting. Examining the registers when you halt should show where there are problems.

Remember that it's possible to debug your test program(s) (i.e., that software, which needs debugging just like any other software) while the machine is being implemented, using the Cebollita simulator. It would be good to verify that the test program doesn't itself have a bug, so that you don't misinterpret a software mistake as an error by the hardware (SMOK) implementation.

Building (Compiling/Assembling/Linking) Test Programs

SMOK understands the Cebollita executable format, and will set up $gp and $sp when the memory component (re)loads the associated contents file.

Simple Test Programs

Your first test programs will be just a couple of instructions. For example, you might have this:

.text
          .global  main
main:     add     $t3, $t2, $t1
          halt

You won't have jal implemented, so you won't be able to use a real prologue to link with this. However, __start is not defined, causing the linker to complain.

One way to solve this problem is to link with cebollita\apps\prologue-standalone.s:

# 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: 

That satisfies the linker, but doesn't create any instructions at all.

Alternatively (and equivalently, in terms of the .exe that is produced), you can just create the symbol __start in your .s file and not link with any prologue:

.text
         .global  __start
__start:  add     $t3, $t2, $t1
          halt

More Complicated Programs in HW4

Suppose you write a test program in C--. You have a main function, because that's where execution starts. And, suppose you're pretty sure you have jal and all the other instructions working.

You can link your C-- program with prologue-noos.s (supplied in the files section of this writeup):

# 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

Note that it uses the Halt instruction to stop, so doesn't need an OS.

SMOK Tips

• SMOK is a Windows-only appplication.

• You can add Halt components to your SMOK model to act as something like breakpoints -- add a Halt that stops when the PC has a particular value to get the garden variety breakpoint, for instance, or add one to stop whenever whatever condition you're worried about occurs.

• The initial model has a Halt component is "triggered" by the initial PLA settings when a BREAK instruction is fetched. So, you can put breakpoints in the software as well.

• The operations of PLA's are controlled by .smokpla files, which must be edited externally to SMOK. You can cause a PLA component in a running instance of SMOK to re-read its PLA file by reinitializing the SMOK model. (The memory component will re-read whatever file you loaded into it as well.)

The Files

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

SMOK-related files:

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

Cebollita-related files:

1. prologue-noos.s: explained in the section on building applications above.

Deliverables

We'll once again use the turn-in program.

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 short (under a page should do it) writeup telling us:

• the names of the team members, and the team name (letter)
• IF you know your machine isn't working, what isn't working and what your guess is about why not
• 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 hw3.tar. To make this file, enter cygwin, navigate to the directory with your files and use the following command:
   
    tar cvzf hw3.tar.gz  <files to include>


for example:
    
    tar cvzf hw3.tar.gz  *.smok *.smokpla *.c *.s mywriteup.txt