CSE 378 - Autumn 2002

Machine Organization and Assembly Language Programming

Problem Set 3: 378 Stack Processor
Due: Wednesday, October 16, at the start of class

There are several goals for this problem set. First, and most basic, it will teach you the basics of writing and debugging assembly language programs. Second, because your program is a processor 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 (the 378 stack processor) from the hardware in the simulator you are using to execute your code (SPIM). Third, because the simulator is a *stack* processor 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 processor you'll be simulating, and then describe what you have to do.

The 378 Stack Processor

The processor you'll simulate (called the 378 stack processor) is a 32-bit CPU 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 stack processor would write a program using those instructions. (In other words, the input to your program is a 378 program.)

Opcode Operation Example Meaning
0000Stop0x00000000Stop the program
0001Add0x10000000Add
0010Sub0x20000000Subtract
0011Mult0x30000000Multiply
0101Bgtz0x5000000C Branch-greater-than-zero: PC := PC + 12 if stack top > 0
0110Bez0x60000010 Branch-equal-to-zero: PC := PC + 16 if stack top == 0
0111Jump0x70000000 Jump to addr in top of stack: PC := code + Stack Top
1000Load0x80000000Load memory to stack top
1001Store0x90000000Store from stack to memory
1101Clear0xD0000000Clear the stack
1110Push0xE0000003Push 3 onto the stack
1111Show0xF0000000Show the stack top
Stop
indicates the end of a program (in the 378 stack processor).
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}.
Bgtz and Bez
compare the value at the top of the stack to zero, branch to the target or fall through, and pop the stack in either case.
Jump
jumps to the address at the top of the stack and pops it.
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 both after the store.
Clear
indicates that the stack should be cleared, that is, set to empty.
Push
adds a new integer to the top of the stack. Notice that only the Push instruction specifies an operand.
Show
requests that the integer at the top of the stack be printed.

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 above. In all instructions other than Bgtz, Bez and Push, the low order 28 bits are ignored. In the Bgtz and Bez 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 into the instruction memory and the 378 PC is set to the address of the first instruction. The processor 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 processors. 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 stack processor 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

http://www.cs.washington.edu/education/courses/cse378/CurrentQtr/Assignments/378.spim

378.spim contains a template for writing your 378 stack processor. 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 processor, as well as pretty much all the code required to implement your processor.

Please note: you should write your 378 stack processor to assume that the base of the array of instructions is represented by the symbol code. Failure to do so will require Dustin 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.)

Running and Testing

Please note: Your 378 stack processor should assume that the symbolic name code (and no other) indicates the start of the array of instructions it should execute. This is so that Dustin can replace your code with his own test code. If your program does not make this assumption, he will "bill" your grade for his effort to make your program execute the test code.

In order to run your program, you'll need to do the following: PCSpim may be flaky. You'll probably have to reload your program or even restart PCSpim between debugging runs.

More Details

To make it easier to read your 378 stack processor'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 number 10.

It is possible for the 378 stack processor 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 processor would cause an exception for these conditions, a somewhat complicated procedure we'll talk about later in the course. Your processor 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: a low count of instructions executed, and a 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.

Testing Your Code

To test your code, we will attempt to run our own 378 program on your 378 machine. You can improve the robustness of your code by writing and running some example 378 programs, including those that will detect error conditions related to the finite size of the stack. You should include checks that detect these error conditions in your 378 stack processor code.

Turn-In

Please email the files to dbarnes@cs for the turnin.