Homework 4 Solution

CS26

60 pts., due Oct. 31

Show all work.

  1. (10 pts.) Consider a system in which the CPU uses a control sequence similar to that in Figure 3.5 and that the CPU and memory operate synchronously.
    1. Assume that a memory operation takes the same amount of time as one internal CPU step. Rewrite the control sequence. 

       1: PCout, MARin, Read, Clear Y, Set carry-in to ALU, Add, Zin
 2: Zout, PCin, MDRmemin
 3: MDRbusout, IRin
 4: R3out, MARin, Read
 5: R1out, Yin, MDRmemin
 6: MDRbusout, Add, Zin
 7: Zout, R1in, End

    2. Assume that a memory operation takes the same amount of time as two internal CPU steps. Rewrite the control sequence. 

       1: PCout, MARin, Read, Clear Y, Set carry-in to ALU, Add, Zin
 2: Zout, PCin
 3: MDRmemin
 4: MDRbusout, IRin
 5: R3out, MARin, Read
 6: R1out, Yin            # These could be carried out in the next step.
 7: MDRmemin
 8: MDRbusout, Add, Zin
 9: Zout, R1in, End

  2. (10 pts.) Assume the following timing constraints:

    What is the minimum time that must be allowed for performing each of the following operations?

    1. Transfer data from one register to another.

    2. Increment the program counter.

    Next, consider the Add instruction that has the control sequence given in Figure 3.5. The CPU is driven by a continuously running clock signal, such that each control step is 20 ns. in duration. How long will the CPU have to wait in steps 2 and 5, assuming that a memory read operation takes 80 ns. to complete? What percentage of the time is the CPU idle during execution of this instruction?

    The CPU waits for 60 ns. in each of the steps. (It spends 20 ns. working in each of the steps.) The total execution time of the instruction is 260 ns. with 120 ns. of waiting. The CPU is idle for 46% of the instruction's execution time.

  3. (20 pts.) For each of the following instructions:
    1. Add the immediate value NUM to register R1.

    2. Add the contents of memory location NUM (direct addressing) to register R1.

    3. Add the immediate value NUM to register R1 (indexed addressing); fetch the memory location whose address is that sum and add it to register R2.

    Write the sequence of control steps for:

    1. The bus structure in Figure 3.1.
      1. Add the immediate value NUM to register R1. 

         1: PCout, MARin, Read, Clear Y, Set carry-in to ALU, Add, Zin
 2: Zout, PCin, WMFC
 3: MDRout, IRin
 4: PCout, MARin, Read, Clear Y, Set carry-in to ALU, Add, Zin
 5: Zout, PCin
 6: R1out, Yin, WMFC
 7: MDRout, Add, Zin
 8: Zout, R1in, End

      2. Add the contents of memory location NUM (direct addressing) to register R1. 

         1: PCout, MARin, Read, Clear Y, Set carry-in to ALU, Add, Zin
 2: Zout, PCin, WMFC
 3: MDRout, IRin
 4: PCout, MARin, Read, Clear Y, Set carry-in to ALU, Add, Zin
 5: Zout, PCin
 6: R1out, Yin, WMFC
 7: MDRout, MARin, Read, WMFC
 8: MDRout, Add, Zin
 9: Zout, R1in, End

      3. Add the immediate value NUM to register R1 (indexed addressing); fetch the memory location whose address is that sum and add it to register R2. 

         1: PCout, MARin, Read, Clear Y, Set carry-in to ALU, Add, Zin
 2: Zout, PCin, WMFC
 3: MDRout, IRin
 4: PCout, MARin, Read, Clear Y, Set carry-in to ALU, Add, Zin
 5: Zout, PCin
 6: R1out, Yin, WMFC
 7: MDRout, Add, Zin
 8: Zout, MARin, Read
 9: R2out, Yin, WMFC
10: MDRout, Add, Zin
11: Zout, R2in, End

    2. The bus structure in Figure 3.13.
      1. Add the immediate value NUM to register R1. 

         1: PCoutA, Pass A, MARin, Read
 2: PCoutA, Clear B, Set carry-in to ALU, Add, PCin, WMFC
 3: MDRoutB, IRin
 4: PCoutA, Pass A, MARin, Read
 5: PCoutA, Clear B, Set carry-in to ALU, Add, PCin, WMFC
 6: R1outA, MDRoutB, Add, R1in, End

      2. Add the contents of memory location NUM (direct addressing) to register R1. 

         1: PCoutA, Pass A, MARin, Read
 2: PCoutA, Clear B, Set carry-in to ALU, Add, PCin, WMFC
 3: MDRoutB, IRin
 4: PCoutA, Pass A, MARin, Read
 5: PCoutA, Clear B, Set carry-in to ALU, Add, PCin, WMFC
 6: MDRoutA, Pass A, MARin, Read, WMFC
 7: R1outA, MDRoutB, Add, R1in, End

      3. Add the immediate value NUM to register R1 (indexed addressing); fetch the memory location whose address is that sum and add it to register R2. 

         1: PCoutA, Pass A, MARin, Read
 2: PCoutA, Clear B, Set carry-in to ALU, Add, PCin, WMFC
 3: MDRoutB, IRin
 4: PCoutA, Pass A, MARin, Read
 5: PCoutA, Clear B, Set carry-in to ALU, Add, PCin, WMFC
 6: R1outA, MDRoutB, Add, MARin, Read, WMFC
 7: R2outA, MDRoutB, Add, R2in, End

    Assume that each instruction consists of two words and that each word occupies one memory location. The first word specifies the operation and addressing mode, and the second word contains the constant NUM.

  4. (10 pts.) Write the sequence of control steps for the instructions
    1. Add (R3), R1, Figure 3.5. 

       1: PCoutA, Pass A, MARin, Read
 2: PCoutA, Clear B, Set carry-in to ALU, Add, PCin, WMFC
 3: MDRoutB, IRin
 4: R3outA, Pass A, MARin, Read, WMFC
 5: R1outA, MDRoutB, Add, R1in, End

    2. The branch-on-negative instruction discussed in Section 3.2.1. 

       1: PCoutA, Pass A, MARin, Read
 2: PCoutA, Clear B, Set carry-in to ALU, Add, PCin, WMFC
 3: MDRoutB, IRin
 4: If N = 0 then End
 5: Offset-field-of-IRout, PCoutB, Add, PCin, End

    for the bus structure in Figure 3.13.

  5. (10 pts.) Write the sequence of control steps for the MIPS instructions jal and jr for the bus structure in Figure 3.13.
    1. jal 

       1: PCoutA, Pass A, MARin, Read
 2: PCoutA, Clear B, Set carry-in to ALU, Add, PCin, WMFC
 3: MDRoutB, IRin
 4: PCoutA, Pass A, R31in
 5: Branch-target-field-of-IRout, Pass A, PCin, End

    2. jr 

       1: PCoutA, Pass A, MARin, Read
 2: PCoutA, Clear B, Set carry-in to ALU, Add, PCin, WMFC
 3: MDRoutB, IRin
 4: R31outA, Pass A, PCin, End

Extra Credit. (10 pts.) Section 3.4.1 states that the simple latches of Figure 3.3 cannot be used to implement the registers in Figure 3.13. Instead, edge-triggered or master-slave flip-flops are needed. However, would it be possible to use the latches of Figure 3.3 if a Z register were included between the output of the ALU and the C bus, similar to Figure 3.1? Justify your answer. How would this affect performance?

Yes, the latches of Figure 3.3 could be used if a Z register were included. The problem with latches is that they can't be used for simultaneous reading and writing. Including a Z register ensures that this doesn't happen by breaking all ALU operations into two steps: read operand registers onto the A and B buses and load Z; and read Z onto the C bus and load destination register.

This has a substantial impact upon performance. Every ALU operation now requires two clock cycles. This negates much of the performance improvement gained by using multiple CPU buses.


Thomas P. Kelliher
Sat Nov 2 15:05:11 EST 1996
Tom Kelliher