IC220 Spring 2009                   Project #1: Peculiar Perrin            Due Thurs Feb 19

 

This project must be completed independently (unlike regular assignments).

This means collaboration between students is not permitted. Online sources (aside from IC220’s website) are also prohibited.  You may consult your notes, textbook, and the instructor. See the instructor for help or clarification.

 

Background: You have already had experience with writing simple MIPS programs and testing them with SPIM.  In this project you will review and integrate your understanding of:

1.       General MIPS programming

2.       Function calls

3.       Recursion

 

Easy Extra Credit! Completing this project will be a big help with understanding the material tested on the 6-week exam. Since you need to do the project sometime anyway, why not finish it early and then have an easier time with the exam? To sweeten the deal, any working project submitted before class on Tues Feb 10 will earn 5 points of extra credit.

 

Task:  Write a recursive MIPS program that computes a term in the “Perrin number” sequence.  This sequence computes the number of “maximal independent sets in an n-vertex cycle graph.” More practically, this sequence of numbers (3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, …) can be computed with the following recursive function:

int perrin (int N) {

  if (N == 0)

    return 3;

  else if (N == 1)

    return 0;

  else if (N == 2)

    return 2;

  else

    return perrin(N-2) + perrin(N-3);

}

Thus, perrin(0) = 3, perrin(1) = 0, perrin(2) = 2, perrin(3) = 3, …. perrin(10) = 17.  Be sure you aren’t off by 1 in the sequence.

 

There are much more efficient ways to compute the Perrin series, but to solidify your understanding of recursion and the stack you are required to have a recursive solution.

 

Specifics: Starter code is provided: ProjectStarterCode.asm. (right-click and use Save As) Start with this!!!! You should do the following with this code:

1. Modify the main function to:

Print a welcome message that includes your name

Call the perrin procedure to compute the Perrin term requested by the user

Print the calculated term after it has been returned to the main function

2. Write a procedure called perrin that:

            Recursively calculates the Nth Perrin term, where N comes from the argument passed in register $a0.     

            Returns the value in $v0.

            You do not have to write this function from scratch – translate the C code given above!

3. Test your code with SPIM.

 

Sample screen shot of completed program:

       

 

(more on back)
Tips:

1.      Start early!  Recursion can be tricky.  Allow time to get help from the instructor if needed.

2.      But don’t make this harder than it needs to be! Your primary task is to simply translate the C code above to a MIPS function.  While this function is recursive, really this is just another example of a nested procedure – follow the rules for nested procedures and recursion will take care of itself.

3.      You will need to use the stack.  Be sure you begin, make sure you understand how to do this and what will need to be saved and restored with the stack.

4.      This assignment requires you to write only about 30 carefully chosen assembly instructions.  If you have many more than that, you probably are misunderstanding what should be done.

5.      The following material may be helpful to you:

·         Lecture notes on MIPS procedure calls, and SPIM

·         Lab #1, where you first used SPIM

·         SPIM reference material: http://www.cs.usna.edu/~lmcdowel/courses/ic220/spim/

6.      Use Alt-PrintScreen to generate a screenshot. 

7.      An error message like “Can’t add 8 bytes to Lstack” means you are stuck in infinite recursion.

8.      Use the starter code!

9.      The next page contains another useful example, demonstrating how to do function calls.  Read this!

 

Deliverables: (1 through 3 handed in, stapled together in the following order)

1)      A cover sheet with your feedback.                                                              (10 pts)

2)      Screenshot showing your program computing perrin(10)                              (10 pts)

3)      Printout of your recursive assembly code                                                     (60 pts)

4)      .asm file saved to your X drive                                                                                (20 pts)

Place this file in your IC220 directory.  Name it Project1-section-lastname.asm

(e.g., Project1-8001-smith.asm).

 

Extra credit (up to 5 pts each):

1. Write a new program to calculate the Perrin numbers in a non-recursive manner.  Turn in this program and a screenshot showing the calculation of Perrin(30).

2. Read ahead about floating point registers, then write a new program to calculate the Perrin numbers using the floating point registers to keep track of the calculations (you can assume that you only have to deal with numbers with no fractional part).  Why might you want to do this?


 

 

 

# Example code demonstrating how to call a function as part of

# a complete SPIM program.

      

 

        .data

str_1:  .asciiz "Enter a number=> "

str_2:  .asciiz "Result=> "

 

        .text

        .globl main

main:  

        # Print the prompt

        la      $a0, str_1              # 'load address' of string to print

        li      $v0, 4                  # syscall #4 = print string

        syscall        

       

        # Read an integer from the user

        li      $v0, 5                  # syscall #5 = read integer

        syscall                         # read int, result goes in $v0

 

        # Call a function to add that number together with 13

        addi $a0, $zero, 13             # Set up first argument to function  (13)

        move $a1, $v0                   # Set up second argument (the number entered by user)

        jal doAdd                       # do add, result now in $v0

        move $s0, $v0                   # save result for later (b/c v0 clobbered below)

       

        # Print string announcing the result

        la      $a0, str_2              # 'load address' of string to print

        li      $v0, 4                

        syscall  

             

        # Print actual result

        li      $v0, 1                  # syscall #1 = print integer

        move    $a0, $s0                # tell syscall what # to print

        syscall

       

        # terminate the program

        li $v0, 10

        syscall

 

# Define the (very simple) function we use

# Notice that this goes OUTSIDE of main

doAdd: 

              add $v0, $a0, $a1               # add two arguments

              jr $ra                          # return