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 – Prelab | CSCI 206 Computer Organization & Programming

Lab 6 – Prelab

A Simple Procedure in MIPS Assembly

When writing procedures in assembly, you should begin by asking:

  1. How many parameters are passed into the procedure?
  2. How many values will result from the computation in this procedure?
  3. Does the procedure I’m writing call other procedures (or itself)?

The answers to these questions have direct consequences on the code you need to write. The specifics depend on the ISA with which you work. With MIPS, if the answer to (1) is “less than or equal to 4″, all the parameters can be passed using registers ($a0, $a1, $a2, and $a3). If the answer to (2) is something like “two words of data,” the returned values can be reported to the caller in registers $v0 and $v1.

On the other hand, if the answer to (1) is “more than 4” and/or if the answer to (2) is “more than two words,” your needs exceed the number of registers available in the MIPS ISA. This is not the end of the world, though, as with a bit more code you can use the stack to handle this passing around of data.

Question (3) determines whether you’re writing a leaf procedure (one that doesn’t call any other functions) or a procedure with nested procedure calls. We will explore both cases in this week’s lab. In preparation, you should first study carefully sections 8.1-8.2 in our zyBook.

After reading, work out a solution to the following problem and have it committed to your git repository by the start of your lab session.

Setup

Create the Lab06 folder in your git repository and copy all of the source files from ~cs206/Labs/Lab06.

Exercise 1: A Leaf Procedure

In this exercise you will complete the program in prelab.s by writing a procedure called my_func which computes the value of the following mathematical expression:

You will be working toward implementing the assembly equivalent of the following C function:

where x and y are function parameters, and C is a global variable defined in the main program.

Review the MIPS register conventions in Figure 8.1.2 (COD Figure 2.11) of your textbook. The values for x and y will be passed into to the procedure using the argument registers. The value for C is a constant defined in the data segment of the program. The procedure should compute and return the result using the appropriate return value register. Keep in mind that your procedure must not modify any of the registers which the convention promises to preserve!

After completing the function, add code to the main program to call my_func twice with different inputs and then print out the sum of the results of the two calls. The arguments are given in the assembly source code.

Note that my_func is a leaf procedure, which means that there is no need to work with an activation record or stack frame. Use MARS to test your program to ensure that it outputs the correct result. Then, add a breakpoint at the start of your function. Run your program to the breakpoint and take note of the value of register $ra each time that my_func is called. Write these address values in hexadecimal in comments at the end of your assembly source code. For each of these addresses, indicate to what line of your program they correspond.

Exercise 2: The Collatz Conjecture

The Collatz conjecture states that following the recursive application of the rules below, for any given input n the result will eventually reach 1:

  • if n is even, n = n/2
  • if n is odd, n = 3*n + 1
  • if n is one, stop

If you think about this carefully, it is very natural to define recursive function to compute the next numbers in a Collatz sequence that starts with a given input value n. We can do this as follows; assume that this function will be named collatz and that it returns an integer number. As with all recursive function definitions, we start with the statement of a base case:

collatz(1) =1

When n, the argument to the function is not equal to 1, we have two possible cases:

(a) when is even: collatz(n) = n/2

(b) when is odd: collatz(n) = 3*n +1

For example, suppose we start with n = 13, using our recursive function, we have:

  • collatz(13) = 3*13 +1 = 40 
  • collatz(40) = 40/2 = 20
  • collatz(20) = 20/2 = 10
  • collatz(10) = 10/2 = 5
  • collatz(5) = 3*5 + 1 = 16
  • collatz(16) = 16/2 = 8
  • collatz(8) = 8/2 = 4
  • collatz(4) = 4/2 = 2
  • collatz(2) = 2/2 = 1
  • collatz(1) = 1 : since we arrived at the base case, the recursion stops.

Starting from n = 13 and recording each number generated by this recursive function, the following sequence emerges:

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

Counting the number of values from the starting until we arrive at the base case, inclusively, for n=13, we determine that the sequence has length 10.

In this exercise you will write a C program that uses a recursive function to compute the Collatz sequence lengths for integers 1…100. We have provided a basic outline in the collatz.c file you should have copied at the beginning of the prelab.  Complete the functions as specified. Do not make structural changes to the code. The file is available for you to copy from ~cs206/Labs/Lab06/collatz.c (or you can just copy and paste). Be sure to create a Makefile to compile your collatz program. Refer back to Lab 4 if you need help with Makefiles.

Note that there are different ways in which you can determine whether a number is even or odd, in C. One option is to use the modulo operator % to get the remainder of the integer division by 2. Another way uses the bitwise and operator & to that end. You can read a discussion of the merits and the drawbacks of each one at http://stackoverflow.com/questions/160930/how-do-i-check-if-an-integer-is-even-or-odd. Feel free to use the method you like best.

To verify your work, the first 13 lines of output should be:

1 ==> 1
2 ==> 2
3 ==> 8
4 ==> 3
5 ==> 6
6 ==> 9
7 ==> 17
8 ==> 4
9 ==> 20
10 ==> 7
11 ==> 15
12 ==> 10
13 ==> 10

Submit

The deliverables for this pre-lab assignment are your files prelab.s and collatz.c. Once you have debugged them to your heart’s content push them to your gitlab repository.

Grading Rubric

25 points total:

  1. [15 points] Exercise 1: Leaf procedure implemented in prelab.s. Function returns the proper value. The static variable C is properly defined in the data segment. $ra is noted for the two calls to my_func in a comment.
  2. [10 points] Exercise 2: collatz.c is completed correctly using a recursive function (find_length) and a leaf function (collatz). C Coding conventions are followed (including adding good comments and creating a proper Makefile).
Print Friendly