Notice: Constant FORCE_SSL_ADMIN already defined in /nfs/unixspace/linux/accounts/COURSES/cs206/public_html/sp17/wp-config.php on line 94
Lab 6 | CSCI 206 Computer Organization & Programming

Lab 6

Procedures in MIPS

Goals

  • Practice implementing procedures in assembly programs
  • Practice using the stack to store data in assembly
  • Practice writing programs in MIPS assembly
  • Practice using git for revision control

The MIPS ISA provides four registers for passing parameters into a procedure and two additional registers that a procedure can use to return results to the caller. Sometimes these registers will not be enough. We have developed procedure calling conventions to work around these limitations. The conventions work on the side of the caller and also on the side of the callee (that is, the procedure being called). This lab will exercise your ability to implement assembly code to follow those conventions.

Setup

Do a “git pull in your local working folder to be sure you have the latest updates from the TAs.  Next, if you haven’t done so already (in the prelab) copy all the files from ~cs206/Labs/Lab06 to your Lab06 folder. Finally, add these files to your git repo (i.e., do a “git add * in the Lab06 folder).

Exercise 1: Searching through ASCII

Characters are represented by one byte when encoded in ASCII. In our assembly programs, as it is the case in C, we will represent strings as contiguous sequences of ASCII characters terminated by a null byte (0×00).

When writing MIPS programs that process individual bytes, rather than words, you can use the lb instruction, which loads a single byte into a register. Note that this instruction has the same base+offset addressing mode as lw, that is, it identifies the memory address of where the byte resides expressed using the base stored in a register plus an offset encoded in the instruction.

For this problem, you will write a MIPS procedure called xfind which finds the first occurrence of the letter ‘x’ in an area of memory. The procedure receives a single argument in $a0, which is the starting memory address of a null-terminated ASCII string. The xfind procedure will locate the first ‘x’ character in the string and return its address in register $v0. If there are no x’es in the string, xfind should return -1 in register $v0. You should start by writing the algorithm in pseudo-code and determining what values each register will contain (i.e. do “register assignments”) – start to code only after you’ve completed these steps.

Some register assignments for your procedure are indicated below (any others are up to you). Document all registers assignments in your assembly file with assembly comments that include the name of the register and text such as what is provided below in italics:

  • $a0The starting memory address of the string. This address will be placed in the register by the main program which calls your procedure.
  • $v0 – The result (a valid address or the constant -1).
  • $raThe return address for the procedure. The instruction jr $ra will use to go back to the caller with

The file xfind.s provides skeleton code and a main program which will call your procedure. Write your code for the xfind procedure at the location indicated by the label with that name. Also, write code to print to the terminal the result of the call to xfind. These should be the only two modifications you need to make in the source code file.

Test your program with the two different inputs provided in the program, one at a time. Note that only one string line should be uncommented at any time. (You will need to change which one is commented, so that the two strings are tested.) Your program should print the address returned by xfind using a syscall you haven’t seen before, which prints hexadecimal values. It works as follows:

  • Place value 34 (base 10) in register $v0
  • Place the value which you want to print in register $a0
  • Invoke syscall

You can verify that your program works by inspecting the hexadecimal address value printed to the terminal. Make sure to write plenty of comments so that your code is as easy to understand as possible.

Once your program works, remember to do add xfind.s to your git repo.

Note: Again, remember that you can see the full list of syscall services provided by the MARS simulator from the help menu or online at http://courses.missouristate.edu/KenVollmar/MARS/Help/SyscallHelp.html. Please do not use the dialog-based syscalls ($v0 > 50) because they complicate grading.

Exercise 2: Non-leaf procedures

A procedure that calls one or more procedures is called a non-leaf procedure and takes more work to write in assembly because they require one to build a stack frame. As you have seen, stack frames can contain saved registers, variables local to the procedure (which we call automatic variables in C), and any parameters passed to the procedure that didn’t fit in the four $a0-$a3 registers. Organizing stack data between the caller of a procedure and the procedure itself (callee) would be a complex task if there weren’t any conventions to guide the assembly programmer.

These conventions can be found the zyBook chapter 8.2 and in this document.

In this problem, the scenario requires you to put to practice the calling conventions discussed in class. Starting from the program skeleton in file largeproc.s, you will write two procedures:

  • small_proc: a leaf-procedure that does nothing; it returns as soon as it is called, and
  • large_proc:  a non-leaf procedure which receives 6 arguments and returns 2 values.

In  pseudo-C code, the behavior of large_proc should be as follows:

The big points to notice are:

  • large_proc receives more arguments than one can fit in the $a0$a3 registers, therefore the excess must be passed via the stack.
  • large_proc returns a result that is two words long so you will need to use both $v0 and $v1 to return it.
  • Remember to use the stack to pass around data that doesn’t fit in registers.
  • You will also have to write the main procedure and it must use for parameters to large_proc the values contained in the global variables declared in the data segment of the skeleton code (A through F). That means, you have to read these parameter values from memory in the data segment and pass them in to your procedure. Use the following mapping of global variables to formal parameters in large_proc: p0=A, p1=B, p2=C, p3=D, p4=E, and p5=F. (Refer to the C program above.)
  • There is a stack frame that needs to be built for each of the two procedures small_proc and large_proc. Use the procedure calling conventions to determine the size and the contents of the stack frames. Also, be sure to use the conventions to determine what the caller (main) and the callees (large_proc and small_proc) have to do in order to set up, read, and discard the stack frames.

You might benefit from the following:

  • lw $t0, LabelA – is a pseudo-instruction that loads the word in the memory position  at label LabelA into register $t0
  • sw $t2, LabelB – is a pseudo-instruction that stores the value of $t2 register into the memory position at label LabelB.

Be sure to include comments with the register assignments in your assembly source, as you did in the previous problem. Also, make sure to write plenty of comments so that your code is as easy to understand as possible.

Once you are done implementing and verifying that your program works to specifications, think about what you might do if you had THREE word sized integer values to return to the caller of largeProc. Describe your solution as comments at the end of your largeproc.s file.

When you are ready to move on, make sure to add largeproc.s to your git repo.

Exercise 3: Collatz in assembly

In the prelab you wrote a C program to compute Collatz sequence lengths (up to N = 99) by calling a recursive function (find_length) that called a leaf-function (collatz) from a loop in main. Now that you are an expert at calling functions from MIPS assembly, create a file called collatz.s where you will write the same collatz program in assembly. There is no skeleton this time, but you must structure your code into a collatz function to compute the next number in a sequence, a recursive function find_length to compute the length of the sequence, and and a main function that loops through calls to find_length. Make sure to write comments in your file to document your register assignments and to explain what your code is doing.

Use MARS to test and debug your program as usual. Your goal is to produce the same output in MARS that you got from your C program.

Once your program is working correctly, there are a few other neat features of MARS that we can play with. The first is the Instruction Counter. From the Tools menu select Instruction Counter.

This will bring up the Instruction Counter window as shown below. Press the “Connect to MIPS” button then go back to your program and compile/run it. You should see the counters increment in real-time.

This gives you useful information into the mix of instruction types used in your program along with the total instruction count. If we had CPI for each instruction type and clock frequency we could compute run time on a real CPU. Neat. By the way, at the completion of collatz.s, my implementation yields the instruction counts below. How do your results compare?

Another similar tool to the instruction counter is the instructions statistics tool. Open this up, connect to MIPS and rerun your program. This gives you a more detailed breakdown of instructions. Again, my values are shown below for reference.

Feel free to try out the other tools, but these are the most useful at this point. Later we may use a couple others.

When you are satisfied with your solution, don’t forget to add collatz.s to your git repo and push your work to gitlab.

Grading

[Lab: 75 points total]:

  1. [20 points] Exercise 1 (xfind.x); (3 points) for documenting register assignments; (2 points) for commenting code; (15 points) for correct functionality.
  2. [30 points] Exercise 2: (largeproc.s) (5 points) for documenting register assignments; (5 points) for commenting code; (5 points) for correct stack frame for small_proc; (5 points) for correct stack frame for large_proc; (10 points) for correct functionality.
  3. [25 points] Exercise 3:  (collatz.s) (3 points) for documenting register assignments; (2 points) for commenting code; (10 points) for correct stack frames in all procedures; (10 points) for correct functionality.

Challenge: Memoizing Collatz

Copy collatz.c/s to collatz_dyn.c/s. For this challenge you will solve the same Collatz sequence length problem using memoization (that word is not misspelled!) Basically this means to reuse previous solutions to a problem. To demonstrate what memoization does, consider the Collatz sequences from 10 and 13:

10, 5, 16, 8, 4, 2, 1
13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Assuming we compute the sequence lengths in order, we will know that collatz(10) has length 7 before we start computing collatz(13). The first number we hit in this sequence less than 13 is 10 after 3 calls to collatz(). At this point, we know that collatz(10)==7, so we can immediately return the result as 3+7 saving 7 redundant calls to collatz().

Modify your C and MIPS assembly programs to use memoization. To achieve this you will have to store the length of each sequence up to N, in an array in memory. This means array[10] would store the value of collatz(10). Place the array in the data segment. Modify your find_length function to access the array instead of recursing whenever a partial solution is available. We suggest you prototype your algorithm in C and once it is working, write that algorithm in MIPS assembly.

When your solution is working, use the instruction counter tool in Mars to compute the speedup achieved by using this technique compared to your first solution. Was it worth the effort?

Print Friendly
Posted in Lab

Leave a Reply

Your email address will not be published. Required fields are marked *

*