Project 2 - Hailstones 1 and 2

CS3410 Spring 2016

Due: 11:59pm, Monday, September 19, 2016

You must work in the same pair for this project as for the next two.

Overview

In the coming projects you will build a MIPS processor. An important part of designing a processor is testing it. In this project you will write two pieces of test code. The first can be used to test the functionality and correctness of your Mini-MIPS processor. The second can be used to test the functionality of your Fully-Pipeline MIPS processor.

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. For this assignment, you will implement and iterative version. Later, we will ask you to implement a recursive version.

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;
  }

You will implement this iterative version of the hailstone function twice using MIPS assembly code.

Hailstone 1: Mini-MIPS Compatible

The first MIPS processor you build will only have a subset of the MIPS instruction set. It will only support the instructions shown in Table A below:

Table A
Immediate arithmetic	ADDIU, ANDI, ORI, XORI, SLTI, SLTIU
Register arithmetic	ADDU, SUBU, AND, OR, XOR, NOR, SLT, SLTU
Move	MOVN, MOVZ
Shifts (constant and variable)	SLL, SRL, SRA, SLLV, SRLV, SRAV
Immediate load	LUI

Notice that you don't have any control instructions, which will make expressing the while loop impossible. To work around this, we will simply hardcode n to a particular value and unroll the loop, simulating the arithmetic that would have happened if we had control instructions. As an example, this is what the code looks like if we hardcode n to 4:

  
      int n = 4;
      int i = 0;
      i = i + 1;
      n = n/2;
      i = i + 1;
      n = n/2;
      return i;

For your implementation, store n in register r8, also known as $t0 and store i in register r9, also known as $t1. Set the initial value of n to be 5. At the end of your function, instead of returning i, simply store the value i in register r2, also known as $v0.

Note: if you just store the return value of hailstone(5) into r2, that completely defeats the purpose of the exercise. Do not optimize/modify the code beyond removing the control instructions. You may only use the instructions in Table A.

Hailstone 2: Fully MIPS Compatible

The second MIPS processor you build will only have a much larger subset of the MIPS instruction set. It will support the instructions shown in Table A above as well as those in Table B below:

Table B
Jumps (with one delay slot)	J, JR, JAL, JALR
Branches (with one delay slot)	BEQ, BNE, BLEZ, BGTZ, BLTZ, BGEZ
Memory Load/Store (little endian, with pipeline stall if needed)	LW, LB, LBU, SW, SB

This will allow you to implement the entire iterative hailstone function body.

At a later point in this course, we will learn about some basic behavior that all functions implement at the very beginning and ending of the functions. You do not have to worry about this in your implementation. (You will have to worry about that when we ask you to implement the recursive hailstone function later in the semeter.)

You should write your code assuming that the value of n will be placed in the register $a0. To test your code, you will nead to write some assembly that initializes $a0 to whatever value you are testing. This assembly should not be in the code you submit, because if your code assumes a particular value of n it will ignore the value our auto-grader sets, and it will look like your code is incorrect. Once again, store n in register r8, also known as $t0 and store i in register r9, also known as $t1. At the end of your function, instead of returning i, simply store the value i in register r2, also known as $v0.

Help and Hints

Delay slot. You will be learning about a thing called a Delay Slot but not in time for this assignment. Please just trust us: place a nop after every control instruction in your assembly. Otherwise your code will be incorrect.

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 the mini-mips 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 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:

Immediate Arithmetic	ADDIU $12, $0, PC
Register Arithmetic	ADDU $13, $0, $20
Immediate Load	LUI $14, 0x123
Shifts	SLL $13, $13, 2 SLLV $15, $14, $3
Jumps	J 0x24 J my_label JR $5 JALR $31, $5 JALR $5
Branches	BEQ $5, $6, -12 BEQ $5, $6, my_loop_top BLEZ $9, 16 BLEZ $9, my_loop_done
Memory Load/Store	LW $12, -4($30) SW $12, 0($30)