CMSC 411Project
Due May 9, 6:00PM

Overview

You will be both writing a small amount of code (for Part II), and performing analysis on the results of running code on a machine in the Linux lab (for both Parts I and II).  You will have to turn in both the code that you write, and a report summarizing results, by answering the questions in each part. 

Part I

Using the code in Exercise 5.2 of Hennessy and Patterson, create and run a program on a Linux lab machine to analyze the size of the caches on the machine.  A file with the code is located here.

Then answer the following questions in a written report:

1. Plot the results of your program with elapsed time on the y-axis and the memory stride on the x-axis. Use a logarithmic scales for both axes. Create a separate line for each array size, where a line denotes the results for a particular cache size. (5.2(a) in H&P)
   
2. How many levels of cache are there? (5.2(b) in H&P)
   
3. What are the overall size and block size of the first-level cache? (5.2(c) in H&P)
   
4. Explain any inconsistencies in your data. What factors may have caused you to get inaccurate results? In an ideal world, what could you do to help reduce the occurrence of inconsistencies that may have occurred?

Part II

Use the information you gathered in Part I to evaluate the performance of the six possible loop orderings for matrix-matrix multiplication.  You should write a function, MM, that performs matrix multiplication on N x N matrices.  The inputs to your matrix multiplication function are two matrices, A of dimension NxN and B of dimension NxN, along with N.  The output of the function is the NxN matrix C = A · B.  Implement all six variants in the C programming language, with three levels of manual loop unrolling for each variant - none, 2 and 4 (loop unrolling at level i means i iterations of the loop are merged into 1 iteration of the unrolled loop).  You can assume that N is divisible by 4. Evaluate the performance of all the programs (18 in total) for values of N up to 512, for N a power of 2, starting at 16 (i.e. N = 16, 32, 64, ..., 512).  Run each variant multiple times to be sure you get consistent timings (i.e. throw out outliers, and average the run times for a given variant).  The matrix entries should have type double. You can fill in the matrix entries however you want (but don't make them all the same).  The overall idea is to determine which variations work best for which values of N, and why.

Write up the results of your program, including:

1. Plot the results of your programs, as in Part I, with elapsed time (in microseconds) on the y-axis and N on the x-axis.  Use a logarithmic scale for both axes.  You must plot the results in two different ways.   The first set of plots has one graph for each of the 6 loop order variants, with one line in a graph for each of the three loop unrolling levels. The second set of plots has one graph for each of the three loop unrolling levels, with one line in each graph for each of the loop order variants. Label graphs and lines within graphs appropriately, so we can tell what is being plotted.  Note that both sets of plots are for the same data.
   
2. Analyze the timing results, commenting specifically on which variants perform better for which matrix sizes, and why.
   
3. What additional optimizations (e.g., those discussed in Chapters 4 and 5 of Hennessy and Patterson) could be used to speed up the base code you wrote?  How would they help?

Runtime environment

You must run your code on the CSIC Linux cluster, available via ssh at linuxlab.csic.cs.umd.edu (that IP address corresponds to the remote login server machines), so that's where you should do your development work and run the programs.  More information about the lab is available here.  To get accurate timing results, we suggest going to the lab and sitting at one of the machines, so that you are likely to be the only user on the machine.  Also, for Part II, the timing routines from Exercise 5.2 for Part I are not accurate enough to time your matrix multiply programs.  For more accurate timing routines, look at the man page for the gettimeofday() C library function.

Submission details

Submission will be handled using the submit program, located in ~cs411001/bin, as project 1 (i.e. submit 1 *.c *.h report.pdf).  Submit all the code you ran (but not the code from Exercise 5.2), and a file with the documentation in Word, Postscript, or PDF format.  You don't need to tar or compress your files - the submit program does that for you.

Web Accessibility