Assignment 3, due Feb 7

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list!

1. Consider this tiny little program:

   	int A, B, C, D;
   	loop
   	    A = input 1
   	    B = input 2
               D = C
   	    C = 0
   	    while B != 0
   	        if odd(B)
   	            C = C + A
                   endif
                   A = A << 1
                   B = B >> 1
   	    endwhile
   	endloop	
   

   In context, input 1 and input 2 are external sources of data, perhaps the outputs of other registers in the system that are global to the current context, while the contents of the C register are observed by the outside world. This problem originated in a context where input 1 and input 2 were the outputs of two analog to digital converters, and the C register was the input to a digital to analog converter.

   Part a) Using the methodology covered in the notes for lecture 5, and work out, the register-transfer and combinational logic for this machine. To keep things organized, stick to this visual layout:

                 X           Y      ...      W
             ____|____   ____|____       ____|____  inputs and
            |_________| |_________| ... |_________| registers
               --|-----------|---------------|---
               --|----|------|-----------|---|---   network to distribute
               --|----|------|--|--------|---|---   register values
                    | |         | |      |     |
     boolean     combinational logic for the various
     outputs     expressions you need to evaluate
     to control <--| |      |    |          |
     unit       <----|------     |          |
               ------|-----------|----------|----   network to distribute
               |-|---------|---|----------|------   values of expressions
             __|_|_|__   __|___|__       _|_|_|_|_ 
             \_______/   \_______/  ...  \_______/  multiplexors
                 |           |               |
                 X           Y      ...      W      outputs and feedback
                                                    to inputs of registers
   

   The above format is presented in a very general form. One-input multiplexors can be simplified to nothing, and some of the combinational elements are trivial. If a register's value is used in only one place, careful layout will allow that register's output to cross directly over the distribution networks to reach its place of use.

   Part b) In terms of your answer to part a, determine what register transfers in the original algorithm can be carried out in parallel. Give annotated code for the algorithm that clearly indicates this parallelism by, for example, blocking each group of parallelizable statements in a parbegin-parend block. Assume in doing this that all flipflops are edge triggered.

   Part c) Use your answer to part b to construct the state table and output table for a Moore control unit for your register transfer system from part a that will make it execute the program. Keep things symbolic as much as possible, making the connection between your state table and the original clear. For example, label the boolean outputs of your register transfer system with the textual expressions they represent and use these expressions as labels on the appropriate input columns of the state table.

2. What does the function in problem 1 do?

3. If your logic has a gate delay of 10 nanoseconds per nand gate, the input data has a precision of 12 bits, and carry propagation in the adder is done using a 4-way balanced tree, estimate:

   Part a) The maximum clock rate for this circuit.

   Part b) The worst-case (slowest) number of iterations per second of the outer loop.

   (If the analog data is audio data, we need at least 40,000 iterations per second to meet the usual standards of the high-fidelity audio marketplace.)