Homework 7 Solved

22C:122/55:132, Spring 2001

Part A: Draw a diagram of the data flow through a divide algorithm, showing the relationship between the AC, MQ, ALU, shifter and multiplexor.

        
   |____Divisor____|         
	   |      _____________________________________ 
	   |     |                       ____________  |
	   |    _|______________________|_           | |
	   |   |__________________________|-- shift  | |
	   |   th|     left shift       |tl  | in    | |
	   |     o------                |    |       | |
	___|_____|___   |               |    |       | |
       |   A     B   |  |               |    |       | |
      _|      _      |  |               |    |       | |
     | |___(A+B+1)___|  |               |    |       | |
     |      tm|         |               |    |       | |
     |________|_________|_____          |    |       | |
     carry   _|_________|_    |         |    |       | |
      out    \1         0/----o---------|----        | |
              \_________/               |            | |
            _______|_______      _______|_______     | |
           |>_____ac_______|    |>_____mq_______|    | |
	           |                    |____________| |
	           |___________________________________|

This roughly follows the topology of the diagram shown near the start of the notes for Lecture 15, but in enough detail that it is easy to see where the control signal from the multiplexor comes from. This system that will perform an n-bit unsigned division using n-clock pulses, with no additional control circuitry required.

Part B: What characteristic or characteristics of the system you described in part A prevent a parallel realization of the divide circuit from computing the remainder and quotient in O(log n) time?

We could, of course, compose n copies of the shift/ALU/multiplex logic at the heart of this iterative circuit to make a parallel circuit, but this would have an unavoidable delay of O(n) because the input to each stage depends on the output of the previous stage and not just on a fixed shift pattern, and in each stage, the multiplexor setting depends on the carry out of the ALU.

Part A: As given, the reciprocal code required one multiplication per iteration. For each iteration, the number of ones in the guess increases by at most one, indicating that at most one new partial product will be added to the sum representing the current product of guess*i. Rewrite this code to take advantage of this fact.
```
   reciprocal( i )
   {
      approx = 0;
      bit = 1 << (n - 1);
      one = 1 << n;
      approxi = 0; -- running computation of approx*i
      iss = i << (n - 1); -- running partial product
      repeat n times {
         guess = approx + bit;
         guessxi = approxi + iss; -- compute guess*i
         if (guessxi <= one) {
            approx = guess;
            approxi = guessxi;
         }
         bit = bit >> 1;
         iss = iss >> 1;
      }
      return approx;
   }
```
Part B: Based on the exercise you did in part A, and on the exercises you did in problem one, how much simpler is the problem of computing reciprocals from the problem of computing generalized quotients.

It is not simpler! With each iteration, we make a comparison and use the result to determine whether to include a one-bit in the result.