Problem Set Number 5
Computer Science 471

Due by 5 PM, Monday Oct. 21, 1996

Chapter 2 of the text is the background reading for some of these problems.

1. (5 points) Exercise 3.23 from the text.

2. (5 points) Exercises 4.18 and 4.19 from the text. Note: exercise 4.18 refers to ``Figure 4.46 on page 283,'' but should instead refer to Figure 4.47 on page 292.

3. (5 points) Exercise 5.6 from the text. Here again the reference to Figure 4.46 should instead be to Figure 4.47. Please answer this using the multi-cycle design of Chapter 5, and the corrected figures in the handout if necessary. Note that lui (load upper immediate) is not a ``load'' instruction (sorry about the name). The reason is that lui puts an immediate value in a register, and never touches the data memory.

4. (20 points) Using the tools pixie and prof on a MIPS-architecture SGI machine, generate an opcode distribution histogram for some non-toy program (your choice). Use CIT machines ernie, elmo, or oscar, or CS machine indy105. The pixie and prof tools are easy to use--just check out the man pages and experiment a little. Turn in your source program (or a pointer to it if it's longer than 2 pages) together with the ``Opcode distribution'' table from the prof output. The opcode distribution table is a list of opcodes sorted by frequency of execution in your program, and includes for each opcode its percentage of all instruction executions and the cumulative percentage.

5. (20 points) The prof (with pixie) tool reports CPI directly, as you saw in your experiments for question 4. Please come up with two programs that demonstrate high and low extremes of CPI (not, repeat not extremes of runtime!) on one of the SGI machines. These can be short, ``toy'' programs, but they should do some meaningful computation and not, e.g., a series of meaningless divides! Things that contribute to a high CPI include complex arithmetic instructions, large data sets, and deep recursions. Small CPI can be achieved by, well, simple instructions, small data sets, etc. Turn in your two source programs, the opcode distribution tables (as in question 4), the CPI reported by prof, and the ratio of the two CPI figures (big one divided by little one). If you find yourself especially interested in this question, you might try this: have the two programs compute the same thing, but with different algorithms (again, we're looking for differences in CPI, not runtime, which may be different too). Try not to irritate the other users of these machines.

6. (5 points) Here comes the Chapter 5 questionnaire: Please fill it out and e-mail the result to the publisher as directed. As usual, please do not ``cc your instructor on this email,'' as the form directs. To get the 5 points for this question, just write down the time you sent your message to the publisher.

7. (1 point) How long did this take you, not counting the reading, and with whom did you work?