Assignment 8, due Oct. 23

Part of the homework for 22C:60, Fall 2009
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated (usually a Friday). The only exceptions to this rule will be by advance arrangement unless there is what insurance companies call "an act of God" - something outside your control. Homework must be turned in on paper and in class! Late work may be turned in to the teaching assistant's mailbox, but see the late work policy. Never push late work under someone's door!

Problems

  1. Background: The 74181 was a popular ALU design that originated with Texas Instruments around 1970. This had 5 control inputs for function selection, although of the 32 functions it offered, most were useless. Each one-bit stage of this ALU has the following inputs and outputs, at least conceptually (the chip had lots of optimization done to it):

    This circuit is well documented. The Wikipedia page for it has links to manufacturer's data sheets, which you will need to examine to solve this problem.

    A Problem: Give the values of the inputs S0, S1, S2, S3 and M that must be given to make this circuit compute the arithmetic sum of inputs Ai and Bi, assuming that these use positive logic (where high value represent ones and low values represent zeros). (1.0 points)

  2. Background: When you multiply two n-digit numbers, the result has 2n digits. This applies in binary as well as it does in decimal, so if you multiply two arbitrary 32-bit unsigned integers, the product could require 64 bits. Here is the most common algorithm used for producing the full product:
            multlong( ier, icand ) {
            -- given ier and icand, 32-bit values
            -- returns prod, a 64-bit value
            -- internally, prodh is the high half of prod,
            -- and prodl is the low half of prod,
                    prodh = 0
    	        prodl = ier
    	        repeat 32 times {
                            if prodl is odd {
                                    prodh = prodh + icand
                            }
                            shift prod one place right
                    }
                    return prod
            }
    

    Assignment: Write a SMAL Hawk subroutine MULTLONG that implements the above algorithm. It should take the multiplier and multiplicand in R3 and R4 and it should return the low half of the product in R3 and the high half in R4. (1.0 points)

    Note: This is not big code. You are not asked for a full working program, no main program, just the subroutine. You are not asked for optimal code. The only really interesting part of the problem is the 64-bit right shift, and that is discussed in the lecture notes for the current chapter, as well as in the Hawk manual, which you should be reasonably familiar with by now.

  3. A Problem: Give SMAL Hawk code to efficiently multiply R3 by the constant 210, producing a 32 bit result. Your code should use everything you know about efficient multiplication by constants. It should not require more than about 5 instructions. There are two very good ways to do this. (1.0 points)