CSE 378 Assignment 3

Winter 2001

Due: Friday 1/26/01

Your 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 HW3 Machine

The machine you'll simulate (called the HW3 machine) is a 32-bit machine with an extremely simple architecture. There are only eight instructions, no general purpose registers, and no explicit addressing of memory. Instead, data memory is organized (by the simulated hardware) as a stack of 32-bit integers, and all instructions refer to the top of the stack for operands. (There is also a separate memory to hold instructions, addressable only through the HW3 PC.) The HW3 CPU has an internal register, the SP, to keep track of the top of the stack. The user's program can affect the SP only indirectly, by adding to or removing from the stack.

The table below lists the set of instructions available (as well as some other info to be explained shortly). A user of the HW3 machine would write a program using those instructions. (The input to your program is an HW3 program.)

Stop indicates the end of a program (in the HW3 machine). Clear indicates that the stack (which is the HW3 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. Add, Sub, Mult, and Div 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}. Notice that only the Push instruction specifies an operand.

HW3 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 Push, the low order 28 bits are ignored. In the Push instruction, the low order 28 bits contain a signed integer.

An HW3 program lives in the HW3 program memory, which is separate from the data (stack) memory. By a process we'll leave unspecified, a program is loaded in that memory and the HW3 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.

Although this machine seems to be too simple to do anything useful, we could turn it into a fully general purpose machine by adding just a few instructions (see the extra credit section, below). 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 HW3 Machine in Software

Your program, a simulator, needs to allocate memory for the HW3 program and stack memory. Stack memory is just an array of MIPS words. Program memory is also an array of MIPS words, but initialized to contain a valid HW3 program.

We've supplied you with a two templates to use in writing your program:

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

Your code must also find a place to keep the HW3 PC and SP. Because those values are small, and are used frequently, you should choose MIPS registers to keep them in (i.e., they are stored throughout your program in registers dedicated to that purpose).

The basic structure of you code mimics the fetch-increment-execute cycle of the HW3 CPU. Basically, your program is a loop. At the top of the loop, it fetches the next HW3 instruction into a MIPS register, and then increments the HW3 PC to point at the next HW3 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 HW3 instruction opcode, and with eight cases corresponding to the eight 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), to load into a register an element of the table given by an index (in your case, the HW3 instruction opcode), and then to 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 hw3.spim
• Load code.spim (this will load your test HW3 program into memory)
• Run/step/debug your program

More Details

To make it easier to read your HW3'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 HW3 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 to serve as operands for). 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 you 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 HW3 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. WE WILL ATTEMPT TO RUN OUR OWN HW3 PROGRAM ON YOUR HW3 MACHINE. This means your code should be resilient to changes to the code.spim file. We won't do anything crazy, but we will provide our own program to test your code. Of course, you should have been testing your code against a variety of programs (to detect error conditions, etc.) all along, so this shouldn't bother you.

Again, we will want you to ask us two questions about anything in the course. Again, we ask this to (1) get you to think a little deeply about the current material, and (2) help us learn what we're not getting across in lecture and section.

This is Too Easy

The first suggestion is motivated by the observation that most of the HW3 machine instructions waste a great deal of space. Try to encode the operands in just 4 bits (you could actually use just 3 bits if you don't do the extra credit option below), except Push, which will need the full 32 bits. Using this encoding scheme will obviously complicate the instruction fetch and decoding procedure. Before machines had lots of memory, encoding instructions compactly was important, because it meant smaller programs. (Ironically, small program size is becoming increasingly important again, as memory IO becomes an increasing bottleneck in performance: if the whole program can reside in a cache, rather than primary memory, it will run much faster.)

The second suggestion is to add a non-stack memory to the HW3 machine. Do this by allocating space for memory in your assembly program, and adding two instructions, load and store. Although the final design is up to you, the instructions might be defined like this:

The exact semantics of load and store are up to you. You can either encode the address to use in the instruction, or assume that it is on the top of the stack. The stack-based scheme might look something like this: 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 from. It interprets the next integer on the stack as the value to store. Deciding which, if any stack items store should remove is a design decision we'll leave up to you.

The third suggestion is to add control constructs to the HW3 machine. Again, the final design is up to you, but here's a minimal set of instructions to get you thinking:

We provide three conditional, PC relative branch instructions: Bgtz, Bgez, Bez, each of which compare the value at the top of the stack to zero, and pop the stack. We also provide two unconditional branch instructions: Jump and Jal.