Problem Set Number 5
Computer Science 471

Due by 5 PM, Wednesday Nov. 11, 1998

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. 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 pixstats on the MIPS-architecture CS machines elan and kastle. 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 an iterative algorithm and a recursive algorithm for some simple problem. You'll find that pixie and pixstats are easy to use--just check out the man pages and experiment a little. Turn in the following:

• your two source programs
• your two assembly language programs
• the two ``Opcode distribution'' tables from the two pixstats outputs (An 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. We are not looking for the ``static opcode frequency'' table, which pixstats also produces.)
• a few sentences that discuss any noticeable differences between the two distributions--can you attribute these differences to features of the source or assembly programs? Or perhaps, despite using two different approaches, your two tables are quite similar--if so, why?

• the ``spec'' opcode in the table is a catch-all for the simple instructions with 3 operands, so you won't be able to tell 3-register adds from subtracts, etc.
• you will want to run your programs on a big enough problem to get some instructions to execute millions of times--problems that are too small can exaggerate the importance of rarely-executed instructions.