CSC 258 exam questions and solutions, 30 April 2004

1. [10 marks]
Prove or disprove the following. The boolean laws handout appears as appendix 'A' to this exam. (You don't need to cite the names of laws unless it is not obvious how you are getting from one line to the next in your proof.)

a)

b)

c)

d)

solutions

2. [5 marks]
Consider the following circuit:

a)

b)

c)

solutions

3. [10 marks]
On a television game show, there are three doors and there is a prize behind only one of them. The player is permitted to open two of the doors. They are far enough apart (physically) that you don't have to worry that the player might attempt to open two of them simultaneously.

A sequential circuit controls locks on these three doors, locking the third door once the player has tried two of them. This sequential circuit has three outputs, one for each door: 1 for locked, 0 for unlocked.

Design this sequential circuit. There are four inputs to your circuit. A "reset" input unlocks all three doors. Three other inputs, one for each door, indicate whether the door is currently open. After the player opens two distinct doors, the third door (only) should lock. However, the player is allowed to open and close one door a few times before trying a second door. Furthermore, the doors might be left open, or might be closed again -- the locking decision has to be made based on the history, not the current door state.

You can use any standard sequential circuit components you like, such as any kind of flip-flops, etc; as well as higher-level combinational circuit components such as decoders, full adders, etc. You can assume a system clock or not, as you wish.

solution

4. [10 marks]
In binary integer multiplication, recall the method for collapsing a run of ones, preceded by a zero, to two terms. E.g. 2⁵ + 2⁴ + 2³ + 2² = 2⁶ - 2².

Use this method, not necessarily very formally but showing your work, to multiply the two unsigned numbers 10000011111000 and 11111 (base two).

(To avoid transcription errors: The first number is 2¹³ + 2⁷ + 2⁶ + 2⁵ + 2⁴ + 2³.)

Your intermediate calculations will involve powers of 2, possibly expressed in base ten, but your final answer should be a string of ones and zeroes which represents an unsigned base two number.

solution

5. [8 marks]
Add the following pairs of four-bit numbers (i.e. the bit x₃ is the sign bit). Specify the resulting values of all four condition code bits.

Example problem:

      0001
    + 0001
      ----

Answer:

      0010

Problems:

  0111
+ 0101
  ----


  1000
+ 1000
  ----


  0101
+ 1101
  ----


  1111
+ 0001
  ----

solution

6. [15 marks]
a) Write a PDP-11 subroutine which takes three arguments which are pushed on the stack, and returns the value 3x² + y + 6z in R0. (Remember that the MUL op produces a two-word result unless its destination register is odd. You will want to use an odd destination register because you just want a one-word result.)

b) Write a PDP-11 "main program" which calls that subroutine to compute f([R0], [100], [102]-1) and puts the result in memory location 104. That is, the parameter x is the contents of R0; y is the contents of memory location 100; and z is one less than the contents of memory location 102. When your program HALTs, it will have placed the value 3[R0]² + [100] + 6([102]-1) in memory location 104. It can change any registers.

solution

7. [10 marks]
Here is a function (method) in C or Java to perform a binary search of an array. It consults a global array of integers named "a", in which it searches for the value passed as parameter. It returns an index at which this value is found, or -1 if the value does not appear in the array. The array is required to be sorted in ascending order.

(I think that everyone here knows C or Java. If not, please ask an invigilator to write this subroutine out for you in some other high-level language you know.)

Write a PDP-11 program (not a subroutine: nothing is on the stack, you can use any registers, and end with HALT) which performs the above binary search algorithm, taking the "x" value from memory location 100 and searching an array of 50 words which starts at location 500. Leave your result in R0. Remember that the DIV op requires an even register as target (destination), and it puts the integer quotient in the named register and the remainder (the "%") in the next higher register.

Do not assemble your program; leave it in symbolic form.

int search(int x)
{
    int low = 0;
    int high = n;
    int mid;

    while (high > low) {
        mid = (high + low) / 2;
        if (a[mid] == x)
            return(mid);
        else if (a[mid] < x)
            low = mid + 1;
        else
            high = mid;
    }

    return(-1);
}

solution

8. [5 marks]
Using our simple one-bus CPU architecture (see appendix B to this exam), write microcode to implement an "RTS". This pops the return address off the stack and puts it into the PC register. This involves memory access, and changing the value of the stack pointer. You can treat R6 as the stack pointer, but the architecture is not byte-addressable; your microcode has only to add 1, not 2, to R6 to constitute popping the stack.

solution

9. [5 marks]
Again using our simple one-bus CPU architecture in appendix B, write microcode to perform a BHI instruction. This is an unsigned version of BGT (and as such is slightly simpler): it branches if the condition codes Z and C are both 0.

The standard fetch sequence will be steps 0, 1, and 2; begin your code with step 3. You have to add the address field of the IR (via "AddressFieldOfIR_out") into the PC register, if and only if Z and C are both 0.

solution

10. [4 marks]
In the PDP-11 (as in most CPUs), when we do a subroutine call with JSR/RTS, the subroutine pushes and restores all registers (GPRs) it wants to use. When an interrupt service routine is called for an interrupt, it preserves GPRs like in a subroutine call, but we also push and restore the PSW (processor status word). Why is this different?

solution

11. [4 marks]
RISC CPUs normally have "three-register format" instructions. Give an example of the advantage of this by comparing a (very short) bit of optimal PDP-11 code to shorter equivalent code using three-register format instructions.

solution

12. [4 marks]
Some RISC CPUs have a "delayed branch rule", in which a branch has a delayed effect -- one more instruction following the branch instruction is executed even though we've supposedly already branched away. How does this (sometimes) save us a cycle?

solution

13. [10 marks]
When we fetch an instruction into the CPU and store it in the IR register, attached combinational circuits decode the instruction for various reasons. One thing they need to do is to extract the opcode and compute the microaddress of the microroutine to branch to.

This is potentially a mess of combinational circuitry, but sometimes we can simplify the circuitry by choosing our opcodes wisely.

Suppose we have a CPU with 6 opcodes. Here we list the ops (by their mnemonics (e.g. "MOV")) and the microaddresses of their microroutines (where we have to microbranch to after fetching the instruction):

Mnemonic	µaddress
ADD	3
SUB	6
XOR	11
BR	19
BEQ	22
BGT	27

Suppose we have a four bit field for the opcode. Choose opcodes (in the range 0 to 15) for these six instructions and draw the decoding circuitry which turns the opcode into the five bit (unsigned) microroutine address, as specified above in base ten, to be loaded into the µPC. Clearly label your circuit's inputs and outputs.

solution

End of exam. Total marks: 100.