CS 47 - T. Howell - Spring, 2008

Homework Assignment #6

Due Tuesday, May 13, 2008 by 23:59 as an email attachment hw6.zip (details below).

You are to write an assembly program access_counter.s to execute the rdtsc instruction and move its result from registers %edx and %eax to locations given by two pointer arguments. This program will be very similar to the mull.s program of HW 3 and HW 5. Its prototype will be:
void access_counter(unsigned *hi, unsigned *lo);
Your program will be functionally equivalent to the one given in Figure 9.9 on page 664, but it will not use the "asm" instruction.

You are to write a single C program that performs a timing study of your program bigfact . If you did bigfactx or subfactx , use that instead. Use the posted solution if you did not get your own bigfact to work. I am willing to discuss other choices for the program to be timed. See me individually if you want use another program as your test subject. You are to use the cycle counter code as described in the text and slides. You are also to set up a K-best timing study as described in the text and the slides. (see pages 663-664 of the text and slides 14, 17, 18, and 20 of class24.ppt) You are to time your code for several values of n. Plot your results as in Figure 6.50 on page 523. Are there any discontinuities? What can you infer about cache behavior? After you run your timing tests, you should describe your results in detail in your header comment, including how many times you ran the code, what variations you saw, and the conclusions you can draw from your study. Note that all code should be compiled with the -O2 option.

Extra credit (+25%): Determine the asymptotic running time of your program: O(n log n), O(n ²), etc. You will probably want to use values of n, up to 10,000 or more if you use an experimental approach. It is also possible to find the answer analytically, but we have not covered techniques to do that in this course. You should check how well your growth rate function fits the experimental data by plotting them together on one graph.

Extra credit (+10% ?): Submit a question for the final exam. If I choose to use your question you will receive an extra 10% on HW 6 plus there will be a question on the exam that you know how to answer. Good exam questions test your understanding of one specific important topic that we have covered this semester. This question should be submitted early and separately from the rest of HW 6 in order to have a chance of being included on the final exam.

Submission requirements and grading system

As noted above, you are to email me your programs as a .zip file hw6.zip, which should contain all of your source code, including a main program to drive the timing tests. Your code should produce output to allow me to check execution times against your own study as described in your header comment. Your email must be sent to me by 23:59 on Tuesday, May 13 (the last day of class). Your email must have the following subject line:

CS 47 Section x Homework #6 John Doe

but of course with your own name and section number instead of "John Doe" and "x." Please also preserve all spacing and capitalization in this subject line.

As with any code you submit, each code file must be appropriately documented with a header comment containing (as a minimum) your name, the class and section number, the homework number, the problem number, the date, and a brief description of the problem.

I will grade according to three criteria: execution tests (70%), source code (20%), and documentation (10%). I believe I have specified these two programs very precisely above, but if you have any questions about the behavior of the programs it is your responsibility to ask me before the submission date.

Failure to observe any of the submission requirements stated above may result in a grade of 0 on this homework!

Happy programming!