Quiz 6

This quiz covers Chapter 5 of Tanenbaum. Please allow yourself up to 1 hour to take the quiz, and return it to me by 10:00 AM, Tuesday, October, 28, if you would like for me to mark it. I will post my answers via the course homepage later that day.

The designers of the Ray-O-Vac 10/97 need your help developing the instruction set. The machine has 32 registers each of which can be accessed by 8 addressing modes, and all instructions are to be 32 bits. Note that all modes and registers may be used for any operand, and that all instructions which require addresses are followed by one, two or three 32-bit words, and whether any are required is determined by the mode or the opcode itself. Design an instruction set (using an expanding opcode) which provides the following: 60 3-operand instructions, 120 2-operand instructions, 150 1-operand instructions, and 128 0-operand instructions.
First, it's important to note that 32 registers can be encoded in 5 bits, and 8 modes in 3 bits. Therefore 3-operand instructions require 24 bits for operands, 2-operand instructions require 16 bits for operands, and 1-operand instructions require 8 bits for operands. There are many possible solutions. Here's one:
```
3-operand instructions:

11000000 xxxxxxxx yyyyyyyy zzzzzzzz
11111011 xxxxxxxx yyyyyyyy zzzzzzzz

2-operand instructions:

10111111 00000000 xxxxxxxx yyyyyyyy
10111111 01111011 xxxxxxxx yyyyyyyy

1-operand instructions:

01111111 11111111 00000000 xxxxxxxx
01111111 11111111 10010101 xxxxxxxx

0-operand instructions:

00111111 11111111 11111111 00000000
00111111 11111111 11111111 01111111
```
Note that the high-order 2 bits encode the number of operands in the instruction. Although this is perhaps useful, it does mean that there is only room for expansion of 4 additional 3-operand instructions, and many more for each of the other types.
Consider the following infix assignment statement:
```
X := ((A-(B+C))*D)/(E/F)
```
1. Convert the infix expression to postfix notation.
```
ABC+-D*EF//
```
  Note that if we treat "=" as a binary operator, we can write the whole statement:
  XABC+-D*EF//=
2. Using two-operand instructions and no more than 4 registers (R0-R3), show the instructions required to implement the statement. Assume that MOVE A,B moves A to B, ADD A,B adds A to B, SUB A,B subtracts A from B, MUL A,B multiplies A times B, and DIV A,B divides A into B. In all cases, A or B can be a register or memory address, and the result is always stored in B.
```
MOVE A,R0
MOVE B,R1
ADD  C,R1
SUB  R1,R0
MUL  D,R0
MOVE E,R1
DIV  F,R1
DIV  R1,R0
MOVE R0,X
```
  Although a program with fewer instructions is possible, it would have more memory references.
3. Assuming each instruction takes 16 bits if only registers are referenced, and 16 additional bits for each memory reference, how many bytes long is your program?
  There are 7 instructions which each require a single memory reference (7 * 4 = 28 bytes) and two instructions which require no memory references (4 bytes) for a total of 32 bytes.
Expain the difference between an interrupt and a trap. Give an example of each.
An interrupt is generally initiated by an I/O device, and causes the CPU to stop what it's doing, save its context, jump to the appropriate interrupt service routine, complete it, restore the context, and continue execution. For example, a serial device may assert the interrupt line and then place an interrupt vector number on the data bus. The CPU uses this to get the serial device interrupt service routine, which it then executes as above.
A trap is usually initiated by the CPU hardware. When ever the trap condition occurs (on arithmetic overflow, for example), the CPU stops what it's doing, saves the context, jumps to the appropriate trap routine, completes it, restores the context, and continues execution. For example, if overflow traps are enabled, adding two very large integers would cause the overflow bit to be set AND the overflow trap service routine to be initiated.
Note: to make matters more confusing, Intel has instructions called INT and INTO which initiate or enable traps, and these are called TRAP and TRAPV on the Motorola. In addition to the hardware-initiated traps/interrupts described above, software initiated traps/interrupts are also possible.