Programming Lab #1: High Performance Matrix Multiplication

Due: Wednesday, January 22nd, 2014 at 8pm

Changelog

The Assignment

Your assignment is to optimize matrix multiplication to run on a single core of Bang. Your starting point is a provided matrix multiplication routine that implements one level of cache blocking, along with a test harness for evaluating performance. 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.

Instructions for setting up your environment on Bang and for submitting jobs are described on the following page:

http://cseweb.ucsd.edu/classes/wi14/cse260-a/Bang

We've provided starter code which is available via svn. For instructions on how to obtain this starter code, visit the following web page:

http://www-cse.ucsd.edu/classes/wi14/cse260-a/HW/A3/StarterCode.html

Things you Should Turn in

The assignment includes a report, and the requirements for your report are described in the following document, along instructions on what and how to turn in:

http://www-cse.ucsd.edu/classes/wi14/cse260-a/HW/A1/WhatToTurnin.html

In the spirit of friendly competition, post your performance results to the A1 Moodle forum. We will post a summary of the class' results listed by group ID, which is known only to the group and course staff.

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.
2. Perform other optimizations to increase performance. Be sure to get the innermost loops to vectorize. Consult below for tips on how to improve performance.
3. Verify correctness. Test your code for different values of n and blocking factor to build confidence in the correctness of your code. 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 substituing an unmodified copy when grading your assignments.
4. Conduct a performance study. Run with different values of the matrix size n, testing various values of n up to n=769. (To conserve time use care in testing larger values of n.) 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.
5. 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 algorithim.
6. Report and comment on performance. Once you have conducted your experiments, plot the Gigaflop rate for the blocked and unblocked algorithms and provide a writeup as describe above in "Things you should Turnin."
7. If working in a group of 3, you must also conduct performance studies on one other platform, that uses a different processor from Bang. Use a laptop or any other machine that comes handy. You likely won't have time to install ATLAS on your machine, so you should report results relative to the peak performance of your processor. Many processors support concurrent multiplication and addition, and SSE3 supports 128 bit arithmetic units. On such processors, the peak double precision floating point rate is 4 times the clock rate. See below for how to determine the characteristics of your processor.
8. Recapping: which files should and shouldn't be changed. Your changes will be confined to dgemm-blocked.c. Don't change the Makefile nor benchmark.c (nor the timer code) as we'll be substituting the original provided version when grading your code.

Grading

Your grade will depend on 2 factors: performance and your methodical explanation of how your code improved performance over the provided code.

Frequently asked questions

We will add questions to this section as the need arises.

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 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 activiites that can affect your results) If the timings are inconsistent across runs, other activities are occupying the processor and must be stopped.

Processor Information

If working in a group of 3, you must 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.

1. The operating system: uname -a
2. The machine you ran on: hostname
3. The compiler and version number: g++ -v (If you aren't using the Gnu C++ compiler, determine the command needed to generate the version information.)

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:

• Cache memory hierarchy: number of levels; for each level: size per level, sharing across cores, associativity.
• R_∞ the peak floating point rate of the processor.
• The source of the above information, e.g. a URL or a file. If running on a Linux system, to include the contents of /cpu/procinfo in your output.

We have provided instructions for how to explore your processor's hardware Here. Bang's hardware is also discussed on that page.

References

• 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 implementation, which also apply to your code.)
• 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.)
• 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 HW in a previous semester of CS267. 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. (Clearly explains cache blocking, supported with performance models.)
• How to Write Fast Code SIMD Vectorization, Markus Püschel, CMU (2008).
• SSE2 Preview, Stefano Tommesani (Many writeups on SSE accessible from this page)
• CEAN: C/C++ Extensions for Array Notations, Jim Dempsey, Dr. Dobb's, Oct. 25, 2010. (Also explains assembler)
• From Intel
  • Intrinsics Guide Handy cheat sheet, a complete reference to all SIMD intrinsics on Intel Archicures. Bang supports SSE, SSE2 and SSE3 instruction sets.
  • Intel 64 and IA-32 Architectures Software Developer Manuals
  • Vectorization and Loops, User and Reference Guide for the Intel C++ Compiler 14.0
• GCC documentation - We are using GCC 4.7.3 on Bang, but this page documents older versions too. Look at the section entitled "Intel 386 and AMD x86-64 Options," spectially the optimations that concern SSE.
• Software Optimization Resources, Agner Fog (see §12 for discussions about vectorization and SSE intrinsics)
• Library Intrinsics, Microsoft
• An Introduction to GCC Compiler Intrinsics in Vector Processing, by George Koharchik and Kathy Jones, Linux Journal, Sep 21, 2012.

Copyright © 2014 Scott B. Baden Fri   [Fri Jan 10 10:00:16 PST 2014]