CPSC 501 Notes

You should be able to get most of the information from Jordan Kidney's CPSC501 page.

I'll put up anything different on this page.

News

1. If you are still having difficulty finding optimizations, you may deoptimize the code and apply an optimization (though there are enough optimizations in there without doing this)
2. Remember that changing the opt flag counts as 1 (only one) optimization.
3. Replacing division with reciprocal multiplication (multiplying by (1/n) in floating point rather than dividing by n) is a strength reduction technique. You have to maintain the number in reciprocal form to eliminate the division operations.
4. If you're familar with pointer syntax, you may want to try replacing array lookups with pointers (data[i] to *data_i)
5. Marking will mostly be based on methodology, actual performance gains are not that important
6. If you're interested to see how much faster the FFT can get, check out FFTW. This includes links to papers describing how it was designed. (On another note, this page also has benchFFT software for benchmarking FFTs, which comes with several FFT implementations)
7. For the bonus you must write an interactive gui and graphing code. Simply producing a graph is not enough. Also, please notify me by email to schedule bonus demos. Remember that the graphs are based on a windowed or chunked view of the sample. The FFT is calculated on each chunk.

Tutorial sections

My ucalgary.ca email is hyswchen.

• Week1 CVS intro

  • You must show that you used CVS(or some other version control) for the assignment, a good way to do this is to use the cvs log command

  • How to connect to a remote CVS server CVS tutorial

    • CVS will try to connect by rsh by default, but you should use ssh
    • bash: export CVS_RSH=ssh
    • csh/tcsh: setenv CVS_RSH ssh
    • Then use the following CVSROOT:
    • :ext:user@host:/full/path/to/repository
    • Your cvs commands will then work the same as before
• Week2 Junit testing

• Week3 Refactoring

  • Tip: Refactoring.com has a nice list of all the refactorings from the book, with a bit of description as well (finally it's up again)
  • In the CPSC lab, I will be in the area near the printers most of the time, I will check the other side if it gets full.

  • For the refactorings covered in class, try to remember all the steps. For an exam, if you only do 2 out of 3 steps, then you might lose marks.

• Assignment 1

  • If you don't have code to refactor for Assignment 1 Jordan Kidney's 501 Code Repository has a VetPetSystem that you can use
  • 2 points per refactoring
  • 5 marks of testing is for properly setting up your unit test framework
  • Remember to show that you used version control (type in cvs log in your checkout dir)
  • The assignment specifies hard copy submissions, you can hand these in at the drop boxes on the second floor of MS.

• Bonus Presentations for Assignment 1

  • Presentations will be Oct 15th and Oct 16th
  • Sign up for the bonus presentations by email or in class.

• Week4 More refactoring

  • I will be covering some of this in Wednesday, since there is no Monday class.

• Assignment 2

  • Jordan Kidney's Assignment 2 driver in zip format, and in tar gz format
  • Do not try to modify the driver code, your Inspector class should work with the plain version.
  • The README file should tell you everything, I will go over it again in lab
  • The exact output format of the inspector does not matter, as long as it is easy to read
  • Setting up packages will cause problems with the driver and marking.
  • This assignment will be submitted through Blackboard
• Week5 Reflection
• Week6 More Reflection: Object Inspector

• Assignment 3

  • You will have to use the array class names to create array objects, so something like “[C” instead of “char[]”.
  • Jordan Kidney has provided the new test driver, also in his code repository, you can find some parts of the serializer and deserializer in the files that start with Asst3. This driver assumes your CML document class has a specific name, CMLDocmument. The test driver comes with a blank CMLDocument.java, so be careful when extracting/copying, or you might overwrite your CMLDocument.java.
  • Remember the difference between a Class and a class instance. Only class instances will be serialized, not the Class objects.
  • To be accurate, you should use the getDeclared* methods along with inheritance(superclass) traversal to get the fields. Otherwise you will miss out on fields that are hidden.
  • You should provide a Junit test case to demonstrate the text stream IO for your CML output/parsing.
• Week7 Serialization
• Week8 Deserialization

• Assignment 4

  • Jordan Kidney's 501 Code Repository has the DFT and FFT code needed under the files and directories with “Asst4_from_class” Asst4_from_class.tar.gz (the “from class” version has an example of running the code)
  • You may have to adjust the size of the input to get measurable results. If you do this, make sure to read the comments for four1 to see the requirements on the size of the input.
  • You'll probably have to balance between increasing the size and creating a loop of executions, to keep the DFT and FFT in comparable ranges.
  • Marking will be more on the basis of following a methodology (optimize, regression test, profile..) for optimization rather than the actual performance improvements.
  • Look at the main function of Dft_fft.cc to see how to use the DFT and FFT functions. You should not be optimizing/timing the create* functions (createSawtooth...etc), only the FFT functions.
  • The DFT is a baseline performance measure, you do not need to optimize it

  • You can generate tests using the baseline DFT or the unmodified FFT. There may be slight floating point differences between the DFT and FFT outputs, so you may have to compare equality within an error margin, rather than strict equality.

  • It is probably easier to just create another executable for regression testing rather than to use a testing framework.
  • Gprof should be all that you need, but if you're interested, you can also try Valgrind which instruments code dynamically, I mistakenly said that it used a sampling technique in the lab section.
  • Unfortunately, gprof doesn't seem like it will help a lot, because the FFT is in one function, but you should provide evidence that you used it anyway. Probably the best way to do this is to extract some functions, which I will allow as a way to show an inlining optimization (you should make a note of this in your report though).
  • Bonus
• Week10 Profiling