Problem Set Number 1
Computer Science 471

Due by 5 PM, Monday Sept. 25, 2000

Reading: Appendix B, Chapter 3, parts of Appendix A of the Patterson and Hennessy text.

1. Make gates out of muxes. Show how to use a single 2-input multiplexor to implement AND, OR, NOT, and EXOR gates (i.e., one mux per gate), if you can. Assume that logical values 0 and 1 are available, and that your two inputs are presented in high-true form only. One of these gates should give you trouble; please explain.

2. What hardware is required to test 32-bit quantities for equality? Draw a gate-level circuit with 32-bit inputs x and y, and 1-bit output x==y. Use some clear shorthand for repeated instances of the same structure.

3. What hardware is required to test whether one 32-bit quantity is less than another? Sketch the general idea for a combinational logic circuit that would take 32-bit, signed, 2's-complement, integer inputs x and y and produce a 1-bit output x<y. You do not need to draw all the gates; just be clear about what is required.

4. Compare the speeds (the sum of the delays through the gates--never mind the wires) of the circuits you proposed for questions 2 and 3: which is faster, and why? How does the speed of the circuits depend on the width of the operands?

5. Draw a gate-level circuit for x>=0 (where x is 32-bit, signed, etc., etc.).

6. Problem B.20 from the text

Note on the following MIPS programming problems: If you like, you may use the text's SPIM simulator, which is installed on the CS machines (not on the CIT machines). Just add these lines into your .cshrc file:

setenv MANPATH ${MANPATH}:/u/cs471/SPIM/man
setenv PATH ${PATH}:/u/cs471/SPIM/bin/${CPUTYPE}

and then use man spim and man xspim to learn how to use the simulator. Appendix A may be helpful too.

7. Problem 3.1 from the text.

8. Problem 3.2 from the text.

9. Problem 3.6 from the text.

10. Problem 3.10 from the text.

11. Problem 3.11 from the text.

12. Problem 3.23 from the text.