UIT2201: CS & the IT Revolution
Tutorial Set 8 (Spring 2008)

(D-Problems discussed on Thursday, 20-Mar-2008)
(Q-Problems due on Tuesday, 25-Mar-2008)
[Note: Q2 added, A9 expanded. 22/3]

Discussion Problems: -- Prepare (individually) for tutorial discussion.

T8-D1: (MAR) (Practice Prob 1 & 2 of S5.2.1 of [SG3].)
Assume that our memory unit is organized as a 1,024 x 1,024 two dimensional array.
(a) How big does the MAR register have to be?
(b) How many bits of the MAR must be sent to the row decoder? To the column decoder?

T8-D2: (ALU and MUX) (Problem 9 of Ch.4 of [SG3].)
Assume that we have an arithmetic/logic unit (ALU) that can carry out 20 distinct operations. Describe exactly what kind of multiplexor circuit would be needed to select exactly one of those 20 operations.
(Note: The ALU given in the lectures (Figure 5.12, p210 of [SG3]) only carries out 4 distinct operations.)

T8-D3: IR [Instruction Register] (Problem 15 of Ch.5 of [SG3].)
Consider the following structure of the instruction register.
op code address-1 address-2
  6 bits     18 bits     18 bits
(a) What is the maximum number of distinct operation codes that can be recognized and executed by the processor on this machine?
(a) What is the maximum memory size on this machine?
(a) How many bytes are required for each operation/instructions?

T8-D4: (Translating algorithm for machine execution.)
In this exercise, we illustrate how to translate a simple algorithm into a sequence of machine instructions. 
  begin
    sum-sf <-- 0;
    k <-- 1;
    while (k <= 100) do
      sum-sf <-- sum-sf + k;
      k <-- k + 1;
    endwhile
    sum <-- sum-sf
  end;
     
         200
         201
         202
 sum-sf  203
      k  204
    sum  205
         206
         ...
 
     0
     1
   100
   
   
   
   
   ...
Assume that the the variables sum-sf, k and sum are stored in memory locations 203, 204 and 205, respecively. In addition, assume that the integer values 0, 1, and 100 have already been stored in memory locations 200, 201, and 202, respectively.
Then, given the set of machine instructions given in S5.2.4 of [SG3], we can roughly translate the algorithm given above to the following machine language program: 
   1 MOVE    200,203      // sum-sf <-- 0;
   2 MOVE    201,204      // k <-- 1;
   3 COMPARE 204, 202     // while-loop compare(k,100)
   4 JUMPGT  8            // jump out of while-loop
   5 ADD     203,204,203  //   sum-sf <-- sum-sf + k   
   6 ADD     204,201,204  //   k <-- k + 1
   7 JUMP    3            // endwhile
   8 MOVE    203,205      // sum <-- sum-sf




Problems to be Handed In for Grading by the Deadline:
(Note: Please submit hard copy to me. Not just soft copy via email.)

T8-Q1: (10 points) (Building a slightly better 32-bit ADD circuit)
In Section 4.4.3 of [SG3], the details of how to build a 32-bit ADD circuit was presented (circuit shown in Figure 4.27, p176). It makes use multiple use (32 times to be precise) of an abstraction of a 1-bit ADD circut shown in Figure 4.26, p.175). The 32-bit ADD circuit uses a total of 700 gates (or 2,208 transistors). Note that the circuit for 1-ADD given in Figure 4.26 is not optimized.
Optimize the circuit for 1-ADD (by applying logic laws or otherwise) to reduce the gate count and the transistor counts of the 32-bit ADD circuit.

T8-Q2: (15 points) (Modified from Problem 16 of Ch.5 of [SG3])
 Assume that the variables v, w, x, y, and z are stored in memory locations 200, 201, 202, 203, and 204, respectively. Using any of the machine language instructionsin Section 5.2.4, translate the following algorithmic operations into their machine language equivalents.

(b) Set v to the value of (w+x)-(y+z).
(Note: Assume the existence of the machine language command SUBTRACT X,Y,Z that computes CON(Z) = CON(X) - CON(Y). Also, you can use the registers to store the intermediate results.)

(c) 
   if (v >= w) then
      set x to y
   else
      set x to z
          (d) 
   Set y to 0
   while y < z do
      set y to the value (y + w + z)
      set z to the value (z + v)
   endwhile
   set answer to the value of y

(Note: Please check out Practice Problem 1-4 in Section 5.2.4 and also their answers at the end of the book [SG3].)

A-Problems: OPTIONAL Challenging Problems for Further Exploration

A9: (Faster ADD circuits)
The n-bit ADD circuit given in Section 4.4.3 of [SG3] is called a ripple carry adder since the carry bit ripples through the individual 1-bit ADD circuits, one step at a time from the 0th bit to the 0th bit. It therefore takes a total of n time steps to complete the addition, and for large n (say n=32 or 64), this makes for a rather slow n-bit ADD circuit.
Design a faster n-bit ADD circuit that takes only lg n time steps.
(Note: You may have to use more gates to achieve this.)

UIT2201: CS & IT Revolution; (Spring 2008); A/P Leong HW