Assignment 7, due Mar 5

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due on Fridays at the start of class, and unless there is what insurance companies call "an act of God", the only exceptions to this rule will be by advance arrangement.

There is a midterm exam on March 12!

1. Consider the addressing modes information given in Implementation and Performance Evaluation of the PDP-11 Family by Edward A. Snow and Daniel P. Siewiorek in Chapter 39 of Bell and Newell (Appendix 1 of the paper).

   The web version of this material is miserably formatted, as a result of OCR without sufficient proofreading. The presentation is supposed to be a tree saying that 100 percent of the instructions are fetched, 40 percent of the instructions have a source operand and 68 percent have a destination operand (this includes all single-operand instructions). The probabilities of the source modes are about 13, 3, 15, 1, 3, 0, 2 and 0 percent, in order of numerical opcodes - this adds up to 40 percent! The probabilities of the destination modes are about 31, 5, 8, 3, 8, 0, 5 and 1 percent, again in order. the probabilities of the 13 double operand instructions are 5, 2, 3, 0, 0.1, 0.1, 6, 2, 0.4, 0.1, 15, 5 and 0, respectively, in order. This should be enough information to help you decode the really bad formatting of the information in the paper.

   a) How many bits should have been devoted to the opcodes of each of the the 2-operand instructions, based on the information from this paper, for an optimal encoding?

   b) How many bits should have been devoted to the addressing modes for source and destination addresses in an optimal encoding of the PDP-11 instruciton set. You will need to give two sets of 8 answers, one for source and one for destination, and you will have to fudge the numbers, since the probabilities you were given are absolute and not conditional on the instruction having a source or destination field.

   c) What instructions should have been omitted from the instruction set?

   d) What addressing modes should have been omitted?

2. Assume that you have to design a machine with a 27-bit word. This makes it natural to group the bits in 3's, and 9's, and it makes it natural to use a carry-lookahead adder based on a 3-ary tree. Commercial carry-lookahead units use 4-ary trees, while the notes only presents a binary tree. Give an external spec for the internal nodes of this tree, showing their inputs, outputs, and describing, in as compact a way as possible, the logical behavior of these nodes.