CS 208: Computer Organization & Architecture

A multiplication subroutine

Hand in via Moodle as multiplication.asm

You may work alone or with a partner on this assignment. If you would like to work with a partner but want to be assigned one, let me know.

Goals

• Write a simple MIPS program
• Organize your MIPS program using a subroutine with a clearly specified interface
• Get familiar with how multiplication works using two's complement integers

Background

MIPS has several integer multiplication instructions, typically optimized in the hardware to make them fast. That said, multiplication in a computer has some subtleties that aren't obvious at first glance, so there's quite a bit of value in implementing multiplication yourself, once. That's what you're going to do for this assignment: implement 32-bit signed multiplication in MIPS without using the built-in multiplication instructions.

The mult subroutine

Your multiplication subroutine must adhere to the following requirements:

• Its name/label is mult
• When it is called, multwill treat the contents of $a0 and $a1 as the factors to be multiplied. It will not refer to locations in memory (e.g. "factor1" and "factor2").
• mult will treat $a0 and $a1 as signed integers. Thus, the product will be negative or positive depending on the signs of $a0 and $a1.
• Before mult returns (via "jr $ra"), it puts the 64-bit product of $a0 and $a1 in $v0 and $v1, where $v0 is the low-order word of the product and $v1 is the high-order word of the product. (This means, for example, that if the product is negative, the sign bit will be the leftmost/highest-order bit of $v1.

The print subroutine

To test your mult subroutine, you will want to be able to print your results. Given that the product consists of two words (64 bits), and may also represent a two-word negative number, this is not as simple as calling print on the two separate words of the product. If you find it simpler, you may write a print subroutine that prints the results as a 16-digit hexadecimal number instead of a long base ten number. (Printing a two-word number in base ten might be interesting, however, so go ahead and do that if you prefer.)

Your print subroutine must adhere to the following requirements:

• Its name/label is print
• print will print the 64-bit two's complement stored in $a1 (high-order word) and $a0 at the time print is invoked
• You may choose to implement print in either of two ways:
  • (Easier) print the 64-bit integer as a single 16-digit hexadecimal number. (For example, if the number is -2, then $a1=0xffffffff and $a0=0xfffffffe, so your output should be 0xfffffffffffffffe.)
  • (Harder) print the 64-bit integer as a base-ten number.
  You won't get more points for doing the base-ten version, but it's fun to figure out how to do it, so feel free if you want.

Since the print subroutine expects its parameters stored in $a1 and $a0, you'll need to move the results of mult from $v1/$v0 to $a1/$a0 before invoking print.

The main program

You may use the main program from bad_mult.asm, adapting the printing section as needed.

A sketch of the algorithm

Here's a rough description of the algorithm I want you to use. Note that for 32-bit integers, this algorithm may take up to 31 iterations of its loop, but no more than that. Thus, this is a vastly superior algorithm to the one in bad_mult.asm, which has the potential to require more than 2 billion iterations.

Note that the variables SIGN, PRODUCT, MULTIPLICAND, and MULTIPLIER are just my names for these numbers. In your code, all four of these quantities will be stored in registers.

Furthermore, note that PRODUCT and MULTIPLICAND must be 64-bit integers, so you'll need to use two registers to represent each of them. You might even want to write a subroutine for adding a 2-register integer to another 2-register integer.

• Save the sign. Set SIGN = 1 if the product should be negative (i.e. product < 0), or SIGN = 0 if it should be non-negative (i.e. product ≥ 0).
• Initialize. PRODUCT = 0, MULTIPLICAND = abs(factor1), MULTIPLIER = abs(factor2), where abs(x) is the absolute value of x.
• LoopStart
  • If MULTIPLIER is odd, PRODUCT = PRODUCT + MULTIPLICAND
  • Shift MULTIPLICAND left by one bit
  • Shift MULTIPLIER right by one bit
  • If MULTIPLIER != 0, go to LoopStart; otherwise the loop ends
• Finish. If SIGN = 1, negate PRODUCT

Always good ideas...

Start early, ask questions, and have fun!