CSE 378 - Winter 2002

Homework 5: SMOK MIPS Design and an Introduction to SMOK
Due Wednesday, February 20

Purpose:

For this assignment, you should work in teams of two and hand in one homework for the two of you. Start now to find a partner. Both of you should work on both parts, so that you both get experience in designing a microarchitecture and working in the SMOK environment. The next assignment is also in teams, but you'll need to partner up with different person for that one.

Tasks:

Task 1: You are to build a single­cycle, small­scale MIPS microprocessor. This will be just like a commercial MIPS microprocessor (the R2000 vintage), except that you will implement only a handful of instructions, and you won't have to pipeline the machine (although you may think about how to do that, since this will be Homework #6). For this assigment the execution of each instruction will happen in one long clock cycle.

Task 2: Write a recursive function that calculates the n'th Fibonacci number. This function Fibonacci(i) will return an integer. You are to write this function first in MIPS assembly language, and then you are to hand assemble your code into binary form. You will then execute this code on the machine you build in Task 1. Because of this you will have to write this function using only the set of instructions you actually implement in Task 1, but these should be enough.

The Details:

1. We are going to use the latest version of SMOK, which executes on Windows only. This version can be downloaded from "http://www.cs.washington.edu/homes/zahorjan/homepage/Tools/SMOK/". Please use the latest version since it has been updated specifically for our class.
2. The format of the instructions for your machine follow the real MIPS encoding format (R­type, I­type and J­type). In addition, just like the real MIPS architecture, your machine will have 32 integer registers, treat register zero as 0^* , register 31 as ra, and other register conventions.
3. The absolute reference for any details with this assignment is the real MIPS documentation, and any other documentation on the real MIPS microprocessor (unless otherwise explicitly modified in this handout, or we tell you otherwise). Now having said this, we are going to make a modification to the memory layout of the process the MIPS processor you build executes. This is only a small hack to make things easier for the SMOK tool and yourselves, but it should be easy to see how to modify things to work like the real microprocessor. The hack is as follows:
   • The real MIPS processor has a protected and privileged operating mode. This is to support process level protection mechanisms that are conventional on modern operating systems. For this assignment there is no operating system, and no protection modes.
   • While your microprocessor operates with 32 bit addresses, in order to not make SMOK explode, you are going to work with only a 256 word (1024 byte) memory.
   • By convention, a process starts at 0x04000000. However, your initial PC should be set to 0x00000000, i.e., your code should start at address 0.
   • By convention, a process stack pointer is set to 0x7ffxxxxx (near the 2 gigabyte boundary). You should set your stack pointer at 1024 bytes (256 words), i.e. just at the end of the memory in the machine.
   • By convention, a process stores static and dynamic data starting at 0x10000000. If you need static and dynamic data, you should start storing them at the 512 byte (128 word) boundary.
   • The real MIPS processor contains delay slots behind branches and delays on load instructions (to account for additional latencies in executing these instructions). Your processor will operate in a single cycle, and so there will be no delay slots.
4. You should understand the following code, and place it at address 0 (load the .smokmem file into your memory unit):

   0x00000000: addiu $sp, $0, 1024 # effectively a li $sp, 1024 
   0x00000004: addiu $sp, $sp, -4 # effectively a sub $sp, $sp, 4 
   0x00000008: addiu $a0, $0, 10 # effectively a li $a0, 10, set subroutine arg to 10
   0x0000000C: jal fibonacci  # begin your subroutine
   0x00000010: addiu $sp, $sp, 4 #restore stack
   0x00000014: beq $0, $0, -4 # effectively a hold
   0x00000018: ­­­­ place your fibonacci program here 
   

   This code sets up the stack pointer, and then makes a procedure call into the fibonacci procedure that you are to write. After returning from fibonacci it removes the stack frame and halts the machine by having a branch instruction jump to itself^*. The smokmem file is here.
5. Your implementation should support the following instructions:

   Arithmetic:

   ADDU, ADDIU, SUBU, SLTI, SLT

   Load/Store:

   LW, SW

   Control:

   JAL, JR, BEQ, BNE

6. Fibonacci numbers are a rather famous sequence of numbers that go something like this:
   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
   The basic pattern is F(n) = F(n­1) + F(n­2), with F(0)=0 and F(1)=1. So your function should be like this:

   def fibonacci(n):
     if n==0:
       return 0
     if n<=2:
       return 1
     return fibonacci(n-1)+fibonacci(n-2)
   

   Note that the function is recursive, so you will need to be careful about how you handle registers. Follow MIPS conventions. Remember to use only the instructions your machine supports. They should be more than enough. Do not worry about improper inputs.
   Please do not be too fancy in how you implement this function. We have to grade it!
7. It will behoove both of you to work on all parts of this assignment. In other words, you can expect questions on the midterm about designing datapath and control.
8. Write a short report (one page is plenty) describing:
   • how you planned and designed your machine, especially mentioning anything you thought was tricky or that you found a partiticularly nice solution for;
   • how you tested your machine, and how you debugged it;
   • what you learned, and what you had trouble with;
   • describe your fibonacci algorithm. How many cycles does it take?
   • the distribution of work between partners.
9. Turn in your code online, using this form, and turn in your written report in class. Please submit as only one person--there is no need for you and your partner to submit code (or written reports) separately. Just make sure to indicate both partners' information on the turnin, so you will both get a grade. Both written and code parts are due by class on 2/20. I suggest you finish the code part early, and leave time to describe it in the written report.

Grading

1. functionality of the fibonacci code on your machine
2. correctness of your machine
3. design of your machine (is it understandable, reasonably fast?)
4. your written report

Hints

• Chapter 5 gives an almost complete machine design in gory detail. It is a good starting point, but there are a few differences to note: The given machine has two memories, because they can't do two memory operations in one cycle. With SMOK, you can have one memory unit, and use two interfaces (one for fetching instructions, the other for loading and storing data). Either implementation is acceptable.
• SMOK's ALU has different opcodes than the one described in the book. That being said, you should not feel bound to the design in chapter 5. If there is something else that makes sense to you, feel free to go that route as long as it is functional.
• It will probably take over 1000 cycles of your machine to compute fibonacci(10), so you might want to start with a smaller input.
• All operations you're implementing that use the immediate field do sign extension. In reality, although dealing with unsigned numbers, ADDIU and other math operators indeed do sign extension, but logical operators (ORI) do not.
• In MIPS, register 0 is hardwired to 0. For this project it acceptable to simply have all registers initialized to zero, and never write anything to register zero. Alternatively, you can devise a scheme to keep register 0 at 0.
• To know SMOK is to love SMOK. But, just like Al Capone when he said the secret to winning elections is to "vote early and often", the secret to loving SMOK is to "save early and often". I have also seen SMOK develop odd behavior, which reinitializing the machine did not fix, but quitting SMOK and reloading the file did. Keep in mind that SMOK is a work in progress.
• Unlike SPIM, which is used by universities across the country and is therefore pretty much free of bugs, SMOK is a homebrew design. So if you find a reproducable error, make note of it, and let others know as well. Additionally, versions of SMOK may change during this assignment. This should not introduce any incompatibilities, but you may find that later versions have new features that help you.
• If you use SPIM to assemble your code to binary, note that (in the default configuration) it doesnt calculate branch offsets from PC+4, and that jump addresses will be very different
• To facilitate testing, you may add a 'halt' component that will trigger when the self-looping branch instruction is detected.
• The component reference page is useful: www.cs.washington.edu/homes/zahorjan/homepage/Tools/SMOK/ComponentRef/index.htm
• You will want to understand what a container/control is and how to use one. It will make your design considerably easier to navigate.