Workshop In Algorithms And Data Structures 2009, Semester B Cache Performance Of Algorithms

1. Submission is in pairs or triplets.
2. Only the first few classes will be held, giving background and technical information concerning the workshop.
   After that, work is independent. You are welcome to contact the teaching assistant (sagihed@post.tau.ac.il) if you have questions or run into difficulties.

1. http://lwn.net/Articles/252125/

1. http://www.cc.gatech.edu/~bader/COURSES/UNM/ece637-Fall2003/ (many references inside)
   
2. http://www.brics.dk/~gerth/Papers/isaac02.ps.gz
3. http://www.daimi.au.dk/~large/ioS08/
4. http://www.dunkel.dk/thesis/
5. http://portal.acm.org/citation.cfm?id=1227161.1227164&coll=ACM&dl=ACM&CFID=24915435&CFTOKEN=71845061
6. http://portal.acm.org/citation.cfm?id=1283383.1283481&coll=ACM&dl=ACM&CFID=24915435&CFTOKEN=71845061
7. http://portal.acm.org/citation.cfm?id=1248377.1248394&coll=ACM&dl=ACM&CFID=24915435&CFTOKEN=71845061
   

1. Library for data structures handling inputs larger than main memory.
   http://stxxl.sourceforge.net/
   

1. getrusage (http://rabbit.eng.miami.edu/info/functions/time.html#getrusage)
   This method enables you to obtain a clean measure of the cpu time spent on your code (excluding time spent by the operating system while your code was running). This method also enables you to obtain a page fault count for your program (how many times a page had to be loaded from disk into memory). This count is relevant if you're comparing algorithm performance when input size does not fit into main memory, and you want to let the operating system manage the disk read/writes on its own. The relevant page fault count is the "major page fault" count (minor page fault do not load from disk), available using the ru_majflt field in the result of getrusage.
   This library is available on any linux in the CS computer network.
   See the documentation above for exact usage details.
   
2. valgrind (http://valgrind.org/docs/manual/cl-manual.html)
   This tool simulates a cache, and provides several measures including a total of instructions executed, level 1 cache misses and level 2 cache misses.
   It also enables you to decide on any cache configuration you'd like, such as the size of the cache, the size of a cache block, and the cache associativity.
   Because the tool performs a simulation, its major drawback is that it slows down the execution considerably. Examine this drawback with different input sizes on your implementation, before choosing to use valgrind.
   The tool is available on nova in the CS computer network.
   Usage:
1. run:
   valgrind --tool=callgrind --simulate-cache=yes --<cache level>=<cache configuration> <program> [arg1] [arg2] ...
   In the standard output, under "D1 misses" is the total level 1 cache misses.
   Under "L2 misses" is the total level 2 cache misses.
   
2. An output file callgrind.out.<process_id> is generated in the current directory. Read it by running:
   callgrind_annotate callgrind.out.<process_id>
   Under "PROGRAM_TOTALS", "Ir" is the number of instructions executed.
3. To set the cache configuration use the parameter -
   --<cache level>=<cache size bytes>,<cache associativity: possible cache blocks per memory block>,<cache block size bytes>
   where "cache level" is either D1 for level 1 cache or L2 for level 2 cache.
   e.g. --D1=16384,256,64 means a 16,384B Level 1 cache, with blocks of size 64B and fully associative.
   
3. cputrack (http://docs.sun.com/app/docs/doc/816-0210/6m6nb7m6s?a=view)
   This tool enables you to obtain a real measure of cache misses and instructions executed on the machine you are running.
   Usage:
   cputrack -T=99999 -c <event> <program> [arg1] [arg2] ...
   <event> can be Instr_cnt for the total instruction count, DC_miss for level 1 cache misses or L2_dmiss_ld for level 2 cache misses.
   This tool is available on aries in the CS computer network.

1. The specification document should be submitted by - 17 / 5 / 2009.
2. The final workshop project should be submitted by - 12 / 9 / 2009.
   Note: the final project deadline is the final deadline for all submitted works from this semester. This deadline is dictated by the university and therefore we have no control over it!! Therefore note that no extensions to this date will be possible.
   

1. The specification document should be in html, word, pdf or rtf:
• your names, IDs and emails.
• describe the algorithm you have selected and how you intend to implement it
• explain how you will test correctness
  
• describe what inputs you intend to run your algorithm on and what you intend to compare
  
2. The final project submission:
   
• All source code and related libraries / files zipped into 1 compressed file.
• do not submit executables
  
• whenever the algorithm is run with a command line “-test” option, it must expect input and printing output in the formats specified for each group
• whenever the algorithm is run with a command line “-trace” option, it must create a new trace.txt file in directory in which the executable is present (overwrite the trace.txt file if it exists). The trace lines to be printed are specified separately for each group.
• all input, output and trace files are space separated between data elements and “\n” or “\r\n” separated between lines
• A documentation in html, word, pdf or rtf:
• your names, IDs and emails.
  
• short reminder of the project you selected
• description of any difference between the original work plan submitted and final work performed on the project.
  
• very general classes and/or main methods overview
• explanation of how to compile and run the programs
  
• explanation of how correctness was checked
• a precise description of the experiments performed, the inputs used and all exact parameters.
• a description on the experiments’ results, including all relevant graphs.
• convincing explanations that the measurements taken are correct.
• instructions on how to compile and execute the code

Good Luck!