Assignment 1: High Performance Matrix Multiplication on a CPU

Due: Friday, October 9th, 2015 at 8pm

Changelog

Your assignment is to optimize matrix multiplication to run on a single core of Bang. Your starting point is a an implementation that performs one level of cache blocking, along with a test harness for evaluating performance. This implementation will behavior poorly, and you will be able to make it go significantly faster. We have also provided a variant that invokes a heavily optimized matrix multiply routine, provided by the ATLAS library. This reference variant will enable you to assess performance goals. ATLAS will outperform most "home made" implementations. See the references at the end to learn more about useful optimizations.

The assignment includes a 2-3 page report, which is important part of the assignment. The requirements for your report are described later in this document.

Part 1. Getting Started with GitLab

All assignments will be turned in using UCSD's GitLab. The turnin procedure is described below in the section "Turning in your assignment". In this section, we'll go over how to set up your repository.

You must follow these steps to get the starter code and to get set up to do assignment 1.

Refer to the link below for instructions on how to obtain the starter code to get started on your assignment

A1 Git Instructions

Try to make your code go as fast as you can. In the spirit of friendly competition, post your performance results to the A1 Piazza Folder. We will post a summary of the class' results on-line.

Your grade will based on 4 factors: performance attained by your implementation; correctness, well-displayed results and comments and explanation and insight into how you realized your reported performance. In determining your grade for the assignment, explanations and insight will be emphasized somewhat more heavily than performance itself, unless there was little improvement in performance over the provided naive code.

Part 2. The Assignment Checklist

1. Add a second level of cache blocking. Modify the code in the file dgemm-blocked.c that implements the blocked algorithm. This is Algorithm 3 described in the Demmel on-line reader. This module must implement the routine square_dgemm using the same signature as in the provided code, but with two levels of blocking. Note that, as discussed in class, a second level of cache blocking won't improve performance much, but is a requisite step to further optimization that will improve performance significantly.


2. Perform other optimizations to increase performance. Be sure to get the innermost loops to vectorize. As a minimum, you will need to use SSE intrinsics combined with register blocking. Consult the tips below for how to improve performance. Your performance goal is between 4 and 5 Gigaflops/second averaged over the complete set of inputs specified in the provided driver program dgemm-blocked. While it is possible to reach nearly theoretical performance for certain inputs (ATLAS can realize 8 GFlops, where the peak for Bang's processors is 9.32 GFlops), performance will vary over the full range of inputs.


3. Verify correctness. The provided code will test for correctness in the test harness, benchmark.c. Do not modify any code in this file, as we'll be substituting an unmodified copy when grading your assignments.


4. Conduct a performance study. Measure the GigaFLOP rate of your code for a few dozen values of N ranging from N=256 to 769. Do this for your improved implementation only; there is little point in performing such a careful study on a slow implementation! The code stores a list of values of n in a static array, and the longest list, currently uncommented provides a complete study. In your early testing use one of the shorter lists to save time. Also report results with the provided naïve code, using 6 different values of N spaced throughout the range you used to test the naïve implementation.

   Specific report requirements. Your report must present certain measurements, but feel free to add others if they illuminate your understanding of high performance matrix multiplication on Kepler. Plot the speedup of your optimized algorithm against the provided naïve code for the values you selected to evaluate the naïve code.

5. Report and comment on your results. The assignment includes a report, which will present and discuss your experimental results as well as your optimizations. The general requirements for your report are described in §6.2 below:
   Required files in the submission.


6. Requirements.
   • Use double precision floating point numbers (64 bits).
   • Your code must handle the case where the blocking factor does not divide n evenly.
   • You must use an O(N³) algorithm for matrix multiply. Do not reduce the operation count with, Strassen's or a similar algorithm.
   • Your changes should be confined to one source code module: dgemm-blocked.c as we'll be substituting the original provided version when grading your code.

Part 3. The Provided Starter Code

We've provided you with starter code that implements the naive ijk algorithm and a single level blocked implementation that uses cache more efficiently. In addition, we've provided an implementation that uses an optimized version of the BLAS (provided by the ATLAS library, which is installed on Bang) to enable you to assess performance of your 2-level blocked implementation. This code has been installed in the UCSD GitLab repository:

 https://git.ucsd.edu/cse260-fa15/pa1-provided 

To build your code, use the provided Makefile, which sets up the appropriate flags for the compiler via an included "arch" file located in in $(PUB)/Arch Do not change the name of the target used in the Makefile nor add additional file names to the Makefile, as we'll be grading your assignment with our own Makefile.

If you'd like to experiment with custom compiler optimization settings (the default is -O3), you can do this by setting, on the command line, a Makefile variable called MY_OPT. For example, if you'd like to specify -O4 -fopenmp, you may do so in one of two ways:

make MY_OPT=-O4\ -fopenmp

make MY_OPT="-O4 -fopenmp"

The effect of setting MY_OPT is to redefine the OPTIMIZATION macro in the Makefile (currently set to -O3). It follows that you may also define custom C pre-processor macros in a similar way:

make MY_OPT="-O4 -DFLAG"

Part 4. How to Take Timings

Use a qlogin node when taking timings. The provided code includes timer calls, which are based on gettimeofday(). For any given combination of N and optimization, take at least 3 timings and report the minimum.

You'll notice that at the end of the run, you'll get two lines of output as follows, which lists the input size -n, the number of repetitions -r, the Gigaflop rate and running time, and the grind time (the running time divided by the product of N and the number of repetitions):

        N    Reps      GF          t_blas      tg_blas
@   1024    50   2.23e+01   9.64e-02   8.97e-11

If you are doing several runs, you can quickly search for the string "@ " (starting in column 1) to extract the performance data from your job output files and process it for plotting (likely with a script).

Part 5. Tips on performance optimization

Basic cache blocking, as explained in class, is a requisite first step but alone is not sufficient to reach even half the processor's peak performance. To improve performance still further, try non-square tiles. Another good optimization is to tile for registers: 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 notes on vectorizing with SSE intrinsics or Jim Demmel's Lecture slides, slides 61-71. There are additional References below.

Feel free to learn from the source code of state-of-art BLAS implementations such as GotoBLAS and of course ATLAS, which is installed on Bang. However, you should not reuse those codes in your submission.

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. (Even then beware of daemons and other system activities that can affect your results) If the timings are inconsistent across runs, other activities are occupying the processor and must be stopped.

Part 6. Turning in your assignment

6.1 Submission via GitLab

When you have completed the assignment, you must submit it. You will do this by pushing your changes to GitLab. Follow these steps (which are more or less the same as the steps from the "pushing changes to GitLab" section above:

1. Run a ’git status’ to see what files have been changed.
2. Use ’git add <files>’ to stage certain files for a commit, use ’git add .’ to add all files in the working directory to the commit (hopefully you will not be doing this at this late stage—all files should already be in your repository!)
3. Use ’git commit -m "FINAL SUBMISSION"’ to commit the changes to your repository and indicate that you are done and this is your final submission.
4. To push your changes onto your repository on GitLab run ’git push origin master’ Don’t forget this push! You must do this to get credit.
5. As an added safety check, you should log on to GitLab on the web and verify that your push went through.

Some of the finer points about this process:

• Watch out for (and resolve) merge conflicts before your final push!!
  If you have been developing on multiple computers and not syncing with gitLab between switching computers, you will likely get merge conflicts. This happens because your code from one repo is out of sync with your code from another and gitLab doesn't know how to merge the files. You will get these conflicts "at the last minute," because git must sync the code in the repo you're trying to push with the code in the repo you're trying to push to. MERGE CONFLICTS WILL PREVENT YOUR CODE FROM COMPILING. So, even if your code was working perfectly just before you attempted your final push, conflicts will break your code.
  
  It is your responsibility to recognize when you have conflicts (it's not hard--you get a big warning), and to fix them. Please leave yourself enough time to do this.


• If you are submitting with a partner, just push to the joint repository on behalf of both partners. That’s your joint submission.


• Use the commit message FINAL SUBMISSION for your final submission in only one of your individual and partner repositories. You shouldn't be using both anyway, but if you happen to have pushed changes to both, just make sure only one contains the FINAL SUBMISSION commit message.


• If you decide you want to resubmit your assignment before the deadline, just do another commit with the message FINAL SUBMISSION (and don’t forget to push to GitLab!!). We will grade the last commit before the deadline that is tagged as the FINAL SUBMISSION.


• If you submit the assignment within 24 hours after the deadline (i.e. if there is a commit tagged "FINAL SUBMISSION") you will be charged a 10% lateness penalty. . If it is more than 24 but within 48 hours, you will be charged a 20% penalty. After 48 hours, we’ll roll back to the last commit tagged as "FINAL SUBMISSION" that was submitted before the deadline.

6.2.1. Source code

Even though we will be substituting fresh copies of all but one source module, include all code files your worked with, in case we need to unravel a problem with your turnin. For this reason, also include your Makefile.

6.2.2. 2 text documents

Your turnin must also fill in two important documents, which accompany the provided code. These documents are required and we will not report a grade for your assignment without them. A 10% penalty will be assessed in cases of missing forms, empty forms, or forms not properly filled out.

1. A completed self-evaluation discussing your work; if in a team this form address the division of labor and other aspects of how you worked together as a team.
2. A file named DECLARATION, that states that the work was your own, and that you did not violate the Academic Integrity policies in effect for the course. Modify the DECLARATION by filling in your correct login ID(s) and the date only. Don't change anything else.
   

6.2.3. Lab Report, a PDF document

This file must have the following format. The stem part of the file name (before the .pdf) should begin with "A1-report" and end with your repository name, e.g. A1-report-baden-powell.pdf.

Document your work in a well-written, two to three page report, including plots, which presents your results, analyzes them, and offers insight. Your report should present a clear evaluation of the design of your code, including bottlenecks of the implementation. If you improved performance of your code in a sequence of steps, document the process. If you like, summarize the information in a list or a table in your report. If necessary, provide pseudo code to illustrate the concepts. Be sure to thoroughly explain the results presented in your plots, relating them to how you designed the code. Discuss the design decisions you made to improve performance, including any negative results.

An important part of your report is your analysis. That is, to provide insight that explains your results. For this reason, if you are running out of time, put more effort into the writeup and your analysis rather than trying yet another performance enhancement. It can take time to collect, tabulate and plot results, as well as offer a reasonable explanation. We prefer a deeper analysis involving a few program optimizations over a shallower analysis over a larger number of optimizations. Spend more time discussing the optimizations that made a difference and less on those that made less of a difference. Negative results are also especially valued if you carefully document them, with the underlying causes, or best guesses if the causes are unclear.

Do not include full code listings in your writeup as these will be in your turnin.

Take care in how you plot your data, plotting only what's necessary to get your points across. Choose log and linear plots carefully, to take advantage of the plotting space. You must also include any plotted data in tabular form. Tabular data may be included electronically (in your turnin) as a spreadsheet or other document called, e.g. Data.xlsx, Data.txt. Be sure to provide a caption for each plot or table that describes the experiment you conducted, e.g. "strong scaling."

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. In such cases you must talk with us (and any code co-authors) prior to get approval.

7. Grading

There are 10 possible points on the assignment and your grade will depend on 4 factors: performance attained by your code, correctness, well-displayed results and comments. You must not only put comments inside your code, but every time you commit to your repository. There should be a steady stream of comments that enable us to retrace your development steps.

Your performance score is divided into two parts. You'll get the bulk of those points for reaching 4 GFlops, but to get all points on performance, you must realize 5 GFlops. Again, these figures are averages taken over the full range of input sizes specified in the driver program, and not for individual inputs. While it is possible to approach the speed of the ATLAS (about 6.8 GFlops (about 70% of the processor's peak theoretical speed) it can take time to realize this performance, so beware!

We will grade your code (on bang) using our own Makefile. Our Makefile will compile your code using gcc and and then link it with the test driver which is similar to dgemm-blocked.c We will use the same compilation flags as in the provided starter code. To get full credit, design, style and comments (including gitlab commit comments) count.

Part 8. Sources

Here are various sources of information that can help you optimize your code. The primary sources are seminal references. The Intel "SSE cheat sheet" will come in handy.

Part 8.1. Primary sources

• Goto, K., and van de Geijn, R. A. 2008. Anatomy of High-Performance Matrix Multiplication, ACM Transactions on Mathematical Software 34, 3, Article 12.
  Explains the design decisions for the GotoBLAS dgemm, a heavily optimized implementation of matrix multiplication. Look for ideas here.
• 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.
  How to write C code for modern compilers and memory hierarchies, so that it runs fast. Recommended reading, especially for newcomers to code optimization.)
• How to Write Fast Numerical Code: SIMD extensions, SSE, compiler vectorization, Markus Püschel, DTH (2015). A handy reference to SSE. Also see the course of the same title: https://www.inf.ethz.ch/personal/markusp/teaching/263-2300-ETH-spring15/course.html.
• Bilmes, et al. The PHiPAC (Portable High Performance ANSI C) Page for BLAS3 Compatible Fast Matrix Matrix Multiply.
  PHiPAC is a code-generating autotuner for matmul that started as a submission for this homework in a previous semester of CS267 at UC Berkeley. Also see ATLAS; both are good examples if you are considering code generation strategies.)
• Lam, M. S., Rothberg, E. E, and Wolf, M. E. 1991. The Cache Performance and Optimization of Blocked Algorithms, ASPLOS'91, 63–74. Explains cache blocking, supported with performance models.

Part 8.2. Reference

• Streaming SIMD Extensions (Wikipedia)
• Vectorization (wikipedia)

Part 8.3. Documentation

• SSE2 Preview, Stefano Tommesani Many writeups on SSE accessible from this page. Although this document is dated (pre SSE3), many of the SSE instructions you will use are part of SSE2.
• From Intel
  • Intrinsics Guide Handy cheat sheet, a complete reference to all SIMD intrinsics on Intel Architectures. Bang supports SSE, SSE2 and SSE3 instruction sets. Sorken also supports SSE4.1 and 4.2, as well as AVX1 and AVX2
  . Except for AVX2, Stampede supports all the variants that Sorken does.
  • Intel 64 and IA-32 Architectures Software Developer Manuals
  • Vectorization and Loops, User and Reference Guide for the Intel C++ Compiler 14.0
  • Intel Architecture Instruction Set Extensions Programming Reference, October 2014.
• GCC documentation - We are using GCC 4.8.4 on Bang, but this page documents older versions too. Look at the section entitled "Intel 386 and AMD x86-64 Options," especially the optimizations that concern SSE.
• Software Optimization Resources, Agner Fog (For discussions about vectorization and SSE intrinsics, see §12 of Optimizing Software in C++, pp 105-113 (skip §12.1, §12.2), 117-118, 122-123)
• Library Intrinsics, Microsoft
• An Introduction to GCC Compiler Intrinsics in Vector Processing, by George Koharchik and Kathy Jones, Linux Journal, Sep 21, 2012.
• HPC Mac OS X. How to obtain software and documentation
• Loop Nest Optimization (SGI) New

[Tue Oct 6 14:47:24 PDT 2015]