Lab 6 - Calling Conventions

CS 3410 Spring 2017

---

Due: Upload your implementation of the Iterative and/or Recursive Hailstone by 11:59pm on Monday, March 13, 2017

Optional: If you upload your memoized version, we will run it through the auto-grader, too.

(Only the highest of the iterative, recursive, or memoized scores counts for this lab grade, but all three versions will be turned in again and graded again as part of your next project, so it is in your best interests to get feedback early on.)

---

Overview

In this lab you will re-visit the hailstone programs that you worked on in a previous project.

A hailstone sequence is defined as follows: start at any positive integer n; if n is even, divide it by 2 to get n/2; else triple it and add one to get 3n+1; then repeat with the new number. You will implement the hailstone function, which counts how many steps it takes for the hailstone sequence to converge to 1 from a given starting point. For instance, hailstone(40) returns 8 because the sequence starting at 40 converges in 8 steps: 40, 20, 10, 5, 16, 8, 4, 2, 1. And hailstone(31) returns 106 due to its long and chaotic sequence: 31, 94, 47, 142, 71, 214, ..., 3077, 9232, 4616, 2308, 1154, 577, ..., 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.

There are several ways to compute the hailstone function. You will implement one (optionally, more) of the methods below (please do not submit MIPS code with any form of main function).

• Iterative hailstone: An efficient approach for computing the answer for just a single sequence.

    int i_hailstone(int n) {
        int i = 0;
        while (n != 1) {
            i = i + 1;
            if ((n % 2) == 0)
                n = n/2;
            else
                n = 3*n+1;
        }
        return i;
    }

• Recursive hailstone: Simple but inefficient. Logisim will be too slow to use this version except when the sequence converges quickly.

    int r_hailstone(int n) {
         if (n == 1)
             return 0;
         else if ((n % 2) == 0)
             return 1 + r_hailstone(n/2);
         else
             return 1 + r_hailstone(3*n+1);
    }

• Memoization hailstone: For computing the answer for more than one sequence, it makes sense to remember previously computed answers since many sequences overlap. So if hailstone(40) has already been computed, then it is easy to compute hailstone(160) since its sequence is identical to the one for 40 after just 2 steps. This memoization version is essentially the same as the recursive version but takes two extra arguments: an array log_array of previously computed answers (should be initialized to all zeros), and the number of entries size in the array.

  Note: the memoized hailstone does not allocate or initialize the array. It assumes that the function calling m_hailstone has already created an array of size size and initialized every entry to zero.

    int m_hailstone(int n, int log_array[], int size) {
        if (n < size && log_array[n] != 0)  /* non-zero means we already computed this */
             return log_array[n];
        if (n == 1)
             return 0;
        else {
            int i;
            if ((n % 2) == 0)
                 i = 1 + m_hailstone(n/2, log_array, size);
            else
                 i = 1 + m_hailstone(3*n+1, log_array, size);
            if (n < size)
                 log_array[n] = i; /* save answer for reuse later */
            return i;
        }
    }

Implement the iterative, recursive and memoized versions of the hailstone function using MIPS assembly code. They must all work on your processor in Logisim, though you will have be careful when testing to selecting starting values that converge in a reasonable time.

Testing and input for hailstone functions

Your hailstone functions are just that: functions. They should get their inputs from registers $a0 and $a1 and they should return their results via register $v0. To test the functions, you will nead to create a "main" program which initializes the stack (by setting $sp and $fp to something reasonable and usable), puts some input in the argument registers, then calls the function via JAL. The hailstone functions never make system calls or any other function calls that could possibly read input from the user. Your main program could if you managed to wire up a keyboard though.

For the interested student

It is an open question whether all starting points eventually converge to 1 or not. The Collatz conjecture states that all positive integers converge to 1, but this isn't yet proven. For this project, you can assume all numbers converge — if you find one that doesn't you get an automatic A for the project. You can watch this video or find links to more reading on the Wikipedia page for the Collatz conjecture.

MIPS (subset) Assembly Syntax

The MIPS Program ROM component has a built-in assembler that understands all of the instructions you will implement. The syntax is standard MIPS syntax. Labels are case sensitive, everything else ignores case. Anything following a pound ('#') is a comment. In this project, you will only use a few of the instructions listed here.

The instruction syntax is the same as given in the MIPS standard (and different from the output of gcc and many other tools). Registers are written as $0, $1, ..., $31, and the destination register goes on the left, followed by source registers and immediate values on the right. Most integer arguments (immediates, shift amounts, jump targets) can be specified in hex (i.e. 0x12ab), in decimal (i.e. 1234 or -1234), a label, or the special constant PC. The assembler will replace PC with the address of the instruction itself. Most constants have some restrictions: jump destinations must have the same upper 4 bits as the PC+4, and must be a multiple of 4; branch destinations must be a multiple of 4 and fit in a signed 18 bit immediate; etc. As a special case, when a branch target is specified symbolically as a label, the assembler will automatically subtract the current PC value to obtain a signed offset.

By default, the first instruction will be placed at address 0, and subsequent instructions are placed at at addresses 4, 8, 12, etc.

Assembler directives. The Program ROM assembler understands two standard MIPS assembler directives, .text and .word, both of which take integer (hex or decimal) arguments. For example, .text 0x50000000 will direct the assembler to place subsequent instructions starting at address 0x50000000. And .word 0x24030005 directs the assembler to use the value 0x24030005 as the next machine instruction, which happens to be the machine code for ADDIU $3, $0, 5.

Symbolic register names. The assembler built into the MIPS Program ROM accepts standard MIPS register names: $zero, $at, $v0, $v1, $a0 - $a4, $s0 - $s7, $t0 - $t9, $k0, $k1, $sp, $gp, $fp, and $ra.

Some examples of instructions are: