Problem Set Number 5
Computer Science 471
Due by 5 PM, Wednesday Nov. 10, 1999
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
sesamest.
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 prof
are easy to use--just do the following for each:
- Compile the program with cc, not lcc,
using the following flags: -o32 and -mips1;
- Run pixie on the program;
- Run a.out.pixie;
- 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:
- your two source programs
- your two assembly language programs
- the two ``Opcode distribution'' tables from the two
prof 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 prof 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?
Hint: 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.
Try not to irritate the other users of these machines!