| Date | Description |
| 4-Oct-12 | Original posting |
| 12-Oct-12 | Tips on performance optimization |
Your assignment is to implement the single core, blocked matrix multiplication algorithm discussed in class, and carry out a set of experiments to assess the performance benefits of the algorithm compared with the unblocked algorithm. In addition to adding cache blocking, try other optimizations in an effort to make the code go as fast as you can. In the spirit of friendly competition, post your performance results to the A1 Moodle forum.
You'll run on the Bang cluster. Your starting point is a matrix multiplication test program that implements the naive algorithm. You need only handle products of square matrices. The driver code also provides a highly optimized matrix multiply routine implemented by the ATLAS library. This variant will enable you to determine when you have met performance goals so you know when to stop improving your code ATLAS will outperform most "home made" implementations, though a bonus of 10% will be awarded to any team that beats ATLAS by more than 5%.
The assignment includes a report, and the requirements for your report are described at the end of this writeup. You'll submit a hard copy lab report and also turn in your assignment (code + report) electronically on Bang. We will announce, via the A1 Moodle forum, when the turnin program has been enabled.
Instructions for setting up your environment on Bang are found here. Additional instructions are provided for running non-interactive batch jobs.
If working in a group of 3, you must also conduct performance studies on two other platforms, that use a different processor from Bang. You could use a laptop or any other machine that comes handy.
The provided verification code, verify.cpp, will enable you to establish code correctness. This code verifies a matrix product that can be expressed in closed form so it is important not to change the matrix initialization routine. Test your code for different values of n, repetition count, and blocking factor in order to build confidence in the correctness of your code.
Next, choosing your largest value of n, measure the effect of the blocking factor on performance. To start with, set the blocking factor to n/2, then double and halve this value a few times until you notice a trend (or trends). Is there a "sweet spot" (or spots) that minimizes the running time? Explain how the optimal value of the blocking factor relates to the L2 cache size. (Teams of 3 must do this for each machine they run on).
You must use double precision arithmetic (64 bits). As an optional part, report performance for single precision arithmetic (32 bits). The code is set up to enable you to switch to single precision arithmetic during compilation.To compile for single precision floating point, specify the argument
single=1on the make command line. This setting defines the _DOUBLE_ macro in types.h so that all instances of _DOUBLE_ will expand to the built-in type float. Be sure to use the generic type specifier _DOUBLE_ wherever you need to specify the built-in floating point type double or float (i.e. declarations or type casts). If you don't specify single=1, the type of _DOUBLE will be set to double precision, i.e. double. When switching types, don't forget to do a make clean before rebuilding the code. Otherwise you'll get loader errors.
You have been provided with starter code that implements the naive algorithm.
This code has been installed
on the "bang" cluster as $PUB/cse260-fa12/A1.
The README file explains the options needed to run the code,
including how to run the BLAS baseline code.
The code enables you to repeatedly execute matrix multiplication. This is necessary with smaller matrices, since it might not be possible to measure reliably short running times for a single matrix product. You may assume that the blocking factor divides n evenly.
Look over the code so you are familiar with the various modules. All of your changes will be made to just one file:
mm_blocked.cpp
To ensure that your program is correctly graded, do not change any of the provided source code files except the file listed above as we will substitute fresh copies of the remaining files when we grade your assignment. Also, don't change the signature of functions defined in mm_blocked.cpp, as certain provided routines make callbacks to them. You may modify the Makefile if you need to add new source code files.
Basic cache blocking, as explained in class, is a requisite first step and may enable you to reach 15% of the processor's peak performance. To improve performance still further, try non-square tiles. Another good optimization is to tile for registers. In this this optimization you unroll innermost loops and use named variables to store copies of the matrices. The tiles will be small, limited by the number of registers (16x128 bit registers on the Nehalem, see the details in Michael Thomadakis' paper). Though you won't be able to reach ATLAS' performance without auto-tuning and SSE intrinsics, you will be able to see an improvement beyond basic blocking if you try the strategies described above. See Brian Van Straalen's lecture slides, or Jim Demmel's Lectures slides, slides 61-71. If you want to dig more deeply into the details, see Goto and A. van de Geijn's paper: Anatomy of high-performance matrix multiplication. ACM Trans. Math. Softw. 34(3), Article 12 (May 2008), 25 pages. Here is a general reference (but long) about how to write code for modern systems; good for novices in code optimization: Chellappa, S., Franchetti, F., and Püschel, M. 2008. How To Write Fast Numerical Code: A Small Introduction, Lecture Notes in Computer Science 5235, 196-259.
For the purposes of this assignment, there is no need for your program to run for more than 15 or 20 seconds. Use the batch queues on Bang to collect timings. You may run interactively (see instructions described here) But you may find it more convenient to collect your measurements by running non-interactively. Here are Instructions for using the batch system to run non-interactive jobs.
Take timings with the provided timer code (it uses gettimeofday()). Take at least 3 timings for each combination of n and block size, and report the minimum timing.
If you are working on a desktop or a laptop, shut down all open applications. Do not run on a machine shared with other users, unless you are sure that no-one else is running at the time you conduct your runs. If the timings are inconsistent across runs, other activities are occupying the processor and must be stopped.
The code enables you to repeatedly execute matrix multiplication. You'll need to use much a large repetition count for smaller matrices since it might not be possible to measure reliably short running times for a single matrix product. As you increase n, you'll need to figure out a schedule for decreasing the repetition count so that each run takes a few seconds (3 to 5). As you increase n still further, you'll eventually set the repetition count to one and will no longer be able to limit the running time to a few seconds (Don’t run for more than 30 seconds or you may run against the hard time limit for the queue you are running on.)
If you are working in a group of 3, your assignment will be somewhat more ambitious. In addition to what has been described above, you also need to complete the following.
When reporting performance results, it is important to identify the hardware and software testbeds used. To this end, run a suite of commands to identify the hardware and the environment you used to develop and run your code.
Place all output from these commands in a file called config.out, e.g. by using the script command. You should report the processor information on the processor you actually ran the job on, that is while running in batch, and not on the front end as on Bang (the front end node is called ccom-bang-login). In particular, you must report the following information
We have provided instructions for how to explore your processor's hardware Here. Bang's hardware is also discussed on that page.
From within your home directory, copy over the provided assignment code, build it.
cp -p -r $PUB/HW/A1 . cd A1 make
Next, request an interactive compute node via the qlogin command. Once you've been granted your node, you'll see the following output, though your job number and assigned node number will differ:
Your job 239 ("QLOGIN") has been submitted
waiting for interactive job to be scheduled ...
Your interactive job 239 has been successfully scheduled.
Establishing builtin session to host compute-0-26.local ...
You are now running in a shell and have exclusive access, for 30 minutes, to a compute node with 8 cores.
Wait until you receive a command prompt. You will now be running in a new shell, within your $HOME directory. You may run commands on the compute node, edit and compile code, but you won't be able to submit non-interactive jobs.
As a courtesy to other users, exit the interactive session when no longer needed.
Explain how your design decisions affected the observed performance. Negative results are also valid and especially valued if you carefully document them, with the underlying causes, or best guesses if the causes are not clear. Provide pseudo code listings to illustrate how you parallelized the code, but do not include full code listings as these will be in your turnin.
Take care in how you plot your data, only plotting what's necessary to get your points across, and choosing log and linear plots carefully. We will discuss plotting strategies in class. You must also include any plotted data in tabular form.
Cite any written works or software as appropriate in the text of the report. Citations should include any software you used that was written by someone else, or that was written by you for purposes other than this class.
Your electronic turnin must include a Makefile so that we can build and test your code. We will run your code to test it and will check correctness using the residual measurement.
Your turnin must also include three important documents:
uname -n > HOSTTeams of three should include an entry for each machine they ran on.
These documents are required, as the turnin process will not complete without them. Blanks for the self evaluation and MEMBERS files are available in the turnin directory, $PUB/turnin Empty forms, or forms not properly filled out, will result in a 10% penalty being assessed, in addition to holding up the grading process.
Since the turnin script will try to compile your project before letting you submit your assignment, it's important that you turn in all the files you have, including a Makefile. However, when grading your assignment, we will substitute all the files that you are not allowed to modify (as noted in the list above) with the original copies of the version we provided you. This is why it is important that you do not change those files in your own turnin, as they will be lost. The turnin script will have an option to do some basic testing, and we strongly suggest you avail yourself of this option.
Don't wait until the last minute to attempt a turnin for the first time. The turnin program will ask you various questions, and it will check for the presence of certain required files, as well as your source code. It will also build the source code if you like, to catch any obvious build errors. Try out the turnin process early on so you are sure that you you are familiar with the process, and that all the required additional files are present. The turnin procedure will be available about a week before the deadline.
Your grade will depend on 3 factors: matrix multiply performance attained by your blocked algorithm; the explanation for you realized that performance and correctness.
We will test your code on Bang. Be sure to do your final testing on that machine, to avoid any surprises at turnin time. Your code will be tested for correctness and performance. Be sure to test against various combinations of matrix size and cache blocking factor, as well as the repetition count.
Copyright © 2012 Scott B. Baden [Fri Oct 12 09:01:58 PDT 2012]