HW07 Instruction Set Architecture
================================================================================

Refer to Chapter 5 in your textbook for documentation and questions.

3. Design an expanding opcode to allow all the following to be encoded in a 32-bit instruction:
15 instructions with two 12-bit addresses and one 4-bit register number
650 instructions with one 12-bit address and one 4-bit register number
80 instructions with no addresses or registers

5. Is it possible to design an expanding opcode to allow the following to be encoded in a 12-bit instruction? A register is 3 bits.
4 instructions with three registers
255 instructions with one register
16 instructions with zero registers

6. Given the memory values below and a one-address machine with an accumulator, what values do the following instructions load into the accumulator?
word 20 contains 40
word 30 contains 50
word 40 contains 60
word 50 contains 70

a. LOAD IMMEDIATE 20
b. LOAD DIRECT 20
c. LOAD INDIRECT 20
d. LOAD IMMEDIATE 30
e. LOAD DIRECT 30
f. LOAD INDIRECT 30

10. Convert the following formulas from infix to reverse Polish notation.
a. A + B + C + D − E
b. (A − B) × (C + D) + E
c. (A × B) + (C × D) − E
d. (A − B) × (((C − D × E) / F) / G) × H

11. Which of the following pairs of reverse Polish notation formulas are mathematically equivalent?
a. A B + C + and A B C + +
b. A B − C − and A B C − −
c. A B × C + and A B C + ×

12. Convert the following reverse Polish notation formulas to infix.
a. A B − C + D ×
b. A B /C D / +
c. A B C D E +×× /
d. A B C D E × F / + G − H / × +

14. Convert the following infix Boolean formulas to reverse Polish notation.
a. (A AND B) OR C
b. (A OR B) AND (A OR C)
c. (A AND B) OR (C AND D)

15. Convert the following infix formula to reverse Polish notation:
(5 × 2 + 7) − (4 / 2 + 1)

20. The Core i7 has a condition code bit that keeps track of the carry out of bit 3 after an
arithmetic operation. What good is it?

21. One of your friends has just come bursting into your room at 3 A.M., out of breath, to
tell you about his brilliant new idea: an instruction with two opcodes. Should you send
your friend off to the patent office or back to the drawing board?

23. For the 16-bit binary number 1001 0101 1100 0011, show the effect of:
a. A right shift of 4 bits with zero fill.
b. A right shift of 4 bits with sign extension.
c. A left shift of 4 bits.
d. A left rotate of 4 bits.
e. A right rotate of 4 bits.

24. How can you clear a memory word on a machine with no CLR instruction?

25. Compute the Boolean expression (A AND B) OR C for
A = 1101 0000 1010 0011
B = 1111 1111 0000 1111
C = 0000 0000 0010 0000

26. Devise a way to interchange two variables A and B without using a third variable or
register. Hint: Think about the EXCLUSIVE OR instruction.

27. On a certain computer it is possible to move a number from one register to another,
shift each of them left by different amounts, and add the results in less time than a multiplication takes. Under what condition is this instruction sequence useful for computing ‘‘constant × variable’’?

29. The loop instructions discussed in the text were for handling for loops. Design an instruction that might be useful for handling common while loops instead.

30. Assume that the monks in Hanoi can move 1 disk per minute . How long will it take them to solve the entire 64-disk problem?
Express your result in years.

32. A computer uses DMA to read from its disk. The disk has 64 512-byte sectors per
track. The disk rotation time is 16 msec. The bus is 16 bits wide, and bus transfers
take 500 nsec each. The average CPU instruction requires two bus cycles. How much
is the CPU slowed down by DMA?

34. Why do interrupt service routines have priorities associated with them whereas normal
procedures do not have priorities?

36. In the text, the concept of speculative LOAD instructions is discussed. However, there is
no mention of speculative STORE instructions. Why not? Are they essentially the same as speculative LOAD instructions or is there another reason not to discuss them?

37. When two local area networks are to be connected, a computer called a bridge is inserted between them, connected to both. Each packet transmitted on either network causes an interrupt on the bridge, to let the bridge see if the packet has to be forwarded. Suppose that it takes 250 μsec per packet to handle the interrupt and inspect the packet, but forwarding it, if need be, is done by the DMA hardware without burdening the CPU. If all packets are 1 KB, what is the maximum data rate on each of the networks that can be tolerated without having the bridge lose packets?

41. The towers of Hanoi is not the only little recursive procedure much loved by computer
scientists. Another all-time favorite is n!, where n! = n(n − 1)! subject to the limiting
condition that 0! = 1. Write a procedure in your favorite assembly language to compute n!.
42. If you are not convinced that recursion is at times indispensable, try programming the
Towers of Hanoi without using recursion and without simulating the recursive solution
by maintaining a stack in an array. Be warned, however, that you will probably not be
able to find the solution