Assignment 3, due feb 6

Part of the homework for 22C:122/55:132, Spring 2004
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 on Fridays at the start of class, and unless there is what insurance companies call "an act of God", the only exceptions to this rule will be by advance arrangement.


For all of the following problems, consider this algorithm for division:

repeat
   A: while (input_ready = 0) do
	B: nothing
      end_while
   C: output_valid = 0
   D: divisor = input_A
   E: dividend = input_B
   F: quotient = 0
   G: while (dividend >= divisor) do
         H: dividend = dividend - divisor
         I: quotient = quotient + 1
      end_while
   J: output_valid = 1
forever

Note that input-ready is a 1-bit input to the whole system, while input_A and input_B are one-word inputs. The outputs from the system are output_valid, one bit, and the remainder and quotient. Also note that the statements in the program have all been given labels for your convenience, should you find a need to reference them in shorthand form.

  1. Which register holds the remainder when output_valid is asserted?

  2. Some of these register transfers form sets that may be carried out in parallel with each other. Identify these sets.

  3. Draw all data paths into the dividend register, showing all multiplexors and other register-transfer-level functional elements that must be present in those paths.

  4. Identify all control inputs to the control unit from the register transfer logic or the outside world, and for each, identify what functions of what registers, if any, are needed to compute that control input to the control unit.

  5. Identify all control outputs from the control unit; divide this list into two subsets, register clock signals and multiplexor or functional element control signals.

  6. Give a state table for the control unit, following the conventions for a Moore machine. This should respond to the inputs you have identified above and produce the outputs you have identified above, conforming to the parallelism you have identified above. Use symbolic state names and symbolic inputs or outputs where your previous answers did not involve giving binary or numeric encodings for these.