These questions are to aid you in your studies. They are not to be turned in and they do not cover all the topics covered in class after Problem Set 5.

1. In class, we discussed how to use Booth's algorithm to be able to multiply 2 bits in a cycle. Implement the same technique to multiply 4 bit in a cyclee. Note that since the algorithm can only do one add (or subtract) in one cycle, that goal cannot be achieved. i.e. sometimes, we can only process 2 or 3 bits in 1 cycle. If the multiplier number is random, on average how many bits are processed at each cycle?

2. Determine the decimal value of the following IEEE floating point numbers.

   1. 1 10000000 10100000000000000000000
   2. 0 00000000 01010000000000000000000
   3. 1 11111111 00000000000000000000000

3. From Tanenbaum, 4th edition, Appendix B, 4.

   The following binary floating-point number consists of a sign bit, an excess 63, radix 2 exponent, and a 16-bit fraction. Express the value of this number as a decimal number.

   0 0111111 0000001111111111

4. From Tanenbaum, 4th edition, Appendix B, 5.

   To add two floating point numbers, you must adjust the exponents (by shifting the fraction) to make them the same. Then you can add the fractions and normalize the result, if need be. Add the single precision IEEE floating-point numbers 3EE00000H and 3D800000H and express the normalized result in hexadecimal. ['H' is a notation indicating these numbers are in hexadecimal]

5. From Tanenbaum, 4th edition, Appendix B, 6.

   The Tightwad Computer Company has decided to come out with a machine having 16-bit floating-point numbers. The model 0.001 has a floating-point format with a sign bit, 7-bit, excess 63 exponent and 8-bit fraction. Model 0.002 has a sign bit, 5-bit, excess 15 exponent and a 10-bit fraction. Both use radix 2 exponentiation. What are the smallest and largest positive normalized numbers on both models? About how many decimal digits of precision does each have? Would you buy either one?

6. The following numbers are represented exactly with a 9-bit floating point representation, in the format of the IEEE Floating Point standard:

   -infinity, -1, 0, 5/16, 19.5, 48.

   1. How many bits are needed for the fraction?
   2. What is the bias?
   3. Write each number in in the 9-bit floating point representation, below:

      Value	Representation
      48
      19.5
      5/16
      0
      -1
      -infinity

7. We must compute the following expression:

       a*x^6 + b*x^5 + c*x^4 + d*x^3 + e*x^2 + f*x + g 
   

   • How many operations and time-steps will the computation take on a single processor system (Use the smallest number of operations possible)?
   • How many operations and time-steps will the computation take on a multiprocessor system with 4 processors? (Use the smallest number of operations possible)
   • What is the speedup of the multiprocessor system over a single processor?

8. In an Omega network as presented in class, assume that there are n inputs and n outputs. Let k be the size of each switch. For k taking the values 2, 4, 8, and 64, answer the following questions. (Assume the cost of each switch is k^2)

   1. What is the cost of the network as a function of n?
   2. What is the latency of the network?
   3. Assume that n=64. What k value would you choose? Why? State your assumptions and design point.