The goals of this problem set are many and varied. First, and most basic, it will teach you the basics of writing and debugging assembly language programs. Second, because your program is a machine simulator, you will learn (1) the workings of a simplified execution cycle, (2) how instructions in the main instruction categories actually work, and (3) the notion of separating the hardware in the simulator you are designing (378) from the hardware in the simulator you are using to execute your code (SPIM). And because the simulator is a *stack* machine simulator, you'll be able to apply the general model of a stack that you learned in cse143 to a particular arena, computer architecture. And lastly, because writing code in assembly language requires you to design algorithms at a lower level than is done when programming in a source language, you will learn the guts of jump tables, implementing them, not simply using them.
First, as a warm-up exercise, do problems 3.2 and 3.6 in the book. This will give you a chance to read and interpret someone elses's code (3.2) and correct someone else's bugs (3.6) before tackling your own. :-) Do the first exercise on paper, without using the SPIM simulator. The second can be done with the simulator. Both should be handed in.
Now you're ready for the main assignment!
The assignment is to write a program in MIPS assembler that is a simulation of a very simple computer. I'll first present the operation of the machine you'll be simulating, and then describe what you have to do.
The machine you'll simulate (called the 378 machine) is a 32-bit machine with an extremely simple architecture. There are only twelve instructions and no general purpose registers. Instead, register storage is organized as a stack of 32-bit integers, and all instructions refer to the top of the stack for operands. The 378 CPU has an internal register, the stack pointer (SP), to keep track of the top of the stack. The user's program can affect the SP only indirectly, by adding data to or removing data from the stack. There is also a separate memory to hold instructions, which is addressable only through the 378 PC, and a separate memory for data. In reality, of course, there is a only one memory on microprocessors which holds both. In this assignment there are two memories, just to make the coding a little easier for you and to correspond to some of the discussions on implementation (chapter 5) in the text book.
The table below lists the set of instructions available (as well as some other info which will be explained shortly). A user of the 378 machine would write a program using those instructions. (In other words, the input to your program is a 378 program.)
| Opcode | Operation | Example | Meaning |
|---|---|---|---|
| 0000 | Stop | 0x00000000 | Stop the program |
| 0001 | Add | 0x10000000 | Add |
| 0010 | Sub | 0x20000000 | Subtract |
| 0011 | Mult | 0x30000000 | Multiply |
| 0101 | Bgtz | 0x5000000C | Branch-greater-than-zero: PC := PC + 12 if stack top > 0 |
| 0110 | Bez | 0x60000010 | Branch-equal-to-zero: PC := PC + 16 if stack top == 0 |
| 0111 | Jump | 0x70000000 | Jump to addr in top of stack: PC := code + Stack Top |
| 1000 | Load | 0x80000000 | Load memory to stack top |
| 1001 | Store | 0x90000000 | Store from stack to memory |
| 1101 | Clear | 0xD0000000 | Clear the stack |
| 1110 | Push | 0xE0000003 | Push 3 onto the stack |
| 1111 | Show | 0xF0000000 | Show the stack top |
378 instructions are encoded as 32-bit values. The high order four bits (bits 28 through 31) specify the opcode, as shown in the table. In all instructions other than Load, Store and Push, the low order 28 bits are ignored. In the Load and Store instructions, the low 28 bits are used for the branch offset; in the Push instruction, the low order 28 bits contain a signed integer.
A 378 program lives in the 378 instruction memory, which is separate from the data memory. By a process we'll leave unspecified, a program is loaded in the instruction memory and the 378 PC is set to the first instruction. The machine then goes into a fetch-increment-execute loop: it fetches the instruction specified by the PC, increments the PC to point to the next instruction, and then performs the operation given by the instruction just fetched.
Stack-based architectures have a long history; today, however, they've mostly fallen out of style, in favor of register-based machines. The big exception is the Java Virtual Machine, which defines a stack-based architecture for executing java programs.
Your program, a 378 simulator, needs to allocate memory for the 378 instruction and data memory and the stack of registers. The stack is just an array of MIPS words. Program and data memory are also arrays of MIPS words, but initialized to contain a valid 378 program or input data, respectively.
We've supplied you with a template to use in writing your program (note that this incorporates what used to be the second template, code.spim):
378.spim contains a template for writing your 378 machine. It also includes a sample 378 program. You should write all of your MIPS assembly code in 378.spim. You will need to add code to allocate data memory space and the stack for your 378 machine, as well as pretty much all the code required to implement your machine.
Please note: you should write your 378 machine to assume that the base of the array of instructions is represented by the symbol code. Failure to do so will require me to edit your code to test it, a bad thing.
Your code must also find a place to keep the 378 PC and SP. Because those values are small, and are used frequently, you should choose MIPS registers to hold them (i.e., they are stored throughout your program in registers dedicated to that purpose).
The basic structure of your code mimics the fetch-increment-execute cycle of the 378 CPU. Basically, your program is a loop. At the top of the loop, it fetches the next 378 instruction into a MIPS register, and then increments the 378 PC to point at the next 378 instruction. Your program now figures out which kind of instruction you have just fetched, fetches the top two elements from the stack for most of the instructions, and then performs the required operation.
If you were writing this program in C, your program would probably contain a switch statement on the 378 instruction opcode, and with twelve cases corresponding to the twelve instructions. To achieve this effect in your MIPS program, you should use a jump table. The textbook talks about jump tables on page 129. The basic idea is to allocate a table of addresses (in MIPS memory), load an element of the table given by an index (in your case, the 378 instruction opcode) into a register, and then perform a MIPS jr instruction to get you to the correct section of MIPS code.
This program isn't very long, and isn't very complicated, so you shouldn't find yourself spending painfully large amounts of time on it. You'll see, though, that programming in assembler is somewhat more inconvenient than programming in a higher level language, like C or C++. (Try to imagine how long it would take you to write a big program in assembler.)
If your template (378.spim) does not include the label code: in the data segment, then you should get a new copy or get code.spim and insert it at the top of your 378.spim file, removing the redundant .data line (there should be one at the top of the file).
Please note: Your 378 machine should assume that the symbolic name code (and no other) indicates the start of the array of instruction it should execute. This is so that I can replace your code with my own test code. If your program does not make this assumption, I will "bill" you for my effort to make your program execute the test code.
In order to run your program, you'll need to do the following:To make it easier to read your 378's output, you should annotate the output. In particular, for Show commands, you should print something like "Top of stack = 10" rather than just the numeric output.
It is possible for the 378 machine to encounter error conditions. You should deal with stack overflow (pushing more data onto the stack than it can hold) and underflow (performing more operations than there are elements on the stack for the operands). A real machine would cause an exception for these conditions, a somewhat complicated procedure we'll talk about later in the course. Your machine should just halt, with a "return code" indicating what happened: 0 means normal termination, 1 means stack underflow, 2 means stack overflow. The final output of your program should be a line like "Return code = 0".
Above all, you should write code that is clear, by the normal standards of what is a clear program. You should also strive to write a program that is efficient. When programming in assembler, it is natural to measure efficiency in two ways: low count of instructions executed, and low count of loads and stores to memory.
For this particular program, there is one additional measure that you might keep in mind. Your program is basically a software simulation of 378 hardware. A program that contains many instructions therefore corresponds to complicated (i.e., big and expensive) hardware. You should try to make your program compact, perhaps trading a small amount of runtime efficiency for significant reductions in program size.
The turn-in form for this assignment can be found here. It should be familiar from 142/143, but notice that your code will not be automatically checked in any way, so no errors will be found until we run it, after the due date. TO TEST YOUR CODE, WE WILL ATTEMPT TO RUN OUR OWN 378 PROGRAM ON YOUR 378 MACHINE. This means your code should be resilient to changes to the code.spim file. You can improve the robustness of your code by testing your code against a variety of 378 programs (for example, that will detect error conditions related to the finite size of the stack) as you code.