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 mentally, without using the SPIM simulator. The second can be done with the simulator.

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 378 Machine

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

Stop indicates the end of a program (in the 378 machine).
Add, Sub, and Mult replace the top two integers on the stack with the single integer result of the operation specified. For example, if the stack contains (from bottom to top) {1 2 3}, a Sub instruction would result in {1 -1}.
Clear indicates that the stack (which is the 378 main memory) should be cleared, that is, set to empty.
Bgtz and Bgez compare the value at the top of the stack to zero, branch to the target or fall through and pop the stack.
Jump jumps to the address at the top of the stack.
Load and Store transfer data to and from memory. Load interprets the integer at the top of the stack as the address to load from. It then replaces that integer with the value it loads. Store interprets the integer at the top of the stack as the address to store to. It interprets the next integer on the stack as the value to store, and removes the value after the store.
Clear indicates that the stack (which is the 378 main memory) should be cleared, that is, set to empty.
Show requests that the integer at the top of the stack be printed.
Push adds a new integer to the top of the stack. Notice that only the Push instruction specifies an operand.

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.

Implementing the 378 Machine in Software

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 two templates to use in writing your program:

The first (378.spim) contains a template for writing your program. The second (code.spim) contains a sample 378 program. You should write all of your MIPS assembly code in 378.spim. You will need to add code to allocate 378 data memory space and the stack, as well as pretty much all the code required to implement the 378 simulator.

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

Running and Testing

• Start xspim
• Load 378.spim
• Load code.spim (this will load your test 378 program into memory)
• Run/step/debug your program

More Details

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

Evaluating Your Code

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.

Turn-In

We'll announce a turn-in procedure for this program, so stay tuned. 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