Problem Set Number 5
Computer Science 471

Due by 5 PM, Wednesday Nov. 8, 2000

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

1. Exercise 2.14 from the text. Please include a short justification for each subset--an equation will do.

2. (counts as 2 questions) Exercise 2.37 from the text, but just find one article or advertisement. The more egregious, the better. Turn in a copy of the article, together with your analysis of it.

3. Exercise 3.17 from the text.

4. Exercise 5.25 from the text. Please answer this using the multi-cycle design of Chapter 5. 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.

5. (counts as 3 questions) Figure out how to use the tools pixie and prof on the MIPS-architecture CIT (not CS) machines you reach by rlogging into "zoe" (you may need to use ssh rather than rlogin). The machine name is important. If you use "sesamest" you may end up on "oscar" which for unknown reasons is configured in some inconvenient way. Then find or write two different (short!) C programs that solve the same problem in two different ways, and generate an opcode distribution histogram for each one, using the tools. For example, you might write two different integer sort programs. You'll find that pixie and prof are easy to use--just do the following for each of your programs:

  1. Compile the program with cc, not lcc, using the following flags: -o32 and -mips1;
  2. Run pixie on the program;
  3. Run a.out.pixie;
  4. Run prof -archinfo on the .Counts file.
(The man pages may be helpful.) The opcode table will be at the bottom of the output. The output will be sent to stdout, so the output should be redirected to a file. Turn in the following: Hint: you will want to run your programs on a big enough problem to get some instructions to execute many millions of times--problems that are too small can exaggerate the importance of rarely-executed instructions and overhead instructions. Try not to irritate the other users of these machines!